點線面的智慧: 轉轉JTS技術如何塑造上門履約地理布局
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/
