質問: 多角形の自己交差を判定するには? 3d空間にある平面多角形で、頂点が1000個ぐらいの多角形を想定しています。 これの多角形の辺同士で交点の有無により、自己交差を判定すると時間がかかってしまいます。 もっと、効率の良い方法はありますか?
回答: n本の線分が交点を持つかどうかを判定する、というのは計算幾何学(computational geometry)の基本的な技法で、shamos-hoeyの算法を使うとo(n log n)の時間で答が出せる。線分同士の全部の組み合わせを調べているとo(n^2)の手間が掛かるのに比べ、かなり速くなります。