Is there an efficient algorithm to generate random points in general position in the plane?

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 s开发者_开发知识库uch a problem?

Update: square is aligned with the axes.

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)

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.

Similar to @LaC's answer. If memory is not a problem, you could do it like this:

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.

You could continue the outer loop until you have enough points, or run out of them.

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

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.

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

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.