How to programmatically partition a large Polygon in smaller parts within a given Area Threshold?

Question

I'm looking for a Java library, or even an algorithm to do the following:

I have a large polygon, about the size of a large city. I need to break it down into smaller polygons such that:

• The area of each part is less than 1 sq KM. (This threshold should be a parameter to the algorithm or function)

• Each Part should have 3 or more sides.

• The Part need not be a regular polygon.

• Each Polygon can have different area.

• These Polygons should cover the entire source Polygon.

• The solution should minimize the number of polygons.

How do I Partition the Polygon in such a way?

Answer 1

Perhaps you could start with JTS and use first RandomPointsInPolygon and create then VoronoiDiagram from this point set. Create lots of polygons and union the smallest one with its neighbor and loop until you are happy. But because the points in the first step are random it is always possible that some of the Voronoi polygons are bigger than the 1 sq km limit. Perhaps some other JTS function in catagory CreateRandomShape would be a better starting point. With RandomPointsInGrid it is possible to define a grid and guarantee that that the density of the initial points is high enough but this function does not seem to take a polygon as input. Anyway, I have a feeling that you can do what you want with JTS. It will be interesting to see your solution.

See also:

http://lin-ear-th-inking.blogspot.fi/2010/05/random-points-in-polygon-in-jts.html

http://lin-ear-th-inking.blogspot.fi/2009/04/delaunay-triangulation-in-jts-111.html

http://lin-ear-th-inking.blogspot.fi/2009/05/voronoi-diagrams-in-jts-111.html