DOCSEARCHbyAlgolia
Submit Docs

DelaBella C++ Library

repository·master·Indexed 42 days ago

https://github.com/msokalski/delabella

A C++ library for high-performance, exact 2D Delaunay triangulation, featuring support for Voronoi diagrams, constrained triangulations, and interior/exterior detection using adaptive-exact predicates for geometric robustness.

Tokens
764
Snippets
2
Records
3
Agent score
4%

What's inside DelaBella

  1. Overview of DelaBella capabilities

    master

    DelaBella is a library for 2D exact Delaunay triangulation. It utilizes adaptive-exact predicates to ensure geometric robustness.

    Key features include:

    • Delaunay triangulations
    • Voronoi diagrams
    • Constrained Delaunay triangulations
    • Interior / exterior detection based on constraint edges

  2. Perform 2D Delaunay triangulation with DelaBella

    master

    To perform a triangulation, use the IDelaBella2<T>::Create() factory method to instantiate the engine. You then call Triangulate by providing the number of points and pointers to the X and Y coordinate arrays.

    Workflow:

    1. Define a coordinate type (e.g., double).
    2. Prepare your point cloud in a contiguous memory layout where X and Y coordinates are accessible via offsets.
    3. Call Triangulate(num_points, x_ptr, y_ptr, stride).
    4. If the return value is greater than 0, use GetNumPolygons() to get the triangle count and GetFirstDelaunaySimplex() to iterate through the resulting triangles.
    5. Use Destroy() to clean up the engine instance.
    #include "delabella.h"

int POINTS = 1000000;
typedef double MyCoord;

struct MyPoint
{
	MyCoord x;
	MyCoord y;
};

MyPoint* cloud = new MyPoint[POINTS];
// ... populate cloud ...

// Create the engine
IDelaBella2<MyCoord>* idb = IDelaBella2<MyCoord>::Create();

// Perform triangulation
// Returns number of vertices if successful, else <= 0
int verts = idb->Triangulate(POINTS, &cloud->x, &cloud->y, sizeof(MyPoint));

if (verts > 0)
{
	int tris = idb->GetNumPolygons();
	const IDelaBella2<MyCoord>::Simplex* dela = idb->GetFirstDelaunaySimplex();
	for (int i = 0; i < tris; i++)
	{
		// Access triangle data via dela
		dela = dela->next;
	}
}

// Cleanup
delete[] cloud;
idb->Destroy();

  3. Iterate through Delaunay simplices

    master

    Once Triangulate succeeds, you can traverse the resulting triangulation using a linked-list style pattern.

    1. Call GetFirstDelaunaySimplex() to obtain a pointer to the first Simplex object.
    2. Access the next simplex in the sequence using the next member pointer.
    3. Continue until next is null or you have reached GetNumPolygons() count.
    const IDelaBella2<MyCoord>::Simplex* dela = idb->GetFirstDelaunaySimplex();
for (int i = 0; i < tris; i++)
{
    // Use dela
    dela = dela->next;
}