最小外接矩形思路以及实现

最小外接矩形
外接矩形计算
对一个凸多边形进行外接矩形计算，需要知道当前面的最大 xy 和最小 xy 值，即可获得外接矩形

最小外接矩形计算
对凸多边形的每一条边都绘制一个外接矩形求最小面积。下图展示了计算流程

计算流程

旋转基础算法实现
旋转点基础
/**
* 旋转点
*
* @param point 被旋转的点
* @param center 旋转中心
* @param angle 角度
* @return 旋转后坐标
*/
public static Coordinate get(Coordinate point, Coordinate center, double angle) {
double cos = Math.cos(angle);
double sin = Math.sin(angle);
double x = point.x;
double y = point.y;
double centerX = center.x;
double centerY = center.y;
return new Coordinate(centerX + cos * (x – centerX) – sin * (y – centerY),
centerY + sin * (x – centerX) + cos * (y – centerY));
}

凸包算法实现
Geometry hull = (new ConvexHull(geom)).getConvexHull();

获得结果
public static Polygon get(Geometry geom, GeometryFactory gf) {
Geometry hull = (new ConvexHull(geom)).getConvexHull();
if (!(hull instanceof Polygon)) {
return null;
}
Polygon convexHull = (Polygon) hull;
System.out.println(convexHull);

// 直接使用中心值
Coordinate c = geom.getCentroid().getCoordinate();
System.out.println(“============== 旋转基点 ==============”);
System.out.println(new GeometryFactory().createPoint(c));
System.out.println(“============== 旋转基点 ==============”);
Coordinate[] coords = convexHull.getExteriorRing().getCoordinates();

double minArea = Double.MAX_VALUE;
double minAngle = 0;
Polygon ssr = null;
Coordinate ci = coords[0];
Coordinate cii;
for (int i = 0; i < coords.length – 1; i++) {
cii = coords[i + 1];
double angle = Math.atan2(cii.y – ci.y, cii.x – ci.x);
Polygon rect = (Polygon) Rotation.get(convexHull, c, -1 * angle, gf).getEnvelope();
double area = rect.getArea();
// 此处可以将 rotationPolygon 放到 list 中求最小值
// Polygon rotationPolygon = Rotation.get(rect, c, angle, gf);
// System.out.println(rotationPolygon);
if (area < minArea) {
minArea = area;
ssr = rect;
minAngle = angle;
}
ci = cii;
}

return Rotation.get(ssr, c, minAngle, gf);
}

测试类
@Test
public void test() throws Exception{
GeometryFactory gf = new GeometryFactory();
String wkt = “POLYGON ((87623.0828822501 73753.4143904365,87620.1073981973 73739.213216548,87629.1690996309 73730.4220136646,87641.882531493 73727.3112803367,87643.0997749692 73714.8683470248,87662.0346734872 73725.0120426595,87669.0676357939 73735.1557382941,87655.9484561064 73735.9672339449,87676.9120937514 73747.4634223308,87651.8909778525 73740.8362078495,87659.4649372597 73755.4431295634,87644.4522677204 73748.680665807,87645.5342619215 73760.7178512935,87635.2553170117 73750.9799034842,87630.5215923822 73760.3121034681,87623.0828822501 73753.4143904365))”;
Polygon read = (Polygon) new WKTReader().read(wkt);
Polygon polygon = MinimumBoundingRectangle.get(read, gf);

// System.out.println(polygon);
// System.out.println(polygon.getArea());

}

注
本文代码及可视化代码均放在 gitee 码云上 欢迎 star & fork