Fit multiple polygons in a rectangle box

algorithm

(Amit Gupta) #1

I’ve to implement an algorithm/program in JS where I can fit many transparent images in a rectangle box in such a way that their non-transparent area should not overlap. An image can be rotated or resize to fit.

I don’t want to put the image in rectangular box because transparent area of two images can intersect.

I’ve found an algorithm which can help to prepare the polygon of non-transparent pixels from an image using canvas. And the other algorithm to find interaction of two polygons. (not tested)


(Jessica P) #2

As far as I understand, the images have opaque and transparent parts. The problem is to place maximum number of images in an rectangular area such that the opaque regions do not overlap.

Overlapping can be detected by checking the color of a particular pixel. If it contains a value, then it is occupied.

A greedy approach may work well in practice though a brute force solution will give accurate results. If images can be rotated without any fixed unit rotation and resize without any limit, the possibilities are endless :railway_track:

If we can resize images without limit, then all images can be accommodated. Are you considering any limit?

It looks like an interesting problem. Can you share with us the details of the two algorithms you have explored? :smiley_cat:


(Amit Gupta) #3

Thanks jessi . I’ve written a sample canvas example to detect intersection between visible parts of two images.

I’m basically trying to design a web app to generate spot it like card game with extra complexities. Check the sample here. It is still in under development.

It works fine for 3-4 symbols on the card. But as the number of symbols on the card grows, they start overlapping. Currently I have kept the limit on checking overlaps otherwise it’ll slow down the generation.


(Amit Gupta) #4

I’ve created voronoi diagrame to separate regions for any dynamic number. But now the challenge is to fit the image polygon into that. I believe such complex approach may slowdown the frontend. So now I’m gonna use some tricks. after all it should satisfy end result.


(Jessica P) #5

I see.

The approach using voronoi diagrams will work but can be an overhead if done on client side.
Keep us updated on the tricks :sparkles: you will be using to accomplish this task.


(Amit Gupta) #6

So as a dirty trick, I’ve provided multiple options to user to manually arrange the symbols on the deck. Check it for almost final application.