我试图创建一个快速的2D点内多边形算法,用于命中测试(例如多边形.contains(p:点))。对有效技术的建议将不胜感激。
当前回答
这大概是一个稍微不那么优化的C代码版本,它来自于这个页面。
我的c++版本使用std::vector<std::pair<double, double>>和两个double作为x和y。逻辑应该与原始C代码完全相同,但我发现我的更容易阅读。我不能为表演说话。
bool point_in_poly(std::vector<std::pair<double, double>>& verts, double point_x, double point_y)
{
bool in_poly = false;
auto num_verts = verts.size();
for (int i = 0, j = num_verts - 1; i < num_verts; j = i++) {
double x1 = verts[i].first;
double y1 = verts[i].second;
double x2 = verts[j].first;
double y2 = verts[j].second;
if (((y1 > point_y) != (y2 > point_y)) &&
(point_x < (x2 - x1) * (point_y - y1) / (y2 - y1) + x1))
in_poly = !in_poly;
}
return in_poly;
}
原始的C代码是
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;
}
其他回答
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;
}
}
令人惊讶的是之前没有人提出这个问题,但是对于需要数据库的实用主义者来说:MongoDB对Geo查询提供了出色的支持,包括这个查询。
你需要的是:
db.neighborhoods。findOne({geometry: {$geoIntersects: {$geometry: { type: "Point",坐标:["经度","纬度"]}}} })
communities是存储一个或多个标准GeoJson格式多边形的集合。如果查询返回null,则表示不相交,否则为。
这里有详细的记录: https://docs.mongodb.com/manual/tutorial/geospatial-tutorial/
在330个不规则多边形网格中,超过6000个点分类的性能不到一分钟,没有任何优化,包括用各自的多边形更新文档的时间。
bobobobo引用的Eric Haines的文章真的很棒。特别有趣的是比较算法性能的表格;角度求和法和其他方法比起来真的很差。同样有趣的是,使用查找网格将多边形进一步细分为“in”和“out”扇区的优化可以使测试非常快,即使是在> 1000条边的多边形上。
不管怎样,现在还为时过早,但我的投票倾向于“交叉”方法,我认为这几乎就是Mecki所描述的。然而,我发现大卫·伯克(David Bourke)对它进行了最简洁的描述和编纂。我喜欢它不需要真正的三角函数,它适用于凸和凹,而且随着边数的增加,它的表现也相当不错。
顺便说一下,这是Eric Haines文章中的一个性能表,在随机多边形上进行测试。
number of edges per polygon
3 4 10 100 1000
MacMartin 2.9 3.2 5.9 50.6 485
Crossings 3.1 3.4 6.8 60.0 624
Triangle Fan+edge sort 1.1 1.8 6.5 77.6 787
Triangle Fan 1.2 2.1 7.3 85.4 865
Barycentric 2.1 3.8 13.8 160.7 1665
Angle Summation 56.2 70.4 153.6 1403.8 14693
Grid (100x100) 1.5 1.5 1.6 2.1 9.8
Grid (20x20) 1.7 1.7 1.9 5.7 42.2
Bins (100) 1.8 1.9 2.7 15.1 117
Bins (20) 2.1 2.2 3.7 26.3 278
您可以通过检查将所需点连接到多边形顶点所形成的面积是否与多边形本身的面积相匹配来实现这一点。
或者你可以检查从你的点到每一对连续的多边形顶点到你的检查点的内角之和是否为360,但我有一种感觉,第一种选择更快,因为它不涉及除法,也不计算三角函数的反函数。
我不知道如果你的多边形内部有一个洞会发生什么,但在我看来,主要思想可以适应这种情况
你也可以把问题贴在数学社区里。我打赌他们有一百万种方法
简单的解决方案是将多边形划分为三角形,并按这里解释的那样对三角形进行测试
如果你的多边形是凸多边形,可能有更好的方法。把这个多边形看作是无限条线的集合。每一行将空间一分为二。对于每一个点,很容易判断它是在直线的一边还是另一边。如果一个点在所有直线的同一侧,那么它在多边形内。
推荐文章
- 确定记录是否存在的最快方法
- 阅读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的性能很差,或者我只是在处理一个糟糕的实现?
- 大概的成本访问各种缓存和主存储器?