给定一个整数3D坐标系,一个中心点 P ,沿某个方向的 vector V 以及一个最大球体半径 R :
我想以 P 并沿 V 的方向开始直到仅到达最大半径 R 的方式仅迭代整数点。
然后,对于某个小 Angular T ,迭代 V 周围的圆锥体(或球面扇区)中的所有点。
逐步扩展 T ,直到T为pi / 2弧度,并且球体中的每个点都已迭代。
我需要使用O(1)空间复杂度来做到这一点。因此,点的顺序无法预先计算/排序,但必须自然地通过一些数学运算得出。
例:
// Vector3 represents coordinates x, y, z
// where (typically) x is left/right, y is up/down, z is depth
Vector3 center = Vector3(0, 0, 0); // could be anything
Vector3 direction = Vector3(0, 100, 0); // could be anything
int radius = 4;
double piHalf = acos(0.0); // half of pi
std::queue<Vector3> list;
for (double angle = 0; angle < piHalf; angle+= .1)
{
int x = // confusion begins here
int y = // ..
int z = // ..
list.push(Vector3(x, y, z));
}
请参阅此示例的图片应该捕获的第一个坐标是:
然后,稍微扩展 Angular (橙色圆锥):
进一步扩大 Angular (绿锥):
我对接下来的猜测是:
额外说明和观察:
最佳答案
Q
简单的3x嵌套
for
在x,y,z
范围内循环遍历<P-R,P+R>
。只需检查球体内部即可u=(x,y,z)-P;
dot(u,u) <= R*R
Q
是否完全在V
上只需通过按乘积检查
PQ
和V
之间的 Angular 即可:u = Q-P
u = u/|u|
v = V/|V|
if (dot(u,v)==1) point Q is on V
只需通过按乘积检查
PQ
和V
之间的 Angular 即可:u = Q-P
u = u/|u|
v = V/|V|
if (dot(u,v)==cos(T/2)) point Q is on "cone"
我假设T
是完整的“圆锥”角而不是一半。当心,您需要为此使用
floats/double
,并以一定的误差进行比较,例如:if (fabs(dot(u,v)-1.0 )<1e-6) point Q is on V
if (fabs(dot(u,v)-cos(T/2))<1e-6) point Q is on "cone"