RoseDelaunay2D Class

Overview

The RoseDelaunay2D class is a helper class that computes a Delaunay triangulation for a set of 2D planar input points. The STEP and IFC faceting libraries use this capability in UV space to create well-behaved meshes.

With a Delauay triangularization, you can draw a circle with the three vertices of a triangle on the perimiter and there will be no other vertex in the mesh inside of the circle.

RoseReal2DArray points;
points.append(10, 10);
points.append(10, 16);
points.append(16, 20);
points.append(22, 10);

RoseBoundingBox2D bb;
RoseDelaunay2D dt;
unsigned i,sz;

// get polygon bounds and initialize
bb.update(points);
dt.init (&bb);

// insert and get index of initial point
unsigned base = dt.insertPoints(points);

// connect the points as a single poly
dt.insertEdge(base+0, base+1);
dt.insertEdge(base+1, base+2);
dt.insertEdge(base+2, base+3);
dt.insertEdge(base+3, base+0);  // close

dt.resolveInside();

for (i=0, sz=dt.getTriangleCount(); i<sz; i++)
{
    const double * pt;
    unsigned v[3];
    dt.getTriangle(v,v+1,v+2, i);

    if (!dt.isInside(i)) continue;

    pt = points.get(v[0]-base);
    printf (%g %g\n, pt[0], pt[1]);

    pt = points.get(v[1]-base);
    printf (%g %g\n, pt[0], pt[1]);

    pt = points.get(v[2]-base);
    printf (%g %g\n, pt[0], pt[1]);
    printf (\n);
}

When run, this program will load the Delaunay class with points for a simple polygon and print the result, which will have two triangles.

getEdgeCount()

unsigned getEdgeCount();

The getEdgeCount() function returns the number of edges in the triangulazation.

getEdgeTriangle()

unsigned getEdgeTriangle(
        unsigned edge_idx, 
        unsigned tri_idx
);

The getEdgeTriangle() function returns one of the triangles on an edge. Each edge has at most two triangles on it. The edge_id parameter is the edge being queried, and tri_idx is either 0 or 1 to identify which triangle of the edge to return.

getEdgeVertex()

unsigned getEdgeVertex(
        unsigned edge_idx, 
        unsigned v_idx
);

The getEdgeVertex() function returns one of the vertices that define an edge. Each edge consists of 2 vertices. The edge_id parameter is the edge being queried, and v_idx is either 0 or 1 to identify which vertex of the edge to return.

getPointCount()

void getPointCount()

The getPointCount() function returns the number of points in the delaunay mesh.

getTriangle()

void getTriangle(
	unsigned *v1,
	unsigned *v2,
	unsigned *v3,
	unsigned idx
	);

The getTriangle() function fetches the three vertices of a triangle. Pointers to three unsigned integer variables are the first parameters and the index of the triangle is the last parameter.

getTriangleCount()

unsigned getTriangleCount();

The getTriangleCount() function returns the number of triangles defined for the set of points.

getTriangleEdge()

unsigned getTriangleEdge(
        unsigned tri_id, 
        unsigned e_idx
);

The getTriangleEdge() function returns an edge os a triangle. Each triangle consists of 3 edges. The tri_id parameter is the edge being queried, and v_idx is either 0, 1, or 2 to identify which edge to return.

getTriangleVertex()

unsigned getTriangleVertex(
        unsigned tri_id, 
        unsigned v_idx
);

The getTriangleVertex() function returns an edge os a triangle. Each triangle consists of 3 vertices. The tri_id parameter is the edge being queried, and v_idx is either 0, 1, or 2 to identify which vertex to return. This provides the same functionality as the getTriangle() method.

init()

int init(
	RoseBoundingBox2D * bbox,
	double aspect=1.
	);

The init() function sets the initial bounding space for the triangularization. All inserted points must lie within this space. The aspect ratio is a multiplier for the V dimension when working in UV space where the two dimensions do not map equally to XYZ space. The function returns zero on error and nonzero on success.

insertEdge()

int insertEdge(
	unsigned p1,
	unsigned p2
	);

The insertEdge() function adds an edge to the triangulization. This forces the given edge to appear in the triangulization, and it will not be crossed by another edge. The function returns zero on error and nonzero on success.

insertPoint()

unsigned insertPoint(const double uv[2]);
unsigned insertPoint(const RosePoint2D& uv);

The insertPoint() function adds a vertex to the triangularization. The mesh is recomputed to accommodate the new point and edges may be flipped during this process. The function returns the index of the vertex which should be used when specifying edges with insertEdge() and which will be returned by later calls to getTriangle()

It is important to note that the first vertex that you insert will not have an index of zero. Initializing the class will insert a triangle large enough to contain all possible points, so your vertices will start after those points.

insertPoints()

unsigned insertPoints(const RoseReal2DArray& pts);

The insertPoints() function takes a 2D point array as a parameter and inserts all points sequentially usinng insertPoint(). It returns the index of the first element (pts[0])

isInside()

int isInside(unsigned fi);

The isInside() function takes a triangle index and returns true if that triangle appear outside of the edges that were defined by insertEdge(). The resolveInside() function must be called once before any calls to this function.

Initializing the class will insert a triangle large enough to contain all possible points, and this triangle may later be split by your points. You must test with this function to eliminate any extra triangles that do not belong to your polygon.

resolveInside()

int resolveInside();

The resolveInside() function is called after inserting the edges with insertEdge(). It resolves the facets that are inside vs outside the edges.