Delaunay Triangulation

Delaunay Triangulation – Divide and Conquer

This is a fairly robust C# implementation of Divide and conquer Delaunay triangulation. The implementation follows Guibas and Stolfi’s paper. This is the vertical cut implementation of divide and conquer.


References

· Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams", ACM Transactions on Graphics, 4(2), 1985, 75–123

http://www.sccg.sk/~samuelcik/dgs/quad_edge.pdf

· Dwyer, R.A., A faster divide-and-conquer algorithm for constructing

Delaunay triangulations. Algorithmica 2(2):137-151, 1987.

https://github.com/rexdwyer/DelaunayTriangulation/blob/master/common.c

· Lecture Notes on Delaunay Mesh Generation

Jonathan Richard Shewchuk

http://web.mit.edu/ehliu/Public/ProjectX/Summer2005/delnotes.pdf

· Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator

https://people.eecs.berkeley.edu/~jrs/papers/triangle.pdf

http://www.geom.uiuc.edu/~samuelp/del_project.html

· Other

http://www.neolithicsphere.com/geodesica/doc/quad_edge_overview.htm

https://cp-algorithms.com/geometry/delaunay.html

http://www.karlchenofhell.org/cppswp/lischinski.pdf

https://pure.mpg.de/rest/items/item_1819432_4/component/file_2599484/content

https://pure.mpg.de/rest/items/item_1819432_4/component/file_2599484/content

http://hjemmesider.diku.dk/~jyrki/Paper/KK88.pdf

Overview

In mathematics and computational geometry, a Delaunay triangulation (also known as a Delone triangulation) for a given set P of discrete points in a plane is a triangulation DT(P) such that no point in P is inside the circumcircle of any triangle in DT(P). Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the triangulation; they tend to avoid sliver triangles. The triangulation is named after Boris Delaunay for his work on this topic from 1934 [from wiki]. Some of the implementation in gitub I checked did triangulations but failed the incircle test.

Guibas and Stolfi’s divide and conquer algorithm uses vertical cuts. Rex Dwyer alternate cut divide and conquer implementation is the fastest implementation of finding Delaunay triangulations for set of points p (J.R.Shewchuk). I’ve implemented vertical cuts in this code but have plans to implement the alternate cut in the next project.

Data Structure

I experimented with implementing quad-edge data structure in c# but mostly unsuccessful. The main issue is, C# does not support pointer arithmetic, by default to maintain type safety and security. So my original implementation of quad-edge data structure uses public variables to store the edges did not work. The ldo and rdo variable did not encompass the splice changes happening in the merge routine [see Bathlamos implementation https://github.com/Bathlamos/delaunay-triangulation]

So I decided to use my own data structure which is vertex based and I believe it is fairly fast and can be improved.

This data structure uses C#’s binary search and IComparer<T> to add each edge automatically sorted in counter-clockwise orientation to the vertex. A simple query is used to find the appropriate edge. The expensive part is adding the edge sorted to a vertex which is at the most O(nlogn) and querying to find the appropriate edge which is also O(nlogn). The assumption is number of edges connected to a vertex is small, so it is not expected to be very expensive.

The idea is to replace the ingenious pointer implementations of Sym, Onext, Rnext, Lnext, Dnext, Lprev, Oprev, Rprev and Dprev with two routines (+two overloads).

Cc_vertical_edge(id) -> returns the counter-clockwise edge given the index

Cc_vertical_edge(edge) -> returns the first counter-clockwise edge after the given edge

Cw_vertical_edge(id) -> returns the clockwise edge given the index

Cw_vertical_edge(edge) -> returns the first clockwise edge after the given edge

The routines 1&3 are used in finding the first base LR edge, 2&4 are used in merging the left right edge sets.

There are two type of addition of edges. The first type is just an edge and the other type is addition of edge and a triangle. When the divide and conquer reduces the points to say 3 left points & 2 right points, the 3 left points are added as two edge-alone addition and third edge as edge-triangle addition, for 2 right points a single edge-alone addition is used. The initial base LR edge is added as edge-alone addition, all the other LR edges added during merge operation is added as edge-triangle addition.

Finding the Initial base LR edge

Finding the intial base LR edge uses helper functions Leftof() and Rightof() to cycle through the edges to find the convex hull bottom most end points. The routine is explained in below pictures. The initial points used are Left[Left.Count-1] which is the right most point in the left vertex set and Right[0] which is the left most point in the right vertex set.

The initial base LR edge is added using edge-alone addition routine.

Merging the Initial base LR edge

As mentioned before merging uses cc_vertical_edge(initial base LR edge) for finding the first left candidate and cw_vertical_edge(initial base LR edge (sym)) for finding the first right candidate. Incircle test is used to check the validity of left and right candidate. If both the edges are valid once again incircle test is used to choose the right candidate. The flow of the algorithm is explained in the below pictures

____________________________________________________________________ End ___________________________________________________________________