A Method for Finding Multiple Large Rectangular Free Spaces in a Map with Convex and Concave Obstacles

This paper proposes a method for finding large contiguous axis-parallel rectangular free spaces in a 2D-Euclidean map with concave and convex polygons. It starts with the vertical slab based planar subdivision of the map and then finds the rectangular free spaces. A graph representing the subdivisions and their adjacency property is traversed to compute the rectangles. Instead of finding a single large rectangular free space, the method finds multiple instances of axis-parallel rectangles to ensure partial or full inclusion of all subdivisions of the open space for the map. It is ensured that the computed rectangles do not include any existing holes or obstacles by “cropping” the rectangles. This proposed method can potentially be used for the identification of strategic locations in a map.