1
$\begingroup$

Assume we have an integral 3D grid $\mathbb{Z}^3$ and a set of line segments $V = \{((0, 0, 0), (x, y, z)): x, y, z \in \mathbb{Z} \land (x, y, z) \ne (0, 0, 0)\}$ from its origin to another grid point. I would like to find the closest (by Euclidian metric or by an angle between $v$ and $\vec{0p}$) single point $p \in N_{26}$, where $N_{26} = \{(x, y, z): x, y, z \in \{-1, 0, 1\} \land (x, y, z) \ne (0, 0, 0)\}$, for any $v \in V$. This is equivalent to finding a primary N26 direction of $v$. If there is a technical term for it, I would like to know.

I would like the method to be computationally efficient, perhaps avoiding using trigonometric functions. It doesn't have to be perfectly accurate: a few percent error is fine if it simplifies calculations.

$\endgroup$
1
$\begingroup$

Without loss of generality assume the variable endpoint of $v$ is $(x,y,z)$ where $x\ge y\ge z\ge0$. There are only three points to test – $(1,0,0)$, $(1,1,0)$ and $(1,1,1)$.

Knowing that $u\cdot v=|u|\cdot|v|\cos\theta$, compute the three values $$v\cdot(1,0,0)=x$$ $$\frac{v\cdot(1,1,0)}{\sqrt2}=\frac{x+y}{\sqrt2}$$ $$\frac{v\cdot(1,1,1)}{\sqrt3}=\frac{x+y+z}{\sqrt3}$$ The vector that gives the largest result (for $\cos$ is decreasing on $[0,\pi]$) is the correct primary $N_{26}$ direction.

$\endgroup$
1
  • $\begingroup$ What I had in mind is something really simple like: $f: (x, y, z) \rightarrow (\lfloor \frac{x}{m} \rceil, \lfloor \frac{y}{m} \rceil, \lfloor \frac{z}{m} \rceil)$ where $m = max(\lvert x\rvert, \lvert y\rvert, \lvert z\rvert)$ which has a few degrees error. $\endgroup$ – Paul Jurczak Feb 2 at 19:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.