使用 javascript 确定界定形状边界的点的算法
我正在开发一个 html 地图制作器，我想为我们的用户提供通过单击区域来快速创建形状的能力，而不是让他们手动定义形状。
首先让我们看看我们目前正在做什么。用户想要绘制区域 A。他所要做的就是在每个点上单击多次来定义形状的边界。
我想知道是否有一种算法允许用户点击在 A 区域中，并且可以根据图像对比度确定要布置哪些点，以便沿着形状边界创建接近最佳的形状。
我处理这个问题的第一个想法是确定距单击点向上、向左、向下、向右最远的点。把这四点作为我们的出发点。然后，对于每个线段，用一个新点对其进行细分，并沿矢量法线移动新点，直到遇到对比边缘。
当然，这种方法有一些限制，但我可以假设
- 形状可以是凸形、凹形等……
- 对比度应该是黑对白，但为了处理可能的演变，对比度阈值应该是可配置的。
- 在上面我一直在考虑的例子中，为了不杀死用户的机器，显然对细分深度有一个限制
。如果你们中有人知道这样的算法，那就太好了。
I'm working on a html map maker, and i'd like to offer our users the ability to create shapes quickly by clicking in a zone instead of having them define the shape manually.
First let's have a look at what we're doing for the moment. The user would like to map the area A. What he has to do is click multiple times on each point to define the boundaries of the shape.
I'd like to know is if there is an algorithm that would allow the user to click in the A area and could determine what points to dispose in order to create an near-optimal shape following the shape boundaries - based on the image contrast.
My first idea to handle this was to determine the furthest points up, left, down, right from the clicked point. Set these four points as our starting points. Then for each segment, subdivide it with a new point and move the new point along the vector normal until i hit a contrasted edge.
Of course, there are some limitations to this approach, but here is what i can assume
- the shape can be convex, concave, etc...
- the contrast should be black against white but to handle possible evolutions the contrast treshold should be configurable.
- in the example i've been thinking about above, there would obviously be a limit to the subdivision depth in order not to kill the users machine
If any of you know about such an alogrithm, that would be really great.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
查看区域增长算法。这与上面tokland在基本情况下描述的洪水填充算法基本相同。
Have a look at Region Growing algorithms. This is basically the same as the flood-fill algorithm described above by tokland in the basic case.
这似乎是一个难题（顺便说一句，我不知道具体的算法）。我的 2 美分：
使用 flood-fill 算法，但不是获取整个表面，仅获取周长。
以周界为起点，单向走；当您检测到虚拟线段（当前点-初始点）与真实周长之间的累积二次误差超过阈值时，在该处放置一个点并重新开始，直到到达起点。
第一步看起来很简单，第二步就难了。
This seems like a hard problem (btw, I don't know about a specific algorithm for this). My 2 cents:
Use a flood-fill algorithm, but instead of getting the whole surface, get only the perimeter.
Take a starting point of the perimeter and go in one way; when you detect that the accumulated quadratic error between the virtual segment (current point - initial point) and the real perimeter goes over a threshold, put a point there and start again till you get to the starting point.
The first step seems pretty easy, the second is harder.
您可以使用边缘检测算法 (EDA)。
在 Javascript 中，您可以使用 Pixastic，或者自己推出。
经过 EDA 处理后，您的图像将变为：
之后，只需向任意方向抛出任意线即可从内部点到第一个白色像素，然后沿着轮廓移动。
You may use an Edge Detection Algorithm (EDA).
In Javascript you may use Pixastic, or roll your own.
After being processed by the EDA, your image gets to:
After that, simply throw any line in any direction from your interior point to the first white pixel, and follow the contour.