GIS中与计算几何相关的数据结构

二 GIS中与计算几何相关的数据结构与算法
算法
三角化Delaunay
Delaunay三角化与Veronoi 图互为对偶图。俗称最小角最大化的三角剖分。这里只关注2d情况。
先假设没有三点共线，四点共圆的病态例子。Delaunay有下面特点，
1.任何一个 Delaunay 三角形的外接圆的内部不能包含其它任何点。
2.给定的任意点集的 Delaunay 三角网是唯一的。
3.三角网的外边界构成了点集的凸多边形的“外壳”

GIS中的应用如LBS中的查找：“最近的公交车站在哪里？”，只需要将所有的公交车站作为顶点，构建Delaunay三角化，就可以找到最近的公交车站。（注：，这里有个距离的概念，如果使用欧式距离来构建三角网络，那么找到的就是欧式距离下的最近公交车站。）

参考http://en.wikipedia.org/wiki/Delaunay_triangulation，图片来自于该wiki
抽稀（Thinning）
在地图1:100000,和1:5000下，需要显示的详细程度不一样，因此，道路需要显示的也不一样。在1:100000时，为了处理速度，以及显示效率，需要将多余的点去掉。这过程通常称为抽稀过程。
道格拉斯-普克 算法，点距算法，都用于抽稀。通常使用道格拉斯-普克算法来抽取线路。
道格拉斯-普克算法描述：先将一条曲线首尾点虚连一条直线，求其余各点到该直线的距离，选其最大者与规定的临界值相比较，若小于临界值，则将直线两端间各点全部舍去，否则将离该直线距离最大的点保留，并将原线条分成两部分，对每部分线条再实施该抽稀过程，直到结束。抽稀结果点数随选取限差临界值的增大而减少，应用时应根据精度要求来确定抽稀限差临界值，以获得最好的结果。
目前，mapinfo中直接可以thinning一副地图，该默认算法采用的就是Douglas算法。
数据结构

网格索引（Grid）
构建简单、查找快速、冗余数据多，适合均匀分布地图。参见图示，如和查找最近的点。


四叉树（QuadTree）
构建简单、查找较快、多数情况下适用。图中是以北京地图的POI构建的四叉树。构建四叉树，需要注意设置1个条件以防止病态例子。
最小矩形大小，当矩形划分小于该矩形，无论有多少个元素都不在划分。这是为了防止许多点都集中在一块，而使得四叉树划分的层次太深。极端情况下，所有点坐标都一样。
对于Polygon和Polyline需要使用MBR（最小外接矩形）来实现。

下面是全北京市公交站点的四叉树，设定每个网格最多32个站点，不同颜色，是表示划分在不同级别中

R-Tree
构建复杂、查找性能稳定、支持复杂查询
适合大范围不均匀地图。

最小外界矩形（MBR，minimum bounding rectangle）[url]  http://en.wikipedia.org/wiki/Minimum_bounding_rectangle[/url]
在R-tree和四叉树中，都会使用这个最小外接矩形数据结构。
它是空间几何的元数据（metadata）；OGC，GML。