我试图创建一个快速的2D点内多边形算法,用于命中测试(例如多边形.contains(p:点))。对有效技术的建议将不胜感激。
当前回答
答案取决于你用的是简单多边形还是复杂多边形。简单多边形不能有任何线段交点。所以它们可以有洞,但线不能交叉。复杂区域可以有直线交点,所以它们可以有重叠的区域,或者只有一点相交的区域。
对于简单多边形,最好的算法是光线投射(交叉数)算法。对于复杂多边形,该算法不检测重叠区域内的点。所以对于复杂多边形你必须使用圈数算法。
下面是一篇用C实现这两种算法的优秀文章。我试过了,效果不错。
http://geomalgorithms.com/a03-_inclusion.html
其他回答
nirg的c#版本的答案在这里:我只分享代码。这可能会节省一些时间。
public static bool IsPointInPolygon(IList<Point> polygon, Point testPoint) {
bool result = false;
int j = polygon.Count() - 1;
for (int i = 0; i < polygon.Count(); i++) {
if (polygon[i].Y < testPoint.Y && polygon[j].Y >= testPoint.Y || polygon[j].Y < testPoint.Y && polygon[i].Y >= testPoint.Y) {
if (polygon[i].X + (testPoint.Y - polygon[i].Y) / (polygon[j].Y - polygon[i].Y) * (polygon[j].X - polygon[i].X) < testPoint.X) {
result = !result;
}
}
j = i;
}
return result;
}
对于检测多边形上的命中,我们需要测试两件事:
如果点在多边形区域内。(可通过Ray-Casting算法实现) 如果点在多边形边界上(可以用与在折线(线)上检测点相同的算法来完成)。
下面是Rust版本的@nirg答案(Philipp Lenssen javascript版本) 我给出这个答案是因为我从这个网站得到了很多帮助,我翻译javascript版本rust作为一个练习,希望可以帮助一些人,最后一个原因是,在我的工作中,我会把这段代码翻译成一个wasm,以提高我的画布的性能,这是一个开始。我的英语很差……,请原谅我 `
pub struct Point {
x: f32,
y: f32,
}
pub fn point_is_in_poly(pt: Point, polygon: &Vec<Point>) -> bool {
let mut is_inside = false;
let max_x = polygon.iter().map(|pt| pt.x).reduce(f32::max).unwrap();
let min_x = polygon.iter().map(|pt| pt.x).reduce(f32::min).unwrap();
let max_y = polygon.iter().map(|pt| pt.y).reduce(f32::max).unwrap();
let min_y = polygon.iter().map(|pt| pt.y).reduce(f32::min).unwrap();
if pt.x < min_x || pt.x > max_x || pt.y < min_y || pt.y > max_y {
return is_inside;
}
let len = polygon.len();
let mut j = len - 1;
for i in 0..len {
let y_i_value = polygon[i].y > pt.y;
let y_j_value = polygon[j].y > pt.y;
let last_check = (polygon[j].x - polygon[i].x) * (pt.y - polygon[i].y)
/ (polygon[j].y - polygon[i].y)
+ polygon[i].x;
if y_i_value != y_j_value && pt.x < last_check {
is_inside = !is_inside;
}
j = i;
}
is_inside
}
let pt = Point {
x: 1266.753,
y: 97.655,
};
let polygon = vec![
Point {
x: 725.278,
y: 203.586,
},
Point {
x: 486.831,
y: 441.931,
},
Point {
x: 905.77,
y: 445.241,
},
Point {
x: 1026.649,
y: 201.931,
},
];
let pt1 = Point {
x: 725.278,
y: 203.586,
};
let pt2 = Point {
x: 872.652,
y: 321.103,
};
println!("{}", point_is_in_poly(pt, &polygon));// false
println!("{}", point_is_in_poly(pt1, &polygon)); // true
println!("{}", point_is_in_poly(pt2, &polygon));// true
`
简单的解决方案是将多边形划分为三角形,并按这里解释的那样对三角形进行测试
如果你的多边形是凸多边形,可能有更好的方法。把这个多边形看作是无限条线的集合。每一行将空间一分为二。对于每一个点,很容易判断它是在直线的一边还是另一边。如果一个点在所有直线的同一侧,那么它在多边形内。
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;
}
推荐文章
- 确定记录是否存在的最快方法
- 阅读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的性能很差,或者我只是在处理一个糟糕的实现?
- 大概的成本访问各种缓存和主存储器?