连接点 - 连接轮廓点之间的线
我有一个 64x64 的灰度图像。我通过一个简单的算法找到了轮廓的点：
- 找到最亮的点（例如：100）
- 除以2（100/2 = 50）
- 在结果周围定义一个带（50-5=45到50+5=55）
- 标记所有在带内有价值的点（45 到 55 之间）
现在的问题是，我如何决定连接点的顺序？
（所有参考文献、链接、想法等都将被接受”）
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
您的算法允许整个图像（除了一个像素）成为“轮廓”。我不确定这是否正是您想要的；通常轮廓是两个不同区域之间的边界。您的方法的问题在于您可以获得大量没有特别明显的遍历顺序的像素。如果轮廓的厚度为单个像素，则遍历顺序会更加明显：顺时针或逆时针。
考虑下图。
在这里，我将所有“暗”（也许<50）标记为
%，将所有亮标记为.。现在，您可以选择两个区域之间边界上的任何像素（我将选择深色一侧；您也可以在浅色一侧绘制轮廓，或者做更多的工作，直接在浅色和深色一侧之间绘制轮廓。 ）现在您尝试沿着黑暗区域的外边缘移动，一次移动一个像素。首先，您朝明亮的方向看（例如，直接向左）。然后你旋转——比如说逆时针——直到遇到一个暗像素。
一旦到达位置
5，您就会看到天黑了。因此，您将其标记为轮廓的一部分，然后尝试通过从您刚刚来自的像素开始扫描来找到轮廓上的下一块，这里
0是您来自的地方 - 并且您'我不会再回到那里 - 然后你尝试像素1和2（都是浅色，这是不行的），直到你到达像素3>，这是黑暗的。通过这种方式，您可以逐个像素地围绕轮廓走动 - 既识别轮廓又获取像素的顺序 - 直到与开始时的相同像素发生碰撞并且将离开它，这样您点击的像素与第一次离开时点击的像素相同。然后轮廓闭合。在我们的示例中，我们制作 8 个连接的轮廓（即我们查看 8 个邻居，而不是 4 个），我们将得到以下结果（其中
@表示轮廓点）。（你必须有两个连续的标准，或者如果你有一个单像素宽的黑暗区域，你会沿着它向上走，但随后无法沿着它向下走。）
此时，你已经覆盖一个整个边界。但可能还有其他人。继续寻找亮像素旁边的暗像素，直到在所有像素上绘制出轮廓。现在您已将两级图片（暗像素和亮像素）转换为一组轮廓。
如果轮廓最终噪声太大，请首先考虑模糊图像。这将使轮廓变得平滑。 （或者，您可以先找到轮廓，然后使用移动窗口对坐标进行平均。）
Your algorithm allows the entire image, save for one pixel, to be "the contour". I'm not sure that's exactly what you want; usually a contour is a border between two different regions. The problem with your method is that you can get huge blobs of pixels that have no particularly obvious traversal order. If you have a contour that is a single pixel thick, then the traversal order is much more obvious: clockwise or counterclockwise.
Consider the following image.
Here, I've marked everything "dark" (<50, perhaps) as
%and everything bright as.. Now you can pick any pixel that is on the border between the two regions (I'll pick the dark side; you can draw the contour on the light side also, or with a little more work, directly between the light and dark sides.)Now you try to travel along the outer edge of the dark region, one pixel at a time. First, you look in the direction of something bright (directly left, for example). Then you rotate around--counterclockwise, let's say--until you hit a dark pixel.
Once you hit position
5, you see that it's dark. So, you mark it as part of the contour and then try find the next piece on the contour by sweeping around starting from the pixel you just came fromHere
0is where you came from--and you're not going back there--and then you try pixels1and2(both light, which is not okay), until you hit pixel3, which is dark.In this way, you can walk around the contour pixel by pixel--both identifying the contour and getting the order of pixels--until you collide with the same pixel you started with and will leave from it so that you hit the same pixel that you did the first time you left it. Then the contour is closed. In our example, where we're making an 8-connected contour (i.e. we look at 8 neighbors, not 4), we'd get the following (where
@denotes a contour point).(You have to have this two-in-a-row criterion or if you have a dark region a single pixel wide, you'll walk up it but then not be able to walk back down along it.)
At this point, you've covered one entire boundary. But there might be others. Keep looking for dark pixels next to light ones until you have drawn a contour on top of all of them. Now you've converted your two-level picture (dark & bright pixels) into a set of contours.
If the contours end up too noisy, consider blurring the image first. That will smooth the contours out. (Alternatively, you can find the contours first and then average the coordinates with a moving window.)
一般来说，给定的一组点可以通过多种方式连接以形成不同的形状。
例如，考虑由正方形的角点及其中心组成的 5 个点的集合。这些点可以连接起来形成一个正方形，其一侧向中心“凹陷”。但哪一边呢？没有唯一的答案。
其他形状可能要复杂得多，没有明显的方法来连接这些点。
如果允许您将点集减少为 凸包，那么它会很多更轻松。
In general, a given set of points can be connected in multiple ways to make different shapes.
For example, consider a set of 5 points consisting of the corners of a square and its center. These points can be connected to form a square with one side "dented in" to the center. But which side? There is no unique answer.
Other shapes can be much more complicated, with no obvious way to connect the dots.
If you are allowed to reduce your set of points to a convex hull, then it would be much easier.
我还尝试创建一种算法，将轮廓点连接成平滑曲线。请参阅我的开源项目 http://outliner.codeplex.com。
这个想法与 FUZxxl 提出的相同，但我不理解他对复杂性的担忧：处理时间与所有轮廓笔划的总长度成正比。
I have also tried to create an algorithm that will connect contour dots into the smooth curve. See my open-source project http://outliner.codeplex.com.
The idea is the same as proposed by FUZxxl but I do not understand his worries about complexity: the time of processing is proportional to the total length of all contour strokes.
我不知道收集这些积分是否能让你走得更远。 （我可以想出一些几乎不可能说出它们应该进入的顺序的情况。）
去最亮的点怎么样。
转到该点周围距离（例如 5 个像素）的 360 个点的亮度点。
从那里继续，但确保你不会回到原来的地方:)
I don't know if collecting those points will get you far. (I can come up with situations in which it's almost impossible to tell which order they should come in.)
How about going to the brightest point.
Go to the brightness point of, say, 360 points surrounding this point at a distance of, say, 5 pixels.
Continue from there, but make sure you don't go back where you came from :)
也许可以尝试：
可能不太好，因为复杂度类似于 O(n²)。正如 aioobe 建议的那样，您可以通过仅查找起点附近的点来简化此过程。这个算法很好，如果点之间的距离只有 2-3px，但可能会创建非常奇怪的网格。
Maybe try:
Probably not good, as complexity is something like O(n²). You may simplify this by looking only for points near the start, as aioobe suggest. This algorithm is good, if the points are just like 2-3px away from each other, but may create very strange grids.
另请参阅洪水填充
以及SO下可爱的小程序
映射-a-branching-tile-path 。
See also Flood fill
and the lovely applet under SO
mapping-a-branching-tile-path .