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