Tutorial Using Polygon Based Constraints
Under Construction -- Additions and Corrections Coming Soon
Sometimes when building a Delaunay Triangulation for a surface, it is useful to partition the data into distinct regions. For example, a terrestrial elevation surface could be divided into regions of distinct vegetation types such grassland and forest. Since information about the vegetation type would not be directly supported by the geometry of the triangulated mesh structure itself, a supplementary data representation would be required to give a complete picture of the surface. In Tinfour, this requirement is addressed by polygon-based constraints. Polygon-based constraints give applications the ability to embed metadata for bounded regions into the structure of the Delaunay Triangulation.
In this tutorial we will look at the Tinfour Application Programming Interface (API) and review some techniques for taking advantage of the region-constraints. But before we do, let's take a look at a couple of examples.
The picture below shows two examples of bottom-depth data for Africa's Lake Victoria. The panel on the left is a pure Delaunay Triangulation. The panel on the right is a Constrained Delaunay Triangulation in which the bottom depth sample points were supplemented with a polygon constraint based on the shoreline of the lake. The constraint allows the triangulation to include information about the true domain of the lake data. This technique was discussed at length in an earlier Wiki article. If you'd like to learn more about it, see Using the Delaunay to Compute Lake Volume.
Here's another example of geographic data. In this case, the triangulation is entirely derived from region constraints derived from the Natural Earth Data geopolitical map data.
While all the examples so far have used geographic data sources, the Delaunay has much broader applications than its use in Geographic Information Systems (GIS). Here's a completely different kind of example:
The Star graphic shown above will be the subject of our tutorial. You can find the code for it in the standard Tinfour source code distribution (see the file ConstraintStarDemo.java in the "demo" module). Here are the first few lines of code from the application:
// Define two lists, one to receive vertices, one to receive constraints
List<Vertex> vertices = new ArrayList<>();
List<IConstraint> constraints = new ArrayList<>();
// populate the elements to be added to the TIN
// 1) a grid of vertices
// 2) the constraint polygon in the form of a five-pointed star
// 3) the 5 wedge-shaped polygons bordering the star
// 4) a circular constraint enclosing the figure
//
addGrid(vertices);
addConstraintStar(constraints);
addConstraintWedges(constraints);
addEnclosingRing(constraints);
// initialize the TIN, populating it with the elements to be presented
tin = new IncrementalTin(1.0);
tin.add(vertices, null);
tin.addConstraints(constraints, true);
The image shows an example of a Delaunay Triangulation based on a grid of vertices into which some geometric forms (a star, a ring) have been embedded. The addGraph() method in the example code populates a list of vertices with the points for that grid. The other "add" methods add polygon-based constraints (regions) to a list of constraints. We'll look at these methods below. For now, observe that the lists of vertices and constraints are used as the vehicle for adding vertices and constraints to the Delaunay Triangulation constructed using the IncrementalTin class (the class named includes the acronymn TIN, which stands for "Triangulated Irregular Network").
One thing to note here is that the IncrementalTin class requires that vertices be added before constraints. In fact, once constraints are added to the IncrementalTin, it can no longer accept additional elements. This behavior is due to limitations in the current implementation and will be addressed in the future. For now, it is how the API has to be used.
Let's take a look at the first of the constraint-adding methods, addConstraintStar(). Here's the code:
// Define angles and dimensions for building the constraints.
// The notches in the star have a radius of 1 unit. The points have
// a computed radius of approximately 2.62 units.
final static double A6 = Math.toRadians(6);
final static double A18 = Math.toRadians(18);
final static double A36 = Math.toRadians(36);
final static double A72 = Math.toRadians(72);
final static double rNotch = 1.0;
final static double rPoint = rNotch * (cos(A36) + sin(A36) * tan(A72));
private void addConstraintStar(List<IConstraint> constraints) {
// the polygon is given in counter-clockwise order.
PolygonConstraint p = new PolygonConstraint();
p.setApplicationData(new Color(128, 255, 128)); // pale green
for (int i = 0; i < 5; i++) {
double a = A18 + i * A72;
double x = rPoint * Math.cos(a);
double y = rPoint * Math.sin(a);
Vertex v = new Vertex(x, y, 0, iVertex++); // a point
p.add(v);
a = A36 + A18 + i * A72;
x = rNotch * Math.cos(a);
y = rNotch * Math.sin(a);
v = new Vertex(x, y, 0, iVertex++); // a notch
p.add(v);
}
p.complete();
constraints.add(p);
}
The code defines a number of static variables for angles given in radians based on their corresponding measure in degrees. The vertices are given as alternating points and notches. The five-pointed star was selected as an example because it demonstrates that a contraint polygon can be non-convex, just as long as it is not self-intersecting. Thus, a five-pointed star is valid polygon. A figure eight is not.
The loop above produces each of the five points and five notches in sequence. When the PolygonConstraint instance is fully populated, a call to the complete method indicates that it is finished and instructs the class to performs some internal bookkeeping related to the constraints geometry. At that point it is ready to be added to the list of constraints.
Note also that a Java Color object was added to the constraint as "application data". In Tinfour, all constraint implementations support the use of optional application data. This data can be anything that the application wishes to use. It could be an instance of a complex class containing several metadata elements, or it could be something much simpler, such as the single color specification used in this example. For the ConstraintStarDemo class, the image-rendering operation uses the application data elements to set the color for each triangle embedded in a region constraint. I'll have more to say about rendering later in this article.
In addition to the five-pointed star constraint, the demonstration application also produces 5 circular wedge polygons that fit neatly into each notch of the star. These constraints are created in the addConstraintWedges() method. Although I won't include it here, the code for creating the wedges is very similar to that which creates the star. There's a good reason for that similarity. Tinfour does not permit polygon constraints to overlap, but it does allow them to share common edges provided that the vertices that form those edges have identical coordinates. It is critical that application code honors this requirement if it is to be successful in its creation of adjacent contrained regions. Thus, in the demonstration application, the arithmetic for creating the Cartesian coordinates for the vertices that define common edges is identical.
Refering to the illustration of the star figure above, note that there is a thin black line marking the edges of all the constraint polygons. In Tinfour, edges in the Delaunay Triangulation carry information about any contraints with which they are associated. They also know whether an edge is the border of a constraint region or if it is one of the interior edges. The image-rendering code included in the demostration application uses that information about constraints to determine color.
You may have noticed that in the addConstraintStar() method, the code for creating the five-pointed star produced vertices in a counter-clockwise order. This ordering reflects a very important point about region constraints. Tinfour assumes that the region defined by a polygon-based constraint lies immediately the the left of the edges on its border. So, when we visualize the construction of a polygon taken in counter-clockwise order, it becomes apparent that the area to the left of each edge lies in the interior of the polygon.
So what happens when a polygon is constructed in clockwise order? The region defined by the constraint lies to the left of each edge, but the interior of the polygon lies to the right. So the interior of the clockwise polygon does not belong to a constrained region. In effect, the constraint defines a "hole" in that region.
This fact was used to advantage in creating the pale green ring surrounding the star. The outer circle of the ring is given in counter-clockwise order, so the triangles immediately inside it are color-filled according to the Java Color object supplied by its application data. But the inner circle is given in clockwise order. Thus it serves to limit the extent of the filled area.
The image rendering for the five-pointed star was designed to illustrate how information about the polygon-based regions embeded in a Constrained Delaunay Triangulation could be extracted using the Tinfour API. As I mentioned above, edges in a Tinfour triangulation can carry information about the constraints with which they are associated. In the example triangulation, not all the edges carry such information. There are 4464 edges that are associated with the polygon constraints (either on the borders or in their interiors). But 3586 edges that have no association. When Tinfour builds triangles from these edges, it can extract information about the edge-to-constraint relationships and know whether the triangles themselves should carry a reference to a constraint.
To render the color-filled triangles, we take advantage of Tinfour's versatile TriangleCollector implementation. A detailed discussion of this implementation is given in the Tinfour Wiki article Tutorial Using TriangleCollector Techniques. The TriangleCollector depends on an application to provide an implementation of a Java "Consumer" that accepts objects of Tinfour's SimpleTriangle class. This arrangement is actually much easier to explain with code than describe in writing. So here's the code for the Consumer in the Constraint Star Demo application:
static class TriangleRenderer implements Consumer<SimpleTriangle> {
final Graphics2D g2d;
final AffineTransform af;
TriangleRenderer(Graphics2D g2d, AffineTransform af) {
this.g2d = g2d;
this.af = af;
}
@Override
public void accept(SimpleTriangle t) {
IConstraint constraint = t.getContainingRegion();
if (constraint != null && constraint.definesConstrainedRegion()) {
Object obj = constraint.getApplicationData();
// The application data should always be a color object.
// But this code checks the type anyway.
if (obj instanceof Color) {
g2d.setColor((Color) obj);
Path2D path = t.getPath2D(af);
g2d.fill(path);
g2d.draw(path);
}
}
}
}
The constructor for the TriangleRenderer accepts a Java Graphics2D element and an AffineTransform. The transform is used to map the Cartesian coordinates for the triangles to the pixel coordinates for the output image.
In the main body of the image-rendering logic, the triangle renderer is constructed and passed to the TriangleCollector as shown below:
TriangleRenderer triangleRenderer = new TriangleRenderer(g2d, af);
TriangleCollector.visitSimpleTriangles(tin, triangleRenderer);
The visitSimpleTriangles method constructs a SimpleTriangle instance for each triangle defined by the Triangulated Irregular Network (TIN). These triangle objects are passed into the TriangleRenderer's accept() method, which extracts constraint information and renders the triangle in the appropriate color. Those triangles that do not have constraint regions are not drawn.
In the discussion above, I mentioned that the borders of the constraints are drawn in black. Here's the loop for drawing edges:
g2d.setColor(Color.black);
for (IQuadEdge e : tin.edges()) {
if (e.isConstrainedRegionBorder()) {
e.setLine2D(af, l2d);
g2d.draw(l2d);
}
}
Although the demonstration code presented in this tutorial does not get constraint directly from Tinfour edge objects, it is possible to do so. To understand the rationale for the API that supports edge-to-constraint references, it is useful to remember that Tinfour was designed to support TIN structures containing a very large number of vertices with a correspondingly large number of edges. Because of that, the design of the edge classes themselves are very lean. Thus the internal logic for extracting constraint references is somewhat indirect and requires the participation of the IncrementalTin instance itself. Here are some example code snippets showing how it is done:
// To get the constrained region to the left of an edge
if (e.isConstrainedRegionBorder()) {
IConstraint constraint = tin.getRegionConstraint(e);
}
// To get the constrained region to the right of an edge,
// you must use the edge's dual
IConstraint constraint = tin.getRegionConstraint(e.getDual());
// If the constraint is in the interior of a region, then
// both sides of it will have the same constraint
if (e.isConstrainedRegionInterior()) {
IConstraint constraint = tin.getRegionConstraint(e);
}