找到一对QuadCurve2Ds的交点（们）

Question

有没有一种简单的方法来近似计算两个QuadCurve2D实例相交的点（如果有）？

也就是说，我该如何计算这张图中红点的坐标呢？在QuadCurve2D中没有明显的方法可以做到这一点。

（注意：由于我手动调整了它们，因此这些点不是精确的。还要注意“缺少”的第四点，即使它位于（无限）抛物线上，但并不位于曲线段上。）

这两个曲线段是使用以下代码创建的：

QuadCurve2D curve1 = new QuadCurve2D.Double(-2.00, -2.00, +0.75, +4.75, +2.00, -0.75);
QuadCurve2D curve2 = new QuadCurve2D.Double(-2.50, -0.75, +5.50, -0.50, +0.50, +1.25);

注意2：我还希望能够求直线和二次曲线的交点，但我认为只要将控制点之一与端点共线即可解决这个问题。

- finnw

---

你已经标记了贝塞尔曲线 - 这是否也需要作为你的曲线看起来只是基本的抛物线？ - mathematician1975

@mathematician1975，是的，因为我拥有的输入是端点+控制点。 - finnw

Answer 1

取决于您是对近似解还是精确解（双精度）感兴趣。对于近似解，您可以将曲线参数化为某些函数f(t)，然后进行一些区间嵌套以找到使曲线之间距离最小的t值。

对于精确解，您需要找到两个圆锥截面相交的四个点。关于此有一个简短的段落，请参见wikipedia。书籍透视几何视角有一个更长的部分解释了细节。肯定有各种语言的实现可用；我现在想到的是Asymptote的一个实现。然而，其一般情况的实现看起来非常可怕，所以可能他们在那里做了过于复杂的事情。

一旦您获取了所有四个交点，仍需决定它们中哪些在由QuadCurve端点限定的拱形部分上，但这相比之下应该很简单。因此，总体而言，您需要完成以下三个步骤：

1. 从端点和控制点计算圆锥曲线的矩阵
2. 使用其笔画中的退化元素相交圆锥曲线
3. 判断这些交点是否位于端点之间

如果您在其中一个步骤的数学细节上遇到问题，最好在数学堆栈交换上提问。那里的人们不仅有更多解决数学问题的经验，而且MathJax特性可用于排版数学，使答案比此处的回答要易读得多。

关于你提到的直线问题，这个问题要容易得多，因为如果你用坐标来表达这个问题，你最终只会得到一个二次方程，而不是原始方法中的四次方程，即使按照上述参考文献所描述的方式解决，也只有三次方程。可以将一般的方法写成一种方法，其中与一条直线相交是解决方案的一步，因此有一个解决这个问题的方法可能已经足够好了。

- MvG

Answer 2

一个实际的方法是通过添加曲线并关闭结果来创建两个“Area”，这些“Area”的交点应该具有所有原始交点作为某些线段的端点。因此，遍历生成的路径，忽略任何贝塞尔控制点，并对于每个段落端点遇到的情况，检查它是否位于原始曲线上。

或者看看“Area”如何实现这一点，并看看是否可以将其适应于您的需求。如果您的许可证允许包括GPL2代码。

- MvG

---

有趣，但我不认为这对于直线情况适用。 - finnw

@finnw：在直线情况下，简单地闭合形状会导致一个空区域，因此您可能需要添加一些额外的点，使其成为三角形或类似形状。 - MvG