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

３Ｄ空間にある平面多角形で、頂点が１０００個ぐらいの多角形を想定しています。
これの多角形の辺同士で交点の有無により、自己交差を判定すると時間がかかってしまいます。

もっと、効率の良い方法はありますか？

No.2 ベストアンサー 回答者： stomachman 回答日時： 2010/02/21 07:30

ANo.1のコメントについて

http://softsurfer.com/Archive/algorithm_0108/alg …
浅野「計算幾何学」(朝倉書店)にも載ってます。

この回答へのお礼

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

お礼日時：2010/02/21 17:44

No.1 回答者： stomachman 回答日時： 2010/02/17 12:26

n本の線分が交点を持つかどうかを判定する、というのは計算幾何学(computational geometry)の基本的な技法で、Shamos-Hoeyの算法を使うとO(n log n)の時間で答が出せる。

線分同士の全部の組み合わせを調べているとO(n^2)の手間が掛かるのに比べ、かなり速くなります。

この回答へのお礼

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

お礼日時：2010/02/20 09:23