Adding a new Point into the correct position in an Array of Points

Question

I have a polygon with several points and a new point has to be added. The existing points are stored in an array:

var points = [
    {x: 0, y:0},
    {x: 100, y: 0},
    {x: 100, y: 100},
    {x: 0, y: 100}
];

How do you determine which position of the array this newPoint should be added into?

Attempt: I iterated through all the existing points and calculate newPoint's distance from them, and sorted the existing points into an array containing the index of these points, in order of increasing distance from newPoint.

Following my current attempt's method, the next step will be to check whether the 2 closest points are adjacent. If they are, add the newPoint between them in the points array. If they are not adjacent, well I'm kind of stuck here :) How do you check whether the 2 points are adjacent?

Any help greatly appreciated!

jsfiddle: http://jsfiddle.net/y3kmm/

---

The reason why the order matters is because Shapes are usually drawn in a clockwise manner. Here's a jsfiddle where the blue polygon had a point added at the correct place, and a red polygon with a point added at the end of the points array.

jsfiddle: http://jsfiddle.net/TyQXV/

Answer 1

As I said before, you don't really have to grow up the complexity of the program using sort: simply stored two initial points, considering them to be the closest, and then replace them as you iterate through the other point.

However, your problem have more than one possible solution; you must define more constraints to it.

For example, think of four points forming a square:

·-------·
|       |
|       |
|       |
·-------·

Now, add a point to a random position inside the polygon:

·-------·
|       |
| ·     |
|       |
·-------·

There are more than two possible orders that will, still, maintain your polygon convex:

·-------·
 \      |
  ·     |
 /      |
·-------·

·   ____·
|\ /    |
| ·     |
|       |
·-------·