|
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 points.remove(r) hull.append(r) remainingPoints.remove(r) return hull |