map-vectorizer算法揭秘：alpha shape与Douglas-Peucker如何简化地图多边形

map-vectorizer算法揭秘：alpha shape与Douglas-Peucker如何简化地图多边形

【免费下载链接】map-vectorizerAn open-source map vectorizer项目地址: https://gitcode.com/gh_mirrors/ma/map-vectorizer

把一张上百年前的手绘地图，变成 GIS 软件可以直接读取的矢量多边形，这个"给地图做OCR"的过程就是地图矢量化。map-vectorizer 正是一款开源地图矢量化工具，由纽约公共图书馆（NYPL）实验室开发，目标是从19世纪的保险地图集中自动提取建筑多边形与属性。而它简化地图多边形的核心秘密，藏在两个算法里：alpha shape与Douglas-Peucker。本文将一步步拆解它们如何配合，让一张布满锯齿的老地图"变身"为干净、简洁、带属性的矢量数据。

地图矢量化是什么？为什么多边形必须"简化"？

在开始讲算法之前，先明确一个问题：矢量化的结果为什么一定要"简化"？

原始地图（如上面的test.tif）是手绘彩色图像，经过阈值化和栅格转矢量之后，建筑的轮廓会变成密密麻麻的锯齿状折线——一个普通建筑可能包含成百上千个顶点。这样的数据又大又难用：

• 文件体积膨胀，加载缓慢；
• 边缘锯齿严重，影响美观与精度；
• 后续的空间分析（面积、拓扑、叠加）效率低下。

所以，简化多边形不是"锦上添花"，而是地图矢量化流程中的必备环节。NYPL 的团队曾靠志愿者手工三年才提取出 17 万个带属性的多边形，而借助 map-vectorizer 这套流水线，这个时间被压缩到了约 24 小时——简化算法功不可没。

map-vectorizer 简化地图多边形的完整流程

整个简化过程并不是一步到位的，而是"先粗后精"的多阶段流水线，主入口在 vectorize_map.py：

1. 阈值化（Thresholdize）：调用 GIMP 对地图做亮度/对比度调整和二值化，让线条变黑、底色变白，参数来自 vectorize_config_default.txt；
2. 粗矢量化（Polygonize）：用gdal_polygonize.py把二值栅格转成粗糙的矢量多边形；
3. alpha shape 重建轮廓：对多边形内部采样点，用 alpha shape 算法"重新勾勒"出光滑的边界；
4. Douglas-Peucker 简化：把重建后的多边形顶点数大幅削减；
5. 属性合并（Consolidate）：补上颜色、圆点、十字标记等属性，输出 Shapefile 与 GeoJSON。

第 3、4 步正是本文的主角，它们的实现在 simplify_map.R 中，只有短短几十行，却浓缩了两个经典几何算法的精华。

alpha shape 算法：从点云中"找回"多边形轮廓

什么是 alpha shape？凸包与凹包的折中

很多新手听说过凸包（Convex Hull）：把所有点包在外层的最小凸多边形。但建筑的轮廓往往是凹的——L 形、U 形、带内庭的形状，凸包会把凹陷处"填平"，完全失真。

alpha shape正是为解决这个问题而生：它引入一个参数alpha，可以理解为一个"滚圆"的半径。当这个圆在点集外部滚动时，圆能滚到的位置就是边界，从而得到一条围绕点集的闭合曲线：

• alpha越大，圆越大，轮廓越接近凸包；
• alpha越小，圆越小，越能"钻"进凹陷，捕捉细节。

可以说，alpha shape 是凸包与精细轮廓之间的调节旋钮，非常适合还原建筑这种不规则凹多边形。

map-vectorizer 如何用 alpha shape 重建建筑轮廓

在 simplify_map.R 中，流程非常巧妙：

1. 先按面积过滤（minarea=20、maxarea=3000平方米），只保留像建筑尺度的多边形；
2. 用spsample在原始多边形内部撒下1000 个采样点，并依次尝试 hexagonal（六边形）、regular（规则）、nonaligned（错位）、stratified（分层）四种采样方式；
3. 调用ashape()函数，以alpha=2计算 alpha shape；
4. 把结果边的端点构造成图（igraph），并做两项"体检"：确保每个顶点度数都为 2（保证是一条闭合环），以及图连通（避免出现多个分离的圈）；
5. 从闭合环中提取点序列，重新拼装成 Polygon。

