Finding largest non-obstructed rectangle?
Author
Given randomly distributed rectangles within an area, and having their x & y coordinates as well as their widths and heights in an array (or arrays, whichever is easier), I need to find the largest non-occupied rectangular space within the area.
I know this must be so simple that it''s been posted before, but my searches are not coming up with anything.
Does anyone have the algorithm for finding where the next rectangle may be placed (x & y) and what the largest possible size may be (height and width) in such a way that it is not overlapping any existing rectangles?
Thanks,
Gary
g.dejarnett@ttu.edu
Are you needing an algorithm or just to do it? If you just need to do it then "regions" under windows may be able to do it for you. Otherwise I think you need to use a tree. The leaves are your free regions. You start with the entire area free. Then each rectangle you add can cause a node to split into up four child regions. At each branch in the tree you add the part of the rectangle contained in a child. I don''t think there will be any problem with overlaps. As an example if your area is 100 by 100 and you add a 50 by 50 region at (25,25) then you have children (0,0)-(100,25), (0,0)-(25,100), (75,0)-(100,100) and (0,75)-(100,100). If you add the region (20,20)-(30,30) then (20,20)-(30,25) would be added to (0,0)-(100,25) and (20,20)-(25,30) to (0,0)-(25,100). The region (25,25)-(30,30) would be irrelivant because it is already occupied.
Author
Thanks for your reply.
I can see that I left out some important information. What I''m doing is displaying (fading in and out) randomly selected photographs on the screen. As each photograph is displayed, it''s coordinates and size are registered in an array.
In answer to your question, I don''t need to write the algorithm, I just need to do it.
The way I see it, your tree suggestion would work perfectly if the photos were all the same size. My problem is that they are various heights and widths, so I''m basically needing to say, "The largest open area on the screen is at these coordinates and is this width/height, get a random photo, will it fit?, if not, go get another one until one fits, start it fading in, now where is the largest open area?"
Again, the question is how to determine that largest "open rectangle".
Thanks again,
Gary
I can see that I left out some important information. What I''m doing is displaying (fading in and out) randomly selected photographs on the screen. As each photograph is displayed, it''s coordinates and size are registered in an array.
In answer to your question, I don''t need to write the algorithm, I just need to do it.
The way I see it, your tree suggestion would work perfectly if the photos were all the same size. My problem is that they are various heights and widths, so I''m basically needing to say, "The largest open area on the screen is at these coordinates and is this width/height, get a random photo, will it fit?, if not, go get another one until one fits, start it fading in, now where is the largest open area?"
Again, the question is how to determine that largest "open rectangle".
Thanks again,
Gary
Author
LilBudyWizer,
Sorry I misread your post initially. I see now that you weren''t assuming rectangles of the same size after all.
I see how using your method, I could keep from colliding the pictures with one another, but am still not certain how I''d cycle through the arrays and determine the largest open area.
Thanks,
Gary
Sorry I misread your post initially. I see now that you weren''t assuming rectangles of the same size after all.
I see how using your method, I could keep from colliding the pictures with one another, but am still not certain how I''d cycle through the arrays and determine the largest open area.
Thanks,
Gary
The idea was that the leaves are all open, but there is a problem with that. A node may have no children for two differant reasons. One is that the area is represents is completely open. The other is that is completely closed. So you would need a flag to say which type it is. When you initially add a node the flag is cleared. The only time you set it is when you add a region and there are no open areas to add as children to a leaf. When you remove a region I think you will have to completely rebuild the tree.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
