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

# Delaunay + Voronoi diagram generator

Released 4 years ago , Last update 4 years ago

Voronoi diagram generator with triangulation pre-computation.

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.

5.0
• 5 1
• 4 0
• 3 0
• 2 0
• 1 0
1 Reviews

## Pricing

### 14-day money-back guarantee

##### \$49.99

• 1 application

• Can distribute binary products only

• Commercial use

## 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
• PM 2 years ago
Thanks very much