空间搜索综述

空间搜索是针对多维空间数据进行的搜索，这听起来是一句废话。但是，这重点强调的是空间数据，而且数据是**多维(2D, 3D …)**的。同时, 空间搜索有别于传统的网页文本搜索(google, baidu等)，传统搜索引擎针对的是海量的文本，分词之后，通过倒排等技术来进行快速的匹配。

空间搜索的数据则是点、线、多边形，多维空间等等几何体。如何能高效准确的搜索出想要的空间数据是空间搜索需要解决的。

在生活中无处不在

无形之中，空间搜索已经存在于我们生活中的方方面面。也许，出门你可能要打个车，看看附近有哪些司机师傅可以接单。自驾要搜索一下沿途的加油站，如果是电车你可能想找一下充电桩。抑或是你今天休息宅在家里，想找个餐厅，定个外卖。所有的这些都离不开空间搜索支持。

现在比较流行的RDBMS数据库 MySQL、PostgreSQL 都原生支持 B+ 树。这种数据结构能高效的查询。MongoDB、Redis等NoSQL数据库原生的支持了空间索引能力。业界对于空间搜索的需求是巨大的。

几何对象类型

• Point 点
• MultiPoint 多点
• LineString 线条
• MultiLineString 多线条
• Polygon 多边形
• MultiPolygon N个多边形
• GeometryCollection 几何图形集合

Quad Tree四叉树

四叉树 是一种非常简单的空间索引技术。在四叉树中，每个节点代表一个bbox，该bbox覆盖被索引空间的某些部分，而根节点则覆盖整个区域。每个节点要么是一个叶子节点-在这种情况下，它包含一个或多个索引点，并且没有子级；要么是一个内部节点，在这种情况下，它正好具有四个子级，每个象限一个子级，方法是将沿两个轴的一半-因此得名。

四叉树如何划分索引区域的表示。

大比例尺制图中实际用到的投影有27种+之多，其中最重要的有：墨卡托(Mercator)投影(85%)，Lambert等角正割圆锥投影(5%)，Albers等积正割圆锥投影，等距圆锥投影, 最为常用的是横轴墨卡托投影。

具体来说，不同的地理区域常用的地图投影方法也不同。

投影种类繁多，命名也极其繁杂，有很多其实是同一类投影，单是叫法很容易混淆。下面进行一个清晰的讲解，让大家了解一下各种投影的区别。

投影方式

投影性质划分

按投影后，在地图上的表示不同，分为等积投影、等角投影

所谓等积投影，就是不同地理位置上投影后的面积是一样的，面积上比例是一样的。

等角投影，主要是指投影后，角度(经度或者纬度)是不变的。

S2其实是来自几何数学中N维球面的一个数学符号S²，它表示的是3维空间内的2维球面。S2 这个库其实是被设计用来解决球面上各种几何问题的。

接下来就看看怎么用 S2 来解决多维空间点索引的问题的。

球面坐标转换

众所周知，地球是近似一个球体。球体是一个三维的，如何把三维降成一维呢？

球面上的一个点，在直角坐标系中，可以这样表示：

1
2
3

x = r * sin θ * cos φ
y = r * sin θ * sin φ 
z = r * cos θ

通常地球上的点我们会用经纬度来表示。

再进一步，我们可以和球面上的经纬度联系起来。不过这里需要注意的是，纬度的角度 α 和直角坐标系下的球面坐标 θ 加起来等于 90°。所以三角函数要注意转换。

于是地球上任意的一个经纬度的点，就可以转换成 f(x,y,z)。

在 S2 中，地球半径被当成单位1了，所以半径不用考虑。x,y,z的值域都被限定在了[-1,1]*[-1,1]*[-1,1]这个区间之内了。

在Lucene-Solr中，提供了空间搜索能力，它主要提供了以下4种FieldType来支持：

• LatLonPointSpatialField
• LatLonType (不再使用) , 以及非地理位置搜索版本 PointType
• SpatialRecursivePrefixTreeFieldType (简写RPT), 包含衍生出的RptWithGeometrySpatialField
• BBoxField

