有没有一种高效算法可以在平面上生成处于一般位置的随机点？

Question

我需要在平面上生成n个处于一般位置的随机点，即任意三个点都不会共线。点的坐标应为整数，并位于固定正方形大小为m x m之内。请问解决这样一个问题最好的算法是什么？

更新：正方形与坐标轴对齐。

- Danylo Mysak

---

这个正方形是否与坐标轴对齐？如果是的话，那么这些坐标实际上只是在一个m²大小的网格上的点。 - Fred Foo

是的，没错。问题在于不能有三个点共线。 - Danylo Mysak

我只想指出，这绝对不是随机的。 - LaC

你认为什么是一条线？由于您正在使用整数，实际碰撞的机会很少。 - Brad

所谓直线是指一条直线。我必须保证没有碰撞。此外，如果n接近m或大于m，则碰撞往往会更频繁发生。 - Danylo Mysak

@Danylo：「直线」仍然不够明确 :) 你是指欧几里得直线，还是曼哈顿/出租车/L1直线？ - Fred Foo

Answer 1

由于它们是在一个正方形内的整数，因此将它们视为位图中的点。在第一个点之后添加一个点时，使用Bresenham算法绘制通过新点和旧点之一的所有线上的所有像素。当您需要添加新点时，请获取随机位置并检查是否清除；否则，请再试一次。由于每对像素都会产生一条新线，并且因此排除多达m-2个其他像素，随着点数的增加，您将拒绝几个随机选择，然后才能找到一个好的选择。我建议的方法的优点是，仅当您有一个好选择时，才需要花费遍历所有线的成本，而拒绝错误选择是非常快速的测试。

（如果您想使用不同的线定义，请使用适当的算法替换Bresenham）

- LaC

Answer 2

与@LaC的答案类似，如果内存不是问题，您可以这样做：

Add all points on the plane to a list (L).
Shuffle the list.
For each point (P) in the list,
   For each point (Q) previously picked,
     Remove every point from L which are linear to P-Q.
   Add P to the picked list.

您可以继续外部循环，直到获得足够的点或用完它们。

- Markus Jarderot

Answer 3

在添加每个点时，似乎没有其他方法可以避免检查每个点，要么通过（a）运行所有可能的线路，或者（b）消除冲突点以减少下一个点的可能位置。这两种方法中，（b）似乎可以提供更好的性能。

- John

---

我同意你的选项（b），在约束编程社区中被称为前向检查，但问题是有些点对可能会消除比其他点更多的点，因此这种生成和测试方法需要回溯或随机重启才能完成。 - Fred Foo

我想到了(a)的优化方法。你需要记住所有当前存在的线，比如它们的系数。当添加新点A时，你需要遍历所有现有的点，对于每个点Bi，构建ABi线并使用二分查找检查它是否已经在你的线集合中。如果是，则需要重新生成点A。当n<<m时，这个过程接近于n^2*log(n)。 - Danylo Mysak

Answer 4

这可能会起作用（虽然随机性可能有点受限）。在正方形内找到你可以画的最大圆（这似乎很容易）。在圆上选择任意n个点，没有三个点会共线 :-).

在代码中，这应该是一个足够简单的任务。假设圆心位于原点（因此形式为x^2 + y^2 = r^2）。假设r是固定的，x是随机生成的，您可以解决以找到y坐标。这为每个x给出了两个在圆上的直径相对的点。希望这可以帮助到您。

编辑：哦，整数点，刚注意到。那真是遗憾。不过我还是会保留这个解决方案-因为我喜欢这个想法。

- kyun

Answer 5

这里有一篇论文，也许可以解决你的问题：

“在一般位置上具有许多相似拷贝的点集”

作者：BERNARDO M. ABREGO 和 SILVIA FERNANDEZ-MERCHANT

- YesThatIsMyName

Answer 6

@LaC和@MizardX的解决方案都非常有趣，但是你可以将它们结合起来得到更好的解决方案。

@LaC的解决方案存在随机选择被拒绝的问题。你已经生成的点越多，生成新点就越困难。如果只剩下一个可用位置，你随机选择它的几率很小（1/（n*m））。

在@MizardX的解决方案中，你永远不会遇到被拒绝的选择，但是如果直接实现“从L中删除与P-Q共线的每个点”的步骤，复杂度会变差（O（n^5））。

相反，最好使用位图来查找应该删除哪些来自L的点。位图将包含一个值，指示一个点是否可以使用以及其在L列表上的位置，或者指示此点已经被划掉。这样，你可以获得最坏情况下的复杂度为O（n^4），这可能是最优的。

编辑：

我刚刚发现了这个问题：在C++中生成非退化点集合。它与这个问题非常相似。最好使用这个答案在C++中生成非退化点集合的解决方案。通过对其进行一些修改，使用基数或桶排序，并将所有可能的n^2个点添加到P集合中并随机排列，可以获得O(n^4)的最坏情况复杂度，代码也更简单。此外，如果空间是一个问题，@LaC的解决方案由于空间要求不可行，那么这个算法将不需要修改就能适应，并提供一个不错的复杂度。

- ciamej

Answer 7

嗯，你没有指定哪个平面...但只需生成3个随机数并分配给x、y和z

如果“平面”是任意的，则每次将z设置为0或其他值...

检查x和y是否在你的m边界内，

比较第三个x、y对是否与前两个在同一条直线上...如果是，则重新生成随机值。

- Randy

---

每一行都存在一些小错误。例如，随机数生成不是生成任意的随机数，而是生成在某个范围内的随机数。比较第三个元素与前两个不对，应该将一个新的元素与所有可能的配对进行比较。 - Karoly Horvath