如何检查经度/纬度点是否在坐标范围内？ [英] How do I check if a longitude/latitude point is within a range of coordinates?
问题描述
我有许多经度和纬度坐标组成了一个多边形区域。我也有一个经纬度坐标来定义车辆的位置。如何检查车辆是否位于多边形区域内？
这基本上是指出球体上的多边形问题。您可以修改光线投射算法，以便使用大圆弧而不是线段。
- 对于每对相邻坐标绘制一个大圆圈。
- 选择一个不在多边形区域内的参考点。
- 绘制一个大圆从参考点开始到车辆点结束。计算该段跨过多边形的一段的次数。如果总次数为奇数，则车辆在多边形内。如果偶数，车辆在多边形之外。
另外，如果坐标和车辆足够靠近在一起，并且不在附近极点或国际日期线，您可以假装地球是平坦的，并使用经度和纬度作为简单的x和y坐标。这样，您可以使用简单线段的光线投射算法。如果你对非欧几里得几何体不舒服，这是更可取的，但是由于弧会变形，所以你的多边形边界会产生一些扭曲。
编辑：更多关于球体上的几何形状。
一个大圆圈可以通过垂直于圆圈所在平面的矢量来标识（AKA， normal vector ）
class Vector {
double x;
double y;
double z;
};
class GreatCircle {
Vector normal;
}
任何两个经度/纬度坐标不是 antipodal 正好分享了一个大圈子。要找到这个大圆，将坐标转换为穿过地球中心的线。这两条线的跨产品是坐标大圆的法线向量。
// //任意将北极定义为（0,1,0）和（0'N，0'E）为（1， 0,0）
// lattidues应该在[-90,90]和经度在[-180,180]
//你必须将南方的晶格和东经转换成它们的负北和西方同行。
Vector lineFromCoordinate（Coordinate c）{
Vector ret = new Vector（）;
//给定：
// tan（lat）== y / x
// tan（long）== z / x
// Vector的大小为1，所以sqrt（x ^ 2 + y ^ 2 + z ^ 2）== 1
//重新排列一些符号，先解决x ...
ret.x = 1.0 / math.sqrt（tan （c.lattitude）^ 2 + tan（c.longitude）^ 2 + 1）;
//然后是y和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）;
向量b = lineFromCoordinate（b）;
GreatCircle ret = new GreatCircle（）;
ret.normal = a.CrossProdct（b）;
return ret;
}
两个大圆相交于球体上的两个点。圆的叉积形成一个通过这些点之一的向量。
Vector交叉点（GreatCircle a，GreatCircle b）{
return a.normal.CrossProduct（b.normal）;
}
矢量对位（矢量v）{
矢量ret =新矢量（）;
ret.x = -v.x;
ret.y = -v.y;
ret.z = -v.z;
return ret;
}
一个大圆段可以通过该段的开始和
class GreatCircleSegment {
Vector start;
向量结束;
Vector getNormal（）{return start.CrossProduct（end）;}
GreatCircle getWhole（）{return new GreatCircle（this.getNormal（））;}
};
GreatCircleSegment segmentFromCoordinates（坐标a，坐标b）{
GreatCircleSegment ret = new GreatCircleSegment（）;
ret.start = lineFromCoordinate（a）;
ret.end = lineFromCoordinate（b）;
return ret;
}
您可以测量大圆段的圆弧大小，或者任何两个矢量，使用 dot产品。
double Vector :: DotProduct（Vector other）{
return this.x * other.x + this.y * other.y + this.z * other。 Z者除外;
$ b $ double Vector :: Magnitude（）{
return math.sqrt（pow（this.x，2）+ pow（this.y，2）+ pow（ this.z，2））;
}
//对于任何两个向量`a`和`b`，
//a.DotProduct（b）= a.magnitude（）* b.magnitude（ ）* cos（theta）
//其中theta是它们之间的角度。
double angleBetween（Vector a，Vector b）{
return math.arccos（a.DotProduct（b）/（a.Magnitude（）* b.Magnitude（）））;
}
您可以测试一个大圆段 a 通过：
- 找到vector
c，交点a的整个大圆圈和b找到d的向量，c。 如果 - c> a.end 或
d位于a.start和<$ c之间$ c> a.end ，然后a与b相交。 -
a与b的整个大圈相交
b与a的整个大圈相交
c 位于 a.start 和<$ c $之间，$ b $ pre $
//返回true if矢量x位于矢量a和b之间。
//注意，如果三个向量共面，这个函数只会给出合理的结果。
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）;
向量d =对映体（c）;
return liesBetween（c，this.start，this.end）或liesBetween（d，this.start，this.end）;
}
两个大圆圈 a 和 b 在以下情况相交：
p>
bool GreatCircleSegment :: Intersects（GreatCircleSegment b）{
返回this.Intersects（b.getWhole（））和b。相交（this.getWhole（））;
}
现在您可以构造多边形并计算参考线经过的次数
bool liesWithin（Array< Coordinate>多边形，坐标pointNotLyingInsidePolygon，坐标vehiclePosition）{
GreatCircleSegment referenceLine = segmentFromCoordinates （pointNotLyingInsidePolygon，vehiclePosition）;
int intersections = 0;
//遍历所有相邻的多边形顶点对
//我们迭代比数组大小更远的一个，因为我们需要测试数组$ b中第一个和最后一个坐标形成的段$ b 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））{
intersection ++;
}
}
返回交点％2 == 1;
}
I have a number of longitude and latitude coordinates that make up a polygonal zone. I also have a longitude and latitude coordinate to define the position of a vehicle. How do I check that the vehicle is located within the polygonal zone?
This is essentially the Point in polygon problem on a sphere. You can modify the ray casting algorithm so that it uses arcs of great circles instead of line segments.
- for each pair of adjacent coordinates that make up your polygon, draw a great circle segment between them.
- Choose a reference point that is not inside the polygonal zone.
- draw a great circle segment that begins at the reference point and ends at the vehicle point. Count how many times this segment crosses over a segment of your polygon. If the total number of times is odd, the vehicle is within the polygon. If even, the vehicle is outside of the polygon.
Alternatively, if the coordinates and vehicle are sufficiently close together, and not anywhere near the poles or international date line, you can pretend the earth is flat and use longitude and lattitude as simple x and y coordinates. That way, you can use the ray casting algorithm with simple line segments. This is preferable if you are not comfortable with non-euclidean geometry, but you'll have some distortion around the borders of your polygons since the arcs will be distorted.
EDIT: A little more on geometry on a sphere.
A great circle can be identified by the vector that lies perpendicular to the plane the circle lies on (AKA, the normal vector)
class Vector{
double x;
double y;
double z;
};
class GreatCircle{
Vector normal;
}
Any two lattitude/longitude coordinates that aren't antipodal share exactly one great circle. To find this great circle, convert the coordinates to lines that pass through the center of the earth. The cross product of those two lines is the normal vector of the coordinate's great circle.
//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;
}
Two great circles intersect at two points on the sphere. The cross product of the circles forms a vector that passes through one of those points. The antipode of that vector passes through the other point.
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;
}
A great circle segment can be represented by the vectors passing through the segment's start and end points.
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;
}
You can measure the arc size of a great circle segment, or the angle between any two vectors, using the 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()));
}
You can test if a great circle segment a intersects a great circle b by:
- find the vector
c, the intersection ofa's whole great circle andb. - find the vector
d, the antipode ofc. - if
clies betweena.startanda.end, ordlies betweena.startanda.end, thenaintersects withb.
//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);
}
Two great circle segments a and b intersect if:
aintersects withb's whole great circlebintersects witha's whole great circle
bool GreatCircleSegment::Intersects(GreatCircleSegment b){
return this.Intersects(b.getWhole()) and b.Intersects(this.getWhole());
}
Now you can construct your polygon and count how many times your reference line passes over it.
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;
}
这篇关于如何检查经度/纬度点是否在坐标范围内？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
