CODEWITHSUNDEEP
algorithm2ddistributionpacking
Anton Harald
Anton Harald

Reputation: 5954

distribute rectangles of various sizes randomly on a plane of variable size (considering a degree of density)

I'm looking for an algorithm, which randomly distributes a number of rectangles (which are defined by their width and height) inside a container rectangle. The later is not defined by size, rather by it's aspect ratio. There must be one more variable that determines the density of the result, or in other words: the average distance of two rectangles. All rectangles are to be placed, which is possible, because the container is not limited in size. And there must be no overlapping of any rectangles.

The final result should be the determined position for each rectangle as well as the size of the used plane itself.

Unfortunately, I could not find an algorithm that does this, or parts of it until now. I'd appreciate any suggestions, comments or references! It turns out that the main problem is to keep track of a list of "free spaces", which is updated after each placement accordingly.

In the real case I need this for, the given rectangles are not completely randomly shaped. They have almost the same height, and tend to be much broader than tall: They are just words taken from a text which should be distributed over a plane as a "cloud".

Upvotes: 2

Views: 219

Answers (2)

Jean-Baptiste Yunès
Jean-Baptiste Yunès

Reputation: 36431

I think that you are looking for some thing like graph visualization with a forced-based layout. If you can model a relation in between your words, then the force is the parameter you need.

Upvotes: 0

user6697869
user6697869

Reputation:

Here's a few thoughts on how to design an algorithm:

  • Since the actual rectangles have similar sizes, you can probably group them into rows and stack multiple rows to get the final layout
  • Use the fact that rowCount * colCount == totalCount and colCount / rowCount == aspectRatio to approximate the number of rectangles in each row and column
  • To determine the free space remaining after the rectangles are placed, compute the area of the bounding box of all rectangles and subtract the sum of the individual rectangle areas. This works since rectangles don't overlap.
  • Perhaps the ratio of totalFreeSpace to boundingBoxArea gives you the desired density. If not, then an O(n^2) algorithm should help calculate the density per the problem description (assuming total rectangle count isn't too large).
  • Once you have the above working, you can tweak things to improve the cloud shape. For example, sorting each row to have the largest rectangles in the center.

Upvotes: 0

Related Questions