Sunday 19 February 2012

3D Convex hull in Python

In this article I present a present a reimplementation in pure Python of Joseph O'Rourke's incremental 3D convex hull algorithm from his book Computational Geometry in C.

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 GitHub.
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.

7 comments:

  1. When I try to open ti with the GNU Meshlab I get an error saying "Premature end of file". What is that supposed to mean?

    ReplyDelete
  2. Hi,
    thank you very much for this piece of code! I am using it succesfully.
    There is only one strange behaviour I couldnt yet figure out why it happens: Sometimes the code doesnt finish saying

    338 # e interior: mark for deletion
    339 e.delete = REMOVED;
    --> 340 elif e.adjface[0].visible or e.adjface[1].visible:
    341 # e border: make a new face
    342 e.newface = self.MakeConeFace( e, p )

    AttributeError: 'NoneType' object has no attribute 'visible'

    in the constructor when calling (Hull(myvectors)).

    Do you have an idea about how I could avoid this? For a some selection of my data points the code works, for some this error occurs and I cant figure out what the pattern is.

    Thanks again!

    ReplyDelete
  3. Thank you for sharing your code!
    it would be great if there was an easy build-in method available, which can calculate the surface area of the resulting convex polyhedron.

    ReplyDelete
  4. Great code! I've used it to create an STL file for a 3D shape that contains concavities and convexity. Unfortunately, the code seems to fill in those concavities to create a convex shape. I'm not a Python expert - is there a (simple?) way to modify this code to not get rid of the concavities?

    ReplyDelete
  5. Thank you very much, this code was very useful for me to represent some data :)

    I added a little function:

    def PrintFile(self, filename='tmpshape.stl'):
    f1 = open(filename, 'w+')
    f1.write("solid points\n")
    for f in self.faces:
    f1.write(str(f) + '\n')
    f1.write("endsolid points\n")
    f1.close()


    to print directly to a stl file which was handy for me.

    ReplyDelete
  6. This professional hacker is absolutely reliable and I strongly recommend him for any type of hack you require. I know this because I have hired him severally for various hacks and he has never disappointed me nor any of my friends who have hired him too, he can help you with any of the following hacks:

    -Phone hacks (remotely)
    -Credit repair
    -Bitcoin recovery (any cryptocurrency)
    -Make money from home (USA only)
    -Social media hacks
    -Website hacks
    -Erase criminal records (USA & Canada only)
    -Grade change
    -funds recovery

    Email: onlineghosthacker247@ gmail .com

    ReplyDelete

  7. Exploring "3D Convex Hull in Python" reveals a depth of programming knowledge. Just as you delve into coding intricacies, dive into the world of oral health in Delhi. Seek the best dentist in delhi —a professional whose expertise forms a robust dental framework, ensuring your journey is marked by precision, care, and the best possible solutions for your dental needs.

    ReplyDelete