How to judge whether a point is within a polygon (including complex polygons or a large number of polygons)

   We use the ray judgment method to judge whether the point is in the polygon , This point emits a ray in any direction , If the total number of intersections with each edge of the polygon is odd, it is inside the polygon , For the even , Outside the polygon .

   If there are thousands on the plane 、 tens of thousands 、 Hundreds of thousands of polygons , Need to judge whether the point falls in one of the polygons ？ If you need to judge whether each edge of countless polygons intersects , Extremely inefficient . We use RTree To simplify this complex process .
1. We first convert each polygon into its circumscribed rectangle .

2. Then divide the circumscribed rectangles of all polygons on the map into regions .

3. Establish a good area according to RTree.

Finally, according to RTree Search out the rectangular area intersecting the ray , Then judge whether the point falls in the polygon of the rectangular area . resume RTree after , Just a few decimals to judge , You can quickly calculate which polygon the good point falls in , Even if the number of polygons is huge .

   If a single polygon itself is extremely complex , By thousands 、 tens of thousands 、 Hundreds of thousands of edges ？ It doesn't mean that a single polygon also needs to judge whether the rays intersect the edges countless times ？ The answer is clearly no , We still use RTree To solve this problem .
The principle is basically consistent with the above method , But the above is to convert a polygon into a rectangle and then divide the area , Here is to convert an edge into a rectangle to divide the area . I won't elaborate on the process , The picture above is finished ……

Reference article ：https://www.cnblogs.com/LBSer/p/4471742.html