wpf - ポリライン間の交点を見つけるアルゴリズム

Question

Bentley-Ottmann アルゴリズムは、一連の直線の交点を見つけるために機能します。しかし、私はたくさんのポリラインを持っています:

一連のポリラインの交点を見つける方法はありますか?

私は考えていますが、それまでの間、誰かがいくつかの指針やアイデアを与えることができれば、それは役に立ちます. 読んでくれてありがとう。ところで、私は WPF/C# を使用しており、すべてのポリラインは PathGeometry です。

画像のソース: http://www.sitepen.com/blog/wp-content/uploads/2007/07/gfx-curve-1.png

Answer 1

スイープ ライン アルゴリズムには優れた理論がありますが、確実に実装するのは困難です。垂直セグメントを処理する必要があり、3 つ以上の線分が 1 つの点で交差する (または共通の線分を共有する) 場合もあります。

R ツリーを使用してポリラインの線分の境界ボックスを格納し、R ツリーを使用して交差する可能性のある要素を見つけます。交差をテストする必要があるのはこれらだけです。利点は、ポリラインごとに個別の R ツリーを使用できるため、必要に応じて自己交差の検出を回避できることです。

信頼できる結果を得るには、CGAL の正確な述語カーネルを使用することを検討してください。