et al, 
56 and 
hat the 
leaves. 
points 
nted in 
; Q that 
Ve have 
> vertex 
will lay 
al. The 
nax(a) 
(1) 
  
  
Antonio Ruiz 
  
34 Robustness 
During the computation of the Delaunay triangulation there appear two geometric predicates that we have to evaluate 
accurately. They are related to two degenerate cases of the points distribution. The first predicate tests the orientation of 
a point respecting to an oriented edge. One point can be to the left or to the right of an oriented edge or, in the degenerate 
case, the three points can be inline. 
The second predicate is named the incircle test. Given a triangle of the triangulation there is a circle that passes through 
its three vertices. A point of the plane can be in the interior of the curcumcircle or out of it. In the degenerate case the 
four points can be cocircular. Both tests can be put in the form of a determinant and the result of the test depends on the 
sign of this determinant. 
0s oly d 
Orient2d(a, b,c) =| b, by 1 (2) 
69 utl 
e Cy Cp TC. 
S p) 
d, d, d;-t d; 
r 
a; y az + ar 1 
SL) 
Incircle(a,b,e,d) = by i bt : (3) 
1 
We do not need to evaluate these determinants exactly. We only need to be confident on its sign. Only in case the value is 
close to zero the result of the computation is unreliable. We need to evaluate the error of the computation and increase the 
number of bits of the computation arithmetic when the absolute value of the determinant is smaller that the computational 
error. We follow the adaptative precision algorithms by Shewchuck (Shewchuk, 1996a, Shewchuk. 1996b). 
35 Refinable model and programming 
We have programmed in C++. In object oriented (OO) programming a class consists of the data structures and its associ- 
ated methods. The main classes we have defined correspond to the geometric objects we manipulate: point, vertex, DCEL 
edge, TIN, PR-quadtree node, face... We distinguish always an active edge and one active side that is to the left or to the 
right of this active edge. We have methods to change these active objects. There are methods to move the active edge to 
the next or to the previous edge around the origin or destination vertex of the current active. There are also iterator classes 
that allow to traverse the triangulation in different ways. One iterator class allows traversing all the edges and vertices 
interior to a polygon. Another can follow the edges that cross an oriented segment. There is a cursor class to represent 
one active edge with its active side. We have not a triangle class. A triangle can be identified by the left or the right of one 
of its boundary edges and can be represented with a cursor. Programming has been done following Meyer's programming 
by contract paradigm (Meyer, 1997). Most methods have preconditions and some of them have postconditions that have 
been really helpfull to detect programming bugs. 
With object-oriented programming the surface model can be extended and refined easily. The default surface model is 
the polyhedrical surface formed by flat triangles. Usually the triangles are not stored and the edges hold void pointers to 
triangular faces. In case a different surface model is required we attach this surface model to the triangular faces. The 
edge pointers to face are then used and the attached face object provides an alternative height function different from the 
height that corresponds to the flat triangle. Some faces we have defined are the exterior face that returns unknown height 
for the region out of the defined domain, the sea surface that returns zero or the batimetric depth depending on a state bit, 
and the building model that returns a value on the visual DSM or the DEM depending on another state bit. 
We can also store efficiently hybrid models consisting of regular grids plus some irregular data (points and lines). This is 
the kind of data we get with authomatic stereo matching methods. The boundary of the regular grid is triangulated and 
also the irregular data plus the vertices of the cells in the grid containing the irregular data. In the cells with irregular data 
the surface model is the polyhedral TIN surface but in the regular grid cells the surface model is the bilinear surface. The 
triangular faces formed by triangulating the boundaries of the regular grid region hold pointers to the grid surface model. 
In this way we do not need to triangulate all the grid nodes. This is another example of the flexibility of our design. 
The methods corresponding to triangulation algorithms belong to the TIN class and the methods corresponding to the QT 
belong to the bucket PR-quadtree class. TINQT class is a refinement of the TIN class with the specific methods for a TIN 
Stored in a QT. It redefines point location as a hierarchical search on the PR-quadtree plus a standard Lawson search on 
the TIN. The bucket PR-quadtree class is also the container class for the vertices. After updating the TIN new vertices are 
  
International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000. 789