1

3 台形と多角形

与えられた 2 つまたは 3 つの台形 (オレンジ)。各台形の少なくとも 1 つの辺が別の台形に隣接し、単純な多角形を形成します。

左上隅から時計回りに、4 つの点のリストとして表される四角形。

[
  {x: 0,  y: 0},
  {x: 50, y: 0}, 
  {x: 75, y: 30},
  {x: 60, y: 30}
]

タスクは、ポイントのリストとして表される単一のポリゴン (緑) を作成することです。

[
  {x: 0,  y: 0},
  {x: 50, y: 0}, 
  {x: 75, y: 30},
  {x: 60, y: 30},
  {x: 60, y: 170}
  …
  {x: 0, y: 0}
]
4

2 に答える 2

1

台形上のすべての点が時計回りの順序になっているので、代わりに有向辺または「円弧」のセット (ラップアラウンドのある連続する点間の矢印) と考えてみましょう。

除外したいアークは、まさにポリゴンの内部アークであり、すべてペアになっています。つまり、[a,b,c,d] が 1 つの台形で、[d,c,x,y] が別の台形である場合、私のポリゴンは [a,b,c,x,y,d] である必要があります。円弧 (c,d) と (d,c) のペア。

(ハッシュまたは隣接行列を介して) 線形時間で除外するアークを見つけることができます。次に、残りの円弧を順番につなぎ合わせるだけで、ポリゴンを見つけることができます。

ポイントをその近傍にマッピングしているとします。上記の例では、次のようになります: a->(b), b->(c), c->(d,x), d->(a,c), x->(y), y ->(d)

1 つの不良アーク ペア (両方向の c から d) を除外すると、次のようになります。 a->(b)、b->(c)、c->(x)、d->(a)、x-> (y)、y->(d)、必要に応じて。

于 2013-11-09T14:38:10.250 に答える