• ベストアンサー

多角形の自己交差を判定するには?

3D空間にある平面多角形で、頂点が1000個ぐらいの多角形を想定しています。 これの多角形の辺同士で交点の有無により、自己交差を判定すると時間がかかってしまいます。 もっと、効率の良い方法はありますか?

質問者が選んだベストアンサー

  • ベストアンサー
  • stomachman
  • ベストアンサー率57% (1014/1775)
回答No.2

ANo.1のコメントについて http://softsurfer.com/Archive/algorithm_0108/algorithm_0108.htm 浅野「計算幾何学」(朝倉書店)にも載ってます。

Schwarz20
質問者

お礼

再度、ご回答、有難うございます 近くの図書館に行ったら、「計算幾何学」(朝倉書店)は、無かったのですが、同じ著者の「計算幾何 理論の基礎から実装まで」(共立出版)が見つかりました。 有難うございました。

その他の回答 (1)

  • stomachman
  • ベストアンサー率57% (1014/1775)
回答No.1

n本の線分が交点を持つかどうかを判定する、というのは計算幾何学(computational geometry)の基本的な技法で、Shamos-Hoeyの算法を使うとO(n log n)の時間で答が出せる。線分同士の全部の組み合わせを調べているとO(n^2)の手間が掛かるのに比べ、かなり速くなります。

Schwarz20
質問者

お礼

回答、有難うございます。 出来れば、参考になるHPもしくは書籍をお教えいただけると助かります

関連するQ&A