6

在 Python 中，如何找到两个圆共有的所有整数点？

例如，想象一个维恩图式的两个（大小相等的）圆的交集，圆的中心点为(x1,y1)和(x2,y2)，半径为r1=r2。此外，我们已经知道圆的两个交点是(xi1,yi1)和(xi2,yi2)。

如何(x,y)以一种有效的方式生成包含在两个圆圈中的所有点的列表？也就是说，绘制一个包含交叉点的框并遍历它会很简单，检查给定点是否在两个圆内，但是有更好的方法吗？

4

6 回答 6

1

如果你的圆的位置和半径的变化粒度小于你的网格，那么无论如何你都会检查一堆点。

您可以通过适当地定义搜索区域来最小化您检查的点数。它的宽度等于交点之间的距离，高度等于

r1 + r2 - D

与D是两个中心的分离。请注意，此矩形通常不与 X 和 Y 轴对齐。（这也让你测试两个圆是否相交！）

实际上，您只需要检查这些点的一半。如果半径相同，您只需要检查其中的四分之一。问题的对称性可以帮助你。

于 2010-04-28T15:55:20.030 回答
1

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

  1. 两个圆圈都不相交，这意味着“公共区域”是空的。
  2. 一个圆圈完全位于另一个圆圈内，这意味着“公共区域”是较小/内部的圆圈。另请注意，如果它们是相同的同心圆，则这种情况的退化情况必须是这种情况，因为它们是您指定的等直径圆。
  3. 两个圆在一个交点处相接触。
  4. 将有两个交点的“一般”情况。从那里，您有两条弧线来定义封闭区域。在这种情况下，画框方法现在可以工作，我不确定是否有更有效的方法来确定交叉点包含的内容。但是请注意，如果您只是对该区域感兴趣，则有一个公式。
于 2010-04-28T15:49:55.270 回答
1

您可能还想研究图形开发中使用的各种裁剪算法。我已经使用剪裁算法来解决很多与您在这里提出的问题类似的问题。

于 2010-04-28T15:50:52.307 回答
1

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.

于 2015-09-11T11:13:46.250 回答
0

所以你想找到两个圆圈内的格点？

您建议的绘制一个盒子并遍历盒子中所有点的方法对我来说似乎是最简单的。只要盒子中的点数与交叉点中的点数相当，它可能会很有效。

即使它不是尽可能高效，你也不应该尝试优化它，直到你有充分的理由相信它是一个真正的瓶颈。

于 2010-04-28T15:45:34.717 回答
0

我假设“所有点”是指“所有像素”。假设您的显示器是 NX x NY 像素。有两个数组

int x0[NY], x1[NY]; initially full of -1.

交叉点呈菱形，位于两条曲线之间。沿每条曲线迭代 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 为整数的点。相反，像素是网格线之间的小方块。这将防止您遇到极端情况问题。

于 2010-04-28T15:58:16.487 回答