如何检查经纬度点是否在一组坐标范围内？

Question

如何检查经纬度点是否在一组坐标范围内？

phpmathgeolocationcoordinateslatitude-longitude

5

我有一些经纬度坐标，它们组成了一个多边形区域。我还有一个经纬度坐标来定义车辆的位置。如何检查车辆是否位于多边形区域内？

- Cameron

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Kevin · Accepted Answer

这本质上是球面上的点在多边形内问题。您可以修改射线投射算法，以便使用大圆弧而不是线段。

对于构成多边形的每一对相邻坐标，绘制它们之间的大圆弧段。
选择一个不在多边形区域内的参考点。
绘制一个从参考点开始并在车辆点结束的大圆弧段。计算此段交叉多少次您的多边形的一个段。如果总次数为奇数，则车辆在多边形内。如果为偶数，则车辆在多边形外。

或者，如果坐标和车辆足够接近，并且不在极地或国际日期变更线附近，您可以假装地球是平的，并将经度和纬度用作简单的x和y坐标。这样，您就可以使用带有简单线段的射线投射算法。如果您不熟悉非欧几何学，则此方法更可取，但是您的多边形边界周围会产生某些畸变，因为弧会被扭曲。

编辑：关于球面几何的更多信息。

一条大圆可以通过垂直于其所在平面的向量（也称为法向量）来确定。

class Vector{
    double x;
    double y;
    double z;
};

class GreatCircle{
    Vector normal;
}

任何两个不是对踵点的纬度/经度坐标只共享一个大圆。要找到这个大圆，将坐标转换为通过地球中心的直线。这两条直线的叉积是该坐标大圆的法向量。

//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;
}

你可以使用点积来测量大圆段的弧长或任意两个向量之间的角度。

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;
}