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

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

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

導讀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.tebozhan.com/showinfo-26-100740-0.html點線面的智慧: 轉轉JTS技術如何塑造上門履約地理布局

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

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

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

標簽：

熱門焦點

盧偉冰長文解析K60至尊版對Redmi有著里程碑式的意義

在今天的Redmi后性能時代戰略發布會結束之后，Redmi總經理盧偉冰又帶來了一篇長文，詳解了為什么 Redmi 要開啟后性能時代？為什么選擇和 MediaTek、Pixelworks 深度合作？以及后性
Redmi Pad評測：紅米充滿野心的一次嘗試

從Note系列到K系列，從藍牙耳機到筆記本電腦，紅米不知不覺之間也已經形成了自己頗有競爭力的產品體系，在中端和次旗艦市場上甚至要比小米新機的表現來得更好，正所謂“大丈夫生居
0糖0卡0脂旭日森林仙草烏龍茶優惠：15瓶到手29元

旭日森林無糖仙草烏龍茶510ml*15瓶平時要賣為79.9元，今日下單領取50元優惠券，到手價為29.9元。產品規格：0糖0卡0脂，添加草本仙草汁，清涼爽口，富含茶多酚，保留
中國家電海外掘金正當時｜出海專題

作者｜吳南南編輯｜胡展嘉運營｜陳佳慧出品｜零態LT（ID：LingTai_LT）2023年，出海市場戰況空前，中國創業者在海外紛紛摩拳擦掌，以期能夠把中國的商業模式、創業理念、戰略打法輸出海外，他們依
網紅炒股不為了賺錢，那就是耍流氓！

來源：首席商業評論6月26日高調宣布入市，網絡名嘴大v胡錫進居然進軍了股市。在一次財經媒體峰會上，幾個財經圈媒體大佬就“胡錫進炒股是否知道認真報道”展開討論。有
2納米決戰2025

集微網報道從三強爭霸到四雄逐鹿，2nm的廝殺聲已然隱約傳來。無論是老牌勁旅臺積電、三星，還是誓言重回先進制程領先地位的英特爾，甚至初成立不久的新
三星Galaxy Z Fold5今日亮相：厚度縮減但仍略顯厚重

據官方此前宣布，三星將于7月26日也就是今天在韓國首爾舉辦Unpacked活動，屆時將帶來帶來包括Galaxy Buds 3、Galaxy Watch 6、Galaxy Tab S9、Galaxy
三星Galaxy Z Fold/Flip 5國行售價曝光：最低7499元/12999元起

據官方此前宣布，三星將于7月26日也就是明天在韓國首爾舉辦Unpacked活動，屆時將帶來帶來包括Galaxy Buds 3、Galaxy Watch 6、Galaxy Tab S9、Galaxy
OPPO K11評測：旗艦級IMX890加持 2000元檔最強影像手機

【Techweb評測】中端機型用戶群體巨大，占了中國目前手機市場的大頭，一直以來都是各手機品牌的“必爭之地”，其中OPPO K系列機型一直以來都以高品質、

AVt天堂网手机版,亚洲va久久久噜噜噜久久4399,天天综合亚洲色在线精品,亚洲一级Av无码毛片久久精品

點線面的智慧: 轉轉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、參考

盧偉冰長文解析K60至尊版對Redmi有著里程碑式的意義

Redmi Pad評測：紅米充滿野心的一次嘗試

0糖0卡0脂旭日森林仙草烏龍茶優惠：15瓶到手29元

中國家電海外掘金正當時｜出海專題

網紅炒股不為了賺錢，那就是耍流氓！

2納米決戰2025

三星Galaxy Z Fold5今日亮相：厚度縮減但仍略顯厚重

三星Galaxy Z Fold/Flip 5國行售價曝光：最低7499元/12999元起

OPPO K11評測：旗艦級IMX890加持 2000元檔最強影像手機

最新推薦

猜你喜歡

熱門推薦

相關資訊