math - 两条曲线的交点

Question

我需要获得两条曲线的交点。我面临的问题可以通过以下方式说明：

给定由直线连接的 N1 和 N2 点定义的两条曲线 C1 和 C2，获得 C1 与 C2 的所有交点。两条曲线不相交。

我尝试了几种方法，但到目前为止似乎都没有。有什么猜测吗？

Answer 1

最简单的方法是测试所有的线段对，每条曲线一个。如果这太慢，请尝试使用带状树。下面的论文可以在作者的网站上找到。

Ballard, DH (1981)，带状树：曲线的层次表示，ACM 通讯，v.24 n.5,310-321

Answer 2

由于您的曲线由线段组成，我建议使用空间树（例如四叉树）来仅检查彼此接近的线段。假设非常接近的交叉点的数量很少，这会将算法的复杂性从O(N1 N2)to O(N log N)(where ) 降低。N = N1 + N2

除此之外，您可以通过这种方式找到交叉点。