多边形边缘上的点应该在多边形内部吗？

Question

最近我遇到了一个小但重要的问题：多边形边缘上的点是否在多边形内部？

我的意思是 - 目前我正在尝试在 JS 中实现2D 几何库以满足自定义需求，并且有方法，可以说Polygon.contains(point)。

所以我的问题是 - 当点位于多边形的边缘之一时 - 结果该点是在多边形的内部还是外部？关于顶点的附加问题：如果点位于多边形顶点的正上方 - 它是在内部还是外部？

我使用的算法取自此处，如下所示：

int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy)
{
    int i, j, c = 0;
    for (i = 0, j = nvert-1; i < nvert; j = i++) {
        if ( ((verty[i]>testy) != (verty[j]>testy)) &&
          (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j] - verty[i]) + vertx[i]) )
           c = !c;
    }
    return c;
}

另外，还有一段来自该网站的引述：

PNPOLY 将平面划分为多边形内部的点和多边形外部的点。边界上的点分为内部点或外部点。

它完全正确，在某些情况下返回 TRUE，在某些情况下返回 FALSE。

事实上，这不是我需要的。所以我的问题开始扩展 - 当点位于多边形边缘时哪种行为是正确的 - 是在内部还是外部。您是否有更好的可预测行为的算法？

更新：

好吧，我找到了另一个算法，称为“绕数”，为了测试它，我仅使用具有整数值的多边形和点：

function isLeft(p0, p1, p2){
    return ( Math.round((p1.x - p0.x) * (p2.y - p0.y)) - Math.round((p2.x - p0.x) * (p1.y - p0.y)) );
}

function polygonContainsPoint(polygon, point){
    var i, j, pointi, pointj;
    var count = 0;
    var vertices = polygon.vertices;
    var length = vertices.length;
    for (i = 0; i < length; i++){
        j = (i + 1) % length;
        pointi = vertices[i];
        pointj = vertices[j];
        if (pointi.y > point.y){
            if (pointj.y <= point.y && (isLeft(pointi, pointj, point) < 0)){
                --count;
            }
        } else if (pointj.y > point.y && (isLeft(pointi, pointj, point) > 0)){
            ++count;
        }
    }
    return 0 !== count;
}

正如你所看到的，没有任何划分；乘法被包装到 round() 方法中，因此无法出现浮点错误。不管怎样，我得到了与奇偶算法相同的结果。我想我开始在这种奇怪的行为中看到“模式”：左侧和顶部边缘可能表明该点位于多边形内部，但是当您尝试将点放在右侧或底部边缘之一时 - 它可能返回假。

这对我来说不好。也许你们中的一些人知道一些具有更可预测行为的算法？

Answer 1

这个问题的简单答案是，边缘上的点既不在多边形内部，也不在多边形外部，它位于多边形的边界上 - 第三种选择。但通常这并不重要（正如你的引文所支持的那样），重要的是避免点分类的错误，这些错误实际上是在内部或外部。

多边形内的点问题有时称为奇偶校验算法：

• 令r为水平半线，其左端点为测试点。
• r计算多边形之间的交点和边的数量。如果该数字是奇数，则测试点位于多边形内，如果数字是偶数，则测试点位于多边形外部。

这里有些例子：

• (a)、(b) - 非退化情况，其中半线不与边缘相交或穿过边缘。
• (c)、(d)、(e)、(f)——必须考虑的四种退化情况。

如果情况(c)和(e)算作一次交叉，而情况(d)和(f)根本不计算在内，则获得正确答案。如果我们为上述算法编写代码，我们就会意识到需要付出大量的努力来覆盖四种退化情况。

随着算法越来越复杂，尤其是 3D 算法，支持退化情况的工作量急剧增加。

上述问题和解释出现在Herbert Edelsbrunner 和 Ernst Peter Mucke 的Simplicity 仿真介绍文章中。提出的解决方案是通过输入点的虚拟最小扰动来消除所有退化。此后，测试点将永远不会在边缘上，而只会在多边形内部或外部。