计算两个圆之间的交点，哪种方法更有效？

Question

3

我正在尝试找到在C#程序中计算两个圆的交点的最快最简单的方法。据我所知，有两种可能的方法，你得原谅我不知道它们的官方名称。

我们假设您知道两个圆的中心点和它们的确切半径，从而可以计算它们之间的距离，因此缺少的是交点坐标。这在标准的x-y坐标系上进行。

第一种是一种替换方法，类似于这里描述的方法，其中您结合两个圆的公式并隔离x或y，然后将其重新代入原始公式中得到一个二次方程，可以解出两个（或可能是一个或零）坐标轴的坐标，然后让您找到其他坐标轴上对应的坐标。

我看过的第二个参考文献是使用余弦定理方法确定角度，然后让您在网格上为每条边绘制一条线，并插入半径以找到实际的交点。

我已经写下了第一种方法的步骤，它似乎非常冗长。第二种方法需要一些研究/学习才能写出来，但听起来更简单。我从未将这样的过程转化为代码，因此我不知道哪种方法最适合该应用程序。有人可以给我建议吗？或者我可能完全错误地进行了操作？是否已经有库可以使用它而不必重新发明轮子？

一些背景: 我主要担心CPU成本来执行这些计算。我计划同时、反复地进行大量计算，因此希望找到最简单的方法来完成它。

- thanby

您放了一个链接，我觉得您忘记在底部放置URL了。此外，这似乎更像是一个数学问题而不是C#问题。 - gunr2171

2

这个问题似乎不适合讨论，因为它涉及到数学。 - DavidG

@DavidG：不，这是关于编程的。也许它“过于宽泛”之类的，但它肯定不会因为主题而被视为离题。 - tmyklebu

哎呀，我修复了链接和一些格式。我最初是为Math.SE编写的，但后来转到这里，因为我认为他们会将其标记为离题。我特别询问它在编程中的应用，包括可能已经执行这些计算的任何库。 - thanby

1个回答

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

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

- tmyklebu · Accepted Answer

计算几何学通常实现起来很痛苦。而且，它几乎总是需要大量的CPU计算。话虽如此，只要你正确地设置，这个问题就只是代数问题。

计算，即两个圆心之间的距离。如果，则没有交点。如果，交点位于(x1, y1) + r1/(r1+r2) * (x2-x1,y2-y1)处。如果，其中一个圆包含在另一个圆内，并且没有交点。您可以推导出两个圆相切且其中一个圆包含在另一个圆内的情况。我只处理剩余的情况。

您需要找到与(x2-x1,y2-y1)正交的距离和与(x2-x1,y2-y1)平行的距离

，使得p^2 + h^2 = r1^2并且(d-p)^2 + h^2 = r2^2。将两个方程相减得到p的线性方程：d^2-2dp = r2^2-r1^2。解这个线性方程得到p。然后h = sqrt(r1^2 - p^2)。

两个点的坐标为(x1,y1) + p (x2-x1,y2-y1) / d +/- h (y2-y1, x1-x2) / d。如果您按照上述推导进行计算，并解出p/d和h/d，则可以得到更少的操作。