我试图创建一个快速的2D点内多边形算法,用于命中测试(例如多边形.contains(p:点))。对有效技术的建议将不胜感激。
当前回答
这个问题的大多数答案并没有很好地处理所有的极端情况。以下是一些微妙的极端情况: 这是一个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
}
其他回答
我知道这是旧的,但这里是一个在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;
}
from typing import Iterable
def pnpoly(verts, x, y):
#check if x and/or y is iterable
xit, yit = isinstance(x, Iterable), isinstance(y, Iterable)
#if not iterable, make an iterable of length 1
X = x if xit else (x, )
Y = y if yit else (y, )
#store verts length as a range to juggle j
r = range(len(verts))
#final results if x or y is iterable
results = []
#traverse x and y coordinates
for xp in X:
for yp in Y:
c = 0 #reset c at every new position
for i in r:
j = r[i-1] #set j to position before i
#store a few arguments to shorten the if statement
yneq = (verts[i][1] > yp) != (verts[j][1] > yp)
xofs, yofs = (verts[j][0] - verts[i][0]), (verts[j][1] - verts[i][1])
#if we have crossed a line, increment c
if (yneq and (xp < xofs * (yp - verts[i][1]) / yofs + verts[i][0])):
c += 1
#if c is odd store the coordinates
if c%2:
results.append((xp, yp))
#return either coordinates or a bool, depending if x or y was an iterable
return results if (xit or yit) else bool(c%2)
这个python版本是通用的。您可以为True/False结果输入单个x和单个y值,也可以使用x和y的范围来遍历整个点网格。如果使用范围,则返回所有True点的x/y对列表。vertices参数需要一个由x/y对组成的二维Iterable,例如:[(x1,y1), (x2,y2),…]
使用示例:
vertices = [(25,25), (75,25), (75,75), (25,75)]
pnpoly(vertices, 50, 50) #True
pnpoly(vertices, range(100), range(100)) #[(25,25), (25,26), (25,27), ...]
实际上,这些都可以。
pnpoly(vertices, 50, range(100)) #check 0 to 99 y at x of 50
pnpoly(vertices, range(100), 50) #check 0 to 99 x at y of 50
答案取决于你用的是简单多边形还是复杂多边形。简单多边形不能有任何线段交点。所以它们可以有洞,但线不能交叉。复杂区域可以有直线交点,所以它们可以有重叠的区域,或者只有一点相交的区域。
对于简单多边形,最好的算法是光线投射(交叉数)算法。对于复杂多边形,该算法不检测重叠区域内的点。所以对于复杂多边形你必须使用圈数算法。
下面是一篇用C实现这两种算法的优秀文章。我试过了,效果不错。
http://geomalgorithms.com/a03-_inclusion.html
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是一个很大的帮助。
我认为下面这段代码是最好的解决方案(从这里开始):
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的性能很差,或者我只是在处理一个糟糕的实现?
- 大概的成本访问各种缓存和主存储器?