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 .