Robust Geometric Computations and Visualization (for ordinary mortals)

The above video was made using the implementation of Mihalis Nikolaou. Please note that despite the student had no previous experience with python, he provided this animation as a companion to his deliverable without even been asked to do so.

So why Python? We think that the best way to demonstrate that Python is a good choice to implement high level algorithms is to show you an example. The Python function below implements the well known "gift wrapping" algorithm that calculates the convex hull of n given points on the plane.

Following the pseudo code that can be found in any standard computational geometry book and using some basic CGAL functionality from the CGAL-Python bindings the implementation is straightforward. Note that r represents the current hull vertex, u is any point not chosen so far as a vertex and t is used to update u.

def jarvis(points):
      Jarvis Convex Hull algorithm.
      points is a list of CGAL.Point_2 points
      r0 = min(points)
      hull = [r0]
      r,u = r0,None
      remainingPoints = [x for x in points if x not in hull]
      while u != r0 and remainingPoints:
            u = random.choice(remainingPoints)
            for t in points:
                  if t != u and \
                     (orientation(r,u,t) == CLOCKWISE or \
                     (orientation(r,u,t) == COLLINEAR and \
                     (u-r).direction() == (t-u).direction())):
                        u = t
            r = u
      return hull
Note the simplicity and expressiveness of the code. Everything is self explanatory and the program looks like pseudo code!