math - 2 つの曲線の交点

Question

2 つの曲線の交点を取得する必要があります。私が直面している問題は、次のように述べることができます。

直線で結ばれた N1 点と N2 点で定義される 2 つの曲線 C1 と C2 が与えられた場合、C1 と C2 のすべての交点を取得します。両方の曲線は交差しません。

いくつかのアプローチを試しましたが、今のところうまくいくものはありません。推測はありますか？

Answer 1

最も簡単な方法は、各曲線から 1 つずつ、セグメントのすべてのペアをテストすることです。それが遅すぎる場合は、ストリップ ツリーを試してください。以下の論文は、著者の Web サイトにあります。

バラード、DH (1981)、ストリップ ツリー: 曲線の階層表現、ACM のコミュニケーション、v.24 n.5,310-321

Answer 2

曲線は線分で構成されているため、空間ツリー (例: quadtree ) を使用して、互いに近接している線分のみをチェックすることをお勧めします。これにより、非常に近い交差点の数が少ないと仮定して、アルゴリズムの複雑さがO(N1 N2)からO(N log N)(where ) に軽減されます。N = N1 + N2

それ以外にも、このように交差点を見つけることができます。