An Efficient Algorithm for Determining an Aesthetic Shape Connecting Unorganised 2D Points

Information

• Publication Type: Journal Paper with Conference Talk
• Workgroup(s)/Project(s):
  • Rendering and Modeling
• Date: December 2013
• Journal: Computer Graphics Forum
• Volume: 32
• Number: 8
• Location: Zaragpza, Spain
• Lecturer: Stefan Ohrhallinger
• Event: Eurographics Symposium on Rendering 2013
• Conference date: 19. June 2013 – 21. June 2013
• Pages: 72 – 88
• Keywords: curve reconstruction, boundary representation, sampling condition, computational geometry

Abstract

We present an efficient algorithm for determining an aesthetically pleasing shape boundary connecting all the points in a given unorganised set of 2D points, with no other information than point coordinates. By posing shape construction as a minimisation problem which follows the Gestalt laws, our desired shape Bmin is non-intersecting, interpolates all points and minimises a criterion related to these laws. The basis for our algorithm is an initial graph, an extension of the Euclidean minimum spanning tree but with no leaf nodes, called as the minimum boundary complex BCmin. BCmin and Bmin can be expressed similarly by parametrising a topological constraint. A close approximation of BCmin, termed BC0 can be computed fast using a greedy algorithm. BC0 is then transformed into a closed interpolating boundary Bout in two steps to satisfy Bmin’s topological and minimization requirements. Computing Bmin exactly is an NP-hard problem, whereas Bout is computed in linearithmic time. We present many examples showing considerable improvement over previous techniques, especially for shapes with sharp corners. Source code is available online.

Additional Files and Images

Weblinks

• http://onlinelibrary.wiley.com/doi/10.1111/cgf.12162/abstract

BibTeX

@article{ohrhallinger_stefan-2013-c2d,
  title =      "An Efficient Algorithm for Determining an Aesthetic Shape
               Connecting Unorganised 2D Points",
  author =     "Stefan Ohrhallinger and Sudhir Mudur",
  year =       "2013",
  abstract =   "We present an efficient algorithm for determining an
               aesthetically pleasing shape boundary connecting all the
               points in a given unorganised set of 2D points, with no
               other information than point coordinates. By posing shape
               construction as a minimisation problem which follows the
               Gestalt laws, our desired shape Bmin is non-intersecting,
               interpolates all points and minimises a criterion related to
               these laws. The basis for our algorithm is an initial graph,
               an extension of the Euclidean minimum spanning tree but with
               no leaf nodes, called as the minimum boundary complex BCmin.
               BCmin and Bmin can be expressed similarly by parametrising a
               topological constraint. A close approximation of BCmin,
               termed BC0 can be computed fast using a greedy algorithm.
               BC0 is then transformed into a closed interpolating boundary
               Bout in two steps to satisfy Bmin’s topological and
               minimization requirements. Computing Bmin exactly is an
               NP-hard problem, whereas Bout is computed in linearithmic
               time. We present many examples showing considerable
               improvement over previous techniques, especially for shapes
               with sharp corners. Source code is available online.",
  month =      dec,
  journal =    "Computer Graphics Forum",
  volume =     "32",
  number =     "8",
  pages =      "72--88",
  keywords =   "curve reconstruction, boundary representation, sampling
               condition, computational geometry",
  URL =        "https://www.cg.tuwien.ac.at/research/publications/2013/ohrhallinger_stefan-2013-c2d/",
}