我试图创建一个快速的2D点内多边形算法,用于命中测试(例如多边形.contains(p:点))。对有效技术的建议将不胜感激。


当前回答

这似乎在R中工作(为丑陋道歉,希望看到更好的版本!)。

pnpoly <- function(nvert,vertx,verty,testx,testy){
          c <- FALSE
          j <- nvert 
          for (i in 1:nvert){
              if( ((verty[i]>testy) != (verty[j]>testy)) && 
   (testx < (vertx[j]-vertx[i])*(testy-verty[i])/(verty[j]-verty[i])+vertx[i]))
            {c <- !c}
             j <- i}
   return(c)}

其他回答

答案取决于你用的是简单多边形还是复杂多边形。简单多边形不能有任何线段交点。所以它们可以有洞,但线不能交叉。复杂区域可以有直线交点,所以它们可以有重叠的区域,或者只有一点相交的区域。

对于简单多边形,最好的算法是光线投射(交叉数)算法。对于复杂多边形,该算法不检测重叠区域内的点。所以对于复杂多边形你必须使用圈数算法。

下面是一篇用C实现这两种算法的优秀文章。我试过了,效果不错。

http://geomalgorithms.com/a03-_inclusion.html

下面是nirg给出的答案的c#版本,它来自RPI教授。请注意,使用来自RPI源代码的代码需要归属。

在顶部添加了一个边界框复选。然而,正如James Brown所指出的,主代码几乎和边界框检查本身一样快,所以边界框检查实际上会减慢整体操作,因为您正在检查的大多数点都在边界框内。所以你可以让边界框签出,或者另一种选择是预先计算多边形的边界框,如果它们不经常改变形状的话。

public bool IsPointInPolygon( Point p, Point[] polygon )
{
    double minX = polygon[ 0 ].X;
    double maxX = polygon[ 0 ].X;
    double minY = polygon[ 0 ].Y;
    double maxY = polygon[ 0 ].Y;
    for ( int i = 1 ; i < polygon.Length ; i++ )
    {
        Point q = polygon[ i ];
        minX = Math.Min( q.X, minX );
        maxX = Math.Max( q.X, maxX );
        minY = Math.Min( q.Y, minY );
        maxY = Math.Max( q.Y, maxY );
    }

    if ( p.X < minX || p.X > maxX || p.Y < minY || p.Y > maxY )
    {
        return false;
    }

    // https://wrf.ecse.rpi.edu/Research/Short_Notes/pnpoly.html
    bool inside = false;
    for ( int i = 0, j = polygon.Length - 1 ; i < polygon.Length ; j = i++ )
    {
        if ( ( polygon[ i ].Y > p.Y ) != ( polygon[ j ].Y > p.Y ) &&
             p.X < ( polygon[ j ].X - polygon[ i ].X ) * ( p.Y - polygon[ i ].Y ) / ( polygon[ j ].Y - polygon[ i ].Y ) + polygon[ i ].X )
        {
            inside = !inside;
        }
    }

    return inside;
}

这个问题的大多数答案并没有很好地处理所有的极端情况。以下是一些微妙的极端情况: 这是一个javascript版本,所有角落的情况都得到了很好的处理。

/** Get relationship between a point and a polygon using ray-casting algorithm
 * @param {{x:number, y:number}} P: point to check
 * @param {{x:number, y:number}[]} polygon: the polygon
 * @returns -1: outside, 0: on edge, 1: inside
 */
function relationPP(P, polygon) {
    const between = (p, a, b) => p >= a && p <= b || p <= a && p >= b
    let inside = false
    for (let i = polygon.length-1, j = 0; j < polygon.length; i = j, j++) {
        const A = polygon[i]
        const B = polygon[j]
        // corner cases
        if (P.x == A.x && P.y == A.y || P.x == B.x && P.y == B.y) return 0
        if (A.y == B.y && P.y == A.y && between(P.x, A.x, B.x)) return 0

        if (between(P.y, A.y, B.y)) { // if P inside the vertical range
            // filter out "ray pass vertex" problem by treating the line a little lower
            if (P.y == A.y && B.y >= A.y || P.y == B.y && A.y >= B.y) continue
            // calc cross product `PA X PB`, P lays on left side of AB if c > 0 
            const c = (A.x - P.x) * (B.y - P.y) - (B.x - P.x) * (A.y - P.y)
            if (c == 0) return 0
            if ((A.y < B.y) == (c > 0)) inside = !inside
        }
    }

    return inside? 1 : -1
}

您可以通过检查将所需点连接到多边形顶点所形成的面积是否与多边形本身的面积相匹配来实现这一点。

或者你可以检查从你的点到每一对连续的多边形顶点到你的检查点的内角之和是否为360,但我有一种感觉,第一种选择更快,因为它不涉及除法,也不计算三角函数的反函数。

我不知道如果你的多边形内部有一个洞会发生什么,但在我看来,主要思想可以适应这种情况

你也可以把问题贴在数学社区里。我打赌他们有一百万种方法

nirg回答的Swift版本:

extension CGPoint {
    func isInsidePolygon(vertices: [CGPoint]) -> Bool {
        guard !vertices.isEmpty else { return false }
        var j = vertices.last!, c = false
        for i in vertices {
            let a = (i.y > y) != (j.y > y)
            let b = (x < (j.x - i.x) * (y - i.y) / (j.y - i.y) + i.x)
            if a && b { c = !c }
            j = i
        }
        return c
    }
}