Premium
Weak Convex Decomposition by Lines‐of‐sight
Author(s) -
Asafi Shmuel,
Goren Avi,
CohenOr Daniel
Publication year - 2013
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/cgf.12169
Subject(s) - convexity , rank (graph theory) , regular polygon , mathematics , extreme point , point cloud , set (abstract data type) , combinatorics , computer science , algorithm , artificial intelligence , geometry , financial economics , economics , programming language
We define the convexity rank of a set of points to be the portion of mutually visible pairs of points out of the total number of pairs. Based on this definition of weak convexity, we introduce a spectral method that decomposes a given shape into weakly convex regions. The decomposition is applied without explicitly measuring the convexity rank. The method merely amounts to a spectral clustering of a matrix representing the all‐pairs line of sight. Our method can be directly applied on an oriented point cloud and does not require any topological information, nor explicit concavity or convexity measures. We demonstrate the efficiency of our algorithm on a large number of examples and compare them qualitatively with competitive approaches.