我有许多构成多边形区域的经度和纬度坐标。我还有一个经度和纬度坐标来定义车辆的位置。如何检查车辆是否位于多边形区域内?
最佳答案
这本质上是 Point in polygon球面上的问题。您可以修改光线转换算法,使其使用大圆弧而不是线段。
- 对于构成多边形的每对相邻坐标,在它们之间绘制一个大圆段。
- 选择一个不在多边形区域内的引用点。
- 绘制一个从引用点开始到车辆点结束的大圆弧段。计算此线段穿过多边形线段的次数。如果总次数为奇数,则车辆在多边形内。如果偶数,则车辆在多边形之外。
或者,如果坐标和车辆靠得足够近,并且不靠近两极或国际日期变更线,您可以假装地球是平的,并使用经度和纬度作为简单的 x 和 y 坐标。这样,您就可以使用具有简单线段的光线转换算法。如果您对非欧几里德几何不满意,这是更可取的,但您的多边形边界周围会有一些变形,因为圆弧会变形。
编辑:关于球体上几何的更多内容。
一个大圆可以通过垂直于圆所在平面的矢量来识别(又名,normal vector)
class Vector{
double x;
double y;
double z;
};
class GreatCircle{
Vector normal;
}
任何两个不是 antipodal 的纬度/经度坐标恰好共享一个大圆圈。要找到这个大圆,请将坐标转换为穿过地球中心的直线。 cross product这两条线的法向量是坐标大圆的法向量。
//arbitrarily defining the north pole as (0,1,0) and (0'N, 0'E) as (1,0,0)
//lattidues should be in [-90, 90] and longitudes in [-180, 180]
//You'll have to convert South lattitudes and East longitudes into their negative North and West counterparts.
Vector lineFromCoordinate(Coordinate c){
Vector ret = new Vector();
//given:
//tan(lat) == y/x
//tan(long) == z/x
//the Vector has magnitude 1, so sqrt(x^2 + y^2 + z^2) == 1
//rearrange some symbols, solving for x first...
ret.x = 1.0 / math.sqrt(tan(c.lattitude)^2 + tan(c.longitude)^2 + 1);
//then for y and z
ret.y = ret.x * tan(c.lattitude);
ret.z = ret.x * tan(c.longitude);
return ret;
}
Vector Vector::CrossProduct(Vector other){
Vector ret = new Vector();
ret.x = this.y * other.z - this.z * other.y;
ret.y = this.z * other.x - this.x * other.z;
ret.z = this.x * other.y - this.y * other.x;
return ret;
}
GreatCircle circleFromCoordinates(Coordinate a, Coordinate b){
Vector a = lineFromCoordinate(a);
Vector b = lineFromCoordinate(b);
GreatCircle ret = new GreatCircle();
ret.normal = a.CrossProdct(b);
return ret;
}
两个大圆相交于球体上的两点。圆的叉积形成一个通过这些点之一的向量。该矢量的对映体穿过另一个点。
Vector intersection(GreatCircle a, GreatCircle b){
return a.normal.CrossProduct(b.normal);
}
Vector antipode(Vector v){
Vector ret = new Vector();
ret.x = -v.x;
ret.y = -v.y;
ret.z = -v.z;
return ret;
}
大圆线段可以用通过线段起点和终点的向量表示。
class GreatCircleSegment{
Vector start;
Vector end;
Vector getNormal(){return start.CrossProduct(end);}
GreatCircle getWhole(){return new GreatCircle(this.getNormal());}
};
GreatCircleSegment segmentFromCoordinates(Coordinate a, Coordinate b){
GreatCircleSegment ret = new GreatCircleSegment();
ret.start = lineFromCoordinate(a);
ret.end = lineFromCoordinate(b);
return ret;
}
您可以使用 dot product 测量大圆弧段的弧长或任意两个向量之间的角度.
double Vector::DotProduct(Vector other){
return this.x*other.x + this.y*other.y + this.z*other.z;
}
double Vector::Magnitude(){
return math.sqrt(pow(this.x, 2) + pow(this.y, 2) + pow(this.z, 2));
}
//for any two vectors `a` and `b`,
//a.DotProduct(b) = a.magnitude() * b.magnitude() * cos(theta)
//where theta is the angle between them.
double angleBetween(Vector a, Vector b){
return math.arccos(a.DotProduct(b) / (a.Magnitude() * b.Magnitude()));
}
您可以通过以下方式测试大圆线段a
是否与大圆b
相交:
- 找到向量
c
,a
的整个大圆与b
的交点。 - 找到向量
d
,c
的对映体。 - 如果
c
位于a.start
和a.end
之间,或者d
位于之间a.start
和a.end
,然后a
与b
相交。
//returns true if Vector x lies between Vectors a and b.
//note that this function only gives sensical results if the three vectors are coplanar.
boolean liesBetween(Vector x, Vector a, Vector b){
return angleBetween(a,x) + angleBetween(x,b) == angleBetween(a,b);
}
bool GreatCircleSegment::Intersects(GreatCircle b){
Vector c = intersection(this.getWhole(), b);
Vector d = antipode(c);
return liesBetween(c, this.start, this.end) or liesBetween(d, this.start, this.end);
}
两个大圆线段 a
和 b
在以下情况下相交:
a
与b
的整个大圆相交b
与a
的整个大圆相交
bool GreatCircleSegment::Intersects(GreatCircleSegment b){
return this.Intersects(b.getWhole()) and b.Intersects(this.getWhole());
}
现在您可以构建多边形并计算引用线经过多边形的次数。
bool liesWithin(Array<Coordinate> polygon, Coordinate pointNotLyingInsidePolygon, Coordinate vehiclePosition){
GreatCircleSegment referenceLine = segmentFromCoordinates(pointNotLyingInsidePolygon, vehiclePosition);
int intersections = 0;
//iterate through all adjacent polygon vertex pairs
//we iterate i one farther than the size of the array, because we need to test the segment formed by the first and last coordinates in the array
for(int i = 0; i < polygon.size + 1; i++){
int j = (i+1) % polygon.size;
GreatCircleSegment polygonEdge = segmentFromCoordinates(polygon[i], polygon[j]);
if (referenceLine.Intersects(polygonEdge)){
intersections++;
}
}
return intersections % 2 == 1;
}
关于php - 如何检查经度/纬度点是否在坐标范围内?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11510326/