顺时针排序一组点并确保连接这些点的路径闭合的算法

Question

我一直在以多种不同的方式解决这个问题，在我自己尝试了一个月之后，我认为是时候让新的眼光来审视它了。我正在尝试制作一个图像缩放应用程序，用于重新调整 8 位精灵的大小并将它们转换为矢量图像。到目前为止，我的工作是这样的；它获取图像，将其分解成形状（具有相同颜色的相邻像素的区域），然后形状中的每个像素被四个像素替换：

private Point[] expand(int x, int y){
    x *= factor;
    y *= factor;
    return new Point[]{new Point(x+half_factor,y), new Point(x+factor,y+half_factor),
            new Point(x+half_factor, y+factor), new Point(x,y+half_factor)};
}

四个点中的每一个都被放入一个二维布尔数组中：

private void placePoint(int x, int y){
    table[x][y] = !table[x][y];
    extrema(x,y);
}

单个形状的结果如下所示：

现在我想把所有这些点（减去内部的点）变成一个多边形，我尝试了很多不同的解决方案，最近我一直在尝试找到最近的邻居，直到它到达开始，但我尝试的每个算法都失败了。对于这个特定的示例，它到达右下角的 goomba 倒置并在其左侧的像素簇中变得混乱。该程序认为路径已经完成，并从那里到左上角创建一条线，完全忽略左下象限中的点。

这就是我想要的样子：

以下是在我的情况下始终正确的一些事情，它们可能有助于找到有效的算法：

所有点列表中的第一个点是最外层路径的一部分
最外层路径中的每个点都有一个距离它 C 个单位或 √C 个单位的邻居
最外面的路径永远是封闭路径

任何帮助将不胜感激！

更新：

我已经尝试了下面的所有解决方案和建议，并取得了一些进展，但仍然没有得到想要的输出。

原版：

输出：

最终更新：

现在可以用了，只需解决小错误！

Answer 1

高水平，

洪水填充以找到一组相连的像素。
应用边界运算符得到嵌入的平面图。
找到外表面。

第 2 步和第 3 步是新的。步骤 2 是通过在集合中的像素与不在集合中的像素相邻的地方放置两条半边来完成的，每个方向一个。例如，

***
* *
***
* *

变成

._._._.
|* * *|
. ._. .
|*| |*|
. ._. .
|* * *|
. ._. .
|*| |*|
._. ._.

其中每个 _ 或 | 表示两个半边，每个方向一个。对于每个点 .，收集指向它的半边，并按逆时针顺序从每个这样的半边指向下一个。每个半边也应该指向相反方向的半边。

第三步是通过如下遍历完成的：给定一条半边，按逆时针方向找到指向同一点的下一条半边，然后找到与该半边相对的半边，如此反复。这将描绘出其中一张脸。如果您想要最外面的，请从集合中最顶部像素的顶部边界开始。

Answer 2

我会尝试使用经典轮廓跟随算法的修改版本。 http://www.imageprocessingplace.com/downloads_V3/root_downloads/tutorials/contour_tracing_Abeer_George_Ghuneim/ray.html

修改在于 horizontal/vertical 移动是用两像素步长进行的（而不是标准版本中的一步）。

要找到所有轮廓，请扫描整个图像，直到遇到一个像素；跟随那个轮廓，关闭它的所有像素。然后在您离开的地方继续扫描。

顺时针排序一组点并确保连接这些点的路径闭合的算法

Algorithm to order a set of points clockwise and make sure the path connecting the points is closed

algorithm

path-finding

convex-hull

computational-geometry