Lab 8

Topic: geometric computations

Getting started:


Part 1 (14:00)


Part 2 (14:10)


Part 3 (15:20)


Part 4 (15:30)


Geometry Review

3d Vector Cross-Product

[from wikipedia.org]

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 \)

Orientation Test


To check whether 3 points are in clockwise order we can use the cross-product:

\(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

In-Circle Test



It can be shown that \(d \in I\!\!R^2\) lies inside, on, or outside the circle defined by \(a,b,c \in I\!\!R^2\) given in cw order, if the following 4x4 determinant

\(\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

Triangle Mesh Representation


Prep Problem 1


Prep Problem 2

Implement and test function rectangle_test in test.cpp


Prep Solutions

Lab Exercise

Secrets