0

直線（無限）の間のすべての交点を見つけたいと思います。線分のセットで機能する Bentley-Ottmann アルゴリズムを変更しようとしていますが、無限の直線を適切に表現する方法がわかりません。最初のアイデアは、各線の開始と終了をシミュレートする境界点を決定することでしたが、それは間違った解決策だと思います (「無限」の点を見つける方法は?)。次のアイデアは、方程式を使用して直線を表すことですが、Bentley-Ottmann アルゴリズムを使用できるかどうかはわかりません (線を順序付けてスケジュールにイベントを追加する方法は?)。さらに、(一連の方程式を解きながら) 2 つの線の交点を検出するために、おそらく除算を使用する必要があります。避けたいと思います。

アドバイスをいただけますか？

どうもありがとう

4

2 に答える 2

0

これを 2 次元のユークリッド空間で行っていると仮定すると、問題が過大になります。高校生は、線は方程式で表すことができると教えてくれます。

y = m*x + b

ただし、垂直線を表すことはできません。より一般的な方程式を使用できます ( MathWorldを参照)。

a*x + b*y = c

2 次元のユークリッド空間では、2 つの行は次のいずれかになります。

  • 共通点が 1 つあります。また
  • 共通点はありません。それらは互いに平行です。また
  • 無限の数の共通点があります。それらは同じ線です。

最初の 2 つのケースは、方程式を解きます。3 番目のケースは、次の場合に当てはまります。

a1/a2 == b1/b2

a2 = 0(もちろん、またはのケースを処理する必要がありますb2 = 0)

于 2015-01-02T12:55:16.907 に答える
0

ベントレー オットマンを忘れてください。賢いのは、あなたが持っていない線分を扱うことです。

線が無限の場合、非平行線のすべてのペアには、交点が 1 つだけあります。したがって、{L1, L2, ... Ln} がすべての行の集合である場合、アルゴリズムは次のようになります。

for Li, i = 1, 2, ... n-1
  for Lj, j = i+1, ... n
    if Li parallel to Lj, output <i, j, PARALLEL> 
    else output <i, j, intersection(Li, Lj)>

便利な場合は、一致する平行線を微調整するための別のチェックを含めることができます。

任意の行を格納する最も堅牢な方法は、(既に述べたように) 係数トリプルです。

<A, B, C>

Ax + By + C = 0 となります。A^2 + B^2 = 1 となるように正規化するのは便利で良い習慣です。ここで [A,B] は線に垂直な単位です。いくつかのベクトル計算を使用すると、2 つの線 g と h の交点 P が単純な外積によって与えられることが非常に簡単にわかります。

P = [x/w, y/w], where [x,y,w] = [Ag, Bg, Cg] X [Ah, Bh, Ch]

平行線 (一致を含む) の場合は w=0 になるため、除算は期待どおりに失敗することに注意してください。w上記の並列ケースを検出するために、非常に小さな絶対値を使用できます。これが [A, B] を正規化する理由の 1 つです。これにより、このテストはスケールに依存しなくなります。

于 2015-01-04T17:26:14.833 に答える