Delaunay triangulator

Delaunay triangulator

Delaunay triangulator class in C++

  • Language: C/C++
  • Released: Jun 23, 2011
    Last Update: Jun 22, 2011

Delaunay triangulation is a fundamental algorithm which has a vast range of applications, both in game development and in other research areas, such as AI and graph theory.

Many libraries include this algorithm among their functions , but they require adding many include files or link to big dll libraries just for getting the functions needed to run the algorithm. In many cases this is not a viable option.

This Delaunay triangulation class is contained in a single include file and it triangulates a set of unordered points in 2D space in the fastest way possible. In addition, the adjacency of each triangle is computed and redundant vertices are discarded.The algorithm used is the flip algorithm in a divide and conquer fashion.

What our users say:

> "Great code that works as expected. It quickly triangulates 500+ points, > removing duplicates and retaining original point indicies. Easier to use > than Triangle in a c++ app and is a low-cost alternative for a commercial > application." - Jason Dunn

An example of usage is shown below:

// first , define some random points in 2d space

double Px[1024],Py[1024];

int N=10;

for ( int i=0; i<N; i++ )
{
    Px[i]=(float)(rand()%450)+350;
    Py[i]=(float)(rand()%400)+150;
}

CDelaunay2D T;

// this function call takes caer of anything

T.Triangulate( Px,Py,N );    

// just to show how is easy to get low level access 
// to data structures an example using mfc is shown here:


    int i,p1,p2,p3;

    const DELAUNAYVERTEX* VertexPtr=T.GetVertexPtr();
    const DELAUNAYTRIANGLE* TrianglePtr=T.GetTrianglePtr();

    CPoint pts[3];

    for ( i=0; i<T.GetTriangleCount(); i ++  )
    {

        p1=TrianglePtr[ i ].p1;
        p2=TrianglePtr[ i ].p2;
        p3=TrianglePtr[ i ].p3;

        // draw with a thick blue pen
       CPen penBlue(PS_SOLID, 1, RGB(0, 0, 55));
       CPen* pOldPen = pDC->SelectObject(&penBlue);

       // and a solid red brush
       CBrush brushRed(RGB(155, 155, 155));
       CBrush* pOldBrush = pDC->SelectObject(&brushRed);

       // Find the midpoints of the top, right, left, and bottom
       // of the client area. They will be the vertices of our polygon.

       pts[0].x = (int)VertexPtr[ p1 ].x;
       pts[0].y = (int)VertexPtr[ p1 ].y;

       pts[1].x = (int)VertexPtr[ p2 ].x;
       pts[1].y = (int)VertexPtr[ p2 ].y;

       pts[2].x = (int)VertexPtr[ p3 ].x;
       pts[2].y = (int)VertexPtr[ p3 ].y;

       // Calling Polygon() on that array will draw three lines
       // between the points, as well as an additional line to
       // close the shape--from the last point to the first point
       // we specified.

       pDC->Polygon(pts, 3);

       // Put back the old objects.

       pDC->SelectObject(pOldPen);
       pDC->SelectObject(pOldBrush);

    }

    for ( i=0; i<T.GetVertexCount(); i++ )
        Point(pDC,(int)VertexPtr[i].x-2,(int)VertexPtr[ i ].y-2,col );

// draws bounding box of triangulation

    Rectangle( pDC,(int)T.GetMinX(),(int)T.GetMinY(),
                                               (int)T.GetMaxX(),(int)T.GetMaxY(),&WhitePen );

// if you want to draw the adjacent triangle just use these lines of code

            j=0;   // we want adjacent traingles to triangle number 0

int p12;

p12=TrianglePtr[ j ].t1;

if ( p12!=-1)   DrawPoly( pDC , p12 ,col2 );

p12=TrianglePtr[ j ].t2;

if ( p12!=-1)   DrawPoly( pDC , p12 ,col1 );

p12=TrianglePtr[ j ].t3;

if ( p12!=-1)   DrawPoly( pDC , p12 ,col3 );
You need to log-in or create an account
  • Create an account
  • Log-in
Please use your real name.
Activation link will be sent to this address.
Minimum 8 characters
Enter your password again

Clicking this button confirms you read and agreed to the terms of use and privacy policy.

X

Save your watchlist

Fill your details below to receive project updates from your watch list - including new versions, price changes and discounts.

I agree to the terms of use and privacy policy.

2 licenses, starting from From » $10.99 14 day money-back guarantee View Licenses
or Get a quote

for customization or integration services

  • Worked well and was fast.
    GC Graeme Cox
    2 years ago, 0 comments
    Was this helpful?
    Flag
  • Lacks boundary definition. A field of points is triangulated but there is no way to specify hole and exterior boundaries. Doesn't guarantee all points either, and no way to turn it on. Because of this, the code has limited utility. Source code was poorly formatted once imported.
    HG Herb Gilliland
    2 years ago, 0 comments
    Was this helpful?
    Flag
Post a comment

Or enter your name and Email
  • vincenzo panella Developer 2 years ago
    This library doesn't generates voronoi diagrams, its just the traingulator.
  • Simon Jackson 2 years ago
    Will this generate Voroni diagrams?
  • GC Graeme Cox License holderPersonal License 2 years ago
    Hi. Im looking for some code to triangulate some large terrain models with over 300,000 points. How long does your code take to triangulate say 300,000 points?
    • vincenzo panella Developer 2 years ago
      The Delaunay triangulation complexity is O(n⌈d / 2⌉) where n is the number of points and d is the dimension , in this case d= 2 so you have O( n ), which is linear complexity. I think that triangulating 300,000 points would take approxx 2 mins.
    • GC Graeme Cox License holderPersonal License 2 years ago
      OK. Sounds good. Have you tested O( n ), which is linear complexity? Sounds a bit good to be true..
    • vincenzo panella Developer 2 years ago
      I am not inventing anything, complexity theory is well known for triangulator, to be sure , before replying, i have just checked in one of my books.