Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In this Wikipedia entry for determining the orientation of a simple polygon, the following explanation is given for one of the steps:

In computations, the sign of the smaller angle formed by a pair of vectors is typically determined by the sign of the cross product of the vectors. The latter one may be calculated as the sign of the determinant of their orientation matrix. In the particular case when the two vectors are defined by two line segments with common endpoint, such as the sides $BA$ and $BC$ of the angle $ABC$ in our example, the orientation matrix may be defined as follows:

$O = \begin{bmatrix} 1 & x_{A} & y_{A} \\ 1 & x_{B} & y_{B} \\ 1 & x_{C} & y_{C} \end{bmatrix}$

Googling "orientation matrix" leads me here, which suggests that orientation matrix is a synonym for rotation matrix. Is this true in this context? If so, how does one view $O$ as a rotation matrix for $BA$ and $BC$?

Secondly, how does the specific case outlined in the quote above differ from defining an orientation matrix for two vectors generally?

share|improve this question
1  
Small typo - that second $x_A$ should be $x_C$. –  Gerry Myerson May 31 '12 at 10:52
add comment

2 Answers

up vote 1 down vote accepted

I too am unfamiliar with the term "orientation matrix". My guess is that this term is used to mean very different (unrelated) things in different contexts.

Also, as Gerry mentions, this is not a rotation matrix. To see this: A rotation matrix is a type of orthogonal matrix. A matrix $A$ is orthogonal if $A^TA=I_n$ (i.e. its transpose is its inverse). This implies that the rows and columns of the matrix form an orthonormal basis for $\mathbb{R}^n$. This in turn implies that each row and column is a unit vector and clearly $[1\;1\;1]^T$ is not a unit vector (its length is $\sqrt{3}$). So it's definitely not a rotation matrix.

Now what is the deal with this matrix? It's not obvious from the definition (to me anyway) what's going on, but with a slight change in perspective the purpose becomes clear.

Consider $A=(x_A,y_A)$, $B=(x_B,y_B)$, and $C=(x_C,y_C)$. Then $\vec{BA}=A-B=(x_A-x_B,y_A-y_B)$ and $\vec{BC}=C-B=(x_C-x_B,y_C-y_B)$. If we form the cross product $\vec{BA}\times\vec{BC}$ then the cross product is $\vec{0}$ if $ABC$ are colinear. The cross product points "upward" if the points are arranged clockwise and downward if the points are arranged counter-clockwise. So if we dot the cross product with the vector $\vec{k}=[0\;0\;1]$, we'll get a positive answer if clockwise and negative if counter-clockwise.

Now keep in mind dotting the cross product with the vector is the same as computing the determinant of the $3\times 3$ matrix $$ \begin{bmatrix} 0 & 0 & 1 \\ x_A-x_B & y_A-y_B & 0 \\ x_C-x_B & y_C-y_B & 0 \end{bmatrix}$$

How does this connect back to the so-called orientation matrix? Let's work with its transpose (since the matrix and its transpose have the same determinant this doesn't matter): $$\begin{bmatrix} 1 & 1 & 1 \\ x_A & x_B & x_C \\ y_A & y_B & y_C \end{bmatrix} \sim \begin{bmatrix} 0 & 1 & 1 \\ x_A-x_B & x_B & x_C \\ y_A-y_B & y_B & y_C \end{bmatrix} \sim \begin{bmatrix} 0 & 1 & 0 \\ x_A-x_B & x_B & x_C-x_B \\ y_A-y_B & y_B & y_C-y_B \end{bmatrix} \sim$$ $$\begin{bmatrix} 0 & 1 & 0 \\ x_A-x_B & 0 & x_C-x_B \\ y_A-y_B & y_B & y_C-y_B \end{bmatrix} \sim \begin{bmatrix} 0 & 1 & 0 \\ x_A-x_B & 0 & x_C-x_B \\ y_A-y_B & 0 & y_C-y_B \end{bmatrix}$$

So far I've just added multiples of rows and columns to other rows and columns (this does not change the determinant). Now I need to swap columns (this changes the sign of the determinant): $$\begin{bmatrix} 0 & 0 & 1 \\ x_A-x_B & x_C-x_B & 0 \\ y_A-y_B & y_C-y_B & 0 \end{bmatrix}$$

Finally we can replace the submatrix (the $2 \times 2$ matrix in the lower lefthand corner) with its transpose. This doesn't change the determinant.

In the end we have that if the determinant of the orientation matrix is positive, then my original matrix coming from the $\vec{k}$ dotted with the cross product is negative (and vice-versa).

Thus the points are arranged in a clockwise fashion if the determinant of the orientation matrix is negative and counter-clockwise if it's positive.

There's probably a more efficient route to the answer but this is what came to mind first. I hope it helps! :)

share|improve this answer
add comment

This is the first time I've come across the phrase, "orientation matrix". I can, however, say with certainty that $O$ is not the matrix of a rotation. The matrix of a rotation has (among other properties) columns that are unit vectors, unlike the first column of $O$.

As for the cross product and the determinant, you may know the formula that says that $$(a,b,c)\times(d,e,f)=\det\pmatrix{{\bf i}&{\bf j}&{\bf k}\cr a&b&c\cr d&e&f\cr}$$ where ${\bf i}=(1,0,0)$, ${\bf j}=(0,1,0)$, ${\bf k}=(0,0,1)$. This must have something to do with what you've quoted, although I confess I don't see exactly what.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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