Computational Geometry
[TOC]
1 Convex Hull
1.1 Introduction
Given a number of paints, how to mix them into a desired color? For simplicity, consider just Red(R) and Green(G). Each paint is then defined as $C = (R, G)$ If two paints are available, $X = (10%,35%),Y = (16%, 20%)$. Can we get by mixing them a paint $U = (12%, 30%)$ ? How about another mixed paint $V = (13%, 22%)$ ? Will a third paint $Z = (7%, 15%)$ help?
Represent paints by planer points:
$X = (10, 35), Y = (16, 20), Z = (7, 15)$
- U can be produced from X and Y iff it lies on the segment XY
- V can be produced from X, Y and Z iff it lies in the triangle XYZ
Mixing ratio for
$$
V(12, 22)=X : Y : Z = \frac{1}{|VX|} : \frac{1}{|VY|} : \frac{1}{|VZ|}
=1 : 3 : 1
$$
1.2 Extremity
Let S be a set of n points in the plane. A point P of S is called an extreme point
- if there exists a line L through P
- such that all points of S lie on the same side of L
- otherwise P is called non-extreme
Convex Combination
Given a point set
$$
Let \space \vec\lambda =\left \langle \lambda_1, \ldots ,\lambda_n \right \rangle^T\in \mathbb{R}^n, \lambda_1+ \cdots +\lambda_n=1 \space and \space \lambda_i>0
$$
The point
$$
P=\left \langle P_1,\ldots,P_n \right \rangle \vec\lambda =\lambda_1P_1+ \cdots + \lambda_nP_n
$$
is called a convex combination of S.
1.3 Strategy
A polygon is convex iff every vertex is extreme. It suffices to construct CH(P) from all extreme points of S. A point A is not an EP of S iff there exists
$$
\lbrace P,Q,R \rbrace \subseteq S\backslash \lbrace A \rbrace \space s.t. \space A\in \Delta PQR
$$
1.4 ITT & TLT
All EPs will be identified if we test each point against every potential triangle:
Using In-Triangle Test
Note that A lies inside the triangle iff all the 3 To-Left Test return TRUE/FALSE when the triangle is given in CCW/CW order