mehrta / monotone-polygon-decomposition

An Algorithm for Monotone Decomposition of Polygons in 2D Space

monotone-polygon-decomposition

An Algorithm for Monotone Decomposition of Polygons in 2D Space

Partitioning a polygon into a set of smaller polygons is called polygon decomposition. There are several methods to decompose a polygon: convex decomposition, monotone decomposition and trapezoidal decomposition, which all of them commonly used in computational geometry. In some cases, it is necessary or desirable to generate minimum number of sub polygons. In this desertation, we propose a greedy algorithm to monotone decomposition of polygons with holes. This algorithm doesn't use Steiner points. The main goal of developing this algorithm is achieving a near minimum decomposition at an acceptable time. Since minimum decomposition of a polygon with holes when Steiner points are not allowed, is a NP-Hard problem, near optimum solutions are the only available practical options for large instances of the problem. In developing this algorithm, two issues have been considered. First subject is about minimality of decomposition. However there is no guarantee about getting the minimum deal, the results of practical implementations demonstrate the effectiveness of this approach. The second issue which is considered in designing of this algorithm is the run time matter. A part of this algorithm is controlled by using a parameter which called ‘Maximum Search Depth’. As the value of this parameter is smaller, the probability of finding near minimum results will be decreased, and in the same, the run time of the algorithm will be decreased. By assigning larger values to this parameter, we can produce better answers but the algorithm's run time will be increased too. By setting this parameter according to the application of this algorithm, we can switch and select between the minimality of analysis or run time performance, or create a balance between them.