您现在的位置是:首页 > 正文

Java求geometry的面积最小外接矩形

2024-02-01 05:55:39阅读 2

Java求geometry的面积最小外接矩形

geom.getEnvelope() 得到外接矩形,不一定是面积最小;可以对多边形的每一条边求外接矩形,然后比较得到最小外接矩形

  • geom.getEnvelope()); // 外接矩形4个点
  • geom.getEnvelopeInternal()); // 外接矩形对角线俩点
  • geom.getBoundary()); // 首尾俩点
  • (new ConvexHull(geom)).getConvexHull(); // 获取凸包(凸包可以理解为线,多线闭合后的多边形)

这篇博客将分为3步进行求解;
1. 获取Envelope的外接矩形,获取面积;
2. 获取凸包,旋转获取每一条边对应的外接矩形,得到凸包面积最小外接矩形;
3. 将1获取的矩形与2获取的矩形面积进行比较,得到最终的面积最小外接矩形;

以上可得出,Envelope获取的外接矩形和凸包旋转获取的外接矩形均有可能为面积最小矩形。下边用俩个例子证明这一点;

1. 效果图

原始geom 黄色线 VS 凸包淡紫色填充:

在这里插入图片描述

原始geom VS Envelope外接矩形 VS 凸包旋转后最小面积矩形 VS EnvelopeInternal对角线 VS Boundary首尾点效果图如下:

呈现了俩组几何的结果
外接矩形面以淡紫色填充为:geom.getEnvelope()); // 外接矩形4个点以polygon面渲染;
矩形的对角线黄色线为:geom.getEnvelopeInternal()); // 外接矩形对角线俩点以线渲染;
原始geom为多点的黄色线;
geom.getBoundary()); // 首尾俩点以蓝色点渲染

在这里插入图片描述可视化可参考之前的博客: 、

Mapbox HTML可视化点,线,多线,面带底图

原始几何 VS Envelope外接矩形 VS 凸包旋转后最小面积矩形 VS EnvelopeInternal对角线 VS Boundary首尾点效果图如下:
在上图的基础上增加了凸包旋转后最小面积矩形,以淡紫色面填充;

在这里插入图片描述

1.1 凸包旋转后的面积最小外接矩形为面积最小矩形可视化如图:

如下图很明显,凸包旋转后的矩形面积比Envelope获取到的矩形面积要小。凸包旋转后的矩形是面积最小矩形。
在这里插入图片描述
代码验证下确实如此:
在这里插入图片描述

1.2 Envelope矩形为面积最小矩形

凸包旋转后的外接矩形不是面积最小矩形可视化如图:
如下图所示,直观来看,凸包旋转后的面积最小矩形 与 Envelope获取到的矩形面积看起来基本差不多,事实是Envelope获取到的矩形是面积最小矩形。
在这里插入图片描述

代码验证如下:Envelope获取到的矩形是面积最小矩形。
在这里插入图片描述

2. java源码

<dependency>
    <groupId>com.vividsolutions</groupId>
    <artifactId>jts</artifactId>
    <version>1.13</version>
</dependency>
import com.vividsolutions.jts.algorithm.ConvexHull;
import com.vividsolutions.jts.geom.*;
import com.vividsolutions.jts.io.ParseException;
import com.vividsolutions.jts.io.WKTReader;
import lombok.extern.slf4j.Slf4j;
import org.junit.jupiter.api.Test;

/*************************************
 *Class Name: TestGeomMinRectangle
 *Description: <测试获取Geometry面积最小外接矩形>
 *@author: Seminar
 *@create: 2022/9/25
 *@since 1.0.0
 *************************************/
@Slf4j
public class TestGeomMinRectangle {

    private static GeometryFactory gf = new GeometryFactory();

    // 多边形几何
    String polygon;
    // 线几何
    String lineString;
    // 多边几何
    String multiPoint;

