The algorithm for finding the points inside the selected area

0 like 0 dislike
68 views
Good time of day.

Please tell me the algorithm for constructing the conditions of finding all points inside a selected area.

image

I was only able to be thought to the next thought.

1. Find the center of the figure coordinates.
lat_center = sum of all lat divided by the number lng_center = sum of all lng divided by the number 2. In the cycle formation condition for the coordinates

$x_query = array(); // build x foreach($x as $value){ if (max($value,$x_center)==$value) { $x_query[] = "`t3`.`lat_ya` <= ".$value; } else { $x_query[] = "`t3`.`lat_ya` >= ".$value; } } $y_query = array(); // build the conditions for y foreach($y as $value){ if (max($value,$y_center)==$value) { $y_query[] = "`t3`.`lng_ya` <= ".$value; } else { $y_query[] = "`t3`.`lng_ya` >= ".$value; } }


3. Next, build the query and get it
SELECT * FROM `_perm_houses` as `t3` WHERE (`t3`.`lat_ya` >= 56.234189 AND `t3`.`lat_ya` >= 56.235627 AND `t3`.`lat_ya` <= 56.236925 AND `t3`.`lat_ya` <= 56.240583 AND `t3`.`lat_ya` <= 56.238459 AND `t3`.`lat_ya` >= 56.235348) AND (`t3`.`lng_ya` <= 58.010264 AND `t3`.`lng_ya` >= 58.007918 AND `t3`.`lng_ya` >= 58.008186 AND `t3`.`lng_ya` >= 58.009228 AND `t3`.`lng_ya` <= 58.011346 AND `t3`.`lng_ya` <= 58.010509) ;


When the selection is rectangular and its sides parallel to the coordinate axes, say, it finds no problems, and when the area to be more accurately highlighted a problem.

Maybe there is some algorithm? Looking for anything similar have not found.

For earlier grateful.
______________________
In the text prepared by the writer from © SoftCoder.ru
by | 68 views

7 Answers

0 like 0 dislike
Point x,y is inside the polygon, and then only when the beam (x,y) (x+m,y) intersects the polygon odd number of times. M is a very large number.
by
0 like 0 dislike
As a student, for cases with convex polygons, I found out the identity of the points by using the equality of the areas of the polygon and the sum of the areas of triangles formed by the point and all the vertices of the polygon. If the sum is greater than the square (some accuracy), then the point lies outside the polygon.
by
0 like 0 dislike
ru.wikipedia.org/wiki/Алгоритм_точки_в_многоугольнике
\r
I think such an algorithm using SQL is not implemented(Although it is possible to try to define a function), so:
1. Draw around your area of the bounding rectangle with sides parallel to the coordinate grid. (Xmin, Ymin, Xmax, Ymax)
2. Choose all the points belonging to the rectangle (simple, quick)
3. Check all these points by the script.
by
0 like 0 dislike
Horse, Akr0n Gave two correct sentences. Another one.
Go around the vertex in order (clockwise or counterclockwise) and check which side of the cut is desired spot. The result is "+", "-" or "0". 0 — point lies on segment, the "+" on one side (depends on how to get around), " - " on the other. If you got all the advantages or all the disadvantages, then the point is inside the polygon. Here is a good article on this topic
by
0 like 0 dislike
sum the angles between the rays (x,y) to(x1,y1) ....(x,y)-(xN,yN) where (x1,y1)... (xN,yN) the coordinates of the vertices, avoiding them in the order in which they are connected. (angles can be negative)
if lies inside — that is 2pi
by
0 like 0 dislike
MYSQL has spatial index's. Read the documentation on this topic. If stored in the database POLYGON the entering point is very fast.
\rdev.mysql.com/doc/refman/5.0/en/spatial-extensions.html
by
0 like 0 dislike
You can use this simple class
\rhttps://github.com/xopbatgh/sb-polygon-pointer

It is enough to specify the coordinates of the polygon and the coordinates of the point

The principle of operation is that in the very beginning it creates such a square, in which fits the polygon. Further, from each side of the square descends perpendicular to the desired point.
After that is the number of intersections of each perpendicular with the edges of the polygon. If all perpendiculars intersect the ribs at least once and never an odd number, it is considered that the point is inside the polygon.

This rule is simple enough to check by using paper and pencil

5a6483d0315dd084509986.png
by

Related questions

0 like 0 dislike
4 answers
0 like 0 dislike
4 answers
0 like 0 dislike
2 answers
0 like 0 dislike
6 answers
110,608 questions
257,186 answers
0 comments
32,718 users