README.md

Polygon-partitioner

This is mainly for partitioning polygons into disjoint rectangles. Because you never know when you need to partition some polygons.

Features

This package implements two main methods:

1. A method that approximates a polygon by a orthogonal polygon.

   This output is guaranteed to cover the input polygon. You to change the coarseness of the approximation.

2. A method that partitions an orthogonal polygon into non-overlapping rectangles.

   This method handles polygons with holes and chords.

Note that the orthogonal polygons used as input are assumed to have edges that are parallel to either the x-axis and y-axis. Also, the functions in this package use JTS Polygons as the class for the input polygon.

Installation

The polygon-partitioner package is composed three submodules: core, plot, and db. In core, you'll find methods that implement the algorithms described above (and documented below); plot includes methods for plotting a polygon and the rectangles created by the partitioning algorithm; and db includes methods for extracting polygons from a PostGIS database with TIGER data. The db submodule has not gotten much attention.

If you want to install polygon-partitioner and all the submodules, add the following to your build.sbt file:

lazy val partitioner = RootProject(uri("git://github.com/djordon/polygon-partitioner.git#v0.1.0"))

lazy val root = Project("root", file(".")).dependsOn(partitioner)

If you only want the algorithms in the core module and don't care about the plotting and db modules, then you can install it by adding the following to build.sbt:

lazy val partitionerUri = uri("git://github.com/djordon/polygon-partitioner.git#v0.1.0")
lazy val partitionerCore = ProjectRef(partitionerUri, "core")

lazy val root = Project("root", file(".")).dependsOn(partitionerCore)

Documentation

Covering a polygon with an orthogonal polygon

If you want to approximate a polygon by an orthogonal polygon, do something like

import org.partitioner.createExteriorCover
import org.locationtech.jts.geom.Polygon

val myPolygon: Polygon = ...
val orthogonalPolygon: Polygon = createExteriorCover(myPolygon)

The above does not handle holes in the input. For that, use the cover method, which attempts to accommodate holes. Here is an example:

import org.partitioner.cover
import org.locationtech.jts.geom.Polygon

val myPolygon: Polygon = ...
val orthogonalPolygon: Polygon = cover(myPolygon)

Note that the output polygon in the above example is not guaranteed to have as many holes from the input polygon.

For both createExteriorCover and cover, there are parameters that you can use to tune the coarseness of the cover. The default settings return the finest orthogonal polygon that covers the input using the covering algorithm implemented here.

Partitioning a polygon

If you want to partition an orthogonal polygon into non-overlapping rectangles, use the following

import org.partitioner.orthogonal.partition
import org.partitioner.Rectangle
import org.locationtech.jts.geom.Polygon

val myPolygon: Polygon = ...
val rectangles: List[Rectangle] = partition(myPolygon)

If you want to find a collection of non-overlapping rectangles whose union covers the input, use the following

import org.partitioner.{decompose, Rectangle}
import org.locationtech.jts.geom.Polygon

val myPolygon: Polygon = ...
val rectangles: List[Rectangle] = decompose(myPolygon)

Note that, under the hood, PolygonPartitioner.partition calls the cover method followed by the orthogonal polygon partition method. The cover method can be relatively slow for polygons with holes and many points along the boundary.

Bugs and issues

File bugs/issues/requests at https://github.com/djordon/polygon-partitioner/issues.

Copyright and license

Code and documentation Copyright 2017 Daniel Jordon. Code released under the MIT license.