    /**
     * 初始化wkt
     */
    public void initWkt() {
        this.polygon = "POLYGON ((116.42486572265626 39.99500778093748, 116.51962280273439 39.886557705928475, 116.44546508789064 39.78110197709871, 116.31637573242189 39.818029898770206, 116.27655029296876 39.93817189499188, 116.42486572265626 39.99500778093748))";

        this.lineString = "LINESTRING (117.18292236328126 40.16208338164619, 119.01489257812501 39.48284540453334)";

        this.multiPoint = "MULTIPOINT ((115.48690795898439 40.12639098502455), (115.80139160156251 40.148438503139076), (115.83847045898439 39.9665957444875), (115.90850830078126 39.854937988531276), " +
                "(115.98403930664062 39.816975090490004), (115.84808349609376 39.769491963709), (115.60638427734376 39.707186656826565), (115.44708251953126 39.82119422647455), " +
                "(115.32348632812501 39.961332959837826), (115.36605834960939 40.09593265290902), (115.59951782226564 39.940277770390324), (115.74371337890626 39.842286020743394), " +
                "(115.58715820312501 39.79271003204449), (115.76019287109376 39.7631584037253), (115.87280273437501 39.67759833072648), (115.96481323242189 40.18307014852534), " +
                "(115.69152832031251 40.2155868104582), (115.63934326171876 40.073868105094846), (115.43060302734376 39.56547053068436), (115.66955566406251 39.470125122358176), " +
                "(115.83709716796875 39.55911824217187), (115.91949462890626 39.44679856427205), (115.54046630859376 39.42346418978385), (115.07354736328125 39.63319206567459), " +
                "(115.11474609375 40.092781012494065), (115.19439697265626 40.287906612507406), (114.98291015625001 39.83385008019448), (114.97467041015626 39.47224533091451), " +
                "(115.27130126953126 39.38101803294523), (115.59265136718751 39.34067026099156))";
    }

    /**
     * wkt 转geometry
     *
     * @param wkt
     * @return
     * @throws ParseException
     */
    public static Geometry wkt2Geo(String wkt) throws ParseException {
        WKTReader reader = new WKTReader(gf);
        Geometry geom = reader.read(wkt);
        return geom;
    }

    /**
     * 旋转
     *
     * @param coord  旋转坐标
     * @param center 旋转中心
     * @param angle  角度
     * @return 旋转后结果
     */
    public static Coordinate[] get(Coordinate[] coord, Coordinate center, double angle) {
        Coordinate[] newCoord = new Coordinate[coord.length];
        double cos = Math.cos(angle), sin = Math.sin(angle);
        double xc = center.x, yc = center.y;
        Coordinate ci;
        double x, y;
        for (int i = 0; i < coord.length; i++) {
            ci = coord[i];
            x = ci.x;
            y = ci.y;
            newCoord[i] = new Coordinate(xc + cos * (x - xc) - sin * (y - yc),
                    yc + sin * (x - xc) + cos * (y - yc));
        }
        return newCoord;
    }

    /**
     * 旋转点
     *
     * @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));
    }

    /**
     * 旋转
     *
     * @param geom   geometry
     * @param center 旋转中心
     * @param angle  旋转角度
     * @param gf     构造器
     * @return 旋转结果
     */
    public static Geometry get(Geometry geom, Coordinate center, double angle, GeometryFactory gf) {
        if (geom instanceof Point) {
            return get((Point) geom, center, angle, gf);
        } else if (geom instanceof Polygon) {
            return get((Polygon) geom, center, angle, gf);
        } else if (geom instanceof LineString) {
            return get((LineString) geom, center, angle, gf);
        } else if (geom instanceof LinearRing) {
            return get((LinearRing) geom, center, angle, gf);
        }
        return null;
    }

    /**
     * 旋转
     *
     * @param linearRing 旋转环
     * @param center     旋转中心
     * @param angle      旋转角度
     * @param gf         构造器
     * @return 旋转后结果
     */
    public static LinearRing get(LinearRing linearRing, Coordinate center, double angle,
                                 GeometryFactory gf) {
        return gf.createLinearRing(get(linearRing.getCoordinates(), center, angle));
    }

    /**
     * x旋转
     *
     * @param geom   旋转面
     * @param center 旋转中心
     * @param angle  旋转角度
     * @param gf     构造器
     * @return 旋转结果
     */
    public static Polygon rotationPolygon(Polygon geom, Coordinate center, double angle, GeometryFactory gf) {
        LinearRing linearRing = get((LinearRing) geom.getExteriorRing(), center, angle, gf);
        LinearRing[] linearRings = new LinearRing[geom.getNumInteriorRing()];
        for (int j = 0; j < geom.getNumInteriorRing(); j++) {
            linearRings[j] = get((LinearRing) geom.getInteriorRingN(j), center, angle, gf);
        }
        return gf.createPolygon(linearRing, linearRings);
    }

