绕数算法与凸边界/边缘上的点

Question

我需要一个算法，可以判断点是否在凸包（C/C++）的内部/外部或边界上。

凸包是由点数组X、Y和整数描述的，连接从i到i+1。

目前我正在使用螺旋数算法，在此处进行了描述： http://geomalgorithms.com/a03-_inclusion.html 它的函数名为“wn_PnPoly()”。

有没有可能，以及如何让螺旋数算法检测到点是否恰好在凸包的边界（边缘）上？ 还有其他的算法可以做到这一点吗？（需要使用int类型）。

- user3157855

---

只需阅读函数的实现，您就会发现测试一个点是否位于边的左侧/上方/右侧的过程。 - user2249683

Answer 1

找到解决方案：

int wn_PnPoly2(Point P, vector<Point> V, int n)
{
    int    wn = 0;    // the  winding number counter

                      // loop through all edges of the polygon
    for (int i = 0; i<n; i++) {   // edge from V[i] to  V[i+1]
        if (V[i].Y <= P.Y) {          // start y <= P.y
            if (V[i + 1].Y  > P.Y)      // an upward crossing
            {
                int l = isLeft(V[i], V[i + 1], P);
                if (l > 0)  // P left of  edge
                    ++wn;            // have  a valid up intersect
                else if (l == 0) // boundary
                    return 0;
            }
        }
        else {                        // start y > P.y (no test needed)
            if (V[i + 1].Y <= P.Y)     // a downward crossing
            {
                int l = isLeft(V[i], V[i + 1], P);
                if (l < 0)  // P right of  edge
                    --wn;            // have  a valid down intersect
                else if (l == 0)
                    return 0;
            }
        }
    }
    return wn;
}

- user3157855

---

缺少isLeft()函数，但也可以在其他来源中找到。例如，在这里：http://forums.codeguru.com/showthread.php?497679-To-check-if-a-point-is-inside-a-polygon - st6mm

Answer 2

我不熟悉"绕线数算法"，但要检测一个点是否位于边上，你只需循环遍历凸包的所有边，并进行以下检查：

如果点u、v是凸包上的连续点，而p是要考虑的点，那么下面的条件是否成立：

p - u = lambda*(v - u) 其中 lambda 是介于0和1之间的任意标量。

- Abhishek Bansal