Mixing the Beauty of Mathematics and Chocolate:

The Newton Apple Wrapper algorithm for 3D convex hulls.


Home
Paper describing the NewtonAppleWrapper algorithm
Privacy policy
GPL Code
NA Wrapper2 GPL Code
Contact

As befits the cleverest chocolates on the Internet we have named a new and elegant algorithm after them!
The algorithm finds the convex hull of a set of points in 3D by wrapping a series of convex hulls round the seed point as new points are added so the algorithm has been christened the Newton Apple Wrapper.


Newton Apple Wrapper Algorith Description.

The convex hull of a set of (3D) points is made up of a set of triangular planar facets exch touching 3 points on the outside of the set. The Newton Apple Wrapper is new algorithm for finding covex hulls of sets of 3D points. It belongs ot the class of sweep-hull algorithms as the final hull if made by adding point to an initial hull. The algorithm has computaitonal complexity of O(nlog(n)) and is faster than qhull for Delaunay triangulation.

The NewtonAppleWrapper algorithm functions as follows: For a set of unique points {x,y,z}_i in R3:

1: Sort the points {x,y,z}_i in z(x(y)).
2: Starting with the first of the sorted points add more points until a non-zero area triangle (or triangles) is created to form the seed hull.
3: 3) Sequentially add new points to the hull. The facets of the hull are triangles, these are maintained as a list with adjacency information. The process of adding a new point to the hull involves determining which triangular facets (on the hull) are visible to the new point and replacing them with new triangles made using the new point and the occluding edges of the hull from the perspective of the new point.

The algorithm generates a convex hull of a set of points. To use the NAW for Delaunay triangulation make z = (x*x + y*y) and keep only downwad facing triangles form the hull. The process of points being added to a hull is shown below!


1: a randomly generated set of 100 points in R2 with z = (x*x + y*y) the hull has been grown to include 96 of the 100 points.


The hull has been grown to include 97 of the 100 points.


The hull has been grown to include 98 of the 100 points.


The hull has been grown to include 99 of the 100 points.


The hull has been grown to include all of the 100 points.


Just the downward facing triangular facets of the hull.


Projection shows the Delaunay triangulation.

If you like the algorithm you can buy a full commercial liense to the GPL code on this site with the button below.

Various delaunay triangulation resources include: q-hull used by MatLab, sweep-line: Steven Fortune's homepage, sweep-hull: s-hull.org, NetLib , Jonathan Shewchuck's homepage .