    public static Polygon getRotatedMinRectangle(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) rotationPolygon(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 rotationPolygon(ssr, c, minAngle, gf);
    }

    /**
     * 获取geom的面积最小外接矩形
     * 1. 获取Envelope的外接矩形,获取面积;
     * 2. 获取凸包,旋转获取每一条边对应的外接矩形,得到凸包面积最小外接矩形;
     * 3. 将1获取的矩形与2获取的矩形面积进行比较,得到最终的面积最小外接矩形;
     *
     * @param geom
     * @return
     */
    private Geometry getMinRectangle(Geometry geom) {
        double envelopeArea = geom.getEnvelope().getArea();
        double rotateMinArea = getRotatedMinRectangle(geom, gf).getArea();
        return envelopeArea > rotateMinArea ? getRotatedMinRectangle(geom, gf) : geom.getEnvelope();
    }

    @Test
    public void testGeom() throws ParseException {
        String lineString = "LINESTRING(120.067304 30.39167,120.067304 30.36469," +
                "120.04022 30.3512,120.013136 30.36469," +
                "120.013136 30.39167,120.04022 30.40516)";
        lineString = "LINESTRING(120.14322240845 30.236064370321," +
                "120.1233608862 30.224531990576,120.0831192649 30.238661839459," +
                "120.07632605996 30.2524671110650)";
        Geometry geom = wkt2Geo(lineString);
        log.info("origin  : {}", lineString);
        log.info("Envelope: {} {}", geom.getEnvelope().getArea(), geom.getEnvelope()); // 外接矩形4个点
        log.info("{}", geom.getEnvelopeInternal()); // 外接矩形对角线俩点
        log.info("{}", geom.getBoundary()); // 首尾俩点
        log.info("{}", (new ConvexHull(geom)).getConvexHull()); // 凸包
        log.info("Rotated : {} {}", getRotatedMinRectangle(geom, gf).getArea(), getRotatedMinRectangle(geom, gf));
        log.info("Min     : {} {}", getMinRectangle(geom).getArea(), getMinRectangle(geom));
    }
}

3. html源码

multi2.html

<!DOCTYPE html>
<html>
<head>
    <meta charset="utf-8">
    <title>Add multiple geometries from one GeoJSON source</title>
    <meta name="viewport" content="initial-scale=1,maximum-scale=1,user-scalable=no">
    <link href="https://api.mapbox.com/mapbox-gl-js/v2.1.1/mapbox-gl.css" rel="stylesheet">
    <script src="https://api.mapbox.com/mapbox-gl-js/v2.1.1/mapbox-gl.js"></script>
    <style>
        body {
            margin: 0;
            padding: 0;
        }

        #map {
            position: absolute;
            top: 0;
            bottom: 0;
            width: 100%;
        }
    </style>
