Algorithm for finding points inside the selected area

Question

MySQL

Good time of the day.

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



I was only able to think until the next thought.

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

1.  
2.                 $x_query        =       array();
3.                 // строим условия для x
4.                 foreach($x as $value){
5.                         if (max($value,$x_center)==$value) {
6.                                 $x_query[] = "`t3`.`lat_ya` <= ".$value;                               
7.                         } else {
8.                                 $x_query[] = "`t3`.`lat_ya` >= ".$value;
9.                         }
10.                 }              
11.                
12.                 $y_query        =       array();
13.                 // строим условия для y
14.                 foreach($y as $value){
15.                         if (max($value,$y_center)==$value) {
16.                                 $y_query[] = "`t3`.`lng_ya` <= ".$value;
17.                         } else {
18.                                 $y_query[] = "`t3`.`lng_ya` >= ".$value;
19.                         }
20.                 }
21.  
22.  

3. Next, I build a request and get it 

1.  
2. SELECT *
3. FROM `_perm_houses` as `t3`
4. WHERE
5. (
6. `t3`.`lat_ya` >= 56.234189 AND
7. `t3`.`lat_ya` >= 56.235627 AND
8. `t3`.`lat_ya` <= 56.236925 AND
9. `t3`.`lat_ya` <= 56.240583 AND
10. `t3`.`lat_ya` <= 56.238459 AND
11. `t3`.`lat_ya` >= 56.235348
12. ) AND (
13. `t3`.`lng_ya` <= 58.010264 AND
14. `t3`.`lng_ya` >= 58.007918 AND
15. `t3`.`lng_ya` >= 58.008186 AND
16. `t3`.`lng_ya` >= 58.009228 AND
17. `t3`.`lng_ya` <= 58.011346 AND
18. `t3`.`lng_ya` <= 58.010509
19. ) ;
20.  
21.  

When the selected area is rectangular and its sides are parallel to the coordinate axes, let's say, it finds it without problems, and when the area is more accurately selected, problems arise.

Maybe there is an algorithm? I searched and didn't find anything like it.

Thanks in advance.
______________________

The text was prepared in Blog Editor by © SoftCoder.ru

Answer 1

A point x,y is inside the polygon if and only if the ray (x,y) (x+m,y) crosses the polygon an unpaired number of times. M is a very large number.

Answer 2

As a student, for cases with convex polygons, I found out the belonging of a point using the equality of the areas of the polygon itself and the sum of the areas of the triangles formed by the point and all the vertices of the polygon. If the sum is greater than the area (+ some calculation error), then the point lies outside the polygon.

Answer 3

en.wikipedia.org/wiki/Algorithm_point_in_polygon
I think that such an algorithm cannot be implemented via SQL (Although you can try to define a function), therefore:
1. “Draw” a bounding box around your area with sides parallel to the coordinate grid. (X _min , Y _min , X _max , Y _max )
2. Select all points belonging to this rectangle (simple, quick query)
3. Check all these points with a script.

Answer 4

Horse, Akr0n Gave two correct options. Another.
Go around the vertices in order (clockwise or counterclockwise) and check on which side of the segment the desired point lies. As a result, get "+", "-" or "0". "0" - the point lies on the segment, "+" on one side (depending on how to bypass), "-" - on the other. If you got all the pluses or all the minuses, then the point is inside the polygon. Here are some good articles on the subject

Answer 5

sum the angles between the rays (x,y)-(x1,y1) ....(x,y)-(xN,yN), where (x1,y1)… (xN,yN) are the coordinates of the vertices, bypassing them in that the order in which they are connected. (angles can be negative)
if it lies inside, then it will be 2pi

Answer 6

MYSQL has spatial indexes. Read the documentation on this topic. If we store in the POLYGON database, then the occurrence of a point in it is found very quickly.
dev.mysql.com/doc/refman/5.0/en/spatial-extensions.html

Answer 7

You can use this simple class
https://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 at the very beginning a square is created in which the entire polygon is placed. Further, from each side of the square, a perpendicular to the desired point is lowered.
After that, the number of intersections of each perpendicular with the edges of the polygon is counted. If all perpendiculars intersect the edges at least once and never an odd number, then the point is considered to be inside the polygon.
This rule is easy enough to check with a piece of paper and a pencil.