當前位置：首頁 > 科技 > 軟件

點線面的智慧: 轉轉JTS技術如何塑造上門履約地理布局

來源：責編：時間：2024-07-12 17:27:05 715觀看

導讀1、引言如上圖所示，在轉轉上門履約的場景中，上門服務的覆蓋區域是在地圖上畫電子圍欄來劃定的。這就涉及到一些幾何圖形的操作和空間關系判斷，其中最核心問題就是要解決如何判斷位置是否在上門覆蓋范圍內。下面介紹下 JT

1、引言

如上圖所示，在轉轉上門履約的場景中，上門服務的覆蓋區域是在地圖上畫電子圍欄來劃定的。這就涉及到一些幾何圖形的操作和空間關系判斷，其中最核心問題就是要解決如何判斷位置是否在上門覆蓋范圍內。下面介紹下 JTS，以及如何通過 JTS 的空間之力來解決這些問題。

2、JTS 介紹

JTS，全稱 Java Topology Suite，是一個用于創建和操作向量幾何的 Java 庫。提供了對幾何模型的抽象，以及各種空間操作和空間關系判斷，非常強大。

2.1 引入 jar 包

JTS 有多個模塊，這里只使用了核心的模塊。

jts-core：提供幾何模型的抽象、空間操作、空間關系判斷算法等
jts-io-common：提供各種格式描述幾何模型的輸入輸出包，如對 WKT、WKB 等格式

<dependency>  <groupId>org.locationtech.jts</groupId>  <artifactId>jts-core</artifactId>  <version>1.19.0</version></dependency><dependency>    <groupId>org.locationtech.jts.io</groupId>    <artifactId>jts-io-common</artifactId>    <version>1.19.0</version></dependency>

2.2 基本的幾何模型

JTS 提供了常見的幾何模型抽象，并且各具特點。

模型	定義	常見應用
點（Point）	空間中的單個位置，由一對 x,y 坐標表示	興趣點、事件位置等
多點（MultiPoint）	由多個獨立的點組成的幾何對象	表示多個相關但分散的位置，如連鎖店分布，多個不同人位置
線（LineString）	由一系列點組成的一維幾何對象，有起點和終點，中間可以有任意數量的點	表示道路、河流等線性特征
多線（MultiLineString）	由多個不相連的 LineString 組成的幾何對象	表示復雜的道路網絡、等高線等
多邊形（Polygon）	由一系列首尾相連的線段圍成的平面區域（可以有內部空洞）	表示行政區劃、建筑物輪廓等
多多邊形（MultiPolygon）	由多個獨立的 Polygon 組成的幾何對象，可以表示不相連的多個區域	表示群島、復雜的行政區劃
幾何集合（GeometryCollection）	可以包含任意類型幾何對象的集合，最靈活的幾何類型，可以混合包含點、線、面等	表示復雜的空間場景，如包含多種類型要素的地圖

在 JTS 中的各幾何模型對象關系如下所示：

在實際應用場景中，最常使用的模型如下：

點（Point）：表示位置信息，如用戶地址位置、工程師位置等
多邊形（Polygon）、多多邊形（MultiPolygon）：用來表示上門履約的覆蓋區域

2.3 幾何模型的描述格式

WKT（Well-Know Text）格式是一種文本格式，用于描述二維和三維幾何對象的空間特征。WKT 的基本語法格式如下：

幾何模型類型 (模型數據)

示例如下所示：

點：POINT (282 455)線：LINESTRING (260 250, 485 248, 520 380)多邊形：POLYGON ((320 390, 370 330, 470 360, 460 430, 375 432, 320 390))

JTS 支持對該格式的讀寫操作，主要是兩個對象WKTReader和WKTWriter，代碼示例如下：

// 讀取wkt描述的幾何對象WKTReader wktReader = new WKTReader();Geometry point = wktReader.read("POINT (282 455)");Geometry line = wktReader.read("LINESTRING (260 250, 485 248, 520 380)");Geometry polygon = wktReader.read("POLYGON ((320 390, 370 330, 470 360, 460 430, 375 432, 320 390))");// 輸出幾何對象的wkt描述WKTWriter wktWriter = new WKTWriter();System.out.println(wktWriter.write(point));System.out.println(wktWriter.write(line));System.out.println(wktWriter.write(polygon));

2.4 空間關系

JTS 中的空間關系是基于 DE-9IM（Dimensionally Extended Nine-Intersection Model）模型定義的，這里列舉常見的空間關系

