2
$\begingroup$

Let's say I have a set of $N$ points which define an ($N-1$) dimensional triangle (or N dimensional surface if you wish). I define a normal to that surface pointing in a specific direction. I want to order my N points such that they have an orientation in the direction of that normal, according to the right hand rule. An example is illustrated below for 3 points. The order of the points would be $[1,2,3]$. How might I achieve this for any dimension where $N \ge 2$?

enter image description here

$\endgroup$
1
$\begingroup$

$\newcommand{\Vec}[1]{\mathbf{#1}}\newcommand{\Reals}{\mathbf{R}}\newcommand{\Basis}{\mathbf{e}}\newcommand{\Brak}[1]{\left\langle #1\right\rangle}$You may be looking for the generalized cross product, a skew-symmetric, $\Reals^{n}$-valued $(n-1)$-fold product in $\Reals^{n}$, defined for vectors $\Vec{v}_{j} = \sum_{i} v_{j}^{i} \Basis_{i}$ by $$ \Vec{v} := \Vec{v}_{1} \times \dots \times \Vec{v}_{n-1} = \left\lvert\begin{array}{@{}cccc@{}} v_{1}^{1} & v_{1}^{2} & \cdots & v_{1}^{n} \\ \vdots & \vdots & \ddots & \vdots \\ v_{n-1}^{1} & v_{n-1}^{2} & \cdots & v_{n-1}^{n} \\ \Basis_{1} & \Basis_{2} & \cdots & \Basis_{n} \\ \end{array}\right\rvert. \tag{1} $$ If $(P_{j})_{j=0}^{n-1}$ is an ordered $n$-tuple of points spanning a hyperplane, put $\Vec{v}_{j} = P_{j} - P_{0}$ for $1 \leq j \leq n - 1$. The set $(\Vec{v}_{j})_{j=1}^{n-1}$ is linearly-independent, the product $\Vec{v}$ given by (1) is proportional to your normal $\nu$, and your points have the desired orientation precisely when $\Brak{\Vec{v}, \nu} > 0$.

(Note, incidentally, that while the ordered set $V = (\Vec{v}_{1}, \dots, \Vec{v}_{n-1}, \Vec{v})$ determines the same orientation as the standard basis $(\Basis_{j})_{j=1}^{n}$, whether or not $V$ is "right-handed" or "left-handed" is an entirely separate geometric matter, determined by whether the standard basis is right- or left-handed.)

$\endgroup$
2
$\begingroup$

Well, actually $N$ points span at most $N-1$ dimensions, as a triangle lives in a 2d plane, and the tetrahedron (3d simplex) has 4 vertices, and so on.

The normal adds one more dimension, and is not needed in determining the orientation. (In your example, already the order of points (1,2,3) in the plane implies an orientation of the plane.)

For the orientation of $P_0,P_1,\dots,P_{N-1}$ in the $N-1$ dimension space, we have to take the sign of the determinant of the matrix whose $i$th column is (the coordinates of) $\overrightarrow{P_0P_i}$ for $i=1,\dots,n-1$.

If you get that the orientation doesn't match the expected, just swap any two points. The 'right hand rule' corresponds to positive determinant.

$\endgroup$
  • $\begingroup$ Two questions then: 1) Is the $0$th column the coordinates of the vector from $P_0$ to $P_0$, because that would make the entire determinant zero. Or am I misinterpreting how you're defining the matrix? 2) How do I know which sign of the determinant matches the right hand rule? $\endgroup$ – zephyr Oct 7 '16 at 0:54
  • $\begingroup$ 1) $i$ starts from $1$. 2) positive determinant - the 'right hand rule' corresponds to the standard basis which makes the identity matrix which has determinant $+1$. $\endgroup$ – Berci Oct 9 '16 at 23:38

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.