rectangle-decomposition

Minimal decomposition of rectilinear polygons into rectangles

rectangle-decomposition

Computes an optimal rectilinear decomposition. Based on the bipartite matching algorithm. References:

  • Jr. W. Lipski, E. Lodi, F. Luccio, C. Mugnai, L. Pagli. (1979) "On two-dimensional data organization II". Fundamenta Informaticae
  • E. Kawaguchi, T. Endo. (1980) "On a method of binary-picture representation and its application to data compression" IEEE Transactions on Pattern Analysis and Machine Intelligence
  • T. Ohtsuki. (1982) "Minimum dissection of rectilinear regions" IEEE Conference on Circuits and Systems
  • T. Suk, C. Hoschl, J. Flusser. (2012) "Rectangular Decomposition of Binary Images",Advanced Concepts for Intelligent Vision Systems. LNCS Vol. 7517

This code is 100% JavaScript and works in both node.js and in a browser via browserify.

var decompose = require("rectangle-decomposition")
 
//First create a region: 
// 
//   *-----* 
//   |     | 
// *-*     | 
// |       | 
// | *-*   | 
// | | |   | 
// | *-*   | 
// |       | 
// *-------* 
// 
//Regions are defined by lists of loops, default oriented counter clockwise 
// 
var region = [  
  [[1,1], [1,2], [2,2], [2,1]],
  [[0,0], [4,0], [4,4], [1,4], [1,3], [0,3]]]
 
//Next, extract rectangles 
// 
var rectangles = decompose(region)
 
console.log(rectangles)
 
//Prints out: 
// 
//  [ [ [ 1, 0 ], [ 2, 1 ] ], 
//    [ [ 0, 0 ], [ 1, 3 ] ], 
//    [ [ 2, 0 ], [ 4, 4 ] ], 
//    [ [ 1, 2 ], [ 2, 4 ] ] ] 
// 
 
//Equivalent to the following decomposition: 
// 
//   *-----* 
//   | !   | 
// *-* !   | 
// | ! !   | 
// | *-*   | 
// | | |   | 
// | *-*   | 
// | ! !   | 
// *-------* 
// 
npm install rectangle-decomposition

Decomposes the polygon defined by the list of loops into a collection of rectangles.

  • loops is an array of loops vertices representing the boundary of the region. Each loop must be a simple rectilinear polygon (ie no self intersections), and the line segments of any two loops must only meet at vertices. The collection of loops must also be bounded.
  • clockwise is a boolean flag which if set flips the orientation of the loops. Default is true, ie all loops follow the right-hand rule (counter clockwise orientation)

Returns A list of rectangles that decompose the region bounded by loops into the smallest number of non-overlapping rectangles.

(c) 2014 Mikola Lysenko. MIT License