最小外接矩形

外接矩形计算

对一个凸多边形进行外接矩形计算，需要知道当前面的最大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());    }