我有两条共享终点的贝塞尔曲线 . 这些曲线中的每一条在左侧和右侧都具有“延伸”，类似于道路的边缘 . 扩展部分由接近贝塞尔曲线的线段组成 .
我想找到这些路径到贝塞尔曲线的共享终点的最近交点 .
Here is a diagram I've drawn of the problem
每条线路径都有超过100个顶点，因此每条线相交并保持最近的交叉点可能变得非常慢，因为它必须实时运行 .
我在线路上运行了一个边界球体相交测试，然后检查一个交叉点以加快速度，但它仍然不够快 . 我的下一个方法是使用某种四叉树结构 .
我查了一下Bentley-Ottmann algorithm，但它似乎要处理找到一组线中的所有交叉点，这也不是查找Bezier曲线交叉算法，但它们似乎需要细分为线段，我已经拥有了 .
是否有任何有用的算法来解决这个问题，或者可能有关于如何优化它的任何想法？
1 回答
给出两条曲线A和B，其延伸宽度为Aw和Bw . 找到点A'，它是从共享节点N沿A的距离Bw . 找到点B'，它同样是从共享节点N沿B的距离Aw . 现在，给定点N，A'和B'，找到与其他三个节点形成平行四边形的第四个点N' . 这一点N'是交叉点 .