顺时针排序一组点并确保连接点的路径闭合的算法
Jed*_*Sam 5 algorithm path-finding convex-hull computational-geometry
我一直在以多种不同的方式解决这个问题，经过一个月的尝试，我认为是时候用新的眼光来审视它了。我正在尝试制作一个图像缩放应用程序，用于重新调整 8 位精灵的大小并将它们转换为矢量图像。到目前为止，我所做的工作是这样的；它获取图像，将其分解为形状（具有相同颜色的相邻像素的区域），然后形状中的每个像素被四个像素替换：
\n\nprivate Point[] expand(int x, int y){\n x *= factor;\n y *= factor;\n return new Point[]{new Point(x+half_factor,y), new Point(x+factor,y+half_factor),\n new Point(x+half_factor, y+factor), new Point(x,y+half_factor)};\n}\n这四个点中的每一个都被放入一个二维布尔数组中：
\n\nprivate void placePoint(int x, int y){\n table[x][y] = !table[x][y];\n extrema(x,y);\n}\n单个形状的结果如下所示：
\n\n
现在我想将所有这些点（减去内部的点）变成一个多边形，并且我尝试了许多不同的解决方案，最近我一直在尝试找到最近的邻居，直到它开始，但是每个算法我尝试失败。对于这个特定的示例，它到达右下角的 goomba，该 goomba 是颠倒的，并且在其左侧的像素簇中变得混乱。该程序认为路径已完成，并从那里创建一条到左上角的线，完全忽略左下象限中的点。
\n\n
这就是我想要的样子：
\n\n
以下是一些在我的情况下始终正确的事情，可能有助于找到有效的算法：
\n\n- \n
- 所有点列表中的第一个点是最外面路径的一部分 \n
- 最外面路径中的每个点都有一个距离它 C 个单位或距离它 \xe2\x88\x9aC 个单位的邻居 \n
- 最外面的路径始终是闭合路径 \n
任何帮助都感激不尽！
\n\n更新：
\n\n我已经尝试了下面的所有解决方案和建议，并取得了一些进展，但仍然没有得到所需的输出。
\n\n原来的：
\n\n
输出：
\n\n
最终更新：
\n\n现在可以了，只需解决小错误即可！
\n\n
小智 2
我会尝试使用经典轮廓跟踪算法的修改版本。http://www.imageprocessingplace.com/downloads_V3/root_downloads/tutorials/contour_tracing_Abeer_George_Ghuneim/ray.html
修改之处在于水平/垂直移动是通过两个像素步长进行的（而不是标准版本中的一个像素步长）。
要找到所有轮廓，请扫描整个图像，直到遇到一个像素；遵循该轮廓，关闭其所有像素。然后从上次离开的地方继续扫描。