</head>
<body>
<div id="map"></div>
<script>

    mapboxgl.accessToken = 'xxxxx';
    var map = new mapboxgl.Map({
        container: 'map',
        style: 'mapbox://styles/mapbox/streets-v11',
        center: [120.06022, 30.37818], //地图中心点
        zoom: 10
    });

    map.on('load', function () {
        map.addSource('national-park', {
            'type': 'geojson',
            'data': {
                'type': 'FeatureCollection',
                'features': [
                    //凸包
                    {
                        'type': 'Feature',
                        'geometry': {
                            'type': 'Polygon',
                            'coordinates': [
                                [
                                    [120.04022, 30.3512], [120.013136, 30.36469],
                                    [120.013136, 30.39167], [120.04022, 30.40516],
                                    [120.067304, 30.39167],
                                    [120.067304, 30.36469], [120.04022, 30.3512]
                                ]
                            ]
                        }
                    },
                    // Envelope外接矩形
                    {
                        'type': 'Feature',
                        'geometry': {
                            'type': 'Polygon',
                            'coordinates': [
                                [
                                    [120.013136, 30.3512], [120.013136, 30.40516],
                                    [120.067304, 30.40516], [120.067304, 30.3512]
                                ]
                            ]
                        }
                    },
                    // 旋转后最小面积外接矩形
                    {
                        'type': 'Feature',
                        'geometry': {
                            'type': 'Polygon',
                            'coordinates': [
                                [
                                    [120.07807106579423, 30.38630713936036],
                                    [120.05653693420575, 30.34307286063966],
                                    [120.00236893420576, 30.370052860639653],
                                    [120.02390306579424, 30.413287139360353],
                                    [120.07807106579423, 30.38630713936036]
                                ]
                            ]
                        }
                    },
                    // 原始几何线
                    {
                        'type': 'Feature',
                        'geometry': {
                            'type': 'LineString',
                            'coordinates': [
                                [120.067304, 30.39167],
                                [120.067304, 30.36469],
                                [120.04022, 30.3512],
                                [120.013136, 30.36469],
                                [120.013136, 30.39167],
                                [120.04022, 30.40516]
                            ]
                        }
                    },
                    // getEnvelopeInternal对角线
                    {
                        'type': 'Feature',
                        'geometry': {
                            'type': 'LineString',
                            'coordinates': [
                                [120.013136, 30.40516],
                                [120.067304, 30.3512]
                            ]
                        }
                    },
                    // getBoundary首点
                    {
                        'type': 'Feature',
                        'geometry': {
                            'type': 'Point',
                            'coordinates': [120.067304, 30.39167]
                        }
                    },
                    // getBoundary尾点
                    {
                        'type': 'Feature',
                        'geometry': {
                            'type': 'Point',
                            'coordinates': [120.04022, 30.40516]
                        }
                    },


                    //凸包
                    {
                        'type': 'Feature',
                        'geometry': {
                            'type': 'Polygon',
                            'coordinates': [
                                [
                                    [120.1233608862, 30.224531990576], [120.0831192649, 30.238661839459],
                                    [120.07632605996, 30.252467111065], [120.14322240845, 30.236064370321],
                                    [120.1233608862, 30.224531990576]
                                ]
                            ]
                        }
                    },
                    {
                        'type': 'Feature',
                        'geometry': {
                            'type': 'Polygon',
                            'coordinates': [
                                [
                                    [120.07632605996, 30.224531990576], [120.07632605996, 30.252467111065],
                                    [120.14322240845, 30.252467111065], [120.14322240845, 30.224531990576]
                                ]
                            ]
                        }
                    },
                    {
                        'type': 'Feature',
                        'geometry': {
                            'type': 'Polygon',
                            'coordinates': [
                                [
                                    [120.07253234575715, 30.236994963370464],
                                    [120.07632605996001, 30.252467111064995],
                                    [120.14322240845, 30.236064370321],
                                    [120.13942869424714, 30.22059222262647]
                                ]
                            ]
                        }
                    },
                    {
                        'type': 'Feature',
                        'geometry': {
                            'type': 'LineString',
                            'coordinates': [
                                [
                                    120.14322240845,
                                    30.236064370321
                                ],
                                [
                                    120.1233608862,
                                    30.224531990576
                                ],
                                [
                                    120.0831192649,
                                    30.238661839459
                                ],
                                [
                                    120.07632605996,
                                    30.252467111065
                                ]
                            ]
                        }
                    },
                    {
                        'type': 'Feature',
                        'geometry': {
                            'type': 'LineString',
                            'coordinates': [
                                [120.07632605996, 30.252467111065],
                                [120.14322240845, 30.224531990576]
                            ]
                        }
                    },
                    {
                        'type': 'Feature',
                        'geometry': {
                            'type': 'Point',
                            'coordinates': [120.07632605996, 30.252467111065]
                        }
                    },
                    {
                        'type': 'Feature',
                        'geometry': {
                            'type': 'Point',
                            'coordinates': [120.14322240845, 30.236064370321]
                        }
                    }
                ]
            }
        });

        map.addLayer({
            'id': 'park-boundary',
            'type': 'fill',
            'source': 'national-park',
            'paint': {
                'fill-color': '#AE00F2',
                'fill-opacity': 0.4
            },
            'filter': ['==', '$type', 'Polygon']
        });

        map.addLayer({
            'id': 'route',
            'type': 'line',
            'source': 'national-park',
            'layout': {
                'line-join': 'round',
                'line-cap': 'round'
            },
            'paint': {
                'line-color': '#DEFF00',
                'line-width': 3
            },
            'filter': ['==', '$type', 'LineString']
        });

        map.addLayer({
            'id': 'park-volcanoes',
            'type': 'circle',
            'source': 'national-park',
            'paint': {
                'circle-radius': 6,
                'circle-color': '#0000FF'
            },
            'filter': ['==', '$type', 'Point']
        });
    });
