algorithm - 円とグリッドの交点を効率的に見つける

Question

中心点と半径と任意のグリッドで定義された円の交点を見つける良い方法は何ですか?

私が見つけようとしているポイントの図：

私がこれまでに考えた可能な解決策：

1. 中心 +- 半径の間にあるすべての線を見つけます。各線について交点を計算します。

2. 円を n 辺のポリゴンにし、ジオメトリ ライブラリを使用して、ポリゴンとグリッド ラインの交点を見つけます。これにより、円以外の形状も使用できるようになります。

Answer 1

各グリッド線と円との交点を見つけて、一連の線の座標を反復処理することは理にかなっているようです。ただし、悪条件の計算を避けるために、独立変数として y ライン、場合によっては x ライン座標を使用する必要があります。具体的には、円を 45°、135°、225°、315° を分割点とする 4 つの円弧に分割します。

円の中心が 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ₒ)²) など。