線分の交差の計算には、Bentley-Ottmann アルゴリズムが使用されます。
ただし、すべての線の交点を見つけるのではなく、2 つの線のグループ間の交点を見つけたいと考えています。これは、行グループ内のすべての行についてA、それらの行とグループ内の行との交点を知りたいということですB。
このためにBentley-Ottmann アルゴリズムを拡張できる方法はありますか? 私はすでに既存の Bentley-Ottmann アルゴリズムを ( CGAL のライブラリに) 実装していますが、それを変更するつもりはありません。しかし、私はそれを再利用して拡張する方法を見つけたいと思っています。
編集: 他のアルゴリズム (必ずしも Bentley-Ottmann に基づくとは限りません) は歓迎されます。これらのアルゴリズムが既存のライブラリに既に実装されているとよいでしょう。
内のすべてのライン間の交点をすべて見つけてA+Bから、同じセット内のライン間の交点を削除できます。複雑さをあまり増やしていないため、単純なラッパー関数のみで CGAL のライブラリ関数を変更せずに使用できます。
はい、Bentley-Ottmann アルゴリズムを拡張して、他の方法と同様にこれを行うことができます。
文学では、赤と青の線の間の交点を報告する線に沿って説明したタスク。
これは、BO スイープを最適なアルゴリズムに拡張する論文です。 http://www.cs.unc.edu/~snoeyink/demos/rbseg/jcdcg25.pdf
複雑さに関する@marcogの主張には同意しません。リンクされた論文では、O(n log(n+k)) の最適時間を主張しています。交差点をフィルタリングすると、すべての行で BO スイープを実行する必要があり、((n+k) log n) になります。
複雑なデータ構造を必要としない他の同様のアルゴリズムがあります http://www.cs.swarthmore.edu/~adanner/cs97/s08/pdf/palazzi93counting.pdf
エッジが少なく、エッジ間の交差が少ない場合は、@ marcog の回答のソリューションがうまく機能する可能性があります。(これは CGAL http://doc.cgal.org/latest/Arrangement_on_surface_2/Arrangement_on_surface_2_2consolidated_curve_data_8cpp-example.htmlの例です)。
複雑なポリゴン (GIS データなど) を処理する必要がある場合、または一般的なアルゴリズムが必要な場合は、このクラスのアルゴリズムを使用する価値があります。
2次元の最も効率的な方法ではないかもしれませんが、完全を期すためにこの回答を追加してください。
3D グラフィックスでは、2 つの KD ツリーに共通であり、重なり合うすべてのノードを検出するために使用できます (ジオメトリのブール演算に使用できます)。
作業例 (C コード)。 https://developer.blender.org/diffusion/B/browse/master/source/blender/blenlib/intern/BLI_kdopbvh.c;3b4a8f1cfa7339f3db9ddd4a7974b8cc30d7ff0b $1089
多くの小さなセグメント (手描きの線のパスなど) がある場合、これはかなり効率的です。ただし、長いエッジ(ピックアップ スティックを考えてください)が多数ある場合は、パフォーマンスが低下するため、パフォーマンスを向上させるために BVH ツリーでリーフ ノードを分割することをお勧めします。ただし、その場合は、他の回答で提案されている別の方法を使用することをお勧めします。
Bentley-Ottman が現在の垂直位置で並べられた線分のツリーを保持しているのに対し、グループ A とグループ B に 1 つずつ、2 つのツリーを保持できませんか? 次に、元のアルゴリズムが現在のポイントの上と下の隣人をチェックする場合、上の A 隣人を下の B 隣人に対してチェックし、その逆も同様です。
これは、ウィキペディアの記事をざっと読んだことに基づいています。過去 10 年間、私は幾何学的なコードをあまり書いていません。