MATLAB: How to randomly generate multiple random shapes within a given area WITHOUT overlapping

MATLABrandom number generator

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.

Best Answer

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.
Related Question