Interpolating an unorganized 2D point cloud with a single closed shape

详细信息    查看全文

• 作者：Stefan Ohrhallinger  ; ;   ; ^a ;   ; ^{s_ohrhal@cse.concordia.ca} ;   ; ^{stefango@gmail.com} ; Sudhir P. Mudur^a ;   ; ^{mudur@cse.concordia.ca}
• 关键词：Computational geometry ; Reconstruction ; Construction ; Shape ; Curve ; Boundary ; Point cloud ; Point set ; EMST
• 刊名：Computer-Aided Design
• 出版年：2011
• 出版时间：December 2011
• 年：2011
• 卷：43
• 期：12
• 页码：1629-1638
• 全文大小：961 K

文摘

Given an unorganized two-dimensional point cloud, we address the problem of efficiently constructing a single aesthetically pleasing closed interpolating shape, without requiring dense or uniform spacing. Using Gestalt¡¯s laws of proximity, closure and good continuity as guidance for visual aesthetics, we require that our constructed shape be a minimal perimeter, non-self intersecting manifold. We find that this yields visually pleasing results. Our algorithm is distinct from earlier shape reconstruction approaches, in that it exploits the overlap between the desired shape and a related minimal graph, the Euclidean Minimum Spanning Tree (). Our algorithm segments the to retain as much of it as required and then locally partitions and solves the problem efficiently. Comparison with some of the best currently known solutions shows that our algorithm yields better results.