我试图创建一个快速的2D点内多边形算法,用于命中测试(例如多边形.contains(p:点))。对有效技术的建议将不胜感激。
当前回答
net端口:
static void Main(string[] args)
{
Console.Write("Hola");
List<double> vertx = new List<double>();
List<double> verty = new List<double>();
int i, j, c = 0;
vertx.Add(1);
vertx.Add(2);
vertx.Add(1);
vertx.Add(4);
vertx.Add(4);
vertx.Add(1);
verty.Add(1);
verty.Add(2);
verty.Add(4);
verty.Add(4);
verty.Add(1);
verty.Add(1);
int nvert = 6; //Vértices del poligono
double testx = 2;
double testy = 5;
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 = 1;
}
}
其他回答
在Ray casting算法中处理以下特殊情况:
射线与多边形的一条边重叠。 点在多边形的内部,光线穿过多边形的顶点。 该点在多边形的外部,光线只接触到多边形的一个角。
检查确定一个点是否在一个复杂多边形内。本文提供了一种简单的解决方法,因此对于上述情况不需要特殊处理。
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;
}
}
如果你正在使用谷歌Map SDK,想要检查一个点是否在一个多边形内,你可以尝试使用GMSGeometryContainsLocation。效果很好!!它是这样运作的,
if GMSGeometryContainsLocation(point, polygon, true) {
print("Inside this polygon.")
} else {
print("outside this polygon")
}
这里是参考资料:https://developers.google.com/maps/documentation/ios-sdk/reference/group___geometry_utils#gaba958d3776d49213404af249419d0ffd
当使用qt (qt 4.3+)时,可以使用QPolygon的函数containsPoint
我认为下面这段代码是最好的解决方案(从这里开始):
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的性能很差,或者我只是在处理一个糟糕的实现?
- 大概的成本访问各种缓存和主存储器?