好吧，让我们仔细看看多边形。
我们叫他泰德。当泰德（或一般的多边形）看到一个点时，他会尝试在自己内部吸收它。为了同化，他决定让他的众多方面之一有幸伸出援手并抓住这一点。现在，泰德正忙于更重要的事情，所以双方需要自己决定哪一方会做好事。我再说一遍；双方。
我们走了，泰德附近有一个点，幸福地没有意识到它很快就会被恶毒地消耗掉。那么，泰德的一方如何决定哪一方将抢夺这一点呢？好吧，它需要是公平的游戏。感觉到从它到该点的垂直距离最短的一侧将是执行此操作的一侧。最短的。垂直。距离。
同化完成！
要记住的另一件事是，像 Ted 这样的多边形重视生存而不是同化。与该点垂直距离最短的一侧只有在它不穿过其他一侧时才开始同化。因此，仅考虑有效同化的方面。否则，坏事就会发生。
我不必要的言辞中有两点很重要；
- 我们添加点的一侧应该与该点有最短的垂直距离。
- 除了与点的垂直距离最短外，将点添加到这一侧应该是有效的。这很重要，毕竟，我们不想进行大规模多边形谋杀。
所以，这里有一些伪代码；
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共同点。
根据这种方法，当且仅当以下之间不存在交集时，加法才有效：
因此，此方法适用于拒绝。如果我们找不到任何交点，边S可以有效地添加点。
方法 1 演示
方法二：
随着多边形的凹度增加，方法 1 失败。因此，我们需要做进一步的检查以确保有效的加点。
This method is really an extension of Method 1. After finding that the pairs Sprev and S2p, and Snext and S1p are not intersecting, we check if the new sides are intersecting with all the other sides of the polygon (apart from Sprev and Snext, of course).
If the addition is not rejected after all the sides are checked, we are completely sure that this addition is valid.
The problem is, that while rejection is quick enough, reaching acceptance takes a long time, making this method quite expensive.
Furthermore, the complexity depends on the number of sides of the polygon. As the polygon complexity increases, checking validity will take more and more time.
Method 2 Demo
我必须注意，我用于检查线段相交的算法取自如何检测两条线段相交的位置？. 这太棒了。
这就是我所拥有的。这是一种方法，我必须说。可能还有另一种更好的方法还没有让我印象深刻。我希望你不要太介意泰德。另外，感谢您提出一个好问题，我很喜欢。