Inserting line segments into triangulations and tetrahedralizations

Published

March 1, 1995

Author(s)

Javier Bernal

Abstract

In this paper, we further develop an algorithm by Bernal, De Floriani, and Puppo, for inserting a line segment into a Constrained Delaunay triangulation. The new version of the algorithm inserts the line segment in exactly the same manner in which the old version does but has the additional capability that it does not delete the triangles intersected by the line segment but transforms them through edge-swapping. Since the concept of edge-swapping generalizes to 3— dimensional space, a 3— dimensional version of the algorithm without the optimization step for the Delaunay property is also presented for attempting to insert a line segment into a tetrahedralization. It is shown that for certain cases the failure of the 3— dimensional algorithm to insert a line segment is an indication that it can not be done. Finally, 3— dimensional problems that can be approached algorithmically as 2— dimensional problems are identified.

Citation

NIST Interagency/Internal Report (NISTIR) - 5596

Report Number

5596

NIST Pub Series

NIST Interagency/Internal Report (NISTIR)

Pub Type

NIST Pubs

Download Paper

DOI Link

Keywords

computational geometry, constrained Delaunay tri angulation, edge-swapping, empty circle criterion, locally equiangular, segment insertion, Voronoi diagram

Citation

Bernal, J. (1995), Inserting line segments into triangulations and tetrahedralizations, NIST Interagency/Internal Report (NISTIR), National Institute of Standards and Technology, Gaithersburg, MD, [online], https://doi.org/10.6028/NIST.IR.5596 (Accessed April 4, 2025)