0

I'm trying to make program which generates "map" with points (cities). Generate only random cities(represented by a graph) isn't problem, but I need set some minimum distance between them (for example, that distance between cities is 5 and more). It's about 3 000 cities, so I'm looking for some effective solution.

I can't devise how to solve it, so I will be grateful for any help.

4

3 回答 3

1

如果您将地图划分为 10x10 方格的网格，那么在给定点的五个单位内的任何点都必然在 (x +/- 5, y +/- 5) 定义的四个方格之一内。一个 10x10 的正方形可能最多包含 8 个点，但是将每个新点与四个最多包含 8 个点的正方形进行检查可能比将其与数千个其他点进行检查相比要快。

使用这种方法需要注意的最重要的事情是，因为整数除法运算符浮点到整数转换运算符的负数行为被选择为对处理器来说很容易，而不是对程序员有用，所以必须注意如果一些坐标是正的而一些是负的，则表示异常。例如，如果x是一个int和一个计算int col = x/10;，col对于从 -9 到 +9 的 x 值将为零（意味着包含点 (0,0) 的框在每个维度上几乎是它们应该的两倍大）。如果坐标可能变为负数，则必须在执行除法之前将它们调整为正数。

于 2013-10-30T20:51:45.167 回答
0

如果您的程序使用 x 和 y 轴，您应该参考距离公式。这是它的链接。圆方程也可能派上用场。把你的第一个城市想象成圆圈的中心。距离最小的第二个城市应该位于圆的圆周上，最小距离是该圆的半径。对于第二个城市应该在哪里，你有无数种可能性。但同样，这是假设您使用的是 x 和 y 轴。

于 2013-10-30T20:44:56.543 回答
0

如果大约有 3,000 个城市，将它们放入您的地图中，然后在您进行时检查您的最小距离标准可能不是那么不合理。检查时间随着 O(n) 的增加而增加，并且您在地图上已有的点越多，您就越有可能发生“碰撞”。

你需要多“随机”？如果你把你的地图分成一个 5x5 方格的网格，然后在盒子的中心 2.5x2.5 中随机放置一个点，你能过吗？那会很快，而且你不会遇到任何碰撞。

研究您需要的城市位置的随机性可能是值得的。

于 2013-10-30T20:17:52.677 回答