algorithm - 行のコレクションからチェーンを見つけるアルゴリズム

Question

共通の終点が 1 つある場合、2 つのラインは同じチェーンに属します。たとえば、(0, 0)-(Rnd, Rnd) として定義された 10 行は、すべて共通の 1 つのエンドポイントを持っているため、1 つの有効なチェーンです。

私が開発したアルゴリズムは、幸運な場合には非常に高速で、他の場合には非常に遅くなります。10,000 行の場合、数秒から数時間かかることがあります。

スピードアップするためのアドバイスを求めています。

チェーンは、次のようなサイクルによって作成されます。

For Each Line in Lines
  If Chain.HasPointInCommonWith(Line) Then
    Chain.Add Line
    Lines.Remove Line
  End If
Next Line

テストを何度も実行しないようにするために、XMin に関するすべての行を並べ替え、曲線を探すループに次のテストを追加しました。

If Line.XMin > Chain.XMax Then Exit For

このテストは、線が多数の長方形を表しており、1 つの長方形が右に並んでいる場合にはうまく機能しますが、それらが多数の長方形を上下に並べている場合には役に立ちません。