How do I randomly generate multiple random shapes within a given area WITHOUT overlapping?

Hi, I have generated a random shape. I need to loop it over to randomly distribute such shapes within a given area WITHOUT overlapping. Area could be n by n units where n being a large integer number compared to the size of an individual shape.

Answer 1

[Jeff Miller]

One very general way is to just keep generating shapes randomly but throw away any newly-generated random shapes that overlap with ones you have previously generated. The algorithm might look something like this:

PixelUsed = false(n,n);  % the full area in which shapes are to be generated.  no pixels used yet.
while WantMoreShapes
    newShape = myRandomShapeGenerator;
    thisShapePixel = PixelMarker(newShape);  % PixelMarker returns (n,n) array indicating whether newShape uses each pixel.
    if ~AnyOverlap(thisShapePixel,PixelUsed)   % Check whether any pixel is true for both n,n arrays.
       % this newShape does not overlap with any used before
       iShape = iShape + 1;
       myStoreShape(iShape) = newShape;
       PixelUsed = PixelUsed | thisShapePixel;  % mark the pixels used by this shape
       WantMoreShapes = ???;
    end
end

Watch out---this process could easily get into an infinite loop, so you should add code to exit after a number of unsuccessful newShape's.

Also, the shapes generated later will tend to be smaller (since larger ones are more likely to overlap with something). If that is a problem for you, then this method probably won't work.

[Anuruddha Jayasuriya]

Hi Jeff, thank you for guiding me to that path. But I see some difficulty in moving generated fills at each loop step. For generating random shapes, I have used random numbers and convex hull algorithm as listed below. If you could see where I am going with this, would be greatly appreciated. Thanks!

[Jeff Miller]

Sorry, but I cannot really follow your code, nor understand the difficulty that you see with "moving generated fills at each loop step".

You might be able to use the 'inpolygon' function to identify whether each point in the n,n space is contained in your currently-generated polygon (though this might be slow). This would be the essence of the PixelMarker function in my schematic algorithm.

[Image Analyst]

With my code, the blobs are already, automatically not overlapping. Did you even try it?

Answer 2

[Image Analyst]

You can use my clouds program. It will generate gray scale images of clouds.

Of course you can then threshold the image and get a binary image with randomly-shaped, non-overlapping shapes.

[Anuruddha Jayasuriya]

It's a pretty long code. But I don't get where you have the algorith to identify the overlapping, and avoiding it.

Care to explain how to avoid two shapes being overlapped?