New Algorithm of Joining a Set of Segments into a Simple Polygon
For the problem of how to link a set of segments to a simple polygon with the shortest whole length, a sufficient condition that a given set of segments can be joined into a simple polygon is given.It is proved that the nearest point or second nearest point of the end point can be obtained in Delaun...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Harbin University of Science and Technology Publications
2018-12-01
|
| Series: | Journal of Harbin University of Science and Technology |
| Subjects: | |
| Online Access: | https://hlgxb.hrbust.edu.cn/#/digest?ArticleID=1625 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849739260504047616 |
|---|---|
| author | JIN Hui LIU Run-tao |
| author_facet | JIN Hui LIU Run-tao |
| author_sort | JIN Hui |
| collection | DOAJ |
| description | For the problem of how to link a set of segments to a simple polygon with the shortest whole length, a sufficient condition that a given set of segments can be joined into a simple polygon is given.It is proved that the nearest point or second nearest point of the end point can be obtained in Delaunay triangulation for the end points of a set of segments S.Based on this result, the method of joining a segment into a polygon is given for getting the polygon with the shortest length.Then, a new algorithm for joining a set of segments into a simple polygon with shorter whole length is presented.The analysis is done on the time complexity for new algorithm.The correctness of new algorithm is proved.The comparison and analysis are done for the new algorithm to show that better result can be obtained with the new algorithm. |
| format | Article |
| id | doaj-art-6171ab9b04e6477b9e5df90f4e00daf5 |
| institution | DOAJ |
| issn | 1007-2683 |
| language | zho |
| publishDate | 2018-12-01 |
| publisher | Harbin University of Science and Technology Publications |
| record_format | Article |
| series | Journal of Harbin University of Science and Technology |
| spelling | doaj-art-6171ab9b04e6477b9e5df90f4e00daf52025-08-20T03:06:19ZzhoHarbin University of Science and Technology PublicationsJournal of Harbin University of Science and Technology1007-26832018-12-01230613814510.15938/j.jhust.2018.06.025New Algorithm of Joining a Set of Segments into a Simple PolygonJIN Hui0LIU Run-tao1School of Sciences, Harbin University of Science and Technology, Harbin 150080,ChinaInstitute of Information and Scientific Computing Technology, Harbin University of Science and Technology, Harbin 150080,ChinaFor the problem of how to link a set of segments to a simple polygon with the shortest whole length, a sufficient condition that a given set of segments can be joined into a simple polygon is given.It is proved that the nearest point or second nearest point of the end point can be obtained in Delaunay triangulation for the end points of a set of segments S.Based on this result, the method of joining a segment into a polygon is given for getting the polygon with the shortest length.Then, a new algorithm for joining a set of segments into a simple polygon with shorter whole length is presented.The analysis is done on the time complexity for new algorithm.The correctness of new algorithm is proved.The comparison and analysis are done for the new algorithm to show that better result can be obtained with the new algorithm.https://hlgxb.hrbust.edu.cn/#/digest?ArticleID=1625set of segmentssimple polygondelaunay triangulationthe enlargement of quadrilateral length |
| spellingShingle | JIN Hui LIU Run-tao New Algorithm of Joining a Set of Segments into a Simple Polygon Journal of Harbin University of Science and Technology set of segments simple polygon delaunay triangulation the enlargement of quadrilateral length |
| title | New Algorithm of Joining a Set of Segments into a Simple Polygon |
| title_full | New Algorithm of Joining a Set of Segments into a Simple Polygon |
| title_fullStr | New Algorithm of Joining a Set of Segments into a Simple Polygon |
| title_full_unstemmed | New Algorithm of Joining a Set of Segments into a Simple Polygon |
| title_short | New Algorithm of Joining a Set of Segments into a Simple Polygon |
| title_sort | new algorithm of joining a set of segments into a simple polygon |
| topic | set of segments simple polygon delaunay triangulation the enlargement of quadrilateral length |
| url | https://hlgxb.hrbust.edu.cn/#/digest?ArticleID=1625 |
| work_keys_str_mv | AT jinhui newalgorithmofjoiningasetofsegmentsintoasimplepolygon AT liuruntao newalgorithmofjoiningasetofsegmentsintoasimplepolygon |