寻找两个圆的所有交点

Question

在Python中，怎么找出两个圆形中所有共同的整数点呢？

举个例子，想象一下两个大小相同的圆，它们的中心点分别是 (x1,y1) 和 (x2,y2)，半径都是 r1=r2。而且我们已经知道这两个圆的交点是 (xi1,yi1) 和 (xi2,yi2)。

那么，怎么高效地生成一个包含两个圆内所有点 (x,y) 的列表呢？虽然可以简单地画一个框，包含这两个圆的交点，然后逐个检查每个点是否在两个圆内，但有没有更好的方法呢？

Answer 1

如果你的圆的位置和半径可以变化，而且变化的幅度比你的网格要小，那么你还是得检查很多点。

你可以通过合理定义搜索区域来减少需要检查的点的数量。这个搜索区域的宽度等于两个圆相交的距离，而高度则是

r1 + r2 - D

这里的D是两个圆心之间的距离。需要注意的是，这个矩形通常并不是和X轴、Y轴对齐的。（这也可以用来判断两个圆是否相交！）

实际上，你只需要检查这些点的一半。如果两个圆的半径相同，你只需要检查四分之一的点。这个问题的对称性在这里帮了你大忙。

Answer 2

你可能还想了解一下在图形开发中使用的各种剪裁算法。我曾经用剪裁算法解决过很多和你这里提问类似的问题。

Answer 3

请记住，这里有四种情况。

1. 两个圆没有交集，也就是说“共同区域”是空的。
2. 一个圆完全在另一个圆里面，这样“共同区域”就是那个较小的内部圆。还有一种特殊情况，就是它们是完全相同的同心圆，这种情况会发生，因为你提到它们是直径相等的圆。
3. 两个圆在一个点上相切。
4. 一般情况下，会有两个交点。在这种情况下，会形成两个弧线来定义被包围的区域。对于这种情况，使用画框的方法可能可以解决问题，不过我不确定有没有更有效的方法来确定交集包含的内容。不过，如果你只是想知道面积的话，这里有一个公式可以用。