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

Simple item page
dc.contributor.authorOhrhallinger, S.en_US
dc.contributor.authorMudur, S.en_US
dc.contributor.editorHolly Rushmeier and Oliver Deussenen_US
dc.date.accessioned2015-02-28T16:16:22Z
dc.date.available2015-02-28T16:16:22Z
dc.date.issued2013en_US
dc.description.abstractWe present anefficient algorithm for determining an aesthetically pleasing shape boundary connecting all the points in a given unorganized 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 minimizes 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 parametrizing 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 (Non‐Polynomial)‐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.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.en_US
dc.description.number8
dc.description.seriesinformationComputer Graphics Forumen_US
dc.description.volume32
dc.identifier.issn1467-8659en_US
dc.identifier.urihttps://doi.org/10.1111/cgf.12162en_US
dc.publisherThe Eurographics Association and Blackwell Publishing Ltd.en_US
dc.subjectcurve reconstructionen_US
dc.subjectgestalt principlesen_US
dc.subjectsparse samplingen_US
dc.subjectI.3.3 [Computer Graphics]en_US
dc.subjectPicture/Image Generation Line and curve generationen_US
dc.subjectI.3.5 [Computer Graphics]en_US
dc.subjectComputational Geometry and Object Modeling Boundary representationsen_US
dc.subjectI.4.8 [Computer Graphics]en_US
dc.subjectScene Analysis Surface Fittingen_US
dc.titleAn Efficient Algorithm for Determining an Aesthetic Shape Connecting Unorganized 2D Pointsen_US
Files
Collections
32-Issue 8