是否有一种有效的算法来生成平面上一般位置的随机点？
我需要在平面上的一般位置生成n个随机点，即没有三个点可以位于同一条线上。点的坐标应该是整数，并且位于固定的正方形 m x m 内。解决此类问题的最佳算法是什么？
更新：正方形与轴对齐。
I need to generate n random points in general position in the plane, i.e. no three points can lie on a same line. Points should have coordinates that are integers and lie inside a fixed square m x m. What would be the best algorithm to solve such a problem?
Update: square is aligned with the axes.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（7）
由于它们是正方形内的整数，因此将它们视为位图中的点。当您在第一个点之后添加一个点时，请使用 Bresenham 算法绘制穿过新点和旧点之一的每条线上的所有像素。当需要添加新点时，随机获取一个位置并检查是否清晰；否则，请重试。由于每对像素都会给出一条新线，因此会排除最多 m-2 个其他像素，因此随着点数的增加，在找到一个好的选择之前，您将拒绝几个随机选择。我建议的方法的优点是，当你有一个好的选择时，你只需支付遍历所有行的成本，而拒绝一个不好的选择是一个非常快速的测试。
（如果您想使用不同的线定义，只需用适当的算法替换 Bresenham 的即可）
Since they're integers within a square, treat them as points in a bitmap. When you add a point after the first, use Bresenham's algorithm to paint all pixels on each of the lines going through the new point and one of the old ones. When you need to add a new point, get a random location and check if it's clear; otherwise, try again. Since each pair of pixels gives a new line, and thus excludes up to m-2 other pixels, as the number of points grows you will have several random choices rejected before you find a good one. The advantage of the approach I'm suggesting is that you only pay the cost of going through all lines when you have a good choice, while rejecting a bad one is a very quick test.
(if you want to use a different definition of line, just replace Bresenham's with the appropriate algorithm)
在添加每个点时，看不到任何方法来检查它，要么通过（a）遍历它可能位于的所有可能的线，要么（b）在进行过程中消除冲突点以减少该点的可能位置下一点。在这两者中，(b) 似乎可以为您提供更好的性能。
Can't see any way around checking each point as you add it, either by (a) running through all of the possible lines it could be on, or (b) eliminating conflicting points as you go along to reduce the possible locations for the next point. Of the two, (b) seems like it could give you better performance.
与@LaC的答案类似。如果内存不是问题，你可以这样做：
你可以继续外循环，直到你有足够的点，或者用完它们。
Similar to @LaC's answer. If memory is not a problem, you could do it like this:
You could continue the outer loop until you have enough points, or run out of them.
这可能会起作用（尽管可能有点随机）。找到你能在正方形内画出的最大的圆（这似乎是非常可行的）。在圆上选取任意 n 个点，没有三个点会共线:-)。
这在代码中应该是一个足够简单的任务。假设圆以原点为中心（因此形式为 x^2 + y^2 = r^2）。假设 r 是固定的，x 是随机生成的，您可以求解找到 y 坐标。这为每个 x 提供了圆上两个完全相反的点。希望这有帮助。
编辑：哦，整数点，刚刚注意到这一点。那就可惜了。不过，我会保留这个解决方案 - 因为我喜欢这个想法
This might just work (though might be a little constrained on being random). Find the largest circle you can draw within the square (this seems very doable). Pick any n points on the circle, no three will ever be collinear :-).
This should be an easy enough task in code. Say the circle is centered at origin (so something of the form x^2 + y^2 = r^2). Assuming r is fixed and x randomly generated, you can solve to find y coordinates. This gives you two points on the circle for every x which are diametrically opposite. Hope this helps.
Edit: Oh, integer points, just noticed that. Thats a pity. I'm going to keep this solution up though - since I like the idea
@LaC 和@MizardX 的解决方案都非常有趣，但您可以将它们结合起来以获得更好的解决方案。
@LaC 解决方案的问题是你的随机选择会被拒绝。您已经生成的积分越多，生成新积分就越困难。如果只剩下一个可用位置，您就有很小的机会随机选择它 (1/(n*m))。
在 @MizardX 的解决方案中，你永远不会被拒绝的选择，但是如果你直接实现“从 L 中删除与 PQ 线性的每个点”。步骤你会变得更糟糕的复杂性（O（n ^ 5））。
相反，最好使用位图来查找 L 中要删除的点。位图将包含一个值，该值指示一个点是否可以自由使用以及它在L列表上的位置是什么，或者一个值指示该点已经被划掉。这样你就可以得到 O(n^4) 最坏情况的复杂度，这可能是最优的。
编辑：
我刚刚发现这个问题：Generate Non-Degenerate Point Set in 2D - C++
与此非常相似。最好使用这个答案的解决方案 生成非-2D 中的简并点集 - C++。对它进行一些修改以使用基数或桶排序，并将所有 n^2 可能的点最初添加到 P 集合中并对其进行打乱，还可以使用更简单的代码获得 O(n^4) 的最坏情况复杂度。此外，如果空间是一个问题，并且@LaC 的解决方案由于空间要求而不可行，那么该算法将无需修改即可适应，并提供不错的复杂性。
Both @LaC's and @MizardX's solution are very interesting, but you can combine them to get even better solution.
The problem with @LaC's solution is that you get random choices rejected. The more points you have already generated the harder it gets to generate new ones. If there is only one available position left you have slight chance of randomly choosing it (1/(n*m)).
In the @MizardX's solution you never get rejected choices, however if you directly implement the "Remove every point from L which are linear to P-Q." step you'll get worse complexity (O(n^5)).
Instead it would be better to use a bitmap to find which points from L are to be removed. The bitmap would contain a value indicating whether a point is free to use and what is its location on the L list or a value indicating that this point is already crossed out. This way you get worst-case complexity of O(n^4) which is probably optimal.
EDIT:
I've just found that question: Generate Non-Degenerate Point Set in 2D - C++
It's very similar to this one. It would be good to use solution from this answer Generate Non-Degenerate Point Set in 2D - C++. Modifying it a bit to use radix or bucket sort and adding all the n^2 possible points to the P set initially and shufflying it, one can also get worst-case complexity of O(n^4) with a much simpler code. Moreover, if space is a problem and @LaC's solution is not feasible due to space requirements, then this algorithm will just fit in without modifications and offer a decent complexity.
这里有一篇论文也许可以解决你的问题：
“POINT-SETS IN GENERAL POSITION AND MANY
类似的图案副本”，
作者：Bernardo M. Abrego 和 Silvia FERNANDEZ-MERCHANT
Here is a paper that can maybe solve your problem:
"POINT-SETS IN GENERAL POSITION WITH MANY
SIMILAR COPIES OF A PATTERN"
by BERNARDO M. ABREGO AND SILVIA FERNANDEZ-MERCHANT
嗯，你不指定哪个平面..但只是生成 3 个随机数并分配给 x、y 和 z（
如果“平面”是任意的），然后每次都设置 z=o 或者其他...
检查一下x 和 y 看看它们是否在您的 m 边界内，
比较第三个 x,y 对，看看它是否与前两个在同一行...如果是，则重新生成随机值。
um, you don't specify which plane.. but just generate 3 random numbers and assign to x,y, and z
if 'the plane' is arbitrary, then set z=o every time or something...
do a check on x and y to see if they are in your m boundary,
compare the third x,y pair to see if it is on the same line as the first two... if it is, then regenerate the random values.