查找线路径的交点

Question

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

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

Here is a diagram I've drawn of the problem

每一行路径在100个顶点，所以彼此相交线，并保持最近的交叉点可能会变得非常慢，因为这必须实时运行。

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

我抬头看了Bentley-Ottmann algorithm，但它似乎处理在一组线中找到所有交点，这不是我所需要的。我也查找过贝塞尔曲线相交算法，但它们似乎需要细分成线段，而我已经有了。

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

Answer 1

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