algorithm - 查找线路径的交点

Question

我有两条贝塞尔曲线，它们共享一个端点。这些曲线中的每一个在左右两侧都有一个“延伸”，类似于道路的边缘。扩展由近似贝塞尔曲线的线段组成。

我想找到这些路径与贝塞尔曲线的共享端点最近的交点。

这是我绘制的问题图

每条线路径都有超过 100 个顶点，因此与每条线相交并保持最近的交点可能会变得非常慢，因为这必须实时运行。

在检查交点以加快速度之前，我已经在线上运行了边界球相交测试，但它仍然不够快。我的下一个方法是使用某种四叉树结构。

我查看了Bentley-Ottmann 算法，但它似乎处理在一组线中查找所有交叉点，这不是我需要的。我还查看了 Bezier 曲线相交算法，但它们似乎需要细分成线段，我已经有了。

是否有任何有用的算法可以解决这个问题，或者关于如何优化它的任何想法？

Answer 1

给定两条延伸宽度为 Aw 和 Bw 的曲线 A 和 B。找到点 A'，它是从共享节点 N 沿 A 的距离 Bw。找到点 B'，它也是从共享节点 N 沿 B 的距离 Aw。现在，给定点 N、A' 和 B'，找到与其他三个节点形成平行四边形的第四点 N'。这个点N'是交点。