LatLonPointSpatialField是用来取代LatLonType的一个FieldType。Lucene在7.0之后，推出了一种基于BKD树而实现的专用于处理多维数据的[索引格式，它原则上可以高效的处理任意维的数据。从一维的(int, long, double)数据类型、二维的点、面类型、三维的空间类型，甚至更多维度数据（暂未实现而已）。

1

<fieldType name="location" class="solr.LatLonPointSpatialField" docValues="true"/>

BBoxField是一种专门用来索引四方形数据的FieldType, 提供的功能包括：图形相交、图形内部、图形包含、图形相等。

1
2
3
4

<field name="bbox" type="bbox" />

<fieldType name="bbox" class="solr.BBoxField" geo="true" distanceUnits="kilometers" numberType="pdouble" />
<fieldType name="pdouble" class="solr.DoublePointField" docValues="true"/>

SpatialRecursivePrefixTreeFieldType则是最为通用的空间搜索解决方案。下面将对其重点来进行解释。

一. GeoHash 算法

1. Geohash 算法简介

Geohash 是一种地理编码，由 Gustavo Niemeyer 在2008年发明的，G.M.Morton在1966年做过类似的工作。。它是一种分级的数据结构，把空间划分为网格。Geohash 属于空间填充曲线中的 Z 阶曲线（Z-order curve）的实际应用。

何为 Z 阶曲线？

Uber H3是Uber实现的一个基于正六边形，分层空间索引系统。

H3：

• 功能-世界分割成正六边形的网格
• 本质是一个分层网格系统
• 支持全球，把世界划分为平米级的网格

使用正二十面体投影

h3选择以正二十面体做为投影，通过把地球坐标映射到正二十面体的20个面上，然后再针对每个面做进一步的切分。正二十面体如下图所示：

空间搜索-分形几何

分形(fractal)

分形（英语：fractal，源自拉丁语：frāctus，有“零碎”、“破裂”之意），又称碎形、残形，通常被定义为“一个粗糙或零碎的几何形状，可以分成数个部分，且每一部分都（至少近似地）是整体缩小后的形状”，即具有自相似的性质。 分形在数学中是一种抽象的物体，用于描述自然界中存在的事物。1975 年本华·曼德博首次提出“分形(fractal)”这个术语。

关于分形的具体定义，权威专家也仍有一些争论，即使作为”分形几何之父“，本华·曼德博也一直更新其定义。
“美丽、（研究起来）极其困难但又非常的有用，这就是分形”。1982年更新为：”分形是一种其豪斯多夫维数严格大于拓扑维数的集合“，后来称为”分形是由与整体在某些方面相似的部分构成的图形“ 。又过了一段时间，决定这样描述分形：“**…在研究和使用分形时，不需要迂腐的定义。用分形维数作为描述各种不同分型的通用术语**”。

通常认为, 理论分型是无限迭代、自相似的、具有分形维数的详细数学结构。
是不是看完以上的描述，还是不太了解什么是分形，那么我们来看几个现实中的例子。

花椰菜	蕨类植物

可以看出，每个花椰菜的凸起，单独拿出来其实都和花椰菜是一样的造型。蕨类植物的叶子，没个分支都和整体的形状一致。

网格系统(Grid System)对于分析海量空间数据集，将地球空间划分为可识别的网格单元(cell)至关重要。

考虑到这一点，Uber开发了 H3 ，这是我们的网格系统，它可以用来有效优化乘车价格和调度、地图空间数据的可视化和挖掘。 H3使我们能够分析地理信息以设置动态价格并在整个城市范围内做出决策。 我们将H3作为网格系统用于整个市场的分析和优化。 H3就是为此目的而设计的，它使我们可以使用六边形层次索引。

今年早些时候，我们在Github上 开源了H3 ，大家都可以使用此强大的解决方案，上周，我们开源了 H3 JavaScript 版本。 在本文中，我们讨论了为什么我们使用网格系统，H3的某些独特属性以及如何开始使用H3。

图1. H3把地球分成很多六边形，使用户可以进行更精准的分析。