javascript - 将新点添加到点数组中的正确位置

Question

我有一个包含多个点的多边形，必须添加一个新点。现有的点存储在一个数组中:

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

你如何确定这个newPoint应该被添加到数组的哪个位置？

尝试:我遍历所有现有点并计算newPoint与它们的距离，并将现有点排序到包含这些点索引的数组中，按照与 newPoint 的距离增加的顺序。

按照我目前尝试的方法，下一步将检查最近的2个点是否相邻。如果是，则在 points 数组中添加它们之间的 newPoint。如果它们不相邻，那么我有点卡在这里了:)你如何检查这两个点是否相邻？

非常感谢任何帮助!

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

---

顺序很重要的原因是因为形状通常是按顺时针方向绘制的。这是一个 jsfiddle，其中蓝色多边形在正确位置添加了一个点，红色多边形在 points 数组的末尾添加了一个点。

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

Answer 1

正如我之前所说，您实际上不必使用排序来增加程序的复杂性:只需存储两个初始点，将它们视为最接近的点，然后在迭代另一个点时替换它们。

但是，您的问题有不止一种可能的解决方案；您必须为其定义更多约束。

例如，考虑形成正方形的四个点:

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

现在，在多边形内的随机位置添加一个点:

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

有两种以上的可能顺序仍然会保持您的多边形凸:

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

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