我可以使用什麼算法來確定半圓內的點？

Question

如何在具有多個「中心」的網格上執行此操作，因此，有重合點，我只需計算一次？

什麼是最有效的方法來做到這一點？

Answer 1

。如果一個點找出來，P，是一個半圓圈內，我會考慮兩部分的測試：

1. 是P半徑內，R，中心，C？
2. 是否P在正確的（即佔用的）半平面？

部分（1）很簡單：比較(P_x-C_x)^2 + (P_y-C_y)^2（二維，加上Z方向在3D，當然）與R^2（不與方根打擾，他們需要時間，不添加任何東西）。第（2）部分幾乎一樣容易：定義向量b = B - C，該半徑指向被佔用的半平面。然後計算矢量v = P - C並帶點積b。如果結果爲正，則該點位於被佔用的半平面中，如果該點處於空閒半位，並且該點位於分界線上，則爲0。像往常一樣，2d中的點積是v*b = v_x*b_x + v_y*b_y。