How can I iterate a coordinate sphere using an expanding spherical sector (cone)?

Question

Given an integer 3D coordinate system, a center point P, a vector in some direction V, and a max sphere radius R:

I want to iterate over only integer points in a fashion that starts at P and goes along direction V until reaching the max radius R.

Then, for some small angle T iterate all points within the cone (or spherical sector) around V.

Incrementally expand T until T is pi/2 radians and every point within the sphere has been iterated.

I need to do this with O(1) space complexity. So the order of the points can't be precomputed/sorted but must result naturally from some math.

Example:

// 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));
}

See picture for this example

The first coordinates that should be caught are:

A(0,0,0), C(0,1,0), D(0,2,0), E(0,3,0), B(0,4,0)

Then, expanding the angle somewhat (orange cone):

K(-1,0,3), X(1,0,3), (0,1,3), (0,-1,3)

Expanding the angle a bit more (green cone):

F(1,1,3), (-1,-1,3), (1,-1,3) (-1,1,3)

My guess for what would be next is:

L(1,0,2), (-1,0,2), (0,1,2), (0,-1,2)
M(2,0,3) would be hit somewhat after

Extra notes and observations:

A cone will hit a max of four points at its base, if the vector is perpendicular to an axis and originates at an integer point. It may also hit points along the cone wall depending on the angle
I am trying to do this in c++
I am aware of how to check whether a point X is within any given cone or spherical vector by comparing the angle between V and PX with T and am currently using this knowledge for a lesser solution.
This is not a homework question, I am working on a 3D video game~

Please provide an minimal reproducible example of your best attempt. Surely you have a program which represents the input data "Given an integer 3D coordinate system, a center point P, a vector in some direction V, and a max sphere radius R" in suitable data structures. Then, since you ask about "iterate", please demonstrate a single step of that iteration, i.e. the body of the innermost loop. Then an answer can help with constructing the loops and the math to derive the current values of the variables for your step. That way you can focus this question on the actual specific prgramming problem you encountered. — Yunnosch
This question keeps coming up today. You didn't address the previous question: There's an infinity of points. A 3-dimensional infinity. Do you only want integer points ? — Jeffrey
@Jeffrey, please elaborate "This question keeps coming up today." Is this a duplicate? Has this user asked a similar question already? Can you link? Do you suspect a homework assignment? — Yunnosch
@Yunnosch this was deleted yearlier on. It was the same question, just even less clear (to me) and 2D. stackoverflow.com/questions/63344611/… — Jeffrey
Hey @Mike, the O(1) space requirement has me puzzled. I tried getting an answer there: cs.stackexchange.com/questions/129183 — Jeffrey

Spektre Spektre · Accepted Answer · 2020-10-26T08:46:28

iterate all integer positions Q in your sphere

simple 3x nested for loops through x,y,z in range <P-R,P+R> will do. Just check inside sphere so
```
u=(x,y,z)-P;
dot(u,u) <= R*R
```
test if point Q is exactly on V

simply by checking angle between PQ and V by dot product:
```
u = Q-P
u = u/|u|
v = V/|V|
if (dot(u,v)==1) point Q is on V
```
test if points is exactly on surface of "cone"

simply by checking angle between PQ and V by dot product:
```
u = Q-P
u = u/|u|
v = V/|V|
if (dot(u,v)==cos(T/2)) point Q is on "cone"
```
where I assume T is full "cone" angle not the half one.

Beware you need to use floats/double for this and make the comparison with some margin for error like:

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"

How can I iterate a coordinate sphere using an expanding spherical sector (cone)?

1 Answers