javascript - 在地图图像上检测“凹壳”

Question

我正在为 Waze（著名的免费 G​​PS 导航器）开发开源 JavaScript 插件，专门用于在线编辑器。这个用户脚本的想法是可以快速选择大型统一彩色地图区域以将它们转换为地标。

到目前为止，我已经成功地在 Photoshop 等图形编辑器中实现了您将称为“Magic Wand”的工具：用户单击地图上的某个位置（例如，在湖或森林上），脚本选择相同颜色覆盖的整个区域并创建一个多边形为地标。

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

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

我在谷歌上搜索合适的算法并翻阅数学论文，但仍然没有找到合适的算法。Stackoverflow 上关于凹壳的最受欢迎的问题是指 Alpha 形状和 Delaunay 三角形。虽然我不明白如何使用它以防万一：所有点都相互连接形成一条连续的折线，因此我似乎找不到合适的 alpha-radius 作为半径等于 1 像素的偶数圆并进行 alpha 曝光。

任何关于如何归档构建凹形船体目标的想法将不胜感激！可能是我走错了方向，需要查看位图矢量化算法吗？

Answer 1

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

Answer 2

您可以在本文中阅读如何实现凹壳算法。基本思想是向内构建凸包和弯曲（凹）边。该算法有 JavaScript 实现：hull.js。