count - 我可以使用什么算法来确定半圆内的点？

Question

如何在具有多个“中心”的网格上执行此操作，因此，我只想计算一次重合点？

最有效的方法是什么？

Answer 1

要确定一个点 ,P是否在一个半圆内，我会考虑一个两部分测试：

1. 是否P在中心的半径 ，R，C？
2. 是否P在正确的（即被占用的）半平面上？

第 (1) 部分很简单：比较(P_x-C_x)^2 + (P_y-C_y)^2（在 2d 中，当然在 3d 中添加 Z 方向）与R^2（不要打扰平方根，它们需要时间并且不添加任何东西）。

第 (2) 部分几乎同样简单：定义将b = B - C指向占据半平面的半圆一分为二的向量。然后计算向量v = P - C并取与 的点积b。如果结果为正，则该点在被占用的半平面上，如果为负，则该点在未占用的半平面上，如果为 0，则该点落在分界线上。2d 中的点积v*b = v_x*b_x + v_y*b_y与往常一样。