Ensure two random shapes are never near each other or overlapping

Question

var random = new Random();
        Canvas.SetLeft(rectangle, random.Next((int)(ImageCanvas.Width - 100)));
        Canvas.SetTop(rectangle, random.Next((int)(ImageCanvas.Height - 100)));
        return rectangle;

So the above code just randomly sets the Top and Left positions of a rectangle that will appear on the canvas. I can easily reuse this code if I want multiple rectangles to appear on the screen, however what I was having trouble doing is tweaking the code so that each rectangle is never overlapping each other.

I thought of maybe doing a while loop that keeps running random.Next((int)(ImageCanvas.Height - 100)) continuously until it is not equal to the previous random... But that isn't perfect. The shapes are quite big, so having slightly different X or Y coordinates doesn't prevent a overlap. They would somehow need to be at least 50 pixels distance between each other or something for this to prevent any overlap between other rectangles.

Answer 1

Assuming your Canvas is reasonably large, i.e. the rectangles will not occupy a large amount of the area, it most likely suffices to simply generate rectangles at random (as in your example code), and then check to make sure they don't overlap with any of the previously selected rectangles.

Note that "overlaps with another rectangle" is really the same as "has a non-empty intersection with another rectangle". And .NET provides that functionality; for WPF, you should use the System.Windows.Rect struct. It even has an IntersectsWith() method, giving the information you need in a single call (otherwise you'd have to get the intersection as one step, and then check to see if the result is empty in a second step).

The whole thing might look something like this:

List<Rectangle> GenerateRectangles(Canvas canvas, int count, Size size)
{
    Random random = new Random();
    List<Rect> rectangles = new List<Rect>(count);

    while (count-- > 0)
    {
        Rect rect;

        do
        {
            rect = new Rect(random.Next((int)(canvas.Width - size.Width),
                (int)(canvas.Height - size.Height), size.Width, size.Height);
        } while (rectangles.Any(r => r.IntersectsWith(rect));

        rectangles.Add(rect);
    }

    return rectangles.Select(r =>
         {
             Rectangle rectangle = new Rectangle();

             rectangle.Width = r.Width;
             rectangle.Height = r.Height;
             canvas.SetLeft(rectangle, r.Left);
             canvas.SetTop(rectangle, r.Top);

             return rectangle;
         }).ToList();
}

You would want something more sophisticated if you were dealing with a more constrained area and/or a larger number of rectangles. The above won't scale well for large numbers of rectangles, especially if the probability of a collision is high. But for your stated goals, it should work fine.