問題タブ [line-intersection]

私は2つの3次ベジエ曲線を持っています、

曲線 1:- 1 番目のアンカー ポイント (a1x、a1y)、1 番目のコントロール ポイント (c1x、c1y)、2 番目のコントロール ポイント (c2x、c2y)、2 番目のアンカー ポイント (a2x、a2y)

曲線 2:- 1 番目のアンカー ポイント (a3x、a3y)、1 番目のコントロール ポイント (c2x、c3y)、2 番目のコントロール ポイント (c4x、c4y)、2 番目のアンカー ポイント (a4x、a4y)

ここで、これら 2 つのベジエ曲線の交点を見つけたいと思います。

どうやってするの？アルゴリズムに関する参考文献はどれでも役に立ちます。

DM Mountによると、線分の交差レポートの問題 (単色の場合) の最適なアルゴリズムは O(nlogn + k) ですが、赤青の交差レポートの問題では O(n^4/3 log^O(1) n + k ）。違いの背後にある明らかな理由は次のように述べられています。単色の交差が存在する場合 (赤と青の場合)、問題はかなり難しくなります。これは、2 色の交点がなくても、2 次的に多くの単色の交点が存在する可能性があるためです。

赤青交差問題を解決するために、最適な線分交差アルゴリズムを使用できないのはなぜですか? これにより、この問題は O(nlogn + k) で解決可能になります

ポイントは平面上にあり、座標を示す 2 つの数字でマークされています。接続シーケンスを示します。

このトピックについて議論しているスタックオーバーフローに関する多くの投稿を見てきました。stackoverflow から解決策を取りましたが、投稿が見つかりませんでした。つまり、2 本の線が交差する場合、外積は左側と右側で 2 つの異なる結果を生成します。1つのポジティブと1つのネガティブ。それ以外の場合は、両方とも同じ符号です。ここまでは問題ありません。使用される式は次のとおりです。ここで、AB は 1 つの行であり、CD は別の行です。

dotproductleft = (Bx-Ax) (Cy-By)-(By-Ay) (Cx-Bx)

dotproductright = (Bx-Ax) (Dy-By)-(By-Ay) (Dx-Bx)

次の特定の GPS 座標に対してこれを計算すると、交差が不可能な場合に交差が得られます。

A: x: 15.4433917 y: 47.0697272

B: x: 15.4433661 y: 47.0697722

C: x: 15.4434363 y: 47.0696776

D: x: 15.442966 y: 47.0700098

Google Maps Engine で描画すると、これらの線の間に交差がないことがわかります。

dotproductleft の結果: -7.372399999828474E-10 および dotproductright の結果: 1.1921940000328E-8

他の例では非常にうまく機能していますが、ここでは正しく機能していないことがわかりました。しかし、式に誤りは見つかりませんでした。

すべての辺が互いに平行または直交している 2 つの凹面多角形の交点を検出する簡単な方法はありますか?