空間關系	定義
相等 (Equals)	兩個幾何對象在拓撲上相等
相離 (Disjoint)	兩個幾何對象沒有任何共同點
相交 (Intersects)	兩個幾何對象有至少一個共同點
內含 (Within)	幾何對象 A 完全位于幾何對象 B 內部
包含 (Contains)	幾何對象 A 完全包含幾何對象 B

以該圖形為例，兩個多邊形的關系判斷的代碼示例

WKTReader wktReader = new WKTReader();Geometry geometryA = wktReader.read("POLYGON ((320 390, 370 330, 470 360, 460 430, 375 432, 320 390))");Geometry geometryB = wktReader.read("POLYGON ((500 420, 430 360, 530 260, 500 420))");System.out.println("Equal: " + geometryA.equals(geometryB));System.out.println("Disjoint: " + geometryA.disjoint(geometryB));System.out.println("Intersects: " + geometryA.intersects(geometryB));System.out.println("Within: " + geometryA.within(geometryB));System.out.println("Contains: " + geometryA.contains(geometryB));

在實際場景中，判斷上門位置是否在上門區域內，轉換成空間關系的判斷就是點是否在多邊形內。解決該問題的實例代碼如下：

WKTReader wktReader = new WKTReader();Geometry geometryA = wktReader.read("POLYGON ((320 390, 370 330, 470 360, 460 430, 375 432, 320 390))");Geometry geometryB = wktReader.read("POLYGON ((500 420, 430 360, 530 260, 500 420))");Geometry point = wktReader.read("POINT (390 380)");System.out.println("point in geometryA: " + geometryA.contains(point));System.out.println("point in geometryB: " + geometryB.contains(point));

2.5 空間操作

JTS 提供了豐富的空間操作功能，用于處理和分析幾何對象。這里列舉常見的幾種

空間操作	定義
相交 (Intersection)	計算兩個幾何對象的共同部分
并集 (Union)	合并兩個或多個幾何對象
差集 (Difference)	從一個幾何對象中減去另一個幾何對象

以該圖為例，操作示例代碼如下：

WKTReader wktReader = new WKTReader();Geometry geometryA = wktReader.read("POLYGON ((320 390, 370 330, 470 360, 460 430, 375 432, 320 390))");Geometry geometryB = wktReader.read("POLYGON ((500 420, 430 360, 530 260, 500 420))");System.out.println("Intersection: " + wktWriter.write(geometryA.intersection(geometryB)));System.out.println("Union: " + wktWriter.write(geometryA.union(geometryB)));System.out.println("Difference: " + wktWriter.write(geometryA.difference(geometryB)));

下面是 Union 合并后的效果

3、快速判斷是否支持上門

在上門履約實際場景中，需要快速的識別用戶所在位置、地址位置是否在上門服務的覆蓋區域內。轉換成空間關系的判斷上，也就是點是否在多邊形內（PIP，Point-In-Polygon）問題了。

在上述的 JTS 介紹中，已經得知 JTS 提供了 contains 的關系判斷能力。但是這只是解決了單個問題，假設全國共有 N 個多邊形，那么就需要遍歷 N 個多邊形來判斷，復雜度是 O(N)，并且還需要全部多邊形加載到內存中。可想而知，直接使用的話會存在性能問題。為此，我們需要一個快速解決 PIP 問題的方案。

3.1 最小外接矩形（MBR）

最小外接矩形 MBR (Minimum Bounding Retangle)，是能夠完全包含一個幾何對象的最小矩形。如下圖所示，這個規則的矩形就是該多邊形的 MBR 表示。

表示 MBR 非常簡單，只需要知道他的左下角和右上角，那么就可以知道這個 MBR 圖形了。如下圖所示：

知道了這個最小外接矩形有什么用？可以斷定：如果點不在這個 MBR 內了，那么肯定不在這個多邊形內。所以把點和 MBR 進行比較，就能夠快速排除不可能有關系的多邊形對象。

那么如何快速的判斷點是否在 MBR 中？比較坐標值的大小就可以了。示例代碼如下：

mbr.getLngMin() <= point.getLng()&& mbr.getLngMax() >= point.getLng()&& mbr.getLatMin() <= point.getLat()&& mbr.getLatMax() >= point.getLat()

綜上，MBR 用簡單的矩形來近似表示復雜的幾何形狀，將復雜的空間關系簡化為矩形之間的關系。 通過 MBR 這一層的初步篩選，就能夠快速排除不可能有關系的多邊形對象。

在 JTS 中，Envelope 對象來表示 MBR。代碼示例如下：

