Browse
Code
for
All Platforms
in
All Categories
sorted by
Popular
• More ...
• More ...
• More ...
• More ...
• More ...
• More ...
• More ...
• More ...
• More ...

# Delaunay triangulator

Released 4 years ago , Last update 4 years ago

Delaunay triangulator class in C++

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 0int 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 );``````
4.0
• 5 1
• 4 0
• 3 1
• 2 0
• 1 0
2 Reviews

## Pricing

### 14-day money-back guarantee

##### \$10.99

• 1 application

• Can distribute binary products only

• Commercial use

2 licenses, starting from From » \$10.99

## Get A Quote

What do you need?
• Custom development
• Integration
• Customization / Reskinning
• Consultation
When do you need it?
• Soon
• Next week
• Next month
• Anytime

### Thanks for getting in touch!

Your quote details have been received and we'll get back to you soon.

Or enter your name and Email
• LG 1 week ago
does it work in 3D delaunay
• VP 3 weeks ago
#include <vector> #include <algorithm> #include <iostream>
• R 3 weeks ago
What libraries are to be included?
• VP 3 weeks ago
#include <vector> #include <algorithm> #include <iostream>