找到两个圆的所有公共点
在Python中，如何找到两个圆的所有公共整数点？
例如，想象一个类似维恩图的两个（大小相同）圆的交集，其中心点为 (x1,y1) 和 (x2,y2) ，半径为 <代码>r1=r2。此外，我们已经知道圆的两个交点是(xi1,yi1)和(xi2,yi2)。
如何以有效的方式生成两个圆中包含的所有点 (x,y) 的列表？也就是说，绘制一个包含交叉点的框并迭代它，检查给定点是否在两个圆内是很简单的，但是有更好的方法吗？
In Python, how would one find all integer points common to two circles?
For example, imagine a Venn diagram-like intersection of two (equally sized) circles, with center-points (x1,y1) and (x2,y2) and radii r1=r2. Additionally, we already know the two points of intersection of the circles are (xi1,yi1) and (xi2,yi2).
How would one generate a list of all points (x,y) contained in both circles in an efficient manner? That is, it would be simple to draw a box containing the intersections and iterate through it, checking if a given point is within both circles, but is there a better way?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
请记住，这里有四种情况。
Keep in mind that there are four cases here.
您可能还想研究图形开发中使用的各种裁剪算法。我已经使用裁剪算法来解决很多与您在这里提出的问题类似的问题。
You may also want to look into the various clipping algorithms used in graphics development. I have used clipping algorithms to solve alot of problems similar to what you are asking here.
如果圆的位置和半径可以以小于网格的粒度变化，那么无论如何您都会检查一堆点。
您可以通过适当定义搜索区域来最大限度地减少检查点的数量。它的宽度等于交点之间的距离，高度等于
r1 + r2 - D，
其中
D是两个中心的间距。请注意，该矩形通常不与 X 轴和 Y 轴对齐。 （这也可以测试两个圆是否相交！）实际上，您只需要检查其中一半的点。如果半径相同，则只需检查其中的四分之一。问题的对称性可以帮助你。
If the locations and radii of your circles can vary with a granularity less than your grid, then you'll be checking a bunch of points anyway.
You can minimize the number of points you check by defining the search area appropriately. It has a width equal to the distance between the points of intersection, and a height equal to
r1 + r2 - Dwith
Dbeing the separation of the two centers. Note that this rectangle in general is not aligned with the X and Y axes. (This also gives you a test as to whether the two circles intersect!)Actually, you'd only need to check half of these points. If the radii are the same, you'd only need to check a quarter of them. The symmetry of the problem helps you there.
你快到了。
迭代框中的点应该相当好，但是如果对于第二个坐标直接在限制之间迭代，则可以做得更好。
假设您首先沿 x 轴迭代，然后针对 y 轴迭代，而不是在边界框坐标之间迭代，找出每个圆与 x 线相交的位置，更具体地说，您对交点的 y 坐标感兴趣，并在这些交点之间进行迭代（注意四舍五入）
当你这样做时，因为你已经知道你在圆圈内，所以你可以完全跳过检查。
如果您有很多点，那么您可以跳过很多检查，并且可能会获得一些性能改进。
作为一项额外的改进，您可以选择 x 轴或 y 轴以最大限度地减少计算交点所需的次数。
You're almost there.
Iterating over the points in the box should be fairly good, but you can do better if for the second coordinate you iterate directly between the limits.
Say you iterate along the x axis first, then for the y axis, instead of iterating between bounding box coords figure out where each circle intersects the x line, more specifically you are interested in the y coordinate of the intersection points, and iterate between those (pay attention to rounding)
When you do this, because you already know you are inside the circles you can skip the checks entirely.
If you have a lot of points then you skip a lot of checks and you might get some performance improvements.
As an additional improvement you can pick the x axis or the y axis to minimize the number of times you need to compute intersection points.
那么你想找到两个圆内的格点吗？
您建议的绘制一个框并迭代框中所有点的方法对我来说似乎是最简单的。只要框中的点数与交点中的点数相当，它就可能是有效的。
即使它的效率不是尽可能高，您也不应该尝试优化它，除非您有充分的理由相信它是真正的瓶颈。
So you want to find the lattice points that are inside both circles?
The method you suggested of drawing a box and iterating through all the points in the box seems the simplest to me. It will probably be efficient, as long as the number of points in the box is comparable to the number of points in the intersection.
And even if it isn't as efficient as possible, you shouldn't try to optimize it until you have a good reason to believe it's a real bottleneck.
我假设“所有点”是指“所有像素”。假设您的显示器是 NX x NY 像素。有两个数组
两条曲线之间的交点是菱形的。
沿每条曲线迭代 x,y 值。在每个 y 值处（即曲线与 y + 0.5 相交的位置），将 x 值存储在数组中。如果x0[y]为-1，则将其存储在x0中，否则将其存储在x1中。
还要跟踪 y 的最低值和最高值。
完成后，只需迭代 y 值，并在每个 y 处迭代 x0 和 x1 之间的 x 值，即 for (ix = x0[iy]; ix < x1[iy]; ix++)（或相反）。
重要的是要理解像素并不是 x 和 y 为整数的点。相反，像素是网格线之间的小方块。这将防止您遇到边缘情况问题。
I assume by "all points" you mean "all pixels". Suppose your display is NX by NY pixels. Have two arrays
The intersection is lozenge-shaped, between two curves.
Iterate x,y values along each curve. At each y value (that is, where the curve crosses y + 0.5), store the x value in the array. If x0[y] is -1, store it in x0, else store it in x1.
Also keep track of the lowest and highest values of y.
When you are done, just iterate over the y values, and at each y, iterate over the x values between x0 and x1, that is,
for (ix = x0[iy]; ix < x1[iy]; ix++)(or the reverse).It's important to understand that pixels are not the points where x and y are integers. Rather pixels are the little squares between the grid lines. This will prevent you from having edge-case problems.