Free Space Detection Algorithm

Posted By: Tempelbauer

Free Space Detection Algorithm - 07/14/14 21:18

I need an algorithm to detect free space on a 2D plane. As input I have a canvas (size) and a list of items (their bounding boxes). I want the biggest rectangle which does not intersect with any item (the biggest free space). It does not have to be perfect.
Random positioning is my fallback solution, but I want something better.

I donīt need code, just an idea or the name of an algorithm that provides this. For some reason iīm unable to find it myself (this is maybe the aftermath from the worldcup party tongue )

Thanks
Posted By: Superku

Re: Free Space Detection Algorithm - 07/15/14 22:14

I would probably reduce that rather complex problem to a one-dimensional problem first and extend it then to two dimension.

Try to find the longest intervals/ biggest free space on for example the x-axis using only item.pos_x+min_x/max_x (shouldn't be trivial) and (optionally?) sort them by length. Then do the same for the y-axis and somehow multiply all (big enough) spaces/ intervals with each of those on the other axis - or somehow like that, I cannot really imagine it right now in my head.
© 2024 lite-C Forums