WKTReader wktReader = new WKTReader();Geometry geometryA = wktReader.read("POLYGON ((320 390, 370 330, 470 360, 460 430, 375 432, 320 390))");Envelope envelope = geometryA.getEnvelopeInternal();System.out.println(envelope.getMaxX());System.out.println(envelope.getMaxY());System.out.println(envelope.getMinX());System.out.println(envelope.getMinY());

3.2 空間索引

上述構建 MBR 可以理解為簡單索引的一種，實際上有復雜的空間索引。常見空間索引有

R 樹（R-tree）：平衡樹，適用于多維空間數據（類似一維的 B+樹）
四叉樹（Quad-tree）：將二維空間遞歸地分為四個象限
網格（Grid）：將空間劃分為規則的網格單元

空間索引的基本原理基本類似，采用分割原理，逐級劃分地理空間。舉個不那么恰當的例子，一個自上而下、逐級劃分地理空間的索引定位過程如下：

北方 還是 南方 ？ 南方廣東 還是 廣西 ？ 廣東深圳 還是 廣州 ？ 深圳福田 還是 南山 ？ 福田

JTS 提供了四叉樹和 R 樹的實現

Quadtree（四叉樹）
STRtree（基于 R 樹的變體）

以這個圖形為例，使用 JTS 構建 R 樹空間索引

示例代碼如下：

WKTReader wktReader = new WKTReader();Geometry geometryA = wktReader.read("POLYGON ((320 390, 370 330, 470 360, 460 430, 375 432, 320 390))");Geometry geometryB = wktReader.read("POLYGON ((500 420, 430 360, 530 260, 500 420))");STRtree rtree = new STRtree();// 向R樹種添加MBR，和自己的數據rtree.insert(geometryA.getEnvelopeInternal(), "Polygon-A");rtree.insert(geometryB.getEnvelopeInternal(), "Polygon-B");rtree.build();// 點只在Polygon-A中System.out.println(rtree.query(wktReader.read("POINT (337 391)").getEnvelopeInternal()));// 點只在Polygon-B中System.out.println(rtree.query(wktReader.read("POINT (496 390)").getEnvelopeInternal()));// 點在Polygon-A和Polygon-B的交集中System.out.println(rtree.query(wktReader.read("POINT (452 367)").getEnvelopeInternal()));

3.3 整體方案流程

綜上所述，快速定位點（Point）在哪些多邊形中的具體流程如下：

先通過 STRtree 構建空間索引
利用空間索引快速篩選可能包含點的多邊形
對篩選后的多邊形進行精確的空間關系判斷

多邊形是隨時都有可能可以調整，如果一個多邊形發生了調整就需要重構整顆索引樹。但是在實踐中，為了降低構建索引樹的頻次，通過定時任務去間隔 10 分鐘在內存中構建一次。并且為了減少索引樹占用的內存大小，向索引樹中添加 MBR 關聯的是多邊形的 Id，初篩后再根據 id 從緩存中取具體的多邊形數據進行精確的空間關系判斷，實現一個類似懶加載的過程。

具體流程如下圖所示：

4、幾何圖形的修復處理

在實際運營過程中，畫的圖形各種形狀，會出現不少異常的情況，如點重疊、邊之間細微的間隙、自交等問題。實際操作中還提拱了圖形合并的能力，合并出來的圖像也有可能也是不符合規范的。為此，需要對這些異常的圖像進行修復。

常見的修復手段有兩種

Buffer 操作：在幾何對象周圍的創建緩沖區，一般用來修復自相交問題、精度導致的小間隙等
Snap 操作：一個幾何對象的頂點捕捉到另一個幾何對象的頂點或邊緣，一般用來修復小的拓撲錯誤

這兩種操作也不是萬能，也是需要自己根據實際情況進行不斷地調整。

下面來看一個修復自交的例子，一個自交的圖形如下所示：

修復代碼示例如下：

WKTReader wktReader = new WKTReader();Geometry geometryA = wktReader.read("POLYGON ((340 490, 370 330, 730 350, 700 270, 340 490))");WKTWriter wktWriter = new WKTWriter();wktWriter.setPrecisionModel(new PrecisionModel(0));System.out.println(wktWriter.write(geometryA.buffer(0)));

修復之后如下圖所示

5、總結

Java Topology Suite (JTS) 作為一個功能強大的空間數據處理庫，為開發者提供了豐富的工具來處理復雜的空間問題。它在許多地理信息系統得到了廣泛的應用。這里只是對其的一個簡單應用，后續還待更深入的挖掘。

