0

I am coding something a bit esoteric.

I have a stream of points which are guaranteed to be planar, however the points are embedded in some high dimensional space (e.g. 3D).

I need to define a notion of orientation for my points, basically given 3 oriented points I need to know if they wind "left" or "right". However I cannot appeal to an ambient space to do so, i.e. I cannot use a normal vector to define orientability.

More precisely I am implementing Jarvis march to get a convex hull of a point set in some arbitrary dimension. But to achieve this I need to be able to say whether a given triplet of points creates a positive or negative angle relative to some arbitrary but consistent choice of orientation. How would I do that?

Makogan
  • 3,329

2 Answers2

2

For any non-zero $w \in \mathbb{R}^n$, let $\eta(w) = \frac{w}{|w|}$ be the unit vector in direction of $w$.

Take a few triplet of points randomly from your set of points.

For each triplet $(a_i,b_i,c_i)$, compute 2 orthonormal unit vectors (if possible) by the recipe: $$u_i = \eta(b_i-a_i)\quad\text{ and }\quad v_i = \eta(c_i-a_i - (u_i\cdot(c_i-a_i)) u_i)$$ Using whatever criteria you want (in particular, you want to avoid those $i$ where $|b_i - a_i|$, $|c_i - a_i|$ too small or $\angle a_ib_ic_i \sim 0$ or $\pi$), pick an $i$ where $u_i, v_i$ you believe to be most numerically accurate.

Let $(a,u,v) = (a_i,u_i, v_i)$ for this particular $i$.

If your set of points is indeed planar, then any point $p$ in it can be represented as

$$p = a + x_p u + y_p v\quad\text{ where }\quad \begin{cases} x_p = u \cdot( p - a)\\ y_p = v \cdot( p - a) \end{cases}$$

You can use $(x_p,y_p)$ as a "2-d" coordinate for your set of points and apply whatever "2-d" algorithm you have to compute the orientation (with respect to this coordinate system).

achille hui
  • 122,701
0

Let $A_1,A_2,A_3$ your points with coordinates $A_k=(x_k,y_k,z_k)$

Plainly, take the sign of the following determinant :

$$D=\begin{vmatrix}x_1&x_2&x_3\\ y_1&y_2&y_3\\ z_1&z_2&z_3\\\end{vmatrix}$$

If $D$ is negative, you say conventionnaly that you turn clockwise ; in the other case, you turn anti-clockwise.

In the exceptional case where $D=0$, it means that the points are aligned.

Why that ? Because this determinant is equal to $3! = 6$ times the oriented volume of the tetrahedron $OA_1A_2A_3$ where $O$ is the origin (see for example here).

Jean Marie
  • 81,803