-
Notifications
You must be signed in to change notification settings - Fork 8
Home
Welcome to the Developer documentation!
jDelaunay is a library written in Java, dedicated to the computing of a mesh that respect the Constrained Delaunay Triangulation properties. It is designed to process the triangulation by processing each input point only once. This page is not intended to describe the algorithms in the details.
This shows how to work with jDelaunay, and how to use it given a set of input vertices and constraint edges.
jDelaunay processes a triangulation, given a set of input point and edges (referred to as constraints in the following). The operation is made in a class named ConstrainedMesh in the package org.jdelaunay.delaunay. you can instanciate a ConstrainedMesh object really easily:
ConstrainedMesh mesh = new ConstrainedMesh();Once this is done, you'll be able to fill the mesh with the input you want to use for the triangulation. If you want to add a constraint edge ed, you can do:
mesh.addConstraintEdge(ed);The edge will be automatically marked as locked, and won't be modifiable during the computation of the mesh.
If you want to add a list of edges in a single operation, you can use the following method:
public final void setConstraintEdges(ArrayList<DEdge> constraint) throws DelaunayError;Whatever the method you use, duplicates in the input will automatically be removed.
The points that define a constraint edge are automatically added to the list of input points.
To add an input point, just use:
public final void addPoint(DPoint point) throws DelaunayError;Here again, duplicates are automatically forgotten while performing this operation.
The efficiency and the correctness of the triangulation will be strongly linked to the quality of the data you use as an input. Indeed, the inputs you use must respect the following property:
- If two input edges intersect, then the intersection point must be an extremity of both edges !
If you don't ensure beforehand that this property is true, then the triangulation will certainly fail. However, jDelaunay provide a method that will try to compute intersections between the edges you want to use as constraint:
public final void forceConstraintIntegrity() throws DelaunayErrorThis method will compute the intersection between the input edges (but not the points, be careful!!!), using the sweep line algorithm. Currently, the implementation still fails to recognize intersection of nearly colinear edges. Use with care, consequently, and remember that this is just a convenient tool, and not the main function of this library ;-).
Once you've filled your input, you're ready to perform the triangulation. Just run :
mesh.processDelaunay();to do that.
The (summarized) underlying mechanism is the following :
- Points are sorted and added one by one.
- When inserting a new point, a visibility test is made to only create the needed triangles.
- When adding triangles, some triangle inversions are made using an algorithm really close to the flip-flap algorithm.
The generated mesh can be retrieved once computed. It is stored in three (or four, if some constraint edges have been used) parts. Triangles, Edges and Points can be retrieved using the following methods:
/**
* Get the points contained in this mesh
* @return
*/
public final List<DPoint> getPoints()
/**
* Get the list of triangles already computed and added in this mesh
* @return
*/
public final List<DTriangle> getTriangleList()
/**
* Get the list of edges
* @return
*/
public final List<DEdge> getEdges()You can still retrieve the input constraint edges by using the following method:
/**
* Get the list of edges that are used as constraints during triangulation
* @return
*/
public final List<DEdge> getConstraintEdges() Note that the set returned by this last method can differ from the one you gave as input before processing the triangulation. Indeed, if you've used forceConstraintIntegrity, and if intersections have been found, what you obtain here is the result of the intersection computation.
jDelaunay is currently just a library, and is designed to be used along greater projects, dedicated for example, to data manipulation. Here is an example of use with Gdms, the data management layer from the OrbisGIS project:
public class Benchmark {
public static DataSourceFactory dsf = new DataSourceFactory();
public static String path = "src/main/resources/chezinecourbe3D.shp";
private static String target = "target/out.gdms";
private static String targetPoints = "target/outPoints.gdms";
private static String targetConstraints = "target/constraints.gdms";
public static void main(String[] args) throws DriverLoadException,
DataSourceCreationException, DriverException, DelaunayError,
ParseException, IOException, NonEditableDataSourceException {
long start = System.currentTimeMillis();
ConstrainedMesh aMesh = new ConstrainedMesh();
aMesh.setVerbose(true);
DataSource mydata = dsf.getDataSource(new File(path));
SpatialDataSourceDecorator sds = new SpatialDataSourceDecorator(mydata);
sds.open();
//We retrieve the data in the input file.
int z;
ArrayList<Edge> toBeAdded = new ArrayList<Edge>();
for (long i = 0; i < sds.getRowCount(); i++) {
Geometry geom = sds.getGeometry(i);
for (int j = 0; j < geom.getNumGeometries(); j++) {
Geometry subGeom = geom.getGeometryN(j);
if (geom.isValid()){
Coordinate c1 = subGeom.getCoordinates()[0];
Coordinate c2;
for (int k = 1; k < subGeom.getCoordinates().length; k++) {
c2 = subGeom.getCoordinates()[k];
toBeAdded.add(new Edge(new Point(c1), new Point(c2)));
c1 = c2;
}
}
}
}
//We perform a first sort to gain time during the insertion.
Collections.sort(toBeAdded);
aMesh.setConstraintEdges(toBeAdded);
sds.close();
//We force the integrity of the constraints given as an input.
aMesh.forceConstraintIntegrity();
//We perform the triangulation
try{
aMesh.processDelaunay();
}catch(Exception e){
}
//We write the triangles in a GDMS output file
File out = new File(target);
if(out.exists()){
out.delete();
}
out = new File(target);
GdmsWriter writer = new GdmsWriter(out);
Metadata md = new DefaultMetadata(new Type[] {TypeFactory.createType(Type.GEOMETRY),
TypeFactory.createType(Type.FLOAT)}, new String[] {"the_geom","Z"});
int triangleCount = aMesh.getTriangleList().size();
writer.writeMetadata(triangleCount, md);
GeometryFactory gf = new GeometryFactory();
Double midZ;
for(DTriangle dt : aMesh.getTriangleList()){
midZ = dt.interpolateZ(dt.getBarycenter());
Coordinate[] coords = new Coordinate[4];
coords[0] = dt.getPoint(0).getCoordinate();
coords[1] = dt.getPoint(1).getCoordinate();
coords[2] = dt.getPoint(2).getCoordinate();
coords[3] = dt.getPoint(0).getCoordinate();
CoordinateSequence cs = new CoordinateArraySequence(coords);
LinearRing lr = new LinearRing(cs, gf);
Polygon poly = new Polygon(lr, null, gf);
MultiPolygon mp = new MultiPolygon(new Polygon[] {poly}, gf);
writer.addValues(new Value[] {ValueFactory.createValue(mp), ValueFactory.createValue(midZ)});
}
// write the row indexes
writer.writeRowIndexes();
// write envelope
writer.writeExtent();
writer.close();
//We write the output points in a GDMS file.
File outPoints = new File(targetPoints);
if(outPoints.exists()){
outPoints.delete();
}
outPoints = new File(targetPoints);
GdmsWriter writerb = new GdmsWriter(outPoints);
md = new DefaultMetadata(new Type[] {TypeFactory.createType(Type.GEOMETRY)}, new String[] {"the_geom"});
int pointCount = aMesh.getPoints().size();
writerb.writeMetadata(pointCount, md);
gf = new GeometryFactory();
for(DPoint dt : aMesh.getPoints()){
Coordinate[] coords = new Coordinate[1];
coords[0] = dt.getCoordinate();
CoordinateSequence cs = new CoordinateArraySequence(coords);
com.vividsolutions.jts.geom.Point mp = new com.vividsolutions.jts.geom.Point(cs, gf);
writerb.addValues(new Value[] {ValueFactory.createValue(mp)});
}
// write the row indexes
writerb.writeRowIndexes();
// write envelope
writerb.writeExtent();
writerb.close();
We write the constraint edges in a GDMS file
File constraints = new File(targetConstraints);
if(constraints.exists()){
constraints.delete();
}
constraints = new File(targetConstraints);
writerb = new GdmsWriter(constraints);
md = new DefaultMetadata(new Type[] {TypeFactory.createType(Type.GEOMETRY)}, new String[] {"the_geom"});
int cstrCount = aMesh.getConstraintEdges().size();
writerb.writeMetadata(pointCount, md);
gf = new GeometryFactory();
for(DEdge dt : aMesh.getConstraintEdges()){
Coordinate[] coords = new Coordinate[2];
coords[0] = dt.getPointLeft().getCoordinate();
coords[1] = dt.getPointRight().getCoordinate();
CoordinateSequence cs = new CoordinateArraySequence(coords);
LineString mp = new LineString(cs, gf);
writerb.addValues(new Value[] {ValueFactory.createValue(mp)});
}
// write the row indexes
writerb.writeRowIndexes();
// write envelope
writerb.writeExtent();
writerb.close();
}
}As the main objective is to represent a terrain in two dimensions and to use this representation to make hydrology processing, we must work with a topographically coherent mesh. Consequently, we don't want to have flat triangles in the TIN. To delete these triangles, you can use the removeFlatTriangles method:
/**
* This operation remove the flat triangles by inserting new points in the mesh,
* that come from the skeleton of the already computed mesh.
* This method must be used after a previous call to processDelaunay().
* This method will compute a triangulation again - the insertion is not incremental.
* @throws DelaunayError
*/
public final void removeFlatTriangles() throws DelaunayError