Accurate, simple and efficient triangulation of a polygon by ear removal with lowest memory consumption
Polygons can conveniently represent real world objects. In automatic character recognition, shapes of individual letters are represented by polygons. In robotics, obstacles are represented using polygons. In computer graphics programming, solid objects are represented using polygons on the two dimen...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Faculty of Science, University of Peradeniya, Sri Lanka
2016-11-01
|
| Series: | Ceylon Journal of Science |
| Subjects: | |
| Online Access: | https://cjs.sljol.info/articles/7402 |
| _version_ | 1828216047831875584 |
|---|---|
| author | K. R. Wijeweera S. R. Kodituwakku |
| author_facet | K. R. Wijeweera S. R. Kodituwakku |
| author_sort | K. R. Wijeweera |
| collection | DOAJ |
| description | Polygons can conveniently represent real world objects. In automatic character recognition, shapes of individual letters are represented by polygons. In robotics, obstacles are represented using polygons. In computer graphics programming, solid objects are represented using polygons on the two dimensional screen. The polygons can be easily manipulated using known mathematical operations. That is the reason for representing real world objects using polygons. However, polygons can be in complicated shapes. Therefore, it is better if there is a way to partition a polygon into smaller pieces. Triangulation is a particular way of doing this from which polygons are partitioned into triangles. The basic triangulation algorithm is widely used in applications where 100% accuracy is necessary. Algorithms with better asymptotic order than the basic triangulation algorithm exist. However they are not 100% accurate and use advanced data structures causing higher memory consumption. This paper proposes a simple, efficient and 100% accurate algorithm which uses lowest amount of memory. The proposed algorithm is more suitable for embedded systems which do not possess large amount of memory. The proposed algorithm was experimentally compared with the basic triangulation algorithm. The experimental results prove that the proposed algorithm is faster than the basic triangulation algorithm. |
| first_indexed | 2024-04-12T15:28:08Z |
| format | Article |
| id | doaj.art-84c69012fb9c4033811c2893a76a1990 |
| institution | Directory Open Access Journal |
| issn | 2513-2814 2513-230X |
| language | English |
| last_indexed | 2024-04-12T15:28:08Z |
| publishDate | 2016-11-01 |
| publisher | Faculty of Science, University of Peradeniya, Sri Lanka |
| record_format | Article |
| series | Ceylon Journal of Science |
| spelling | doaj.art-84c69012fb9c4033811c2893a76a19902022-12-22T03:27:12ZengFaculty of Science, University of Peradeniya, Sri LankaCeylon Journal of Science2513-28142513-230X2016-11-01453657610.4038/cjs.v45i3.74025618Accurate, simple and efficient triangulation of a polygon by ear removal with lowest memory consumptionK. R. Wijeweera0S. R. Kodituwakku1University of RuhunaUniversity of PeradeniyaPolygons can conveniently represent real world objects. In automatic character recognition, shapes of individual letters are represented by polygons. In robotics, obstacles are represented using polygons. In computer graphics programming, solid objects are represented using polygons on the two dimensional screen. The polygons can be easily manipulated using known mathematical operations. That is the reason for representing real world objects using polygons. However, polygons can be in complicated shapes. Therefore, it is better if there is a way to partition a polygon into smaller pieces. Triangulation is a particular way of doing this from which polygons are partitioned into triangles. The basic triangulation algorithm is widely used in applications where 100% accuracy is necessary. Algorithms with better asymptotic order than the basic triangulation algorithm exist. However they are not 100% accurate and use advanced data structures causing higher memory consumption. This paper proposes a simple, efficient and 100% accurate algorithm which uses lowest amount of memory. The proposed algorithm is more suitable for embedded systems which do not possess large amount of memory. The proposed algorithm was experimentally compared with the basic triangulation algorithm. The experimental results prove that the proposed algorithm is faster than the basic triangulation algorithm.https://cjs.sljol.info/articles/7402computational geometry, computer graphics programming, triangulation, computational statistics, linear programming |
| spellingShingle | K. R. Wijeweera S. R. Kodituwakku Accurate, simple and efficient triangulation of a polygon by ear removal with lowest memory consumption Ceylon Journal of Science computational geometry, computer graphics programming, triangulation, computational statistics, linear programming |
| title | Accurate, simple and efficient triangulation of a polygon by ear removal with lowest memory consumption |
| title_full | Accurate, simple and efficient triangulation of a polygon by ear removal with lowest memory consumption |
| title_fullStr | Accurate, simple and efficient triangulation of a polygon by ear removal with lowest memory consumption |
| title_full_unstemmed | Accurate, simple and efficient triangulation of a polygon by ear removal with lowest memory consumption |
| title_short | Accurate, simple and efficient triangulation of a polygon by ear removal with lowest memory consumption |
| title_sort | accurate simple and efficient triangulation of a polygon by ear removal with lowest memory consumption |
| topic | computational geometry, computer graphics programming, triangulation, computational statistics, linear programming |
| url | https://cjs.sljol.info/articles/7402 |
| work_keys_str_mv | AT krwijeweera accuratesimpleandefficienttriangulationofapolygonbyearremovalwithlowestmemoryconsumption AT srkodituwakku accuratesimpleandefficienttriangulationofapolygonbyearremovalwithlowestmemoryconsumption |