Getting started:
Part 1 (14:00)
Part 2 (14:10)
Part 3 (15:20)
Part 4 (15:30)
For \(a,b \in I\!\!R^2\):
\(a \times b = ||a|| \cdot ||b|| \cdot n(a,b) \cdot \sin(\theta(a,b)) \), where
\(\begin{array}{lcl} ||v|| &:& \mbox{length of vector $v$}\\ n(a,b) &:& \mbox{unit vector perpendicular to $a$ and $b$ ("normal vector") using the right-hand rule}\\ \theta(a,b) &:& \mbox{angle turning $a$ into $b$ (counter-clockwise)} \end{array}\)
When \(a,b\) are in the \((x,y)\) plane (\(a_z=b_z=0\)), \(n\) faces upwards if and only if \(b\) is in left half-plane w.r.t.\(~a\)
More generally, the \(z\) component of \(a \times b\) tells us how \(b\) relates to \(a\):
\(\begin{array}{lcl} z \gt 0 &:& b \mbox{ in left half-plane w.r.t. }a\\ z \lt 0 &:& b \mbox{ in right half-plane w.r.t. }a\\ z = 0 &:& a,b \mbox{ collinear} \end{array}\)
\(a \times b\) can be computed by evaluating the following 3x3 determinant:
\(\begin{vmatrix} i & j & k \\ a_x & a_y & a_z\\ b_x & b_y & b_z \end{vmatrix} = i \cdot \begin{vmatrix} a_y & a_z\\ b_y & b_z \end{vmatrix} - j \cdot \begin{vmatrix} a_x & a_z\\ b_x & b_z \end{vmatrix} + k \cdot \begin{vmatrix} a_x & a_y \\ b_x & b_y \end{vmatrix} \)
where \(i,j,k\) are the unit vectors in \(x,y,z\) direction, respectivly, and \(|m|\) denotes the determinant of matrix \(m\)
In particular: \((a \times b)_z = \begin{vmatrix} a_x & a_y\\ b_x & b_y \end{vmatrix} = a_x \cdot b_y - b_x \cdot a_y \)
\(a,b,c \in I\!\!R^2\) are in clockwise (cw) order if and only if for vectors \(u = b-a\) and \(v = c-a\), \(v\) lies in the right half-plane w.r.t. \(u\), i.e.,
\(u_x \cdot v_y - v_x \cdot u_y \lt 0\)
Likewise, \(a,b,c \in I\!\!R^2\) are in counter-clockwise (ccw) order if and only if
\(u_x \cdot v_y - v_x \cdot u_y \gt 0\)
If \(u_x \cdot v_y - v_x \cdot u_y = 0\), the three points are collinear, i.e., they lie on a line
\(\begin{vmatrix} a_x & a_y & a_x^2+a_y^2 & 1 \\ b_x & b_y & b_x^2+b_y^2 & 1 \\ c_x & c_y & c_x^2+c_y^2 & 1 \\ d_x & d_y & d_x^2+d_y^2 & 1 \end{vmatrix} \)
is \(\lt 0, = 0, \mbox{or} \gt 0\), respectively
If \(a,b,c\) are in ccw order, the signs are reversed
Thus, in-circle tests are basic polynomial computations, which are exact when using rational arithmetic. No square roots or trigonometric functions are required! This is useful for detecting beneficial edge flips when generating Delaunay triangulations
Implement and test function rectangle_test in test.cpp