高效找到圆和网格的交点

Question

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

我试图找到的要点的说明：

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

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

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

Answer 1

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

\n\n

假设圆心为 x\xe2\x82\x92,y\xe2\x82\x92，半径为 r。\n当 \xce\xb4 = (r\xc2\xb7\xe2\x88\x9a2)/2 时，顶部和底部圆弧的 x 坐标范围是从 x\xe2\x82\x92-\xce\xb4 到 x\xe2\x82\x92+\xce\xb4。左右弧的 y 坐标范围是从 y\xe2\x82\x92-\xce\xb4 到 y\xe2\x82\x92+\xce\xb4。

\n\n

设 y\xe2\x82\x81, y\xe2\x82\x82 为对应于 x 的顶部和底部 y 坐标。对于顶部和底部弧线，使用公式 d=\xe2\x88\x9a(r\xc2\xb2-(xx\xe2\x82\x92)\xc2\xb2); y\xe2\x82\x81=y\xe2\x82\x92+d; y\xe2\x82\x82=y\xe2\x82\x92-d。

\n\n

设x\xe2\x82\x81、x\xe2\x82\x82为y对应的左右x坐标。对于左右弧，使用公式 d=\xe2\x88\x9a(r\xc2\xb2-(yy\xe2\x82\x92)\xc2\xb2)；x\xe2\x82\x81=x\xe2\x82\x92+d; x\xe2\x82\x82=x\xe2\x82\x92-d。

\n\n

正如评论中指出的，这些方程源自圆方程。在这种情况下，即 (xx\xe2\x82\x92)\xc2\xb2 + (yy\xe2\x82\x92)\xc2\xb2 = r\xc2\xb2，从中我们得到 (xx\xe2\x82 \x92)\xc2\xb2 = r\xc2\xb2 - (yy\xe2\x82\x92)\xc2\xb2 使得 xx\xe2\x82\x92 = \xc2\xb1\xe2\x88\x9a(r\ xc2\xb2 - (yy\xe2\x82\x92)\xc2\xb2) 等，或 (yy\xe2\x82\x92)\xc2\xb2 = r\xc2\xb2 - (xx\xe2\x82\ x92)\xc2\xb2 使得 yy\xe2\x82\x92 = \xc2\xb1\xe2\x88\x9a(r\xc2\xb2 - (xx\xe2\x82\x92)\xc2\xb2) 等

\n