Abstract

Aiming at Delaunay triangulation with islets constrains in terrain simulation. A general Delaunay triangulation algorithm for constrained data set with islets is proposed. The algorithm firstly constructs Constrained Delaunay Triangulation with constraint polygons which are inner boundary of islets, then according to topological relations within edge, surface, arc segment, applies bidirectional search to find the triangle in islet, lastly it carries on certain corresponding processing to complete the Delaunay triangulation algorithm with islets. The analyses show the algorithm simple, fast speed. The algorithm can be used in 3-D terrain vision.

1. Introduction

The triangulation has a wide range of applications in the GIS, geology, computer graphics, virtual reality and so on. Delaunay triangulation has the most performance in the terrain simulation. The build Delaunay triangulation technology taking into account the mandatory constraint data in the establishment of high-quality DEM played a decisive role [1]. At present, based on the points, line segments constrained, the Delaunay triangulation (CDT) has been a lot of algorithms. But the triangulation with the islets constrained data field, due to the complex of data constraint, it is necessary to satisfy the constraints and the characteristics of Delaunay triangulation, so the algorithm with great difficulty [2,3]. The existing triangulation algorithm needs to determine the convex-concave of nature polygon, or using connect bridge technology, the algorithms or more complex, or the result is not Delaunay triangulation [4-8]. This paper proposes an algorithm solution to the islets constrained, the algorithms is simple, without determine the convex-concave of polygon and geometric intersection Computing.

2. With Islets Constrained Triangulation Algorithm

2.1. The Basic Concept of the Islets

Anyone of islet can be abstracted into polygon (convexconcave polygon). The line of Constituted polygonal called arc, polygon composed by arc is Islet, polygon does not contain islet called a simple polygon, is single-connected region, the polygon with islet called compound polygon, is complex connected region. In the complex connected region, including the outer boundary and inner boundaries, the islet polygon is inner boundary. The Polygons with islets was defined as follows: Set P₁, P₂, ..., P_n (n > 1) are simple polygon, if the degrees of all vertex of P_i (i = 1,2, ..., n) is 2, the edges without common vertex do not intersect, and one of polygons (set P_j, 1 ≤ j ≤ n) included  all the other polygons, then the polygon composed by P₁, P₂, ..., P_n is called islet polygons (shown in Figure 1), P₁ is called the outer polygon, the other is called the inner polygon (islet or hole) [7].

Triangulation with islets constraints is build delaunary triangulation between the islets and outer boundary that is with islets.

2.2. Classic Triangulation Algorithm with Islets Constraints

For the Delaunay triangulation algorithm with islets constrained, according to occasion of islets constrained data embedded, can be divided into the following categories:

1) Taking into account the impact of islets In the Delaunay triangulation, directly build Delaunay Triangulation with islets constraint. Such as the Triangulation algorithm with islets constrained data fields proposed by Liu Shao-Hua [4].

2) First, without considering islets constraints, building Delaunay triangulation with all the vertex of islet polygons and edges constraints, then delete the triangles within constraints fields. Such as Reference [7,8]. These algorithms are simple, compatible with non-constrained Delaunay triangulation.

3. Improvement of Delaunary Triangulation with Islets Constraints

3.1. Algorithm Theory

Two-dimensional Delaunay triangulation with islets constrained is described as: For the plane field D (P, Q), it containing a set of points P and Q, Q = {Qi ∈ D|I = 1, n2} is a points set that distributed in the boundary of islets, if a triangulation of the point set P, Q is a Delaunay triangulation (DT), delete the triangle within the islets, then it is a Delaunay triangulation with islets constrained on the plane field D (P, Q) [8].

Based on the above principle, we can build Delaunay triangulation with islets constrained step by step. First, without considering the nature of boundary points of islets, building Delaunay triangulation with the P and Q, then embedding edge constraint, the edges constrained are boundary line segment of islets, shown in Figure 1. Finally we found all the triangles inside the islets, according to need to be deleted, or retained. Based on the relationship between edges and triangles, this paper proposed a bi-directional search method and found all the triangles inside island, in order to complete with island constraints DT division.

3.2. Data Structure

According to the algorithm needs to establish topological relations among point, line, surface, and arc. This data structure can preferably establish topology data model of triangular mesh, and can be quickly index at the point, edge, triangle, and arcs. The algorithm is program with the Java, The data structure is as follows:

1) The point class:

public class Point{//class Point public double x, y, z;

}

2) The edge class:

In order to finding two triangles that hane one and the same edge quickly, so the class has the two neighbor triangles.

Public class Edge {//Edge private int [] pointNum = new int[2]

//the point number private Triangle [] tri = new Triangle[2];

//Edges corresponding to two adjacent triangles private boolean constrainEdge = false;

//is it binding edge

}

3) The triangle class:

In order to finding the edge of the triangle quickly, so the class has the three edges.

Public class Triangle {//class Triangle private int [] pointNum = new int [3];

//Triangle of three dots private Edge [] edge = new Edge [3];

//Side of the object created by the three Edge

}

4) The islet class:

Storages a list of all inner border line segment of islet, according to counter-clockwise storages.

Public class IsletArea {//Islet Class private List Pointlist = new LinkedList ();

//the Island of arc

}

5) The Islets influence field class:

The internal class, record the edge within islet, and a known triangle in a side of the edge a.

private class IsletDomain {

private Edge e; //Islands within the affected side of private Triangle tri; //Islandsthathey affect a certain edge e adjacent to a known triangle

}

Considering the deleted or retained the triangle within Islands, in the algorithm, there is a list that stores the triangular within islet.

3.3. Algorithm Implementation

Assume all the arcs that surround the inner border of islets are counter-clockwise order, so the left side of closed arcs is within the islets, the right is exterior the islet, the triangle on the left of the arcs fall within the islet. The key of algorithm is to find the triangle within the islet, based on the relationship between the edges and the triangle, from a known triangle and a triangle edge start to expend the other two edges of the known triangle and the adjacent triangle both sides, until the find all the triangles within the islets, the steps are as follows:

1) Doing Delaunay triangulation for the islets boundary points and the other discrete points within the plane.

2) All the borders of the islets are as line segment constraints, embedded in the Delaunay triangulation, carried out Delaunay triangulation with constraints, stored line segment constraints into constraint edge list.

3) Order all line segment constraints in the constraint edge list by counter-clockwise.

4) Pick-up any inner boundary arc (edge) e from anyone  islets, and two triangles both sides e, to find the left side triangle t from these two triangles, building a new IsletDomain object with e and t, push it into the stack. Modify the topology of e, set the reference (pointer) of e and t to null.

5) Pick-up the top element of the stack, that is a IsletDomain object. Store the member triangle of IslandDomain, tri, into triangle within islets list, and pick-up the other two side edges of the tri, from the two direction to search, there are three situation:

•Two edges are not in the constraint edge list;

•one edge is the constraint edge list, another edge is not in the constraint edge list;

•Two edges are in the constraint edge list.

For three cases, if the edge is in the constraint edge list, looking for adjacent triangle of the edge, building the IsletDomain object, push stack; if the edge is not in the constraint edge list, modify the topology of the edge, set the reference (pointer) of the triangle that pointed to by tri to null.

6) Redo step 5, until the stack is empty.

7) According to the needs, delete or retain elete the triangles in the triangle within islets list.

Based on the above steps, the flow chart of Delaunay triangulation with island constraint is Figure 2.

Based on the above steps to complete Delaunay triangulation with islets constrained, the result shown in Figure 3.