Polyline-sourced geodesic voronoi diagrams on triangle meshes
This paper studies the Voronoi diagrams on 2‐manifold meshes based on geodesic metric (a.k.a. geodesic Voronoi diagrams or GVDs), which have polyline generators. We show that our general setting leads to situations more complicated than conventional 2D Euclidean Voronoi diagrams as well as point‐sou...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2018
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/87051 http://hdl.handle.net/10220/45220 |
| _version_ | 1811680227166781440 |
|---|---|
| author | Xu, Chunxu Liu, Yong-Jin Sun, Qian Li, Jinyan He, Ying |
| author2 | School of Computer Science and Engineering |
| author_facet | School of Computer Science and Engineering Xu, Chunxu Liu, Yong-Jin Sun, Qian Li, Jinyan He, Ying |
| author_sort | Xu, Chunxu |
| collection | NTU |
| description | This paper studies the Voronoi diagrams on 2‐manifold meshes based on geodesic metric (a.k.a. geodesic Voronoi diagrams or GVDs), which have polyline generators. We show that our general setting leads to situations more complicated than conventional 2D Euclidean Voronoi diagrams as well as point‐source based GVDs, since a typical bisector contains line segments, hyperbolic segments and parabolic segments. To tackle this challenge, we introduce a new concept, called local Voronoi diagram (LVD), which is a combination of additively weighted Voronoi diagram and line‐segment Voronoi diagram on a mesh triangle. We show that when restricting on a single mesh triangle, the GVD is a subset of the LVD and only two types of mesh triangles can contain GVD edges. Based on these results, we propose an efficient algorithm for constructing the GVD with polyline generators. Our algorithm runs in O(nNlogN) time and takes O(nN) space on an n‐face mesh with m generators, where N=max{m, n}. Computational results on real‐world models demonstrate the efficiency of our algorithm. |
| first_indexed | 2024-10-01T03:21:42Z |
| format | Journal Article |
| id | ntu-10356/87051 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T03:21:42Z |
| publishDate | 2018 |
| record_format | dspace |
| spelling | ntu-10356/870512020-03-07T11:48:51Z Polyline-sourced geodesic voronoi diagrams on triangle meshes Xu, Chunxu Liu, Yong-Jin Sun, Qian Li, Jinyan He, Ying School of Computer Science and Engineering Curve Surface This paper studies the Voronoi diagrams on 2‐manifold meshes based on geodesic metric (a.k.a. geodesic Voronoi diagrams or GVDs), which have polyline generators. We show that our general setting leads to situations more complicated than conventional 2D Euclidean Voronoi diagrams as well as point‐source based GVDs, since a typical bisector contains line segments, hyperbolic segments and parabolic segments. To tackle this challenge, we introduce a new concept, called local Voronoi diagram (LVD), which is a combination of additively weighted Voronoi diagram and line‐segment Voronoi diagram on a mesh triangle. We show that when restricting on a single mesh triangle, the GVD is a subset of the LVD and only two types of mesh triangles can contain GVD edges. Based on these results, we propose an efficient algorithm for constructing the GVD with polyline generators. Our algorithm runs in O(nNlogN) time and takes O(nN) space on an n‐face mesh with m generators, where N=max{m, n}. Computational results on real‐world models demonstrate the efficiency of our algorithm. MOE (Min. of Education, S’pore) Accepted version 2018-07-25T03:51:47Z 2019-12-06T16:34:03Z 2018-07-25T03:51:47Z 2019-12-06T16:34:03Z 2014 Journal Article Xu, C., Liu, Y.-J., Sun, Q., Li, J., & He, Y. (2014). Polyline-sourced geodesic voronoi diagrams on triangle meshes. Computer Graphics Forum, 33(7), 161-170. 0167-7055 https://hdl.handle.net/10356/87051 http://hdl.handle.net/10220/45220 10.1111/cgf.12484 en Computer Graphics Forum © 2014 The Author(s) (©The Eurographics Association and John Wiley & Sons Ltd). This is the author created version of a work that has been peer reviewed and accepted for publication by Computer Graphics Forum, The Author(s) (©The Eurographics Association and John Wiley & Sons Ltd). It incorporates referee’s comments but changes resulting from the publishing process, such as copyediting, structural formatting, may not be reflected in this document. The published version is available at: [http://dx.doi.org/10.1111/cgf.12484]. 10 p. application/pdf |
| spellingShingle | Curve Surface Xu, Chunxu Liu, Yong-Jin Sun, Qian Li, Jinyan He, Ying Polyline-sourced geodesic voronoi diagrams on triangle meshes |
| title | Polyline-sourced geodesic voronoi diagrams on triangle meshes |
| title_full | Polyline-sourced geodesic voronoi diagrams on triangle meshes |
| title_fullStr | Polyline-sourced geodesic voronoi diagrams on triangle meshes |
| title_full_unstemmed | Polyline-sourced geodesic voronoi diagrams on triangle meshes |
| title_short | Polyline-sourced geodesic voronoi diagrams on triangle meshes |
| title_sort | polyline sourced geodesic voronoi diagrams on triangle meshes |
| topic | Curve Surface |
| url | https://hdl.handle.net/10356/87051 http://hdl.handle.net/10220/45220 |
| work_keys_str_mv | AT xuchunxu polylinesourcedgeodesicvoronoidiagramsontrianglemeshes AT liuyongjin polylinesourcedgeodesicvoronoidiagramsontrianglemeshes AT sunqian polylinesourcedgeodesicvoronoidiagramsontrianglemeshes AT lijinyan polylinesourcedgeodesicvoronoidiagramsontrianglemeshes AT heying polylinesourcedgeodesicvoronoidiagramsontrianglemeshes |