終点を共有する 2 つのベジエ曲線があります。これらの各カーブには、道路の端と同様に、左右両側に「延長」があります。拡張は、ベジエ曲線に近似する線分で構成されます。
これらのパスの最も近い交点をベジエ曲線の共有終点に見つけたいと思います。
各ライン パスには 100 を超える頂点があるため、リアルタイムで実行する必要がある場合、各ラインを交差させて最も近い交点を維持することは非常に遅くなる可能性があります。
交点をチェックして速度を少し上げる前に、境界球の交差テストをラインで実行しましたが、それでもまだ十分な速さではありません。私の次のアプローチは、ある種の四分木構造を使用することです。
Bentley-Ottmann アルゴリズムを調べましたが、1 組の線分内のすべての交差点を見つけることを扱っているようですが、これは必要なものではありません。ベジエ曲線の交差アルゴリズムも調べましたが、すでに持っている線分への細分化が必要なようです。
この問題に役立つアルゴリズムはありますか、または最適化する方法についてのアイデアはありますか?