Selecting submatrices at random given a set of constraints

New to programming here and I really have no idea how to approach this.

My problem: I have a bunch of images that are annotated with rectangular bounding boxes and want to pick other rectangular bounding boxes at random that do not overlap with the bounding boxes I already have. So basically I have a matrix M and a predefined subset X of submatrices of M and I want to generate new submatrices with random positions that do not overlap with X but can overlap with each other; the generated submatrices should be about the same size as the submatrices in X and contained in matrix M.

http://i.imgur.com/74AEI2x.png

In the example above, the boxes in that image represent X, positive exambles of soccer balls; I want to generate an equal number of boxes of the same size that do not enclose soccer balls, to represent negative examples of soccer balls.

Any direction is appreciated.

Answer 1

[Matt J]

Because the soccer balls are such a small region of the image, I think you could just randomly generate rectangles without constraints, then reject the ones that overlap with the soccer balls.

That reduces the problem to one of detecting whether two rectangles overlap. There are a variety of tools on the File Exchange for doing that. One of them is

http://www.mathworks.com/matlabcentral/fileexchange/30892-representing-polyhedral-convex-hulls-by-vertices-or--in-equalities

If you have the vertices V1 and V2 of two rectangles, you can use vert2lcon to get them in inequality form,

A1*x<=b1; %rectangle 1
A2*x<=b2; %rectangle 2

They intersect in a (possibly empty) rectangle with vertices

V=lcon2vert([A1;A2],[b1;b2])

If V=[], you reject.

[Matt J]

If the rectangles are non-rotated, as shown in your posted image, it becomes even easier to detect their intersection. Just project them onto the x and y axes. If the intervals they project into do not overlap on both axes, then the rectangles do not intersect.