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；y2=yₒ-d。

设x₁, x₂ 为y 对应的左右x 坐标。对于左右弧，使用公式d=√(r²-(y-yₒ)²); x₁=xₒ+d；x2=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ₒ)²) 等。