寻找线路路径的交点

Question

寻找线路路径的交点

algorithmgeometryintersectionbezierline-segment

3

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

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

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

我先在检查交点前对这些线进行了包围球相交测试以加快速度，但仍然不够快。我的下一步尝试将是使用某种四叉树结构。

我查阅了Bentley-Ottmann算法，但它似乎处理的是在一组线中找到所有交点，这不是我所需要的。我还查阅了贝塞尔曲线相交算法，但它们似乎需要将其细分为线段，而我已经有了线段。这里是我绘制的问题示意图 Bentley-Ottmann算法有没有针对这个问题的有用算法，或者对如何进行优化有什么想法？

- Paul Allen

1

为什么是最近的交点而不是唯一的交点？A和B在多个交点上相遇的可能性存在吗？ - saastn

相关链接：https://dev59.com/BmbWa4cB1Zd3GeqPTRom - finnw

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tyler Durden · Answer 1

给定两条曲线A和B，其扩展宽度分别为Aw和Bw。找到点A'，它是从共享节点N沿着A的距离Bw处。同样地，找到点B'，它是从共享节点N沿着B的距离Aw处。现在，给定点N、A'和B'，找到第四个点N'，它与其他三个节点形成平行四边形。这个点N'就是交点。