Vol.12, No.1, February 2023.                                                                                                                                                                              ISSN: 2217-8309

                                                                                                                                                                                                                        eISSN: 2217-8333


TEM Journal



Association for Information Communication Technology Education and Science

Fast Shape-Preserving Method for Integrating Polygon into Two-and-Half Dimensional Triangulation


Bozhidar Stanchev, Hristo Paraskevov


© 2023 Hristo Paraskevov, published by UIKTEN. This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License. (CC BY-NC-ND 4.0)


Citation Information: TEM Journal. Volume 12, Issue 1, Pages 22-28, ISSN 2217-8309, DOI: 10.18421/TEM121-03, February 2023.


Received: 07 October 2022.

Revised:   07 December 2022.
Accepted: 13 January 2023.
Published: 27 February 2023.




This paper presents an approach in integrating polygons into a triangulation. The motivation behind this work is to find a way to overcome the lack of appropriate shape-preserving methods for modifying 2.5D triangle meshes. Widely used approaches for constructing Constrained Delone Triangulation (CDT) work in two steps: first constructing pure Delone triangulation, and next inserting the line segments one-by-one into it [1], [2], [3]. The presented method implements an effective mesh data structure and a walking-on-mesh approach allowing for fast polygon traversal looking for the intersected edges of the 2.5D mesh. Instead of reconnecting vertices or re-triangulating the affected mesh area, we introduce new mesh vertices and subdivide the mesh in order to integrate the polygon. The technique also examines and enhances the aspect ratios of the 2.5D triangles that are present in (and near) the partitioned area while maintaining the shape.


Keywords –constrained Delone triangulation, mesh data structure, mesh traversal, edge swapping, triangle aspect ratio.



Full text PDF >  



Copyright © 2023 UIKTEN
Copyright licence: All articles are licenced via Creative Commons CC BY-NC-ND 4.0 licence