IDEAS home Printed from https://ideas.repec.org/a/ids/injams/v11y2019i1p36-54.html
   My bibliography  Save this article

A quasi-visibility graph based clique-extraction heuristic model for partitioning of planar shape

Author

Listed:
  • Sourav Saha
  • Ankita Mandal
  • Sayantan Rana
  • Priya Ranjan Sinha Mahapatra

Abstract

This paper presents a graph theoretical model to partition polygonal approximation of a shape into visually meaningful constituent parts based on a heuristic approach. The proposed model introduces a new concept of approximated vertex-visibility graph termed as quasi-visibility graph to generate different viable cuts for partitioning the shape. In the shape representative graph, a maximal-clique perceptually corresponds to a distinguishable part. Based on this notion, we propose a heuristic based clique extraction strategy to decompose the shape exploring its quasi-visibility graph. A few refinement strategies are also attempted by exploring the options of: a) merging correlated parts for better visual interpretation; b) inserting antipodal points of reflex vertices in polygonal approximation for more possible viable cuts. The performance of the proposed model is evaluated by comparing partition-graphs of similar shapes. The partitioning based on the proposed model appears to be coherent with human observation and comparable with existing algorithms.

Suggested Citation

  • Sourav Saha & Ankita Mandal & Sayantan Rana & Priya Ranjan Sinha Mahapatra, 2019. "A quasi-visibility graph based clique-extraction heuristic model for partitioning of planar shape," International Journal of Applied Management Science, Inderscience Enterprises Ltd, vol. 11(1), pages 36-54.
    • Handle: RePEc:ids:injams:v:11:y:2019:i:1:p:36-54
    as

    Download full text from publisher

    File URL: http://www.inderscience.com/link.php?id=96654
    Download Restriction: Access to full text is restricted to subscribers.
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:ids:injams:v:11:y:2019:i:1:p:36-54. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sarah Parker (email available below). General contact details of provider: http://www.inderscience.com/browse/index.php?journalID=286 .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.