Extract from : http://s01.middlebury.edu/cx330a/ch1.html

Getting Started in Computational Geometry

(Convex hulls)

So you've got a problem...?

 

General Principles

  1. Understand the (underlying) geometric properties
  2. Consider how to apply proper algorithmic techniques
  3. Choose data structure appropriate to problem and algorithm

EXAMPLE: Convex Hulls

Preliminary Definition: A subset S of the plane is called convex if and only if for every pair of points p,q in S, the line segment pq is completely contained in S.

Convex Hull Definition #1: The convex hull CH(S) of a set S is the smallest convex set that contains S.

Convex Hull Definition #2: The convex hull CH(S) of a set S is the intersection of all convex sets that contain S.

Convex Hull Definition #3: The convex hull CH(S) of a set S is the unique convex polygon which contains S and all of whose vertices are points from S.

 

Problem: Given a finite set S of planar points, compute CH(S).

Details:

Input: A finite set of points S={p1,p2,....,pn} given as a list of ordered pairs of Cartesian coordinates:{(x1,y1),(x2,y2),...,(xn,yn)}

Output: A listing of the vertices of CH(S) in CW order.

Geometric properties?

  1. pi in S is a vertex of CH(S) if and only if there are no three points pj, pk and pl in S such that pi falls in the triangle pjpkpl.

Algorithm Idea #1: Test every point pi in S against every other triple of points in S and accept pi as part of CH(S) only if it falls inside no such triangle. When all points are found, sort in CW order.

Geometric properties revisited?

  1. Let P be a convex polygon. Then a traversal of P in CW direction has no "left turns".
  2. (pi,pj) is an edge of CH(S) if and only if all vertices of S lie on the right side of the vector pipj.

Algorithm Idea #2: Test every pair of points pi,pj in S and see if all other points pk lie to the right of pipj. We accept a pair (pi,pj) only if no other point pk is found to the left of pipj .