How to cover a rectangle area with irregular shapes and no holes

Question

I have detailed, highly irregular shapes like these:

and I'm looking for a way to make them cover a rectangle area with no holes and minimal blend/cover between shapes. Limited up-scaling and free rotation is also allowed.

I searched through packaging and covering algorithms but there is not a lot of information about irregular shapes and every one I looked at assumes shapes cannot blend. In my case this is acceptable.

Given above shapes one solution would look something like this:

To achieve above result shapes have been transalted, rotated and scaled.

Given:

• All shapes can be scaled up and down (max 2x) and rotated
• Shapes can overlap
• Part of shape can be outside of rectangle
• Shapes don't have holes in them

Do you know an algo that could solve this?

Ossetic

@stark I would assume all the excess outside the rectangle are supposed to be minimized too. This does give an easy upperbound though, that can be used to eliminate bad solutions in a more advanced optimization algorithm. – Wiburg

You can't minimize two conditions without specifying their relative values. – Kadiyevka

@Kadiyevka up-scaling is limited, maxed to about 2x – Ossetic

@Wiburg outisde excess is not as important, worst case scenario if there is a little hole next to border, it should add a new shape to cover this hole, even if lets say 90% of the shape is outisde the box – Ossetic

I would be inclined to use the largest shapes, suitably scaled, to cover as much of the rectangle as possible. Then use the smallest possible shapes, again scaled, to cover the remaining holes. Try for one extra shape per hole. – Aphanite

@HubertRzepinski Please don't add precisions like that in the comments. "up-scaling is limited, maxed to about 2x" <<< that's a super important piece of information and will result in different solutions. Please use the edit button to add this info to your question. "outisde excess is not as important, worst case scenario if there is a little hole next to border, it should add a new shape to cover this hole, even if lets say 90% of the shape is outisde the box" Please include that as well in the question. – Wiburg

You're absolutly right @Stef, added. – Ossetic

Some of the shown shapes are not convex – Rashid

I'd start by fitting the largest possible rectangle in each shape. Then the problem becomes a packing problem with flexible rectangles. – Backsight

Is down-scaling also limited to 2x? Do you know how many copies of the shapes are typically needed to cover the area? 4? 100? 1000000? – Rashid

@GilbertLeBlanc That leaves us with holes unfortunetly. This to my knowledge cannot be solved as packaging problem. – Ossetic

@Rashid Yes. Copy number is limited to 2 milion per shape. I left this info because it further complicates already complicated problem. In the real-world use case rectangle will have size mesasured in kilemeters and shapes in meters. – Ossetic

Then one sensible approach could be to strive for a regular pattern so that the optimization problem has less degrees of freedom. Look here for some repeating tesselation patterns: en.wikipedia.org/wiki/Wallpaper_group#Group_p1 Another advantage is that as soon as a good match is found, the rectangle can be arbitrarily huge without further increasing the overlapping area percentage. – Rashid

How many different shapes are there? – Rashid

@Rashid around 100. – Ossetic

That is huge! Then approaches, which first consider only the approximate shape (to reduce overlapping, but ignore the details) or ones, which try to fit borders of shapes like a puzzle to combine them bottom up to larger shapes, could be best. A perfect solution is very far from the capabilities of any mathematician or computer, an approximate solution could be simple or complicated - depending on the irregularity of the shapes. – Rashid

Yeah, I thought of representing these shapes as circles with something like arxiv.org/ftp/arxiv/papers/1212/1212.3193.pdf and then the problem becomes circle packaging. Ideally instead of circles there could be approximate convex polygons (eg convex hulls) to minimize overlay, but these shapes are significantly more difficult to pack. – Ossetic

Circle packing is bad, as it keeps holes. You would e.g. inscribe the shapes of the wallpaper groups. Most simple would be to try to inscribe rectangles (with any rotation/best fit) and then just keep the shape, which was best and repeat it over the whole area. – Rashid

Yes, there will be holes between circles, but circles themselves will be smaller then actual shapes, so when circle are "converted" back to the shape it represent, most holes should to covered. – Ossetic

Next simple would be a parallelogram. – Rashid

What is the aim? To need as few area as possible (with overlapping area counting multiple times)? Or similarly as few shapes as possible? Or as few overlap area as possible? Or the 2 million per shape are not enough, so if there is a best fitting one, we still need to use the others? Or we just have to fill without holes and one solution is as good as the others? – Rashid

Let us continue this discussion in chat. – Ossetic