9

次のように、多くのポリゴンとその中にポイントがあるマップがあります。 多角形

ポリゴンのエッジの x 座標と y 座標は、次のようなデータベースに保存されます (たとえば)。

Polygon(Point(11824, 10756), Point(11822, 10618), Point(11912, 10517), Point(12060, 10529), Point(12158, 10604), Point(12133, 10713), Point(12027, 10812), Point(11902, 10902)),
Polygon(Point(11077, 13610), Point(10949, 13642), Point(10828, 13584), Point(10772, 13480), Point(10756, 13353), Point(10849, 13256), Point(10976, 13224), Point(11103, 13294), Point(11171, 13414), Point(11135, 13558)),
Polygon(Point(11051.801757813, 11373.985351563), Point(11165.717773438, 11275.469726563), Point(11281.733398438, 11255.646484375), Point(11381.07421875, 11333.15625), Point(11440.202148438, 11467.706054688), Point(11404.73046875, 11584.534179688), Point(11301.662109375, 11643.852539063), Point(11169.486328125, 11644.079101563), Point(11067.555664063, 11579.676757813), Point(11018.21484375, 11454.750976563)),
Polygon(Point(12145, 13013), Point(12069.065429688, 13014.67578125), Point(12012.672851563, 12953.833984375), Point(11973.942382813, 12910.14453125), Point(11958.610351563, 12853.736328125), Point(11988.58203125, 12780.668945313), Point(12046.806640625, 12735.046875), Point(12117.080078125, 12729.838867188), Point(12185.567382813, 12743.389648438), Point(12225.575195313, 12803.530273438), Point(12255.934570313, 12859.2109375), Point(12263.861328125, 12914.166992188), Point(12221.2578125, 12978.983398438)),

それらは後で描画されます。私はそれにはアクセスできません。この座標にのみアクセスできます。したがって、ポリゴンのエッジの x/y と赤い点の x/y があります。ここで、赤い点がどのポリゴンにあるかを知る必要があります。

次に、私が必要とする最も重要なことはこれです： ポリゴン

赤い点の x 座標と y 座標、およびエッジの xy 座標があります。緑色の点の x 座標と y 座標が必要です (ポリゴンの外側の最も近い場所)。

ルアで必要ですが、どの言語でも自由に答えてください。翻訳できます。

4

3 に答える 3

7

ポイントがどのポリゴンにあるかを知るには、レイ キャスティング アルゴリズムを使用できます。

最も近いエッジを見つけるには、単純なアプローチを使用して各エッジまでの距離を計算し、最小値を取ることができます。エッジとの交点がエッジの外側にあるかどうかを確認することを忘れないでください (これを確認してください)。外側にある場合は、エッジの最も近い端までの距離をとります。

疑似コードを使用して直感をよりよく説明します。

dot(u,v) --> ((u).x * (v).x + (u).y * (v).y)
norm(v)  --> sqrt(dot(v,v))     // norm = length of vector
dist(u,v)--> norm(u-v)          // distance = norm of difference

// Vector contains x and y
// Point contains x and y
// Segment contains P0 and P1 of type Point
// Point  = Point ± Vector
// Vector = Point - Point
// Vector = Scalar * Vector
Point closest_Point_in_Segment_to(Point P, Segment S)
{
     Vector v = S.P1 - S.P0;
     Vector w = P - S.P0;

     double c1 = dot(w,v);
     if ( c1 <= 0 )   // the closest point is outside the segment and nearer to P0
          return S.P0;

     double c2 = dot(v,v);
     if ( c2 <= c1 )  // the closest point is outside the segment and nearer to P1
          return S.P1;

     double b = c1 / c2;
     Point Pb = S.P0 + b * v;
     return Pb;
}

[Point, Segment] get_closest_border_point_to(Point point, Polygon poly) {

    double bestDistance = MAX_DOUBLE;
    Segment bestSegment;
    Point bestPoint;

    foreach s in poly.segments {
        Point closestInS = closest_Point_in_Segment_to(point, s);
        double d = dist(point, closestInS);
        if (d < bestDistance) {
            bestDistance = d;
            bestSegment = s;
            bestPoint = closestInS; 
        }
    }

    return [bestPoint, bestSegment];
}

もちろん、ポイントが入っているポリゴンを取得したら、この疑似コードでうまくいくはずです。

于 2013-09-27T10:16:23.063 に答える