SpaceSubdivisionTestbed: A Graphical Tool for Arbitrary Shaped 2D Polygon Subdivision
Subdivision of 2D polygons is the basis of many computational geometry algorithms and procedural modeling methods. Existing tools for space subdivision often require the assistance of users and cannot perform subdivision on all types of shapes (rectangular, axis-aligned, convex, and irregular). In this work, an open-source graphical desktop tool for drawing and automatic subdivision of arbitrary 2D polygons is introduced. An algorithm for subdivision of all shape types was developed. The algorithm is based on the usage of polygon bounding boxes, intersection edges and detection of polygons from newly formed edges. A dataset of 60 examples of all shape types was collected and successfully drawn by using the tool. Iterative subdivision was performed on all examples. Shape simplification was fully successful only for axis-aligned shapes. Partial simplification with leftover elements taking up less than 5% of overall polygon area was successful after 5 iterations for axis-aligned, and 10 iterations for convex and irregular shapes on average. This indicates that the tool and subdivision algorithm can be used for simplification of complex shape types with arbitrarily small leftover element area.