I’m using an open source constrained delaunay triangulation library called jmescher for my true type font library. It can be found at Google Code Archive - Long-term storage for Google Code Project Hosting.

It is dependent upon two GPL libraries that can easily be removed. @louhy created https://github.com/hamersly/jDelaunay that can replace the javax.vecmath dependency.

The APFloat library doesn’t need to be replaced, there are, if memory serves, two methods in the Mesh class that need to be commented out and two that need a slight adjustment to account for the now missing methods. The two methods are only used when advanced precision is required which is only really necessary if you’re doing something like facial recognition.

This library only takes in a series of points and edges then triangulates them. It doesn’t account for holes or the fact that your desired result is concave. Holes will be filled in with triangles so you need a method to determine whether a particular triangle is inside or outside of your desired shape.

For me it wasn’t too hard, glyph contours in a true type font are read so that the ‘inside’ of the shape is to the right of the direction of travel. What I did was modify the `addConstraint`

method in the Mesh class of jmescher so that it would return the `HalfEdge`

created by adding the constraint and then maintained a list of the `HalfEdge`

constraints that I added. When triangulation was finished I determined what triangles were in the shape by looking at each constraint in the list and determining if the off-edge point in the associated triangle was to the right of the edge or not, if it was I added the `HalfEdge`

's triangle to the list of triangles to draw, if it wasn’t I added the `HalfEdge`

's ‘sibling’ traingle instead.

In jmescher you can get the three points of a triangle by looking at a `HalfEdge`

. Each `HalfEdge`

is defined by an origin point the the origin point of the next `HalfEdge`

. So a full triangle is defined as `HalfEdge.origin`

, `HalfEdge.next.origin`

and `HalfEdge.next.next.origin`

. For each `HalfEdge`

in my constraints the off-edge point is `HalfEdge.next.next.origin`

.

So what I did was create a class that defines a constraint edge:

```
private class Seg {
public final Point p1;
public final Point p2;
public HalfEdge he;
private Seg(Point p1, Point p2) {
this.p1 = p1;
this.p2 = p2;
}
/**
* Determines if the supplied point is on the right side of
* the line segment.
*
* @param p The point to check against.
* @return True if the point is on the right side otherwise false.
*/
public final boolean onRight(Point p) {
return (p2.x - p1.x) * (p.y - p1.y) - (p2.y - p1.y) * (p.x - p1.x) < 0;
}
/**
* Determines if the supplied point is on the segment.
*
* @param p The point to check against.
* @return True if the point is on the line segment otherwise false.
*/
public final boolean onLine(Point p) {
float ab = FastMath.sqrt(FastMath.sqr(p2.x - p1.x) + FastMath.sqr(p2.y - p1.y));
float ap = FastMath.sqrt(FastMath.sqr(p.x - p1.x) + FastMath.sqr(p.y - p1.y));
float pb = FastMath.sqrt(FastMath.sqr(p2.x - p.x) + FastMath.sqr(p2.y - p.y));
float result = ab - (ap + pb);
return (result >= 0) ? result < EPSILON : result > -EPSILON;
}
}
```

Whenever I created an edge while reading the contour I used this class with `p1`

as the starting point of the edge and `p2`

as the ending point, `he`

was set later when I added the constraint to the triangulation. Then I iterated over the list of `segs`

using the `onRight`

method to determine if the off-edge point of the triangle was on the right or left. In jmescher each `HalfEdge`

has a ‘sibling’ which is the opposite triangle, if the off-edge point was on the right, great, if not the ‘sibling’ triangle’s off-edge point was on the right.

I don’t know the format you’re using to get the points that define your shape, but I must assume there’s some method for determining where the ‘inside’ of the shape is in relation to the points you’re reading.

P.S. In regards to creating glyphs there’s quite a few more steps than just the above, such as looking for triangles inside the shape that don’t share an edge with the contour, looking for overlapping quadratic curve triangles and splitting them in two etc…