当两个圆的交点和相应的半径给定时，如何找到它们的中心？

Question

我读了史蒂文和费利克斯·哈利姆的“竞争性编程3”第7章。然后，我发现了这个问题，如图所示：

​

​

给出了两个圆的两个相交点和相应的半径。我得找到两个圆圈的中心。他们给出了解决方案代码。但我不明白背后的技术。给出的代码是：

​

​

我找过很多次了，但没找到。有人能解释一下这个技巧吗？

无论如何，预先谢谢:)

Answer 1

让我们首先可视化代码中定义的变量d2和h：

​

正如我们所看到的，d2代表p1和p2之间距离的平方。让我们把d = sqrt(d2)。然后是d^2 = d2。

使用毕达哥拉斯：r^2 = h^2 + d^2/4。因此，h^2 = r^2 - d^2/4。

在连接1和p1的直线方向上的酉矢量(范数= p2 )是：

v := (p2 - p1)/d = (p2.x - p1.x, p2.y - p1.y)/d.

其垂直度

w := (p2.y - p1.y, p1.x - p2.x)/d

现在，我们可以将c1表示为垂直方向的点：

c1 = q + w*h = (p1 + p2)/2 + w*h,

因为w有范数，所以1和h就是c1和q之间的距离。因此，

c1 = (p1.x + p2.x, p1.y + p2.y)/2 + (p2.y - p1.y, p1.x - p2.x)*h/d

哪里

h/d = sqrt(r^2 - d^2/4)/d = sqrt(r^2/d2 - 1/4)

这就解释了密码。

Notes

1. 从图片上看，r总是ge而不是d/2。因此，不需要检查r^2 ≥ d^2/4或(r/d)^2 ≥ 1/4是否需要检查det < 0，因为它从来都不是(只要圆圈相交)。
2. 上面的推导实际上将为c1生成两个解决方案，一个在从p1到p2的蓝线右侧，这是绘图中的一个，另一个在所述行的左侧。事实上，这些方程对应于 c1 =q±w*h =q+ w*(±h) 为了决定我们应该使用+h还是-h，我们可以应用一个众所周知的标准来确定一个点是在有向段的左边还是右边。例如，我们可以计算行列式的符号。 ( p2.x - p1.y )-( p2.y -p1.y)- (p2.y-p1.y)( c1.x - p1.x )

它将有+h的标志，而-h的标志正好相反。使h生成D < 0的值是将c1留在从p1到p2的段右侧的值。

Answer 2

在正确的三角形中应用毕达哥拉斯。这给出了p1p2中点和中心之间的距离。

从单元向量并行到正交到p1p2，很容易得到偏移矢量。