5

多角形のゾーンを構成する経度と緯度の座標がいくつかあります。また、車両の位置を定義するための経度と緯度の座標もあります。車両がポリゴンゾーン内にあることを確認するにはどうすればよいですか？

4

1 に答える 1

8

これは本質的に、球上のポリゴンの点の問題です。線分ではなく大円の円弧を使用するように、レイキャスティングアルゴリズムを変更できます。

  1. ポリゴンを構成する隣接する座標のペアごとに、それらの間に大円セグメントを描画します。
  2. ポリゴンゾーンの内側にない基準点を選択してください。
  3. 基準点で始まり、車両点で終わる大円セグメントを描画します。このセグメントがポリゴンのセグメントと交差する回数を数えます。合計回数が奇数の場合、車両はポリゴン内にあります。偶数の場合、車両はポリゴンの外側にあります。

または、座標とビークルが十分に接近していて、極や日付変更線の近くにない場合は、地球が平らであると偽って、経度と緯度を単純なx座標とy座標として使用できます。このようにして、単純な線分でレイキャスティングアルゴリズムを使用できます。これは、非ユークリッドジオメトリに慣れていない場合に適していますが、円弧が歪むため、ポリゴンの境界の周りにいくらかの歪みがあります。

編集：球上のジオメトリについてもう少し。

大円は、円が置かれている平面に垂直に置かれているベクトル（AKA、法線ベクトル）によって識別できます。

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

class GreatCircle{
    Vector normal;
}

対蹠ではない2つの緯度/経度座標は、正確に1つの大円を共有します。この大円を見つけるには、座標を地球の中心を通る線に変換します。これらの2つの線の外積は、座標の大円の法線ベクトルです。

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

2つの大円が球上の2点で交差します。円の外積は、それらの点の1つを通過するベクトルを形成します。そのベクトルの対蹠地は他の点を通過します。

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

内積を使用して、大円セグメントの円弧サイズ、または任意の2つのベクトル間の角度を測定できます。

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との共通部分を見つけます。ab
  • dの対蹠地であるベクトルを見つけますc。
  • との間にある場合、またはとcの間にa.startある場合は、と交差します。a.endda.starta.endab

 

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

次の場合、 2つの大円セグメントaとb交差します。

  • abの大円全体と交差します
  • baの大円全体と交差します

 

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;
}
于 2012-07-16T18:51:52.000 に答える