A convex hull in pure Python
This is the second, rather off topic, article on computational geometry in this blog. The previous article presented an implementation of the marching tetrahedrons algorithm.
The goal of this article is to provide object oriented, pythonic code to compute the convex hull of a collection of 3D points. The code is contained in a single Python module that may be downloaded from my website.
A sample of how to use this module is shown below, where we create a a roughly spherical cloud of points, calculate its convex hull and print this hull in STL format to stdout. The resulting object is shown in the image (as seen in Blender).
from random import random from chull import Vector,Hull sphere= for i in range(2000): x,y,z = 2*random()-1,2*random()-1,2*random()-1 if x*x+y*y+z*z < 1.0: sphere.append(Vector(x,y,z)) h=Hull(sphere) h.Print()
Difference from the original implementation
The original code restricted the coordinates of points to integers, here there is no such restriction. This might result in errors if the coordinates are large.