How to select random points within grid meeting min/max distance requirements from each other?

Question

I have a 2D grid map that is relatively large. I'd like to pick some semi-random points all over it (say N points). The rule I want to ensure here, though, is that any selected points are at least M distance from every other selected point but no more than L distance from at least one other point.

Is there a fairly elegant way of doing this without having every new point's distance calculated for every existing point (being less computationally expensive as well)?

I imagine the rules could be met by something like partitioning the map out into rectangular segments and just kind of flood-fill randomly from one inner segment outwards, but I'm having a little trouble visualizing that where my L, M, and N values are randomly chosen (L is of course greater than or equal to M, but not entirely sure what the rules will be for M or N or even the size of the map).

The reason for this whole thing is a procedural waypoint system that I can then build a 2D dungeon crawler type map by using a path finding system to create tiles from waypoint to waypoint essentially.

If this is too vague or any other issues, just let me know and I'll happily try to explain further.

Edit: To give some hard numbers as an example, say the full grid is 2,000 by 1,000 total possible points. Assume you want 5,000 total waypoints spread fairly randomly across the map. Each of the 4,000 points need to be (euclidean distance) greater than 20 from every other point and less than 30 away from at least one other point.

Answer 1

Every point must be greater then 20 and less then 30 away from each other.

Red    is the Point.
Purple is the radius 20 from point. If any point is placed here it means it is inside the radius of another point.
Green  is radius 30 from point.
White  is out side. No points should be placed here because it means that point will be 30 units away from any other point.

Next simply add a point randomly in a green space and fill in its neighbors. Each point is now greater then 20 and less then 30 from every other point.

Im guessing you will store your grid of points as a object that contains the state of the square.

There is also this method maybe this is what you were looking for in the first place :D

Answer 2

Your point selection rules can be satisfied by a Poisson-Disk sampling distribution & can be solved in O(n) with Bridson's algorithm. Basically, the algorithm divides the output region into a grid of cells sized relative to the minimum allowable distance, such that only one point can appear in each cell. Then, when you consider adding a new point, you only need to check a disk shaped collection of neighboring cells as opposed to the entire list of points. With respect to your problem, the cell & neighborhood size will account for your M parameter, the disk radii will account for your M parameter. Your N parameter is handled by terminating when enough points have been generated.

Mike Bostock has a nice animation showing the algorithm in progress.

The standard implementation is only concerned with a fixed minimal distance between points. amitp mentioned Herman Tulleken's Poisson Disk sampling article; it includes an adaptation to for varying the minimum distance across the resulting image/map which may make it better suited for your problem. It also includes source code.

Answer 3

Here's an idea of how it might go. Keep in mind the more points you create the less random their placing will be.

For(int i=0; i<3999; i++){
    array.add(new Point(random.int(x);
    random.int(y));
}

For(int i=0; i<3999; i++){
    int dist = Point.calcDistance(array.get(i),array.get(i++)); 
    //distance formula between two points: sqrt((x2-x1)^2+(y2-y1)^2))

    if(dist < 20 && dist> 30){
        array.remove(i++); //or create another one
    }
}