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


当前回答

当使用qt (qt 4.3+)时,可以使用QPolygon的函数containsPoint

其他回答

David Segond's answer is pretty much the standard general answer, and Richard T's is the most common optimization, though therre are some others. Other strong optimizations are based on less general solutions. For example if you are going to check the same polygon with lots of points, triangulating the polygon can speed things up hugely as there are a number of very fast TIN searching algorithms. Another is if the polygon and points are on a limited plane at low resolution, say a screen display, you can paint the polygon onto a memory mapped display buffer in a given colour, and check the color of a given pixel to see if it lies in the polygons.

像许多优化一样,这些优化是基于特定情况而不是一般情况,并且基于摊销时间而不是单次使用产生效益。

在这个领域工作,我发现约瑟夫·奥鲁克斯的《计算几何》在C' ISBN 0-521-44034-3是一个很大的帮助。

简单的解决方案是将多边形划分为三角形,并按这里解释的那样对三角形进行测试

如果你的多边形是凸多边形,可能有更好的方法。把这个多边形看作是无限条线的集合。每一行将空间一分为二。对于每一个点,很容易判断它是在直线的一边还是另一边。如果一个点在所有直线的同一侧,那么它在多边形内。

当我还是Michael Stonebraker手下的一名研究员时,我做了一些关于这方面的工作——你知道,就是那位提出了Ingres、PostgreSQL等的教授。

我们意识到最快的方法是首先做一个边界框,因为它非常快。如果它在边界框之外,它就在外面。否则,你就得做更辛苦的工作……

如果你想要一个伟大的算法,看看开源项目PostgreSQL的源代码的地理工作…

我想指出的是,我们从来没有深入了解过左撇子和右撇子(也可以表达为“内”和“外”的问题……


更新

BKB's link provided a good number of reasonable algorithms. I was working on Earth Science problems and therefore needed a solution that works in latitude/longitude, and it has the peculiar problem of handedness - is the area inside the smaller area or the bigger area? The answer is that the "direction" of the verticies matters - it's either left-handed or right handed and in this way you can indicate either area as "inside" any given polygon. As such, my work used solution three enumerated on that page.

此外,我的工作使用单独的函数进行“在线”测试。

...因为有人问:我们发现当垂直的数量超过某个数字时,边界盒测试是最好的——如果有必要,在做更长的测试之前做一个非常快速的测试……边界框是通过简单地将最大的x,最小的x,最大的y和最小的y放在一起,组成一个框的四个点来创建的……

另一个提示是:我们在网格空间中进行了所有更复杂的“调光”计算,都是在平面上的正点上进行的,然后重新投影到“真实”的经度/纬度上,从而避免了在经度180线交叉时和处理极地时可能出现的环绕错误。工作好了!

这只适用于凸形状,但是Minkowski Portal Refinement和GJK也是测试一个点是否在多边形中的很好的选择。您使用闵可夫斯基减法从多边形中减去点,然后运行这些算法来查看多边形是否包含原点。

另外,有趣的是,你可以用支持函数更隐式地描述你的形状,它以一个方向向量作为输入,并输出沿该向量的最远点。这可以让你描述任何凸形状..弯曲的,由多边形制成的,或混合的您还可以执行一些操作,将简单支持函数的结果组合起来,以生成更复杂的形状。

更多信息: http://xenocollide.snethen.com/mpr2d.html

此外,game programming gems 7讨论了如何在3d中做到这一点(:

我知道这是旧的,但这里是一个在Cocoa实现的光线投射算法,如果有人感兴趣的话。不确定这是最有效的方法,但它可能会帮助别人。

- (BOOL)shape:(NSBezierPath *)path containsPoint:(NSPoint)point
{
    NSBezierPath *currentPath = [path bezierPathByFlatteningPath];
    BOOL result;
    float aggregateX = 0; //I use these to calculate the centroid of the shape
    float aggregateY = 0;
    NSPoint firstPoint[1];
    [currentPath elementAtIndex:0 associatedPoints:firstPoint];
    float olderX = firstPoint[0].x;
    float olderY = firstPoint[0].y;
    NSPoint interPoint;
    int noOfIntersections = 0;

    for (int n = 0; n < [currentPath elementCount]; n++) {
        NSPoint points[1];
        [currentPath elementAtIndex:n associatedPoints:points];
        aggregateX += points[0].x;
        aggregateY += points[0].y;
    }

    for (int n = 0; n < [currentPath elementCount]; n++) {
        NSPoint points[1];

        [currentPath elementAtIndex:n associatedPoints:points];
        //line equations in Ax + By = C form
        float _A_FOO = (aggregateY/[currentPath elementCount]) - point.y;  
        float _B_FOO = point.x - (aggregateX/[currentPath elementCount]);
        float _C_FOO = (_A_FOO * point.x) + (_B_FOO * point.y);

        float _A_BAR = olderY - points[0].y;
        float _B_BAR = points[0].x - olderX;
        float _C_BAR = (_A_BAR * olderX) + (_B_BAR * olderY);

        float det = (_A_FOO * _B_BAR) - (_A_BAR * _B_FOO);
        if (det != 0) {
            //intersection points with the edges
            float xIntersectionPoint = ((_B_BAR * _C_FOO) - (_B_FOO * _C_BAR)) / det;
            float yIntersectionPoint = ((_A_FOO * _C_BAR) - (_A_BAR * _C_FOO)) / det;
            interPoint = NSMakePoint(xIntersectionPoint, yIntersectionPoint);
            if (olderX <= points[0].x) {
                //doesn't matter in which direction the ray goes, so I send it right-ward.
                if ((interPoint.x >= olderX && interPoint.x <= points[0].x) && (interPoint.x > point.x)) {  
                    noOfIntersections++;
                }
            } else {
                if ((interPoint.x >= points[0].x && interPoint.x <= olderX) && (interPoint.x > point.x)) {
                     noOfIntersections++;
                } 
            }
        }
        olderX = points[0].x;
        olderY = points[0].y;
    }
    if (noOfIntersections % 2 == 0) {
        result = FALSE;
    } else {
        result = TRUE;
    }
    return result;
}