同一直線上の辺を持つポリゴンからポリゴンを抽出する

同一直線上の辺を含むポリゴンから簡単なポリゴンを抽出するにはどうすればよいですか？以下の非常に単純なケースでは、エッジ2-3と6-0は同一直線上にあります。同一直線上の辺を持つポリゴンからポリゴンを抽出する

すべてのエッジの共線性を1つおきに比較することはできますが、これは遅いO（n^2）アプローチです。これは、0,1,2,3,4,5,6と分けています。より速い方法がありますか？

alt text

2011-01-10 Morrowless

外接円を探します。境界円と各辺がある線との間の上/右の交わりを計算する。これはO（n）です。各エッジをその角度のタプルと境界円との交差の角度位置でソートします。これはO（nlogn）であり、ソートされたリストで共線のエッジをグループ化します。

平行でも非線形でもないエッジがたくさんある場合は、境界円のものをスキップして角度で並べ替えることができます。平行でない非線形の角度がたくさんある場合は、単に角度を使っても「うまくいく」というだけで、効率をほとんど向上させることはできません。

出典

2011-01-10 07:14:06

同様のことは、各行を勾配交差型に変換するだけです。どちらの方法でも、ソートの代わりにハッシュセットを使用することができます。 –

これを理解するのが難しいです。境界線を描こうと思ったら、どの角度を見ますか？ – Morrowless

@Chrisええ、私の最初の考えは、勾配迎撃のフォームを使用することでしたが、特殊なケースの垂直エッジが必要です。境界円のことはそれを避ける試みでした。ハッシュは、不正確さに対処することを難しくします。並べ替えを行うと、実際に類似しているものが近くに配置されるので、小さな違いに対処する方法を選択できます。あなたは小さな違いを "ハッシュアウェイ"しようとすることができますが、ハッシュ境界の近くで問題に遭遇します。あなたが本当にハッシュしたいのであれば、重複するハッシュバケットを持つことができ、各エッジを複数のバケットに置くことができます。 –

1-2と6-0の交差点を見つけることができますか？そうであれば、エッジと頂点のグラフを生成できます。そして、重なり合わないすべてのポリゴンを見つけることは簡単です。

出典

2011-12-08 15:07:02

同一直線上の辺を持つポリゴンからポリゴンを抽出する

答えて

関連する問題