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


当前回答

下面是golang版本的@nirg答案(灵感来自于@@m-katz的c#代码)

func isPointInPolygon(polygon []point, testp point) bool {
    minX := polygon[0].X
    maxX := polygon[0].X
    minY := polygon[0].Y
    maxY := polygon[0].Y

    for _, p := range polygon {
        minX = min(p.X, minX)
        maxX = max(p.X, maxX)
        minY = min(p.Y, minY)
        maxY = max(p.Y, maxY)
    }

    if testp.X < minX || testp.X > maxX || testp.Y < minY || testp.Y > maxY {
        return false
    }

    inside := false
    j := len(polygon) - 1
    for i := 0; i < len(polygon); i++ {
        if (polygon[i].Y > testp.Y) != (polygon[j].Y > testp.Y) && testp.X < (polygon[j].X-polygon[i].X)*(testp.Y-polygon[i].Y)/(polygon[j].Y-polygon[i].Y)+polygon[i].X {
            inside = !inside
        }
        j = i
    }

    return inside
}

其他回答

这似乎在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)}

计算点p与每个多边形顶点之间的有向角和。如果总倾斜角是360度,那么这个点在里面。如果总数为0,则点在外面。

我更喜欢这种方法,因为它更健壮,对数值精度的依赖更小。

计算交集数量的均匀性的方法是有限的,因为你可以在计算交集数量的过程中“击中”一个顶点。

编辑:顺便说一下,这种方法适用于凹凸多边形。

编辑:我最近在维基百科上找到了一篇关于这个话题的完整文章。

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

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

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

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

如果你正在使用谷歌Map SDK,想要检查一个点是否在一个多边形内,你可以尝试使用GMSGeometryContainsLocation。效果很好!!它是这样运作的,

if GMSGeometryContainsLocation(point, polygon, true) {
    print("Inside this polygon.")
} else {
    print("outside this polygon")
}

这里是参考资料:https://developers.google.com/maps/documentation/ios-sdk/reference/group___geometry_utils#gaba958d3776d49213404af249419d0ffd

当我还是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线交叉时和处理极地时可能出现的环绕错误。工作好了!