我试图创建一个快速的2D点内多边形算法,用于命中测试(例如多边形.contains(p:点))。对有效技术的建议将不胜感激。
当前回答
简单的解决方案是将多边形划分为三角形,并按这里解释的那样对三角形进行测试
如果你的多边形是凸多边形,可能有更好的方法。把这个多边形看作是无限条线的集合。每一行将空间一分为二。对于每一个点,很容易判断它是在直线的一边还是另一边。如果一个点在所有直线的同一侧,那么它在多边形内。
其他回答
计算点p与每个多边形顶点之间的有向角和。如果总倾斜角是360度,那么这个点在里面。如果总数为0,则点在外面。
我更喜欢这种方法,因为它更健壮,对数值精度的依赖更小。
计算交集数量的均匀性的方法是有限的,因为你可以在计算交集数量的过程中“击中”一个顶点。
编辑:顺便说一下,这种方法适用于凹凸多边形。
编辑:我最近在维基百科上找到了一篇关于这个话题的完整文章。
我已经做了nirg的c++代码的Python实现:
输入
Bounding_points:组成多边形的节点。 Bounding_box_positions:筛选的候选点。(在我从边界框创建的实现中。 (输入为元组列表,格式为:[(xcord, ycord),…])
返回
多边形内的所有点。
def polygon_ray_casting(self, bounding_points, bounding_box_positions):
# Arrays containing the x- and y-coordinates of the polygon's vertices.
vertx = [point[0] for point in bounding_points]
verty = [point[1] for point in bounding_points]
# Number of vertices in the polygon
nvert = len(bounding_points)
# Points that are inside
points_inside = []
# For every candidate position within the bounding box
for idx, pos in enumerate(bounding_box_positions):
testx, testy = (pos[0], pos[1])
c = 0
for i in range(0, nvert):
j = i - 1 if i != 0 else nvert - 1
if( ((verty[i] > testy ) != (verty[j] > testy)) and
(testx < (vertx[j] - vertx[i]) * (testy - verty[i]) / (verty[j] - verty[i]) + vertx[i]) ):
c += 1
# If odd, that means that we are inside the polygon
if c % 2 == 1:
points_inside.append(pos)
return points_inside
同样,这个想法也是从这里得来的
以下是M. Katz基于Nirg方法的答案的JavaScript变体:
function pointIsInPoly(p, polygon) {
var isInside = false;
var minX = polygon[0].x, maxX = polygon[0].x;
var minY = polygon[0].y, maxY = polygon[0].y;
for (var n = 1; n < polygon.length; n++) {
var q = polygon[n];
minX = Math.min(q.x, minX);
maxX = Math.max(q.x, maxX);
minY = Math.min(q.y, minY);
maxY = Math.max(q.y, maxY);
}
if (p.x < minX || p.x > maxX || p.y < minY || p.y > maxY) {
return false;
}
var i = 0, j = polygon.length - 1;
for (i, j; i < polygon.length; j = i++) {
if ( (polygon[i].y > p.y) != (polygon[j].y > p.y) &&
p.x < (polygon[j].x - polygon[i].x) * (p.y - polygon[i].y) / (polygon[j].y - polygon[i].y) + polygon[i].x ) {
isInside = !isInside;
}
}
return isInside;
}
为了完整性,这里是nirg提供的算法的lua实现,由Mecki讨论:
function pnpoly(area, test)
local inside = false
local tx, ty = table.unpack(test)
local j = #area
for i=1, #area do
local vxi, vyi = table.unpack(area[i])
local vxj, vyj = table.unpack(area[j])
if (vyi > ty) ~= (vyj > ty)
and tx < (vxj - vxi)*(ty - vyi)/(vyj - vyi) + vxi
then
inside = not inside
end
j = i
end
return inside
end
变量区域是一个点的表,这些点依次存储为2D表。例子:
> A = {{2, 1}, {1, 2}, {15, 3}, {3, 4}, {5, 3}, {4, 1.5}}
> T = {2, 1.1}
> pnpoly(A, T)
true
GitHub Gist的链接。
下面是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
`
推荐文章
- 如何有效地从数组列表或字符串数组中删除所有空元素?
- 在SQL Server上使用varchar(MAX) vs TEXT
- .toArray(new MyClass[0]) or .toArray(new MyClass[myList.size()])?
- 是什么导致JNI调用变慢?
- 检查属性是否有属性
- 如何快速清除JavaScript对象?
- Node.js vs .Net性能
- 如果使用if-return-return或if-else-return?
- 为什么MYSQL的高LIMIT偏移量减慢查询?
- SQL JOIN vs IN性能?
- 如何产生类似ios7模糊视图的效果?
- GraphViz -如何连接子图?
- 如何找到Java堆大小和内存使用(Linux)?
- 如何在HTML5中改变视频的播放速度?
- 我如何提高ASP。NET MVC应用程序性能?