count - 半円内の点を決定するために使用できるアルゴリズムは何ですか?

Question

複数の「中心」を持つグリッドでこれを行うにはどうすればよいですか?したがって、一度だけカウントしたい一致点がありますか?

これを行う最も効率的な方法は何ですか?

Answer 1

Pポイントが半円内にあるかどうかを調べるには、次の 2 つの部分のテストを検討します。

1. 中心Pの半径 内にありますか?RC
2. 正しいP(すなわち、占有された) 半平面にあるか?

パート (1) は簡単です: (P_x-C_x)^2 + (P_y-C_y)^2(2 次元では、もちろん 3 次元では Z 方向を追加します) とR^2(平方根を気にしないでください。時間がかかり、何も追加しません) と比較してください。

b = B - Cパート (2) もほぼ同じです。占有された半平面を指す半円を二等分するベクトルを定義します。次に、ベクトルv = P - Cを計算し、 で内積を取りbます。結果が正の場合、ポイントは占有された半分の平面にあり、負の場合、ポイントは占有されていない半分の場所にあり、0 の場合、ポイントは分割線上にあります。2 次元のドット積はv*b = v_x*b_x + v_y*b_y通常どおりです。