我试图创建一个快速的2D点内多边形算法,用于命中测试(例如多边形.contains(p:点))。对有效技术的建议将不胜感激。
当前回答
这只适用于凸形状,但是Minkowski Portal Refinement和GJK也是测试一个点是否在多边形中的很好的选择。您使用闵可夫斯基减法从多边形中减去点,然后运行这些算法来查看多边形是否包含原点。
另外,有趣的是,你可以用支持函数更隐式地描述你的形状,它以一个方向向量作为输入,并输出沿该向量的最远点。这可以让你描述任何凸形状..弯曲的,由多边形制成的,或混合的您还可以执行一些操作,将简单支持函数的结果组合起来,以生成更复杂的形状。
更多信息: http://xenocollide.snethen.com/mpr2d.html
此外,game programming gems 7讨论了如何在3d中做到这一点(:
其他回答
计算点p与每个多边形顶点之间的有向角和。如果总倾斜角是360度,那么这个点在里面。如果总数为0,则点在外面。
我更喜欢这种方法,因为它更健壮,对数值精度的依赖更小。
计算交集数量的均匀性的方法是有限的,因为你可以在计算交集数量的过程中“击中”一个顶点。
编辑:顺便说一下,这种方法适用于凹凸多边形。
编辑:我最近在维基百科上找到了一篇关于这个话题的完整文章。
Java版本:
public class Geocode {
private float latitude;
private float longitude;
public Geocode() {
}
public Geocode(float latitude, float longitude) {
this.latitude = latitude;
this.longitude = longitude;
}
public float getLatitude() {
return latitude;
}
public void setLatitude(float latitude) {
this.latitude = latitude;
}
public float getLongitude() {
return longitude;
}
public void setLongitude(float longitude) {
this.longitude = longitude;
}
}
public class GeoPolygon {
private ArrayList<Geocode> points;
public GeoPolygon() {
this.points = new ArrayList<Geocode>();
}
public GeoPolygon(ArrayList<Geocode> points) {
this.points = points;
}
public GeoPolygon add(Geocode geo) {
points.add(geo);
return this;
}
public boolean inside(Geocode geo) {
int i, j;
boolean c = false;
for (i = 0, j = points.size() - 1; i < points.size(); j = i++) {
if (((points.get(i).getLongitude() > geo.getLongitude()) != (points.get(j).getLongitude() > geo.getLongitude())) &&
(geo.getLatitude() < (points.get(j).getLatitude() - points.get(i).getLatitude()) * (geo.getLongitude() - points.get(i).getLongitude()) / (points.get(j).getLongitude() - points.get(i).getLongitude()) + points.get(i).getLatitude()))
c = !c;
}
return c;
}
}
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
}
}
这只适用于凸形状,但是Minkowski Portal Refinement和GJK也是测试一个点是否在多边形中的很好的选择。您使用闵可夫斯基减法从多边形中减去点,然后运行这些算法来查看多边形是否包含原点。
另外,有趣的是,你可以用支持函数更隐式地描述你的形状,它以一个方向向量作为输入,并输出沿该向量的最远点。这可以让你描述任何凸形状..弯曲的,由多边形制成的,或混合的您还可以执行一些操作,将简单支持函数的结果组合起来,以生成更复杂的形状。
更多信息: http://xenocollide.snethen.com/mpr2d.html
此外,game programming gems 7讨论了如何在3d中做到这一点(:
我认为下面这段代码是最好的解决方案(从这里开始):
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;
}
参数
nvert:多边形中的顶点数。是否在末端重复第一个顶点在上面的文章中已经讨论过了。 vertx, verty:包含多边形顶点的x坐标和y坐标的数组。 testx, testy:测试点的X坐标和y坐标。
它既简短又高效,适用于凸多边形和凹多边形。如前所述,您应该首先检查边界矩形,并单独处理多边形孔。
这背后的想法很简单。作者描述如下:
我从测试点水平运行一条半无限射线(增加x,固定y),并计算它穿过多少条边。在每个十字路口,光线在内部和外部之间切换。这叫做乔丹曲线定理。
当水平射线穿过任意一条边时,变量c从0变为1,从1变为0。基本上它记录了交叉边的数量是偶数还是奇数。0表示偶数,1表示奇数。
推荐文章
- 确定记录是否存在的最快方法
- 阅读GHC核心
- Python: List vs Dict用于查找表
- 为什么MATLAB的矩阵乘法运算这么快?
- for循环和for-each循环在性能上有区别吗?
- 就性能而言,使用std::memcpy()还是std::copy()更好?
- 什么时候我应该(不)想要在我的代码中使用熊猫apply() ?
- 如何加速gwt编译器?
- MySQL OR与IN性能
- 应该……接住环内还是环外?
- 哪个更快/最好?SELECT *或SELECT columnn1, colum2, column3等
- 加快R中的循环操作
- INT和VARCHAR主键之间有真正的性能差异吗?
- c++标准是否要求iostreams的性能很差,或者我只是在处理一个糟糕的实现?
- 大概的成本访问各种缓存和主存储器?