相关疑难解决方法(0)

我想检查一个点是否位于特定的多边形内.多边形是:

 polygon=   [ [-73.89632720118, 40.8515320489962],
              [-73.8964878416508, 40.8512476593594],
              [-73.8968799791431, 40.851375925454],
              [-73.8967188588015, 40.851660158514],
              [-73.89632720118, 40.8515320489962] ]

我要检查的要点是:

1 = [40.8515320489962,-73.89632720118]
2 = [40.8512476593594,-73.8964878416508]
3 = [40.851375925454,-73.8968799791431]
4 = [40.851660158514,-73.8967188588015]
5 = [40.8515320489962,-73.89632720118]

如何判断每个点是否在此多边形内？

此算法无效.我不知道为什么.

pt[lat,long]

function isPointInPoly(poly, pt){
    for(var c = false, i = -1, l = poly.length, j = l - 1; ++i < l; j = i)
        ((poly[i][1] <= pt[1] && pt[1] < poly[j][1]) || (poly[j][1] <= pt[1] && pt[1] < poly[i].y))
        && (pt[0] < (poly[j][0] - poly[i][0]) * (pt[1] …

假设平面上有许多凸多边形,也许是地图.这些多边形可以相互碰撞并共享边缘,但不能重叠.

为了测试两个多边形P和Q是否重叠,首先我可以测试P中的每个边缘以查看它是否与Q中的任何边相交.如果找到了交叉点,我声明P和Q相交.如果没有相交,那么我必须测试P完全被Q包含的情况,反之亦然.接下来,有P == Q的情况.最后,情况是共享一些边缘,但不是全部.(最后两种情况可能被认为是相同的一般情况,但这可能并不重要.)

我有一个算法,可以检测两个线段相交的位置.如果这两个段是共线的,则不会认为它们与我的目的相交.

我是否正确列举了这些案例？有关这些案件的测试建议吗？

请注意,我不是要找到交叉的新凸多边形,我只想知道交叉是否存在.有许多记录良好的算法可以找到交集,但我不需要经过所有的努力.

(就我的目的而言,"多边形"不包括自相交多边形或带孔的多边形 - 只是简单(凹或凸)多边形.)

我找到了针对这个问题的各种建议,主要基于以下几点:

如果Polygon1的边缘与Polygon2的边缘之间没有交叉点,并且Polygon2的至少一个顶点是"内部"Polygon1,则Polygon1包含Polygon2.

(例如,请参阅此处接受的答案)

然而,魔鬼在细节:

• "内部"Polygon1是否包含"Polygon1"的边缘？显然它必须,否则在图F中(参见下面链接的图像)Polygon2(红色)在Polygon1(蓝色)内部没有顶点,因此在应该通过时不能通过上述测试.

• 两条边的"交点"是否包含一条边(即顶点)末端的点？如果"是",则下面的图A和E具有交叉点,因此当它们通过时测试失败.但如果"不",则图B,C和D没有交叉点,因此当它们失败时通过测试.

(NB图A,B和C在Polygon1的边缘上具有Polygon2的顶点,图D和E反之亦然.)

我无法确定一个条件来测试这些不同情况之间的区别.我会感激任何指针？