交差Nラインセグメント（整数グリッド上）

Question

Iはほとんど与えられた線分のすべての交点を求める古典CSの問題のように見える問題があります。私は、その交点における全てのセグメント
2.得られた分割セグメントが整数座標を有していなければならない分割する必要
1：

わずかな修正があるという事実です。

すべての交差点を見つけるために標準的なスイープアルゴリズムを適用するだけで、これらの点の座標を整数にキャストするのではなく、交差点が整数グリッドに移動することによって新しい交差点が得られることがあります。

私はステップ、私は新たな交差点を見つけていない状態に達するの限られた数で、（私はそれを証明することはできません）、おそらく繰り返し、このアルゴリズムを適用すると、ことがあります。 しかし、よりシンプルで洗練されたソリューションが必要であると確信しています。

私はこのようなアルゴリズムに関する論文を検索しようとしましたが、何とかまさにこの問題に対処するだろうものを見つけることができませんでした。

あなたは、このようなパプ、または（例えばブーストポリゴンライブラリなど）のグラフィックスライブラリで使用されるアルゴリズムの記述に私を指す伝えることはできますか？

ありがとうございます。

Answer 1

これは、線分交差問題に興味深いバリエーションです。これらのセグメントの交点の座標を見つけるという元の問題は、線掃引アルゴリズムを使用して解決することができます。

Hereは、上記の問題のラインスウィープ技術の実装について話している深い記事です。これにより、交差点はO（n * logn）時間で見つけることができます。

さて、整数座標を見つけるために、あなたは交差点をキャストすることができます。しかし、ここではキャスティングの方向について確認する必要があります（これは後にコンバージェンスに役立ちます）。

Cの交点がABの交点にある場合は、ACとCBに分割します。 ACの場合は、をAの方向に、CBの場合はBの方向にキャストします。 （方向によって、私は線分方向に沿ったものではなく、別の終点を含む半平面に沿っていることを意味します）。これにより、交差点ごとに線分の長さが減少します。

PROOF： Mは、線分の最大長であると考えてください。交差点がその上にあるたびに、新しい線分の長さが少なくとも1単位減少します。だから、繰り返しの数はこのように、あなたのアルゴリズムの全体的な反復がM.

複雑= O（M * N * LOGN）