Test polygons overlap in Google Maps

Question

In my project I have a map with a lot of polygons drawed. Each polygon is represented as a MVCArray.

The user can draw a new polygon on the map in this way:

• If the user click on the map, there will be a new marker: it will be connected with the temporal predecessor and the first marker created.
• If the user click on a marker, it will be deleted, and there will be a new connection between the marker's predecessor and successor.

I don't want to let the user draw over another polygon in the map. Either that the newly created marker is on another polygon, either that a connection line created by a new marker (or from the deletion of another) pass over another polygon.

Can somebody help me or give me a hint?

Answer 1

The naive overlap test would be iterating through the edges of your polygons and testing line-line intersection.

From the sounds of it, you may have too many edges for this to be effective by itself in real time. From there your strategy needs to focus on quickly culling polygons/edges that don't need to be compared before you test for Line-Line intersections. Take a look at bounding circles and cube-tree elimination if you need ideas.