Drawing resizable (not intersecting) polygons

Question

Hello everyone, I have been searching everywhere but I could not find an answer. I need to have drawing resizable polygons with mouse interaction but I do not want irregular, overlapping or intersecting polygons in the end.

Here is a simple example of drawing resizable polygons http://www.wolfpil.de/polygon.html

You can easily create & resize polygons which is great. But I need an extra functionality to detect intersections and NOT allowing weird looking shapes/polygons. You can see the problem in this video: http://www.youtube.com/watch?v=zou2jcGM8zw

The only solution for that problem I found at http://www.wikimapia.org. They have added features to handle the problem. You can see it in this video: http://www.youtube.com/watch?v=K7-K0k2D-2A

I spent 3 days trying out to achieve something like this. I have gone through wikimapia's javascript code but it is way too complex for me to understand.

In sum, it does not have to look as fancy as as wikimapia's. I just need resizable polygons which do NOT intersect while resizing or adding new points to it. Can you give me any suggestions how to achieve that?

Thank in advance.

Answer 1

Depending on how many points that you allow, a naive, simple O(N^2) line intersection algorithm suffices. Algorithmically this is not the best solution, but for starting out it's the most accessible for a beginner in computational geometry.

For starter, see Wikipedia article on line segment intersection. One of its links has an easy to understand explanation on how to compute the intersection point of two line segments.

Good luck!

Answer 2

While this is not a complete answer, note that the example you supplied appears to be using the Geometry Controls from the GMaps Utility Library, which is an open source project hosted on Google Code.

You can check the full source code in the Google Code browser.