Random squares/rectangles in a square

I have a square of size 1, that is (0,1)x(0,1). In this square, I would like to create random squares or rectangles of various sizes where none of them share an edge with each other. Meaning, I want them randomly spaced out. Then, i would like to save the values or coordinates within each squares to compare them with an input (x,y) such that (x,y) has value 1 if it's in the square, and zero if it's not.

I want to repeat this(random sampling of squares) for 5 different samples.

Thanks!

Answer 1

[William Rose]

@Tony Haines,

So you want option B. OK.

Ns=5;                   % number of squares
P=zeros(4,2,Ns);        % vertex coords
s=zeros(Ns,1);          % side lengths 
anyOverlaps=1;          % =0 if no squares overlap
inSquare=zeros(Ns,1);   % =1 when point is in square i
j=0;                    % initialize counter
while anyOverlaps>0 
    for i=1:Ns
        LL=rand(1,2);           % lower left coords of square: [x1,y1]
        s(i)=(1-max(LL))*rand(1,1); % side length
        P(:,:,i)=[LL; LL+[s(i),0]; LL+[s(i),s(i)]; LL+[0,s(i)]]; % vertex coords
        pgon(i)=polyshape(P(:,:,i)); % create square polygon
    end
    tf=overlaps(pgon);
    anyOverlaps=sum(tf,'All')-Ns;
    j=j+1;
end
fprintf('After %d attempts, we found %d non-overlapping squares.\n',j,Ns)

After 2 attempts, we found 5 non-overlapping squares.

fprintf('Minimum, maximum side lengths = %.3f, %.3f.\n',min(s),max(s))

Minimum, maximum side lengths = 0.011, 0.167.

fprintf('Total area covered by squares=%.3f.\n',sum(s.^2))

Total area covered by squares=0.049.

Now we have 5 "random" non-overlapping squares.

Pick a point (x,y) and see if it is in any of the squares.

x=rand(1,1); y=rand(1,1);
for i=1:Ns
    inSquare(i)=inpolygon(x,y,P(:,1,i),P(:,2,i)); 
end
fprintf('Point (x,y) is in %d square(s).\n',sum(inSquare,'all'))

Point (x,y) is in 1 square(s).

Plot the point and the squares.

figure
for i=1:Ns
    plot(pgon(i)); hold on; 
end
plot(x,y,'r*')
axis equal; xlim([0,1]); ylim([0,1])

I had to run the script above at least 10 times before I got a case where the point was in one of the squares.

[William Rose]

In my script, I pick Ns=5 random squares. Then I check to see if any of them overlap.

I thought it might take a lot of trials to find 5 non-overlapping squares, but it has not, in my attempts.

One could pick the first square, then pick successive squares one at a time, and check each one for overlap with the ones already picked. Maybe you can code that algorithm.

[Tony Haines]

Thank you so much for this! I made a few modifications to your first code by picking the first square, then requiring the next one to be non-overlapping by making use of the logic return "inpolygon". I dropped the cases where either square S1 was in S2 or S2 was in S1. I was able to run this to produce about 150 non-overlapping squares within the unit square. This increases the likelyhood of a test point being found.

Thank you once again.

[William Rose]

@Tony Haines, You're welcome. I'm glad you found a solution that you are happy with. When you have 149 squares, do you pick a "random" square, S150, and compare it to each of the 149 squares already found?

I guess that, since you pick squares sequentially, the expected size of square N+1 is smaller than all earlier squares, since the latter square must fit in around the early squares.

Good luck with your work.

[Tony Haines]

Yes, that's right. If I had N squares, then the size of square N+1 has to satisfy the non-overlapping rule with the N previously choses squares and also fit the remaining vacant space. And sice the dimension of square N+1 is randomly chosen using rand(), this allows for any number of square sizes. Out of 1000 iterations, I found 192 squares satisfying the conditions.

Note: some of the squares look close together but they acutually do not touch.

[William Rose]

@Tony Haines, very nice!

Answer 2

[William Rose]

@Tony Haines,

Do you want

A. One random square inside the unit square, and you want choose that random square 5 times, and each time you want to see if a random point (x,y) falls within the random square?

or

B. Five "random" non-overlapping little squares inside the unit square. If this is the case, then the 5 little squares are not really random, since the location and size of each is constrained by the square(s) already chosen.

or something else? I assume you want A. I will do A, with six examples, instead of five. I will use one random point and compare it to six different squares.

x=rand(1,1); y=rand(1,1);  % point of reference
pointInSquare=zeros(1,6);  % initialize array for whether point is in the square
figure
for i=0:1
    for j=0:2
        BL=rand(1,2); %x,y coords of bottom left corner of random square inside the unit square
        s=(1-max(BL))*rand(1,1);  % side length
        P=[BL; BL+[0,s]; BL+[s,s]; BL+[s,0]]; % array of vertices of square
        pgon=polyshape(P); % create square polygon
        pointInSquare(3*i+j+1)=inpolygon(x,y,P(:,1),P(:,2)); % =1 if x,y in or on square 
        subplot(2,3,3*i+j+1); 
        plot(pgon); hold on; plot(x,y,'r*'); axis equal; xlim([0,1]); ylim([0,1])
    end
end

fprintf('(x,y) in square for  %d square(s).\n',sum(pointInSquare));

(x,y) in square for  1 square(s).

Try it.

[Tony Haines]

I was thinking along the line of option B. I wanted for example, 6 non-overlapping squares(of varying sizes) inside the unit square. And then to check if a random point (x,y) is in any of those 6 non-overlapping squares.