Created 2006-09-02 Modified 2007-01-22
Chelton Evans
Convex Polygon Tessellation
Intro
Fans
Linking
Growth
Unique Simplex Generation
Incremental Linked Simplex Tessellation with Ordered Points
I present two clear linear time convex tessellation algorithms. These are the Fans algorithm which is the simplest and strongest because it only requires a convex hull of points.
The second linear tessellation algorithm is the Incremental Linked Simplex Tessellation with Ordered Points which uses a linked simplex mesh with state. I believe Delaunay Triangulation could also be used in the mesh re balancing with expected linear time.
The third is on growth and a little vague but that is how some algorithms start.
There are other algorithms - I came across one in an exam paper using a sweep algorithm but I did not understand it so I could not include it.
These are the simplest way to tessellate. Simply fix a point and iterate through the surface to neighboring faces. Any simplex generated has a unique global point which all the simplexes in the tessellation share.
In 2D the surface is the lines making the border of the polygon. In 3D the surface is a 2D mesh.
At all times the fan is connected. ie move from any one simplex in the fan to another.
The mesh could be rebalanced after construction. For a minimizer that re balances the mesh in constant time (which is not hard) the tessellation is O(n). For example iterate over all the simplexes and re balance with the neighbor. Since this is not recursive it is (fan construction+re balance) O(n)+O(n)=O(n) in time.
If I say iterate about the mesh linking simplexes, the act of linking will require its own algorithm and or operators. In 2D this is easier but in 3D the extra dimension makes it harder. So whatever the construction method linking will need to be done to form a linked simplex mesh.
The advantage of knowing the surface allows you to construct the tessellation without having to split mesh simplexes so simplex construction is done once for each simplex. Even when the simplexes are going to be changed such as the act of balancing the mesh, iterating over a known surface can be the simple step. For example joining two convex hulls it is convenient to first connect the two hulls with simplexes then re balance the mesh. To get the mesh balanced in the first place could be a very difficult algorithm.
An issue with linking is that it is equivalent to knowing the surface tessellation. In 2D this is effectively communicated as an ordered list of points. In 3D as there are two dimensions in the iteration it is much harder.
Since convex tessellation involves iterating over the surface, another way to iterate over the surface is to grow it in all directions. As the surface grows new directions are tried out.
Here is a growth algorithm where distant points are added but in such a way that iteration about a vertex is avoided and each simplex created is unique.
Both fans and growth can be used for unique simplex generations. That is one a simplex is created its points are never changed.
The splitting operator is not allowed to be used in this process as this would alter one of the existing simplexes. Therefore points have to be fed to the tessellation algorithm in order.
Linked simplexes with a state can be used to get a O(n) time algorithm by ordering the points in the tessellation so that the order of the points is such that the points are near to each other.
Since the mesh will have a current simplex, this should be near the last inserted point, so the new inserted point will also be near and the insertion point is found in constant time.
To avoid a situation where the mesh is built in a long way for W dimensional space initially take W points from the convex hull at random and construct the initial convex space.
Since the insertion time is constant and we iterate over n points O(n)O(1) = O(n) and the algorithm is linear in time.