# rectangle-decomposition

1.0.0 • Public • Published

# 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.

## 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

## Package Sidebar

### Install

`npm i rectangle-decomposition`

76

1.0.0