我正在尝试制作生成带有点(城市)的“ map ”的程序。仅生成随机城市(由图表表示)不是问题,但我需要设置它们之间的最小距离(例如,城市之间的距离为 5 或更多)。 大约有 3000 个城市,所以我正在寻找一些有效的解决方案。
我无法想出如何解决这个问题,所以我将不胜感激任何帮助。
最佳答案
如果将 map 划分为 10x10 方格的网格,则给定点 5 个单位内的任何点都必然位于 (x +/- 5, y +/- 5) 定义的四个方格之一内。一个 10x10 的正方形可能最多包含 8 个点,但是对照每个最多有 8 个点的四个正方形检查每个新点可能比对照数千个其他点进行检查要快。
使用这种方法时,您需要注意的最重要的事情是,因为选择整数除法运算符浮点到整数转换运算符的负数行为是为了使处理器更容易,而不是对程序员有用,所以如果有些坐标为正,有些坐标为负,则必须注意异常情况。例如,如果 x
是一个 int
并且计算 int col = x/10;
,则 col
将是x 值从 -9 到 +9 为零(意味着包含点 (0,0) 的框在每个维度上几乎是应有的两倍)。如果坐标可能为负值,则必须在执行除法之前将其调整为正值。
关于java - 如何生成 "random"个点,它们之间的距离最小,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19692872/