这套"采样 → alpha shape → 图修复"的组合，保证了即使原始多边形形状怪异，也能稳定地重建出一条闭合且连通的轮廓。

Douglas-Peucker 算法：给多边形"瘦身减负"

alpha shape 重建出的轮廓虽然形状正确，但顶点依然偏多。接下来登场的是Douglas-Peucker 算法（道格拉斯-普克算法），它是地图制图领域最经典的线要素简化算法，也是本项目的"瘦身神器"。

算法原理：递归寻找最大偏离点

Douglas-Peucker 的思路非常直观，可以概括为三步：

1. 连接折线的首尾两点，得到一条基准线段；
2. 找出整条折线上离这条线段最远的那个点，计算其垂直距离；
3. 如果这个距离大于容差（tolerance），就保留该点，并把它作为分界点，把折线拆成两段递归重复上述过程；否则，丢弃中间所有点，只保留首尾。

简单说，它像一个"贪心压缩器"：保留弯曲最剧烈的地方，抹平无关紧要的小毛刺。容差越大，保留的点越少，图形越简洁。

容差 0.5 与面积过滤：平衡精度与简洁

在 map-vectorizer 中，Douglas-Peucker 的调用只有一行：dp(temp, 0.5)，这里的 0.5 就是容差阈值，来自 R 的shapefiles包。

• 容差 0.5：意味着偏离基准线不超过 0.5 个单位的顶点都会被移除，足以抹掉栅格化产生的锯齿，又不会把建筑直角"磨圆"；
• 面积过滤（20~3000 平方米）：在简化前先剔除过小（噪声）和过大（地块）的多边形，只保留建筑级别的目标。

两者配合，最终输出的多边形顶点数大幅下降、形状保持完好，可以直接进入 GIS 软件或 Web 地图使用。

简化之后：颜色、圆点、十字标记等属性如何保留？

矢量化的价值不止于形状，还有属性。map-vectorizer 在简化完成后，还会给每个多边形"贴标签"：

• 平均颜色：用 PIL 计算多边形范围内像素的平均 RGB（见 map_vectorizer/util.py 的average_color），再与配置中的基准色（纸色、红色、绿色、黄色等）做最近邻匹配，判断它是建筑还是背景；
• 圆点检测：用 OpenCV 的HoughCircles统计多边形内圆点数量与类型（实心/空心）；
• 十字标记检测：用matchTemplate模板匹配，与 detector_templates/cross1.jpg 比对，找出地图上的十字符号；
• 质心计算：把多边形质心转换到 WGS84 经纬度坐标，方便地理定位。

这些逻辑集中在 map_vectorizer/detect.py，最终连同简化后的几何写入*-traced.shp与*-traced.json。

一分钟上手：亲自体验地图矢量化

想亲手看看 alpha shape 与 Douglas-Peucker 的效果？克隆项目并运行测试即可：

git clone https://gitcode.com/gh_mirrors/ma/map-vectorizer cd map-vectorizer pip install -r requirements.txt python vectorize_map.py test.tif

处理好后，目录下会出现test-traced.shp、test-traced.json等输出文件，仓库的 map_vectorizer/test/fixtures/mulberry.shp 还提供了现成的 Shapefile 测试数据供你对比。整个过程约 70 秒，让你直观感受"老地图 → 矢量多边形"的魔法。

结语：两个算法，一套开源地图矢量化流水线

回看整个 map-vectorizer，它的思路堪称优雅：alpha shape 负责"重建"，从采样点云中还原出真实、闭合、允许凹陷的多边形轮廓；Douglas-Peucker 负责"精简"，在保持形状的前提下把顶点数压到最低。前者解决了"形对不对"，后者解决了"数据重不重"，两者一前一后，构成了一套完整的地图多边形简化方案。

对新手而言，理解这两个算法，就等于拿到了阅读 map-vectorizer 源码的钥匙；对开发者而言，这套"采样重建 + 递归简化"的组合拳，也完全可以迁移到任何轮廓提取与数据压缩场景。下次再看到那些干净利落的建筑多边形，不妨想想：背后是 alpha shape 与 Douglas-Peucker 在悄悄发力。🧩

【免费下载链接】map-vectorizerAn open-source map vectorizer项目地址: https://gitcode.com/gh_mirrors/ma/map-vectorizer