</script>

</body>
</html>

参考

网站文章

  • 常见的Web应用攻击手段

    常见的Web应用攻击手段 1.XSS攻击 XSS攻击即跨站点脚本攻击(Cross Site Script),指黑客通过篡改网页,注入恶意HTML脚本,在用户浏览网页时,控制用户浏览器进行恶意操作的一种...

    2024-02-01 05:55:09
  • unity 检测物体是否在相机视野范围内

    脚本挂在摄像机要显示的对象上前提:该对象有 render 组件public class visibleTT : MonoBehaviour{ public bool isRendering = false; public float lastTime = 0; public float curTime = 0; void Update() {

    2024-02-01 05:55:03
  • androidstudio 使用正则表达式替换xml相关内容

    androidstudio 使用正则表达式替换xml相关内容

    例如我在xml文件中,需要在edittext增加限制输入数据类型为数字类型 在替换栏中使用$n(n代表正则表达式中括号的索引,从1开始)来保存原来的换行等需要保留的内容 替换后的效果: ...

    2024-02-01 05:54:56
  • 企业的述职如何做才有效?

    企业的述职如何做才有效?

    有句话说的好,群众的眼睛是雪亮的。他们的回答是完全走形式,我的上级就在述职现场那我肯定挑好的说,作用不大。每年的问题都差不多,每年都述职,我都没感觉了。让所有的参与人,包括评估者和被评估者正确理解36...

    2024-02-01 05:54:50
  • 移植RTT--官方教程

    移植RTT--官方教程

    CPU架构移植:大部分的CPU都移植好了,不太需要用户去操作。libcpu文件夹里面就是各种的CPU架构。主要处理标红四个函数: 函数和变量 描述 rt_base_t rt_hw_interrupt_...

    2024-02-01 05:54:20
  • 怎样做到长期写一个价值博客?

    怎样做到长期写一个价值博客?

    怎样做到长期写一个价值博客?(一)为什么你应该(从现在开始就)写博客用一句话来说就是,写一个博客有很多好处,却没有任何明显的坏处。(阿灵顿的情况属于例外,而非常态,就像不能拿抽烟活到一百岁的英国老太太...

    2024-02-01 05:54:14
  • XxlJob(一) 分布式定时任务XxlJob用法及核心调度源码详解

    XxlJob(一) 分布式定时任务XxlJob用法及核心调度源码详解

    XxlJob是目前最流行的分布式定时任务中间件,对比quartz,代码的侵入明显少了很多,而且admin组件提供了可视化ui, 简单易用,目前已经接入几百家物联网公司使用,由此可见XxlJob的强大任务调度能力为广大开发者所认可,那XxlJob是怎么工作的? XxlJob最新依赖版本: 2.3.0 和源码地址: com.xuxueli ...

    2024-02-01 05:54:08
  • java 数据库 html_HTML,Java,C语言,SQL数据库常用单词汇集1

    HTMLlist 列表;img 图片(image);&amp; nbsp; 空格(&amp;和n之间的空格去掉,不要忘记分号); (文字末尾添加)换行;background 背景;position 位...

    2024-02-01 05:53:40
  • JavaScript之迭代器Iterator

    JavaScript之迭代器Iterator

    2024-02-01 05:53:32
  • char str1[]=&quot;abc&quot;; char str2[]=&quot;abc&quot;;str1与str2不相等,为什么

    两者不相等,是因为str1 和 str2 都是字符数组,每个都有其自己的存储区,它们的值则是各存储区的首地址。但有些情况却不一样, 程序如下: #include int main(void) { const char str3[] = &quot;abc&quot;; const char str4[] = &quot;abc&quot;; const char *st

    2024-02-01 05:53:25