How to sort points in a Google maps polygon so that lines do not cross?

Question

I am trying to make a map where a user can outline any shape they would like. But I am running into an issue where users can select points that will make the lines of the polygon cross and exclude area's that I would like to include.

To see what i'm talking about go to this page and take the following steps:

1. click 4 points to make the 4 corners of a box
2. click in between each of the 4 points you just made to further define the perimter of the box
3. click done

You should see something like this:

Is there an easy way to solve this problem, or am I basically dealing with a "Traveling Salesman" type situation here? All the logic is done in javascript so feel free to "view source" if you would like to see how i'm doing this.

Answer 1

A convex hull might include areas that the user wishes to exclude. Here is another way to approach this that might give more satisfactory results. Check each line to see which ones cross (there are lots of ways to do that). Then reverse the subsequence of points that appear between those two lines.

For example, suppose you are given points A-B-C-D-E-F-A, where B-C and E-F cross. You can uncross them by reversing the subsequence C..E resulting in A-B-E-D-C-F-A.

It's something to try anyway.

Answer 2

It's not a convex hull.

Imagine if you had a stop at "Linfield Oaks" near where those two lines cross. A convex hull would skip this and draw a straight line between "international" and "82"

What you are trying to do is determine if each new point is inside the polygon formed by the existing points - if it is then you need to break the nearest polygon side and insert the new point in that edge. See http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm for point in polygon tests.

Answer 3

I solved a similar problem in the past and ran into the issue that Jeffrey mentioned about not knowing exactly what shape the user is expecting. I ended up solving that issue by requiring the user to select the two points that they wanted the new point to be between. It requires more clicks (3 versus 1), but the user is entirely in control about what shape they want. I might still have the code that I used around somewhere (it was for Google Maps) if you're interested.