Bentley-Ottmann アルゴリズムを使用して、一連の線分のすべての交点をn log n時間内にスキャンできます。しかし、可変精度でこれを行うことができるバージョンはありますか? つまり、線が特定の距離よりも近づくと、線が交差すると見なされる場所はどこですか?
2 に答える
1
2つのセグメントが交差しない場合、それらの間の最小距離は少なくとも1つのセグメントの終点にあります。そのため、あなたの場合、セグメントのペアが交差するかどうか、またはあるセグメントの終点が他のセグメントの近くにあるかどうかをテストするだけで十分です。
最初のテストはBentley-Ottmannアルゴリズムの標準であり、2番目の部分はスイープラインのセグメントの追加と削除で実行できます。セグメントがSL（左端）に追加されると、左端に近いSL上のセグメントと、SLから左への特定の距離で終了したセグメントをテストするのに十分です。セグメントがSLから削除された場合も同様です。
対称性があるため、片側だけをテストするのに十分だと思います。たとえば、SLにセグメントを追加します。
エンドポイントがソートされているため、この検索は高速である必要があります。セグメントが許容誤差に関して密でないという保証がある場合、この変更はn log n元のアルゴリズムの実行時間を変更しません。
于 2012-09-19T09:00:24.480 に答える
1
2D の線分について話していると仮定します。
私の知る限り、それについて特別なことは何もありません。クラス/オブジェクトの機能を調整するだけです。「実際の」交差点を示す (または他の) 値を返す代わりに、2 つのセグメント間の最小距離が定義済みのしきい値を下回っている場合に戻り、交差点の定義を示します。アルゴリズムに変更はありません。intersects(...)LineSegmentbooleantrue
1参照:
于 2012-09-18T08:15:22.883 に答える