通过地图/矩阵对河流不相交的地形地图进行聚类？
通过地图/矩阵对河流不相交的地形地图进行聚类？
提问于 2013-03-20 22:31:04
我有简单的矩阵(矩阵，它代表二维游戏中的地形图，包含ASCII字符，例如'm‘代表山脉，'v’代表河谷，'r‘代表河流)，在地图上可能有一条河流，也可能没有河流。河流可以从矩阵的任何位置流向任何位置(并且始终将两个不同部分的地图分开，=>地图上不可能有河流的来源，总是从一端进入而存在于另一端)。如果有河流，如何在两个集群上分离矩阵/地形图？
示例地形
v v v v v v v v r v v v v v
v v v v v m m m r m m m m m
v v v v v m m r r m m m m m
m m v m m m m r r m m m v v
v v v v v v r r v v v v v v在这里，我应该得到左群和右群的坐标，它们不是河流。
回答 2
Stack Overflow用户
回答已采纳
发布于 2013-03-20 22:39:10
您应该尝试查找Fill算法。http://en.wikipedia.org/wiki/Flood_fill
基本上，你想选择一个不在河流中的点，启动泛洪填充算法，它将给你一组连接到起始点的点。这样，你现在就有了一个部分，从现在开始，找到那个部分就很容易了。
Stack Overflow用户
发布于 2013-03-20 22:55:42
你的地图会引出一个图表：
- 每个地图像元都有一个折点，如果两个折点相邻，则它们是相连的和，它们都不是'r'
一旦构建了图形，您就可以运行breadth-first search (BFS)或depth-first search (DFS)之类的图形遍历算法来查找图形的connected components。
我推荐使用BFS，因为如果map很大，那么DFS可能会导致堆栈溢出(如果使用了它的递归实现)。
您将只想在非‘r’节点上运行BFS，这样最终您将得到两个连接的组件。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/15526420
复制相关文章
相似问题
腾讯云开发者
