algorithm - 有效地找到圆和网格的交点

Question

有什么好方法可以找到由圆心和半径定义的圆与任意网格的交点？

我试图找到的点的说明:

到目前为止我想到的可能的解决方案:

1. 找到中心 +- 半径之间的所有直线。为每条线计算交点。

2. 使圆成为 n 边多边形，并使用几何库找到多边形和网格线之间的交点。这也允许使用圆形以外的其他形状。

Answer 1

遍历线的坐标集，找到每条网格线与圆的交点似乎是合理的。然而，为了避免病态计算，有时应该使用 y 线坐标，有时使用 x 线坐标作为自变量。具体来说，将圆分成四个圆弧，分割点分别为°45°、135°、225°和315°。

假设圆心在 xₒ,yₒ，半径为 r。 当 δ = (r·√2)/2 时，顶弧和底弧的 x 坐标范围是从 xₒ-δ 到 xₒ+δ。右弧和左弧的 y 坐标范围是从 yₒ-δ 到 yₒ+δ。

令 y₁, y₂ 为对应于 x 的顶部和底部 y 坐标。对于顶部和底部弧，使用公式 d=√(r²-(x-xₒ)²)； y₁=yₒ+d； y₂=yₒ-d。

令 x₁, x₂ 为对应于 y 的左右 x 坐标。对于右弧和左弧，使用公式 d=√(r²-(y-yₒ)²); x₁=xₒ+d； x₂=xₒ-d。

如评论中所述，方程式源自圆方程式。在这种情况下，即 (x-xₒ)² + (y-yₒ)² = r²，从中我们得到 (x-xₒ)² = r² - (y-yₒ)² 以便 x-xₒ = ±√( r² - (y-yₒ)²), 等等，或者 (y-yₒ)² = r² - (x-xₒ)² 使得 y-yₒ = ±√(r² - (x-xₒ)²), 等等。