點(diǎn)線面的智慧: 轉(zhuǎn)轉(zhuǎn)JTS技術(shù)如何塑造上門履約地理布局

作者：揭榮 2024-07-12 07:08:06

JTS，全稱 Java Topology Suite，是一個(gè)用于創(chuàng)建和操作向量幾何的 Java 庫。提供了對(duì)幾何模型的抽象，以及各種空間操作和空間關(guān)系判斷，非常強(qiáng)大。

1、引言

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

2、JTS 介紹

2.1 引入 jar 包

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

jts-core：提供幾何模型的抽象、空間操作、空間關(guān)系判斷算法等
jts-io-common：提供各種格式描述幾何模型的輸入輸出包，如對(duì) 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 提供了常見的幾何模型抽象，并且各具特點(diǎn)。

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

在 JTS 中的各幾何模型對(duì)象關(guān)系如下所示：

在實(shí)際應(yīng)用場景中，最常使用的模型如下：

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

2.3 幾何模型的描述格式

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

幾何模型類型 (模型數(shù)據(jù))

示例如下所示：

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

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

// 讀取wkt描述的幾何對(duì)象
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))");

// 輸出幾何對(duì)象的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 空間關(guān)系

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

空間關(guān)系	定義
相等 (Equals)	兩個(gè)幾何對(duì)象在拓?fù)渖舷嗟?/span>
相離 (Disjoint)	兩個(gè)幾何對(duì)象沒有任何共同點(diǎn)
相交 (Intersects)	兩個(gè)幾何對(duì)象有至少一個(gè)共同點(diǎn)
內(nèi)含 (Within)	幾何對(duì)象 A 完全位于幾何對(duì)象 B 內(nèi)部
包含 (Contains)	幾何對(duì)象 A 完全包含幾何對(duì)象 B

以該圖形為例，兩個(gè)多邊形的關(guān)系判斷的代碼示例

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));

在實(shí)際場景中，判斷上門位置是否在上門區(qū)域內(nèi)，轉(zhuǎn)換成空間關(guān)系的判斷就是點(diǎn)是否在多邊形內(nèi)。解決該問題的實(shí)例代碼如下：

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 提供了豐富的空間操作功能，用于處理和分析幾何對(duì)象。這里列舉常見的幾種

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

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

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、快速判斷是否支持上門

在上門履約實(shí)際場景中，需要快速的識(shí)別用戶所在位置、地址位置是否在上門服務(wù)的覆蓋區(qū)域內(nèi)。轉(zhuǎn)換成空間關(guān)系的判斷上，也就是點(diǎn)是否在多邊形內(nèi)（PIP，Point-In-Polygon）問題了。

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

3.1 最小外接矩形（MBR）

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

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

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

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

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

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

在 JTS 中，Envelope 對(duì)象來表示 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 空間索引

上述構(gòu)建 MBR 可以理解為簡單索引的一種，實(shí)際上有復(fù)雜的空間索引。常見空間索引有

R 樹（R-tree）：平衡樹，適用于多維空間數(shù)據(jù)（類似一維的 B+樹）
四叉樹（Quad-tree）：將二維空間遞歸地分為四個(gè)象限
網(wǎng)格（Grid）：將空間劃分為規(guī)則的網(wǎng)格單元

空間索引的基本原理基本類似，采用分割原理，逐級(jí)劃分地理空間。舉個(gè)不那么恰當(dāng)?shù)睦樱粋€(gè)自上而下、逐級(jí)劃分地理空間的索引定位過程如下：

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

JTS 提供了四叉樹和 R 樹的實(shí)現(xiàn)

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

以這個(gè)圖形為例，使用 JTS 構(gòu)建 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，和自己的數(shù)據(jù)
rtree.insert(geometryA.getEnvelopeInternal(), "Polygon-A");
rtree.insert(geometryB.getEnvelopeInternal(), "Polygon-B");
rtree.build();

// 點(diǎn)只在Polygon-A中
System.out.println(rtree.query(wktReader.read("POINT (337 391)").getEnvelopeInternal()));
// 點(diǎn)只在Polygon-B中
System.out.println(rtree.query(wktReader.read("POINT (496 390)").getEnvelopeInternal()));
// 點(diǎn)在Polygon-A和Polygon-B的交集中
System.out.println(rtree.query(wktReader.read("POINT (452 367)").getEnvelopeInternal()));

3.3 整體方案流程

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

先通過 STRtree 構(gòu)建空間索引
利用空間索引快速篩選可能包含點(diǎn)的多邊形
對(duì)篩選后的多邊形進(jìn)行精確的空間關(guān)系判斷

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

具體流程如下圖所示：

4、幾何圖形的修復(fù)處理

在實(shí)際運(yùn)營過程中，畫的圖形各種形狀，會(huì)出現(xiàn)不少異常的情況，如點(diǎn)重疊、邊之間細(xì)微的間隙、自交等問題。實(shí)際操作中還提拱了圖形合并的能力，合并出來的圖像也有可能也是不符合規(guī)范的。為此，需要對(duì)這些異常的圖像進(jìn)行修復(fù)。

常見的修復(fù)手段有兩種

Buffer 操作：在幾何對(duì)象周圍的創(chuàng)建緩沖區(qū)，一般用來修復(fù)自相交問題、精度導(dǎo)致的小間隙等
Snap 操作：一個(gè)幾何對(duì)象的頂點(diǎn)捕捉到另一個(gè)幾何對(duì)象的頂點(diǎn)或邊緣，一般用來修復(fù)小的拓?fù)溴e(cuò)誤

這兩種操作也不是萬能，也是需要自己根據(jù)實(shí)際情況進(jìn)行不斷地調(diào)整。

下面來看一個(gè)修復(fù)自交的例子，一個(gè)自交的圖形如下所示：

修復(fù)代碼示例如下：

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)));

修復(fù)之后如下圖所示

5、總結(jié)

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