使用JavaScript编写的确定形状边界点的算法

Question

我正在开发一个HTML地图制作工具，我希望为我们的用户提供通过单击区域来快速创建形状的功能，而不是让他们手动定义形状。

首先，让我们看看我们目前正在做什么。用户想要映射区域A。他需要做的是多次单击每个点以定义形状的边界。

我想知道的是是否有一种算法可以允许用户在A区域单击，并确定要放置哪些点以创建近似最优的形状，遵循形状边界 - 基于图像对比度。

我处理这个问题的第一个想法是确定从点击点最远的上、左、下、右四个点。将这四个点设置为我们的起始点。然后对于每个线段，使用新点将其细分，并沿着法向量移动新点，直到它碰到对比度边缘。

当然，这种方法有一些局限性，但以下是我能假设的：

- 形状可以是凸形、凹形等等。 - 对比度应该是黑色对白色，但为了处理可能的演变，对比度门槛应该是可配置的。 - 在上面考虑的示例中，显然应该限制细分深度，以避免卡死用户的机器。

如果您知道这样的算法，那就太好了。

- samy

---

每个节点的连接线是否已知？如果是，即使它在一侧中间（例如第三张图像中的第二个点），它们是否可以导航到下一个节点？如果可以，您可以使用“保持左侧”或“保持右侧”的路由样式来查找最内部的连接形状。 - Peter-Paul van Gemerden

对不起，我假设图像是基于矢量的。实际上，它是位图吗？ - Peter-Paul van Gemerden

我想这需要将图像转换为画布，以便读取像素的颜色。也许您可以添加“canvas”标签来吸引画布专家对这个问题的关注 ;) - Lukman

地图最初是如何表示的？有什么阻止你在服务器中编译所有可能的区域并将处理后的数据直接发送到客户端吗？ - hugomg

@missingno，地图可以是任何带有区域的图像。它不是生成的，甚至可以是jpg图像。然而，我们主要用于具有明确定义区域的地图。这个改进将为几乎每个用户节省时间。 - samy

Answer 1

请查看区域生长算法。在基本情况下，这与tokland描述的泛洪算法基本相同。

- Jeff Foster

---

区域生长算法非常适合构建初始区域，作为查找周长的基础，但据我所读，它并不能帮助找出组成周长的点。 - samy

Answer 2

这似乎是一个难题（顺便说一下，我不知道有没有针对这个问题的具体算法）。我的建议是：

1. 使用泛洪填充算法，但不是获取整个表面，而是只获取周长。

2. 从周长的起始点开始沿着一个方向前进；当检测到虚拟线段（当前点-初始点）和真实周长之间的累积二次误差超过阈值时，在那里放置一个点，并重新开始，直到回到起始点。

第一步似乎很容易，第二步比较困难。

- tokland

---

是的，这看起来确实是一个难题。不过我不太确定你在第二部分中的意思。一开始我有一种感觉，你在谈论从任何一个点开始走遍边界，每走一步都检查新点是否与前面的点在倾斜方面匹配（），但是在考虑了你的回答之后，我不确定你在回答中所说的“初始点”的含义。你是指“种子点”，也就是你最初点击的那个点吗？ - samy

@samy，不是种子点，而是从计算出的周长开始的起始点。您必须从任何一点沿周长行走并决定“拐角”在哪里。这种检测很棘手，一方面您必须检测到角度的突然变化（想象一个多边形形状），但也要检测到小的连续变化（想象一个圆周形状）。这两个标准的结合应该可以给您带来良好的结果。 - tokland

好的，这正是我想的。坦白地说，我不会费心去处理周长形状；我一开始并不想覆盖所有情况，而是处理那些占90%的情况。我会尝试构建一个解决方案。 - samy

@samy：如果您不关心连续变化，请将角度更改本地化为相对较小的片段。您需要使用Math.atan2函数。 - tokland

好的，我要下定决心并考虑到目前为止没有现有的算法可以确定周长的点；我试图作弊并查看了哈里斯角检测，但在某些方面它并不符合要求。 - samy

Answer 3

您可以使用边缘检测算法（EDA）。在Javascript中，您可以使用Pixastic，或者自己编写。经过EDA处理后，您的图像会变成：

之后，只需从内部点向第一个白色像素沿任意方向投掷一条线，并跟随轮廓。

- Dr. belisarius

---

是的，我可以跟随轮廓，但如何确定线条中的方向变化对应于多边形中的新点而不是线条中的楼梯。然后还有要处理的伪影（例如在您的图像中，一些来自EDA的线条宽度为两个像素）。所以我同意您的答案建议，只是“跟随轮廓”的部分并不那么简单。至少我不知道如何轻松地做到这一点 :) - samy