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

Stefan Ohrhallinger, Sudhir Mudur
Interpolating an unorganized 2D point cloud with a single closed shape
Computer-Aided Design, 43(1):1629-1638, January 2011. [ paper]
Content:

Information

Abstract

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 (EMST). Our algorithm segments the EMST 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.

Additional Files and Images

Additional files:
paper paper: Reconstruction of 2D Point Cloud

BibTeX

Download BibTeX-Entry
@article{ohrhallinger_stefan-2011-001,
  title =      "Interpolating an unorganized 2D point cloud with a single
               closed shape",
  author =     "Stefan Ohrhallinger and Sudhir Mudur",
  year =       "2011",
  abstract =   "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 (EMST). Our algorithm segments the
               EMST 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. ",
  pages =      "1629--1638",
  month =      jan,
  number =     "1",
  issn =       "0010-4485",
  journal =    "Computer-Aided Design",
  volume =     "43",
  keywords =   "EMST, Curve, Point cloud, Reconstruction, Shape
               Construction, Boundary, Computational geometry, Point set",
  URL =        "http://www.cg.tuwien.ac.at/research/publications/2011/ohrhallinger_stefan-2011-001/",
}