我得到了一组坐标坐标的顺序有点随机，但坐标被聚在一起形成不同的区域。我正在努力创建一个算法来创建坐标顺序正确的单独路径。我一直在寻找寻路和图像处理的解决方案来解决这个问题，但迄今为止没有运气。
坐标如下所示。
有谁能提供一些帮助来创建一个算法来将这些坐标（按正确的顺序）排序成路径？
最佳答案
这个问题似乎有点棘手，因为其中一条路径实际上由两个循环组成。在这幅图中，如果选择了正确的起始位置，仍然是可行的，但请考虑以下情况：
XXX XX XXX XXXXX
X X X XXX X X X
X X X X X XXXXX X
XXX XX XX X XXXX
XXXXXXX XX
很容易看出，在任意的道路上，我们最终会有“克尼斯伯格的七座桥”（顺便说一下，由于桥梁数量的一些变化，这个问题现在有可能解决…）
至少有两种方法可以改变问题，使其得以解决：
允许多次遍历同一路径。
只考虑循环。
只给它提供可以绘制的路径，而不必多次遍历任何点。
找到路径段不是很困难，但是将它们组合成循环需要更详细地定义问题。
在路径查找中，我们需要能够确定路径从属于该路径的单个点到的所有方向这可以通过考虑像素所有可能的3x3邻域来实现。
还有一个附加的要求：如果路径从像素A到相邻像素B，则必须存在这两个之间的反向路径。这一要求缩小了可能性此外，还有很多对称性（90°旋转，镜像）。
应注意的是，可能有多达4个近邻（在以下配置中）：
.X. X.X
XXX .X.
.X. X.X
上面评论中引入的优先级规则是一个很好的规则。所以：
所有直接邻居都表示到/从一个点的路径
对角线邻域表示路径，如果它们旁边没有直接邻域
后一条规则可通过以下方式加以说明：
.XX .N.
XX. => N .
..X ..N
其中n代表邻居。
因此，每个点都有一个0..4个相邻点的列表相邻点具有类似的列表，因此连接是一对一的。
但现在我们有了挑战如何将连接信息合并到列表中？
简单的案例：
如果没有邻居（0），则该点本身形成一条路径
如果有一个邻居，他们属于同一条路
如果有两个邻居，这三个点都属于同一条路
之后我们有路段和交叉口。在这个答案开头的例子中，我们有：
111 33 666 AAAAA
1 1 3 X5X 6 A A
1 1 3 4 7 X8X99 A
11X X4 77 B XAAA
2222222 BB
这里0..b表示区段，x是它们的3或4个交叉点。
似乎至少有一条有用的规则可以用来简化结果：
如果有一个3交叉点，其中两个分支属于同一个环路，则可以从交叉点旁边的路径开始将其连接到环路中
在我们的示例图中，这可以应用于最左边的循环：
111 33 666 AAAAA
1 1 3 X5X 6 A A
1 1 3 4 7 X8X99 A
111 X4 77 B XAAA
1111111 BB
然后，对于每个3个交叉口，有三种连接方式：
/ / /
/ / /
/ /
----- --- -- |
\ \
\ \ \
\ \ \
对于每个4个交叉口，有四种不同的可能性：
| | | |
/ \
--------- --- --- --- --- --- ---
/ \
| | | |
由于我的图表有五个3-交叉点和一个4-交叉点，因此有3^5 x 4=972种不同的连接线段的方式。这可以通过详尽的搜索来完成，但是必须确定哪种解决方案是最好的也许路径的数量需要最小化，但是它是不是更好地最大化最长路径或最大化最短路径？或者别的什么？
有一些优化的空间，因为组合线段的几种不同方法可能会给出基本相同的结果（所有端点都在3个交叉点处的循环可以双向运行）。
总结一下：
找到附近的联系
隔壁邻居都是邻居
只有在没有隔壁邻居的情况下，对角邻居才是邻居
将简单案例连接成段（0、1或2个邻居）
创建交叉口列表
对段进行分组，以便单独处理完全独立的段组（单独的路径）
消除琐碎的3个交叉口（属于同一路段的两个相邻交叉口）
搜索所有可能的剩余交叉口，选择您最喜欢的结果
问题中显示的情况不需要最后一条规则，因为只有两个微不足道的3个交叉口。
关于image - 将坐标点分类为路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24404754/