我试图创建一个快速的2D点内多边形算法,用于命中测试(例如多边形.contains(p:点))。对有效技术的建议将不胜感激。
当前回答
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
其他回答
对于检测多边形上的命中,我们需要测试两件事:
如果点在多边形区域内。(可通过Ray-Casting算法实现) 如果点在多边形边界上(可以用与在折线(线)上检测点相同的算法来完成)。
下面是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
}
Like David Segonds' answer suggests I use an approach of angle summation derived from my concave polygon drawing algorithm. It relies of adding up the approximate angles of subtriangles around the point to obtain a weight. A weight around 1.0 means the point is inside the triangle, a weight around 0.0 means outside, a weight around -1.0 is what happens when inside the polygon but in reverse order (like with one of the halves of a bowtie-shaped tetragon) and a weight of NAN if exactly on an edge. The reason it's not slow is that angles don't need to be estimated accurately at all. Holes can be handled by treating them as separate polygons and subtracting the weights.
typedef struct { double x, y; } xy_t;
xy_t sub_xy(xy_t a, xy_t b)
{
a.x -= b.x;
a.y -= b.y;
return a;
}
double calc_sharp_subtriangle_pixel_weight(xy_t p0, xy_t p1)
{
xy_t rot, r0, r1;
double weight;
// Rotate points (unnormalised)
rot = sub_xy(p1, p0);
r0.x = rot.x*p0.y - rot.y*p0.x;
r0.y = rot.x*p0.x + rot.y*p0.y;
r1.y = rot.x*p1.x + rot.y*p1.y;
// Calc weight
weight = subtriangle_angle_approx(r1.y, r0.x) - subtriangle_angle_approx(r0.y, r0.x);
return weight;
}
double calc_sharp_polygon_pixel_weight(xy_t p, xy_t *corner, int corner_count)
{
int i;
xy_t p0, p1;
double weight = 0.;
p0 = sub_xy(corner[corner_count-1], p);
for (i=0; i < corner_count; i++)
{
// Transform corner coordinates
p1 = sub_xy(corner[i], p);
// Calculate weight for each subtriangle
weight += calc_sharp_subtriangle_pixel_weight(p0, p1);
p0 = p1;
}
return weight;
}
因此,对于多边形的每一段,都形成一个子三角形,并计算点,然后旋转每个子三角形以计算其近似角度并添加到权重。
调用subtriangle_angle_approx(y, x)可以替换为atan2(y, x) / (2.*pi),但是一个非常粗略的近似值就足够精确了:
double subtriangle_angle_approx(double y, double x)
{
double angle, d;
int obtuse;
if (x == 0.)
return NAN;
obtuse = fabs(y) > fabs(x);
if (obtuse)
swap_double(&y, &x);
// Core of the approximation, a very loosely approximate atan(y/x) / (2.*pi) over ]-1 , 1[
d = y / x;
angle = 0.13185 * d;
if (obtuse)
angle = sign(d)*0.25 - angle;
return angle;
}
这个问题的大多数答案并没有很好地处理所有的极端情况。以下是一些微妙的极端情况: 这是一个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
}
简单的解决方案是将多边形划分为三角形,并按这里解释的那样对三角形进行测试
如果你的多边形是凸多边形,可能有更好的方法。把这个多边形看作是无限条线的集合。每一行将空间一分为二。对于每一个点,很容易判断它是在直线的一边还是另一边。如果一个点在所有直线的同一侧,那么它在多边形内。
推荐文章
- 确定记录是否存在的最快方法
- 阅读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的性能很差,或者我只是在处理一个糟糕的实现?
- 大概的成本访问各种缓存和主存储器?