I have saved multiple polygons in a KML file as well as a MySQL database. Now suppose I have a point X (51.60388069248056, 0.01671853610330363).

How do I find out if this point X lies within or even on the edges of multiple polygons at the same time using Google Maps API (preferred) or with any other alternate?

Please note: I'm aware of Google Maps containsLocation() function but it has the option to find with a single polygon, a workaround that I could think of is to keep querying with separate polygons but it will not be cost-effective especially if you have 50-100 polygons.

CodePudding user response：

If your polygons remain the same for many points queries, you can build new data structure - calculate intersections of polygons, build new polygons, every one keeps information about corresponding old polygons. This operation might be time-consuming.

So if a point lies in some new polygon, you have a list of old polygons containing the point.

Look at R-tree, this is alike structure for rectangles.

CodePudding user response：

If you don't need to know which polygon(s) contains the point, then form the union of all polygons and use a trapezoidal decomposition to speed-up the point-in-polygon query (will take O(Log(N)) for a union made of N vertices).

Otherwise, as MBo said, compute the intersection map and also its trapezoidal decomposition. The cost of a query is still O(N) where N is the number of vertices of the map, but the algorithms are more difficult and the preprocessing cost higher.