2

セグメント S とポリゴン P が与えられた場合、ポリゴン P と交差する S のサブセグメントの全長を返す高速なアルゴリズムはありますか?

注: P は、閉じた LineString (つまり、最初と最後の点が等しい点の配列) によって定義されます。P には「穴」はありませんが、凹型および/または自己交差する可能性があります。

注: 最終的な目標は、交差するすべてのサブセグメントの合計の長さです。これらすべての明示的な配列を取得せずにこれをより高速に実行できれば、なおさらです。

ボーナス ポイント: 上記のアルゴリズムの Java 実装。結果として得られるソリューションが高速である限り、JTS のようなライブラリを使用しても問題ありません。

JTS を使用した単純なソリューションは既に存在しますが、自己交差ポリゴンをサポートしておらず、最速ではないと思います。このソリューションでは、Polygon オブジェクト (P の場合)、2 ポイントの LineString オブジェクト (S の場合) を作成し、結果の交点の長さを取得します。

これを行うコードは次のとおりです。

    GeometryFactory fact = new GeometryFactory();
    WKTReader wktRdr = new WKTReader(fact);

    String wktP = "POLYGON((40 100, 40 20, 120 20, 120 100, 60 40, 40 100))";
    String wktS = "LINESTRING(20 60, 160 60)";
    Geometry pl = wktRdr.read(wktP);
    Geometry ls = wktRdr.read(wktS);
    Geometry in = pl.intersection(ls);
    System.out.println("P = " + pl);
    System.out.println("S = " + ls);
    System.out.println("P intersection S = " + in);
    System.out.println("S length = " + ls.getLength());
    System.out.println("P intersection S length = " + in.getLength());

編集: 自己交差ポリゴンに関する考慮事項: 解決策は、最速ではないかもしれませんが、自己交差ポリゴンを複数の非自己交差ポリゴンに分割して前処理することを含む可能性があります。

この問題に関するいくつかの説明と疑似コードは次のとおりです。 自己交差したPath2Dを複数の自己交差しないパスに分割するアルゴリズム?

4

1 に答える 1

2

O(n*log n) で自己交差しないポリゴンの交差長を求めます。

擬似コード:

function intersecting_segment_length(set P, segment S):
  let starting_point = the bottom-most, left-most point in P.
  let E1, E2 = the edges of starting_point

  let intersections = new array.
  do:
     while E1 != E2 and E1 does not cross S:
        E1++ //move E1 "clockwise" around P
     while E2 != E1 and E2 does not cross S:
        E2-- //move E2 "counterclockwise" around P
     if E1 != E2:
        p1 = the intersection of E1 and S
        p2 = the intersection of E2 and S
        intersections.add(new line segment from p1 and p2)
  until E1 == E2.

  return sweepline(intersections)

スイープラインの擬似コード:

function sweepline(array segments):
  let points = start and end points of all segments
  sort points as they intersect S

  let last_point = points.first()
  let num_segments = 0 //num segments intersected by sweepline
  let length = 0

  for each point p in points - last_point:
     if p is the leading point in p.owning_segment:
        num_segments++
     else: //trailing point
        num_segments--
        if num_segments % 2 == 0: //I think
           length += distance between p and last_point
     last_point = p

  return length

複雑：

  • P: 内のエッジをウォーキングしますO(n)。ここで、nは P 内のエッジ/頂点の数です。
  • 交点の並べ替え: O(m*log m)、ここmで、 は P と S の交点の数です。
  • スイープラインを使用して全長を求める: O(m).
  • 残念ながら、S と交差する「櫛形の多角形」を構成できるO(n)ため、全体の複雑さはO(n*log n)最悪のケースになります。

ノート：

  • P の自己交差を特定できる場合 (たとえば、P の周りを歩いているとき)、それらのイベントをスイープラインに注入し、それに応じてアルゴリズムを変更できます。結果はおそらくで実行できO(n*log n)ます。
  • スイープラインの実装例 (疑似コードを除く) については、この回答を参照してください。
于 2012-08-30T14:09:33.327 に答える