グラフ理論 (Google it) のユークリッド二部マッチング (EBM) 問題は、すべてのエッジの長さの合計を最小化するために、青と赤のポイントを一致させようとします。これは、ハンガリーのアルゴリズムを使用して解決できます。これが交差のないグラフであることを確認するには、「悪い」グラフと「良い」グラフを検討してください。エッジの長さの合計は、「良い」画像では常に小さくなります。(こちらはもう少し詳しい議論です。)
詳細を提供する別のSOの回答を次に示します。
これが私が有望だと思うアプローチです。赤と青の点 (R1,B1)、(R2,B2)、.. (Rn,Bn) のペアを作成します。次に、リストを調べて、それぞれの (Rj,Bj) に対して直線 Rj--Bj を描きます。この線が他の線 Ri--Bi と交差する場合は、これらの線を Ri--Bj と Rj-Bi に置き換えて「交差を解除」します (つまり、「悪い」図を「良い」図に変更します)。
これらの新しい線が他の既存の線と交差するかどうかを確認する必要があります。その場合は、交差する線がなくなるまで、同じ「スワップ」と「交差チェック」を繰り返し実行します。次に、(Rj,Bj) の後でペアに参加し、完了するまで続けます。
私の他の回答で述べたように、合計エッジ長を最小化する赤と青のポイントのペアリングも交差しません。この回答で与えられたアプローチでは、エッジを「クロス解除」するたびに、すべてのエッジの長さの合計を減らすことに注意してください。アルゴリズムは、エッジの長さの合計が最小のペアリング構成に到達しない可能性が最も高いです。ただし、スワップごとに合計エッジ長が減少するという事実は、アルゴリズムが常に終了することを意味します (つまり、エッジ スワップの繰り返しシーケンスには入りません)。
それを証明する方法はわかりませんが、空間を 2 つの異なる半分に分割する線を定義する点 (ax1,ay1)->(bx1,by1) のペアが少なくとも 1 つは常に存在しなければならないというのは正しいと思います。それぞれの半分には、対応していない a 点と b 点の数が同じです。これに当てはまらないポイントのレイアウトを思いつくことはできません。
この分割が検出されると、2 つのポイントが接続済みとしてマークされ、両側の 2 つの半スペースが再度処理されます。これは、両方の半スペースにゼロ点が含まれるまで繰り返されます。
サブディバイディング ペアを見つけることは簡単ではありませんが、徹底的な検索によって行うことができます。誰かが計算量の少ない方法を考え出すことを願っていますが、これはうまくいくはずです。
ここではすでに間接的に回答されています: 2 つの線分が交差する場所をどのように検出しますか?
接続されたポイントの任意の組み合わせをテストし、それらが交差するかどうかを確認するのは簡単です!
