例如，受限空间为 100 x 100 x 100 大，每个球的半径为 5，我需要在该空间内的任意位置生成 100 个这样的球，并且不允许重叠。我提出了两种方法：
使用 srand 得到 100 个位置，然后做一个检查删除相互重叠的球（检查两个球中心的距离是否小于半径的两倍），然后生成另一个 x 个球（x 是球的数量已删除）并继续重复该过程，直到 100 个球不重叠。
首先将空间划分为 100 个立方体，然后使用 将每个球放在其分配的立方体内srand，这样它们就不会重叠。
我觉得第一种方式在随机方面更合适，但太费时，第二种方式又快又容易，但我不确定随机的想法。而这个模型正试图模拟分子在空气中的位置。也许这两种方法都不好，如果有更好的方法，请告诉我。提前致谢！
编辑：@Will 为我提供了一个与我原来的第一种方法相似但更清洁的选项；每次添加新球时，检查它是否与任何现有球重叠，如果重叠，则重新生成。复杂度是1+2+3...+(n-1)，大约是O(n^n)。我仍然想知道是否有更快的算法。
Edit2：抱歉 1+2+..n 应该是 n^2
您可以执行 O((n + f) log n) 算法，其中 f 是失败尝试的次数。本质上，花费时间过长的问题是找到与哪些相邻的球重叠。您可以使用称为 KD-tree 的外部数据结构来有效地存储球的位置。然后你可以通过KD树查找你“最近”的相邻球。这将花费 O(log n) 时间。确定它们是否重叠，然后将球添加到空间和 KD 树中——插入是 O(log n) 操作。总共有 n 个球，每个球取 O(log n) 将是 O(n log n)，失败的尝试将是 O((n+F)*log n)。CGAL（计算几何算法库）提供了一个很好的 KD-tree 实现。这是 CGAL 的链接和 KD 树的链接：
https://en.wikipedia.org/wiki/K-d_tree
还有其他结构，例如 KD 树，但这对于您的情况来说是最容易使用的。
如果您想避免使用花哨的数据结构，可以在空间上计算网格。将整个空间中的每个随机球插入其网格单元中。然后在检查重叠时，您只需要检查相邻单元格中的球（假设球大小不会重叠超过一个邻接）。这不会提高整体时间复杂度，但在计算机图形学中是一种常用方法，可提高邻居查找例程的执行时间。
与其将区域划分为 100 个立方体，不如将其划分为 8,000 个 5 x 5 的立方体，然后将居中的球放入 100 个这些立方体中。这样球仍然随机放置在空间中，但不能重叠。编辑：另外，在检查球是否重叠时，您可能需要考虑使用一种数据结构，该结构允许您仅检查最接近您正在检查的球的球。检查所有这些是浪费的，因为空间完全不同侧的球不可能重叠。我对八叉树不太熟悉，但如果你真的想优化你的代码，你可能想看看它们。
你的球体的体积大约是你空间体积的 1/1900，所以如果你只是选择随机位置并检查重叠，你就不必重新生成很多。如果你真的只需要 100 个，那么使用像八叉树这样的奇特算法来检查碰撞将是一种浪费。
当然，一旦您编写代码，有人会要求您为 10,000 个球体而不是 100 个球体进行编码，所以我刚才所说的一切都是错误的。
我喜欢克里斯的建议，即把它们放在随机选择的立方体中。也许不是最现实的，但接近且简单得多。