将新Point添加到Points of Points中的正确位置

Question

我有一个带有几个点的多边形,并且必须添加一个新点.现有点存储在一个数组中:

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

你如何确定newPoint应该添加到阵列的哪个位置？

尝试:迭代遍历所有现有点并计算newPoint它们的距离,并将现有点分类为包含这些点索引的数组,按距离增加的顺序排列newPoint.

按照我当前尝试的方法,下一步将检查2个最近点是否相邻.如果是,请newPoint在points数组中添加它们.如果他们不相邻,那么我有点卡在这里:)你怎么检查2点是否相邻？

任何帮助非常感谢!

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

---

订单之所以重要的原因是因为形状通常以顺时针方式绘制.这是一个jsfiddle,其中蓝色多边形在正确的位置添加了一个点,并且在points数组的末尾添加了一个点的红色多边形.

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

Answer 1

好吧，让我们仔细看看多边形。

我们就叫他特德吧。当泰德（或一般的多边形）看到一个点时，他试图将它吸收到自己的内心。为了同化，他决定给予他的众多一方之一伸手抓住要点的荣誉。现在，特德正忙着处理更重要的事情，因此双方需要自行决定由谁来做善事。我再说一遍；双方。

就这样，特德附近有一个点，他幸福地没有意识到它很快就会被恶意吞噬。那么，特德的球队如何决定哪一方会抢分呢？嗯，这需要是公平的游戏。感觉到从它到该点的垂直距离最短的一侧将是执行此操作的一侧。最短的。垂直。距离。

同化完成！

另一件需要记住的事情是，像泰德这样的多边形更看重生存而不是同化。距该点垂直距离最短的一侧仅在不穿过其他侧时才开始同化。因此，仅考虑具有有效同化的一方。否则，就会发生不好的事情。

在我不必要的长篇大论中，有两点很重要：

• 我们添加点的一侧应该与该点具有最短的垂直距离。
• 除了距该点的垂直距离最短之外，该点在这条边上的相加应该是有效的。这很重要，毕竟我们不想进行大规模的多边形谋杀。

所以，这里有一些伪代码；

For each side S in polygon P
Do
    d := perpendicularDistanceFromSide(S, point);
    If d is less than shortestPerpendicularDistance
    Do
        If additionIsValid(S, point, P)
        Do
            shortestPerpendicularDistance := d;
            index = S.index;
        End If
    End If
End For

很容易找到与侧面的垂直距离；

var perpendicularDistance = function(side, point) {
    //Find direction vector of side
    var dir = {x: side.p2.x - side.p1.x, y: side.p2.y - side.p1.y};
    var m = Math.sqrt(dir.x*dir.x + dir.y*dir.y);
    if(m !== 0) {
        d.x = d.x/m;
        d.y = d.y/m;
    }

    //Find position vector of point, from side
    var pVec = {x: point.x - side.p1.x, y: point.y - side.p1.y};

    //Absolut of cross product of dir and pVec. 
    //It's essentially |pVec|*Sin(q), q is the angle between
    //dir and pVec.
    return Math.abs(dir.x*pVec.y - dir.y*pVec.x);
};

现在，让我们看看有效性。如果在将点添加到多边形后，新的边穿过任何其他边，那么这个小家伙就结束了。我们需要确保我们的算法考虑到了这一点。

我为此想出了两个版本；一种便宜，一种昂贵。

方法一：

如果多边形中几乎没有凹度，则此方法非常有效。此方法仅检查新边不与旧边相邻的边相交。

说我们有一方S。它的两个相邻边是Sprev和Snext。两个新边是S1p和S2p。S1p并且Sprev有共同点S.p1。S2p并且Snext有共同点S.p2。

根据此方法，当且仅当以下各项之间不存在交集时，加法才有效：

• Sprev和S2p
• Snext和S1p

所以，这个方法对拒绝有效。如果找不到交点，则该方S可以有效地添加该点。

方法一演示

方法二：

当多边形的凹度增加时，方法 1 就会失效。因此，我们需要做进一步的检查以确保加点有效。

此方法实际上是方法 1 的扩展。在发现Sprev和S2p、 和Snext、 和S1p不相交后，我们检查新边是否与多边形的所有其他边相交（当然，除了Sprev和）。Snext

如果在所有方面都检查后没有拒绝添加，我们完全确定此添加是有效的。

问题是，虽然拒绝的速度足够快，但获得接受需要很长时间，使得这种方法相当昂贵。

此外，复杂性取决于多边形的边数。随着多边形复杂度的增加，检查有效性将花费越来越多的时间。

方法2演示

我必须注意，我用于检查线段相交的算法取自如何检测两条线段相交？。太棒了。

这就是我所拥有的一切。我必须说，这是一种方法。可能还有另一种更好的方法，但我还没有想到。我希望你不太介意特德。另外，感谢您提出了一个好问题，我很喜欢。