6、參考

Java Topology Suite (JTS)：https://github.com/locationtech/jts
OSGeo中國：https://www.osgeo.cn/

本文鏈接：http://www.www897cc.com/showinfo-26-100740-0.html點線面的智慧: 轉轉JTS技術如何塑造上門履約地理布局

聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。郵件：2376512515@qq.com

上一篇：解鎖搜索的力量：關鍵詞、相似性和語義解釋

下一篇： 2024 最值得關注的 Rust Web 框架！

標簽：

熱門焦點

鴻蒙OS 4.0公測機型公布：甚至連nova6都支持

華為全新的HarmonyOS 4.0操作系統將于今天下午正式登場，官方在發布會之前也已經正式給出了可升級的機型產品，這意味著這些機型會率先支持升級享用。這次的HarmonyOS 4.0支持
iPhone賣不動了！蘋果股價創年內最大日跌幅：市值一夜蒸發萬億元

8月5日消息，今天凌晨美股三大指數高開低走集體收跌，道指跌0.41%；納指跌0.36%；標普500指數跌0.52%。熱門科技股也都變化極大，其中蘋果報181.99美元，跌4.8%，創
多線程開發帶來的問題與解決方法

使用多線程主要會帶來以下幾個問題：（一）線程安全問題　　線程安全問題指的是在某一線程從開始訪問到結束訪問某一數據期間，該數據被其他的線程所修改，那么對于當前線程而言，該線程
2天漲粉255萬，又一賽道在抖音爆火

來源：運營研究社作者 | 張知白編輯 | 楊佩汶設計 | 晏談夢潔這個暑期，旅游賽道徹底火了：有的「地方」火了——貴州村超旅游收入 1 個月超過 12 億；有的「博主」火了&m
得物寵物生意「狂飆」，發力“它經濟”

作者｜花花小萌主近日，得物宣布正式上線寵物鑒別，通過得物App內的“在線鑒別”，可找到鑒別寵物的選項。通過上傳自家寵物的部位細節，就能收獲擁有專業資質認證的得物鑒
騰訊蓋樓，字節拆墻

來源 | 光子星球撰文 | 吳坤諺編輯 | 吳先之“想重溫暴刷深淵、30+技能搭配暴搓到爽的游戲體驗嗎？一起上晶核，即刻暴打！”曾憑借直播騰訊旗下代理格斗游戲《DNF》一
ESG的面子與里子

來源 | 光子星球撰文 | 吳坤諺編輯 | 吳先之三伏大幕拉起，各地高溫預警不絕，但處于厄爾尼諾大“烤”之下的除了眾生，還有各大企業發布的ESG報告。ESG是“環境保
信通院：小米、華為等11家應用商店基本完成APP簽名及驗簽工作

中國信通院表示，目前，小米、華為、OPPO、vivo、360手機助手、百度手機助手、應用寶、豌豆莢和努比亞等9家應用商店，以及抖音和快手2家新型應用分發平
三星折疊屏手機去年銷售近1000萬臺今年目標定為1500萬

7月29日消息，三星率先發力可折疊手機市場，在全球市場已經取得了非常亮眼的成績，接下來會進一步鞏固和擴大這一優勢。三星在推出Galaxy Z Flip5和Galax

日韩成人免费在线_国产成人一二_精品国产免费人成电影在线观..._日本一区二区三区久久久久久久久不

點線面的智慧: 轉轉JTS技術如何塑造上門履約地理布局

1、引言

2、JTS 介紹

2.1 引入 jar 包

2.2 基本的幾何模型

2.3 幾何模型的描述格式

2.4 空間關系

2.5 空間操作

3、快速判斷是否支持上門

3.1 最小外接矩形（MBR）

3.2 空間索引

3.3 整體方案流程

4、幾何圖形的修復處理

5、總結

6、參考

鴻蒙OS 4.0公測機型公布：甚至連nova6都支持

iPhone賣不動了！蘋果股價創年內最大日跌幅：市值一夜蒸發萬億元

多線程開發帶來的問題與解決方法

2天漲粉255萬，又一賽道在抖音爆火

得物寵物生意「狂飆」，發力“它經濟”

騰訊蓋樓，字節拆墻

ESG的面子與里子

信通院：小米、華為等11家應用商店基本完成APP簽名及驗簽工作

三星折疊屏手機去年銷售近1000萬臺今年目標定為1500萬

最新推薦

猜你喜歡

熱門推薦

相關資訊