Contents of Local updates

Local updates

In general, a local update is described by two sets of triangles, each triangulating the same region with a different number of triangles (the more numerous set giving the triangulation at higher resolution). A specific MT-generator is usually characterized by the repeated application of a specific pattern which is repeated at each update. The most popular patterns are:

Vertex insertion/deletion: a refinement update inserts a new vertex in the data set and updates the TIN by eliminating a triangulated polygon in the area surrounding the new vertex, and by filling the hole with a fan of triangles incident at the new vertex [De Floriani et al.1985,Fowler and Little1979,Franklin1994,Rippa1992]; a simplification update works in reverse by eliminating a vertex and its incident triangles first, and triangulating the resulting hole next [de Berg and Dobrindt1995,Lee1989].
Edge collapse: a simplification update shrinks an edge of the TIN by collapsing either one of its endpoints to the other endpoint, or both endpoints to a new vertex lying along the edge; each of the two triangles incident at the edge collapses to an edge, while the other triangles incident at its endpoints are warped consistently [,Hoppe1996].

Also in this case, there is no clear superiority of one such approach with respect to the other.

[ENRICO: IN REALTA' IN QUALCHE NOSTRO LAVORO PRECEDENTE CI SONO DISCORSI CON CUI CERCHIAMO DI DIMOSTRARE CHE IL PRIMO APPROCCIO E' MEGLIO, MA NON INSISTEREI SU QUESTO QUI]

In VARIANT, we provide MT-generators based on the former kind of local updates. It would be simple to extend the system with more MT-generators of the second kind by incorporating kernel primitives for building an MT into existing code for TIN generalization.

In order to incorporate line features, which are crucial to a variety of applications, we also provide an MT-generator that is based on simplification through vertex deletion. Input data are in the form of a set of points and a set of segments representing line features. The algorithm starts from a triangulation of the domain containing all the given points and line segments as vertices and edges, respectively, thus representing terrain and features at their maximum resolution. Then, the algorithm deletes a vertex at each iteration, with the constraint that a vertex lying on a line feature can be deleted only if it is shared by exactly two feature edges. In this case, deleting the vertex simplifies the shape of the line feature. Additional constraints prevent degenerative phenomena such as intersections between line features during simplification.

[ENRICO: NELLA VERSIONE VECCHIA C'ERA MOLTO DI PIU' SU QUESTO ALGORITMO. SENZA ENTRARE IN FUFFO QUEL DETTAGLIO FORSE SI POTREBBE DIRE ANCORA QUALCOSA, OPPURE E' SUPERFLUO?]