locationtech / jts

The JTS Topology Suite is a Java library for creating and manipulating vector geometry.
Other
1.98k stars 443 forks source link

MinimumDiameter.minimumRectangle result is incorrect #907

Open dr-jts opened 2 years ago

dr-jts commented 2 years ago

As reported in https://github.com/libgeos/geos/issues/679, the result computed by the MinimumDiameter.minimumRectangle method is not always correct. This is because the algorithm assumes the minimum diameter is also the height of the minimum-area rectangle. But this is not always the case, since the perpendicular to the diameter may be long enough that another rectangle is smaller in area.

A reproducer is:

POLYGON ((150 300, 200 300, 300 300, 300 250, 280 120, 210 100, 100 100, 100 240, 150 300))

image

The fix is to create a new MinimumRectangle class using the classic Rotating Calipers algorithm.