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?

  • 1
    I suspect finding such an algorithm may be more on-topic for Mathematics but one thing you may need to specify wherever the question finishes is whether it can be assumed that there are no true curves involved.
    – PolyGeo
    Commented Feb 6, 2015 at 5:32

1 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:





Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.