通常の式を使用して 2 つの 2D セグメント間の交差を計算する場合、つまりここで、結果を整数に丸めると、非対称の結果が得られます。
つまり、丸め誤差が原因で、intersection(A,B)!=intersection(B,A).
最善の解決策は、フロートを使用し続け、結果を特定の精度まで比較することです。ただし、交差を計算した後、結果を整数に丸める必要があり、浮動小数点数で作業を続けることができません。
これまでの私の最善の解決策は、平面内のセグメントに完全な順序を使用し、intersection常に小さいセグメントと大きいセグメントを比較する必要があることでした。
より良い方法はありますか？何か不足していますか？
セグメントの長さを比較したくありません。
また、 と比較intersection(A',B')すると、の座標が の と表現的に同一でintersection(B",A")あることが理解されると仮定します (との同上)、そうでなければ解決策はありません。A'A"B'B"
ここで、 、、およびは[PQ]平面上の点です。セグメントの交点が必要です。[RS]PQRS
[PQ] [RS][QP] [RS][PQ] [SR][QP] [SR][RS] [PQ][SR] [PQ][RS] [QP][SR] [QP]...常に同じ座標ペアを返します。
最初に各セグメントのエンドポイント、次にセグメント自体 (各セグメントの最小エンドポイントに基づく) の順序付けが、再現可能な結果を保証する唯一のソリューションです。P<Q順序付け自体はiffのように計算上は自明ですが、何百万ものセグメントを処理する場合P.x < Q.x || P.x == Q.x && P.y < Q.y、分岐は高価になる可能性があります (順序付けを生成するために、可能な場合は SIMD を使用してセグメント座標をその場で交換する方法を参照してください)。