# Delaunay + Voronoi diagram generator

Voronoi diagram generator with triangulation pre-computation.

• Language: C/C++
• Released: Jul 2, 2011
Last Update: Jul 2, 2011

This single include file will first triangulate then compute a voronoi diagram decomposition from an unordered set of points in bi-dimensional space. The voronoi diagram is an important method for game development for map generation, navigation, influence map computation and more. It is also used as a biology simulator for bacteria growth simulation.

This class is very simple to use - create a random set of points then pass them to the class like this

``````// this will triangulate the points set

T.Triangulate( Px,Py,N );

// this will compute the voronoi diagram
T.Voronoi();``````

Assuming you are working under mfc, to trace the diagram you will need to have low level access to the data structure. For example:

``````void DrawPoly( CDC *pDC,int i ,COLORREF &c,COLORREF& b )
{
const DELAUNAYVERTEX* VertexPtr=T.GetVertexPtr();
const DELAUNAYTRIANGLE* TrianglePtr=T.GetTrianglePtr();

int p1,p2,p3;
CPoint pts[3];

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

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

// and a solid red brush
CBrush brushRed(c);
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);

}

void Rend(CDC *pDC)
{

int i,j;

for ( i=0; i::iterator it;

for ( i=0; iSelectObject(&penBlue);
for ( i=0; i<(int)CellPtr[j].p.size()-1; i++ )
DrawLine( pDC,(int)CellPtr[j].p[i].x,(int)CellPtr[j].p[i].y,(int)CellPtr[j].p[i+1].x,(int)CellPtr[j].p[i+1].y,&penBlue );
DrawLine( pDC,(int)CellPtr[j].p[i].x,(int)CellPtr[j].p[i].y,(int)CellPtr[j].p[0].x,(int)CellPtr[j].p[0].y,&penBlue );
pDC->SelectObject(pOldPen);
DrawPoint( pDC,(int)CellPtr[j].cx-2,(int)CellPtr[j].cy-2,col2 );
}``````

Is important to call the functions in order. If you want only triangulation there is no need to call the vonoroi computation, but if you need the vonoroi diagram you need to triangulate first.

Plus you have access to adjacency data structures, for each point is stored the triangle it belongs to and for each triangle which triangle is adjacent. This class doesn't use the Fortune's code for vonoroi computation it obtains from the delaunay triangulator on the fly.

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.

1 license From » \$49.99 14 day money-back guarantee
or

for customization or integration services

• Does exactly what it describes and is very easy to integrate and use. Two function calls is enough to turn a set of random points into a Voronoi diagram which can be accessed by individual Voronoi cells; very useful for map generation.
SJ Simon Jackson
2 years ago, 0 comments
Was this helpful?
Flag

Or enter your name and Email
• PM 1 year ago
Thanks very much
• License holderPersonal License 2 years ago
Thanks very much. After looking at other solutions, such as Voro++ (and finding out it doesn't do 2d), this seemed like a good solution as I only wanted something small which could return the Voronoi cells. Will rate it once I've tried it
• Developer 2 years ago
You can buy the single user version and since its basically yours , i cannot stop you from using into a commercial package. I don't know if i am going against Binpress rules, but you have my permission , just give me some credits if you like ;-).
• KW 11 months ago
Would it be possible to hire you to make a constrained Delaunay triangulation? I would have no objections to you sharing or selling the code later. Please contact me if you are interested.
• Developer 11 months ago
Hello Keith , the library you are looking for has been already developed and its free of charge, its called poly2tri , there is also Triangle, right now in this moment i am working on a project for a contractor and i have used the poly2tri its excellent and very robust.