javascript - 在 map 图像上检测到 "concave hull"

Question

我正在为 Waze 开发开源 JavaScript 插件——著名的免费 G​​PS 导航器——专门用于 online editor .这个用户脚本的想法是可以快速选择大的统一颜色的 map 区域以将它们转换为地标。

到目前为止我已经 successfully implemented您在 Photoshop 等图形编辑器中称为“魔术棒”的工具:用户单击 map 上的某处(例如，在湖泊或森林上)，脚本选择由相同颜色覆盖的整个区域并为地标创建多边形。

一切都很好，除了我使用凸包算法来获得...好吧...凸包 :) 即:连接找到的点云的最外点的多边形。

但众所周知，只有少数地标具有凸形，而现实世界中的大多数物体都是具有凹形区域的折线形。在上图中，您可以看到该区域几乎没有锋利的边缘，右下角的农田被凸包覆盖——这是错误的。

我在谷歌上搜索了合适的算法并翻阅了数学论文，但仍然找不到合适的算法。 The most popular question关于 Stackoverflow 上的凹包是指 Alpha 形状和 Delaunay 三 Angular 形。虽然我不明白如何使用它以防万一:所有点都相互连接形成一条连续的多段线，因此我似乎找不到合适的 alpha 半径，因为半径等于 1 像素的偶数圆被 alpha 暴露。

任何关于如何实现构建凹壳目标的想法都将不胜感激!可能是我走错了方向，需要查看位图矢量化算法？

Answer 1

Alpha 形状是通过找到一组点的 delaunay 三 Angular 剖分然后删除超过 alpha 的边来定义的。您需要 delaunay 三 Angular 剖分但不需要圆圈。它也适用于线条。要使用 JS 计算形状，您可以使用 TopoJSON 或尝试这个答案:Calculate bounding polygon of alpha shape from the Delaunay triangulation .你也可以试试我的php包http://concavehull.codeplex.com/ .