randomly generated non-intersecting ellipses

Hi all,

i need to generate randomly distributed ellipses within square bounds that are non-intersecting

generating the random points is easy, and creating ellipses is simple enough (likely will involve local and global coordinate systems),

But ensuring that the ellipses do not intersect is a challenge.

Is anyone aware of a pre-existing matlab code to check whether ellipses intersect or not?

Or alternatively, does anyone have a recommendation as to how to approach this problem?

Any help would be greatly appreciated

thanks!

Answer 1

[Matt J]

You could randomly cut up the region into rectangular tiles.

 Tiles=true(M,N);

 Tiles(randi(M,mtiles,1),:)=false;
 Tiles(:,randi(N,ntiles,1))=false;

 S=regionprops(Tiles,'BoundingBox');

Then inscribe the tiles with ellipses.

[Tyler]

I have thought of using a similar approach - however i nglected to mention that these ellipses can be on an angle as well.

one method would be to bound the ellipse in a local coordinate system with a rectangle, and then in the global coordinate system see if those lines intersect with any existing ellipses over the appropriate bounds - but i was hoping for something more simple

[Image Analyst]

I think Matt's method (a clever one I voted for) is like the method you suggested except with his, you don't need to check for overlap because they're guaranteed to not overlap. Sure there are some little nooks where you could insert an even smaller ellipse, after all the tiles have been filled, but do you need to fill those? If so, you could find those little nooks with a distance transform.

And of course if you have a rectangular bounding box, there's nothing that says you need to put in a perpendicular ellipse - you could place a tilted ellipse in there if you want.

How many ellipses to you want to place? Just a fixed number, like 100, or keep going with smaller and smaller ellipses until you're down to one pixel big ellipses?

[Matt J]

however i nglected to mention that these ellipses can be on an angle as well.

As Image Analyst says, this in itself is not a limitation of what I proposed.

Perhaps what you really meant, however, is that you don't want to require the ellipses to be separable by horizontal/vertical lines.

If so, a related idea is to choose a random set of scattered (x,y) points in the field of the image. Then use voronoin() or delaunayn() to cut the field up into non-rectangular cells. Then inscribe ellipses into these. It would be a bit harder to incribe ellipses into polygons/triangles as opposed to rectangles, but still doable.

[Matt J]

It would be a bit harder to incribe ellipses into polygons/triangles as opposed to rectangles, but still doable.

This File Exchange tool

http://www.mathworks.com/matlabcentral/fileexchange/34767-a-suite-of-minimal-bounding-objects

would possibly be of help. Using incircle, you can inscribe the voronoi polygons or Delaunay triangles with circles. You can then shrink the circle by a random amount along some axis to obtain an inscribing ellipse.

Answer 2

[Sean de Wolski]

http://www.mathworks.com/matlabcentral/fileexchange/7844-geom2d