Ear-slicing and quality triangulation

• Autorzy: Kajak B. , Gewali L. , Selvaraj H.
• Języki publikacji: EN

Abstrakty

EN

Most algorithms for polygon triangulation do not consider the quality of generated triangles. We present two approaches for modifying the ear-cutting triangulation algorithm so that the resulting mesh contains higher proportion of quality triangles. The first approach is based on searching for the best triangle by scanning the boundary. The second approach uses "stabbing diagonals" to partition the polygon onto components which can then be separately triangulated to increase the number of quality triangles.

Słowa kluczowe

EN

ear-slicing triangulation algorithm; polygon triangulation; triangulation quality; mesh generation

• Wydawca: Oficyna Wydawnicza Politechniki Wrocławskiej
• Czasopismo: Systems Science
• Rocznik: 2010
• Tom: Vol. 36, no 4
• Strony: 105--109
• Opis fizyczny: Bibliogr. 5 poz., rys.

Twórcy

autor

Kajak B.

autor

Gewali L.

autor

Selvaraj H.

• HRH College of Engineering, University of Nevada, Las Vegas

Bibliografia

• [1] O'Rourke J., Computational Geometry in C, Second Edition, Cambridge University Press, 1998.
• [2] ElGindy H., Everett H., Toussaint G.T., Slicing an Ear Using Prune-and-Search, Pattern Recognition Letters, 14, (9), 1993, 719-722.
• [3] Chazelle B., Triangulating a Simple Polygon in Linear Time, Discrete and Computational Geometry, 6, 1991, 485-524.
• [4] Berg de M., Kreveld van M., Overmars M., Schwarzkoft O., Computational Geometry, (2nd revised ed.). Springer Verlag, 2000.
• [5] Zydek D., Selvaraj H., Hardware Implementation of Processor Allocation Schemes for Mesh-Based Chip Multiprocessors, Journal of Microprocessors and Microsystems, Vol. 34, No. 1,2010,39-48.