Fast algorithms of constrained Delaunay triangulation and skeletonization for band images

Wei Zeng; ChengLei Yang; XiangXu Meng; YiJun Yang; XiuKun Yang

doi:10.1117/12.532615

15 September 2004 Fast algorithms of constrained Delaunay triangulation and skeletonization for band images

Wei Zeng, ChengLei Yang, XiangXu Meng, YiJun Yang, XiuKun Yang

Proceedings Volume 5403, Sensors, and Command, Control, Communications, and Intelligence (C3I) Technologies for Homeland Security and Homeland Defense III; (2004) https://doi.org/10.1117/12.532615
Event: Defense and Security, 2004, Orlando, Florida, United States

Abstract

For the boundary polygons of band-images, a fast constrained Delaunay triangulation algorithm is presented and based on it an efficient skeletonization algorithm is designed. In the process of triangulation the characters of uniform grid structure and the band-polygons are utilized to improve the speed of computing the third vertex for one edge within its local ranges when forming a Delaunay triangle. The final skeleton of the band-image is derived after reducing each triangle to local skeleton lines according to its topology. The algorithm with a simple data structure is easy to understand and implement. Moreover, it can deal with multiply connected polygons on the fly. Experiments show that there is a nearly linear dependence between triangulation time and size of band-polygons randomly generated. Correspondingly, the skeletonization algorithm is also an improvement over the previously known results in terms of time. Some practical examples are given in the paper.

Citation Download Citation

Wei Zeng, ChengLei Yang, XiangXu Meng, YiJun Yang, and XiuKun Yang "Fast algorithms of constrained Delaunay triangulation and skeletonization for band images", Proc. SPIE 5403, Sensors, and Command, Control, Communications, and Intelligence (C3I) Technologies for Homeland Security and Homeland Defense III, (15 September 2004); https://doi.org/10.1117/12.532615

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available