点线面的智慧转转JTS技术如何塑造上门履约地理布局

见贤思齐

1引言2JTS介绍2.1引入jar包2.2基本的几何模型2.3几何模型的描述格式2.4空间关系2.5空间操作3快速判断是否支持上门3.1最小外接矩形（MBR）3.2空间索引3.3整体方案流程4几何图形的修复处理5总结6参考1引言如上图所示，在转转上门履约的场景中，上门服务的覆盖区域是在地图上画电子围栏来划定的。这就涉及到一些几何图形的操作和空间关系判断，其中最核心问题就是要解决如何判断位置是否在上门覆盖范围内。下面介绍下JTS，以及如何通过JTS的空间之力来解决这些问题。2JTS介绍JTS，全称JavaTopologySuite，是一个用于创建和操作向量几何的Java库。提供了对几何模型的抽象，以及各种空间操作和空间关系判断，非常强大。2.1引入jar包JTS有多个模块，这里只使用了核心的模块。jts-core：提供几何模型的抽象、空间操作、空间关系判断算法等jts-io-common：提供各种格式描述几何模型的输入输出包，如对WKT、WKB等格式  org.locationtech.jts    1.19.0    org.locationtech.jts.io        1.19.02.2基本的几何模型JTS提供了常见的几何模型抽象，并且各具特点。模型定义常见应用点（Point）空间中的单个位置，由一对x,y坐标表示兴趣点、事件位置等多点（MultiPoint）由多个独立的点组成的几何对象表示多个相关但分散的位置，如连锁店分布，多个不同人位置线（LineString）由一系列点组成的一维几何对象，有起点和终点，中间可以有任意数量的点表示道路、河流等线性特征多线（MultiLineString）由多个不相连的LineString组成的几何对象表示复杂的道路网络、等高线等多边形（Polygon）由一系列首尾相连的线段围成的平面区域（可以有内部空洞）表示行政区划、建筑物轮廓等多多边形（MultiPolygon）由多个独立的Polygon组成的几何对象，可以表示不相连的多个区域表示群岛、复杂的行政区划几何集合（GeometryCollection）可以包含任意类型几何对象的集合，最灵活的几何类型，可以混合包含点、线、面等表示复杂的空间场景，如包含多种类型要素的地图在JTS中的各几何模型对象关系如下所示：在实际应用场景中，最常使用的模型如下：点（Point）：表示位置信息，如用户地址位置、工程师位置等多边形（Polygon）、多多边形（MultiPolygon）：用来表示上门履约的覆盖区域2.3几何模型的描述格式WKT（Well-KnowText）格式是一种文本格式，用于描述二维和三维几何对象的空间特征。WKT的基本语法格式如下：几何模型类型 (模型数据)示例如下所示：点：POINT(282455)线：LINESTRING(260250,485248,520380)多边形：POLYGON((320390,370330,470360,460430,375432,320390))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（DimensionallyExtendedNine-IntersectionModel）模型定义的，这里列举常见的空间关系空间关系定义相等(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(MinimumBoundingRetangle)，是能够完全包含一个几何对象的最小矩形。如下图所示，这个规则的矩形就是该多边形的MBR表示。表示MBR非常简单，只需要知道他的左下角和右上角，那么就可以知道这个MBR图形了。如下图所示：知道了这个最小外接矩形有什么用？可以断定：如果点不在这个MBR内了，那么肯定不在这个多边形内。所以把点和MBR进行比较，就能够快速排除不可能有关系的多边形对象。那么如何快速的判断点是否在MBR中？比较坐标值的大小就可以了。示例代码如下：mbr.getLngMin() = point.getLng()& mbr.getLatMin() = 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 recisionModel(0));System.out.println(wktWriter.write(geometryA.buffer(0)));修复之后如下图所示5总结JavaTopologySuite(JTS)作为一个功能强大的空间数据处理库，为开发者提供了丰富的工具来处理复杂的空间问题。它在许多地理信息系统得到了广泛的应用。这里只是对其的一个简单应用，后续还待更深入的挖掘。6参考JavaTopologySuite(JTS)：https://github.com/locationtech/jtsOSGeo中国：https://www.osgeo.cn/关于作者揭荣，转转上门履约业务研发工程师想了解更多转转公司的业务实践，欢迎点击关注下方公众号：