Bozhidar Angelov Stanchev†, Hristo Ivanov Paraskevov‡
Abstract: In this paper we present an edge swapping approach for incorporating line segments into triangulation. If the initial triangulation is Delaunay, the algorithm tends to produce optimal Constrained Delaunay triangulation by improving the triangles’ aspect ratios from the
local area being constrained. There are two types of methods for constructing Constrained Delaunay Triangulation: straight-forward ones which take both points and line segments as source data and produce constrained triangulation from them at once; and post-processing ones
which take an already constructed triangulation and incorporate line segments into it. While most of the existing post-processing approaches clear the triangle’s edges intersected by the line segment being incorporated and fill the opened hole (cavity) by re-triangulating it, the
only processing that our algorithm does is to change the triangulation connectivity and to improve the triangles’ aspect ratios through edge swapping. Hereof, it is less expensive in terms of both operating and memory costs. The motivation behind our approach is that most of the existing straight-forward triangulators are too slow and not stable enough. The idea is to use pure Delaunay triangulator to produce an initial Delaunay triangulation and later on to constrain it to the line segments (in other words, to split the processing into two steps, each of which is stable enough and the combination of them works much faster). The algorithm also minimizes the number of the newly introduced triangulation points – new points are added only if any of the line segment’s endpoints does not match an existing triangulation point.
MSC: 32B25, 42A15, 94A08
keywords: Delaunay triangulation, constrained Delaunay triangulation, edge swapping, triangle aspect ratio
DOI 10.56082/annalsarscimath.2020.1-2.164
† bstanchev@gmail.com University of Shumen, Bulgaria
‡ h.paraskevov@shu.bg University of Shumen, Bulgaria; Paper written is partially supported of the National Scientific Program Information and Communication Technologies for a Single Digital Market in Science, Education and Security (ICTinSES), financed by the Ministry of Education and Science.
PUBLISHED in Annals Academy of Romanian Scientists Series on Mathematics and Its Application, Volume 12 no 1-2, 2020
