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.

Example

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:
//
//   *-----*
//   | !   |
// *-* !   |
// | ! !   |
// | *-*   |
// | | |   |
// | *-*   |
// | ! !   |
// *-------*
//

Install

npm install rectangle-decomposition

API

require("rectangle-decomposition")(loops[,clockwise])

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.

Credits

(c) 2014 Mikola Lysenko. MIT License