1
$\begingroup$

I need to place N rects on a 2-dimensional grid with constraints.

For the each rect height/width and placing limitations($x_{min}$-$x_{max}$) are known.

The problem is to place all rects on a grid with no intersections that every rect's bottom left $x$ is in rect's $x_{min}$-$x_{max}$.

I've implemented the naive solution where I just iterating over rects and incrementing $x$ by some fixed step while checking for intersections. If no place found then I increment $y$ and iterate again.

The question: I'm sure that there are algorithms/data structures that will help me to solve this task faster, but I do not know where to start.

$\endgroup$
1
$\begingroup$

I suggest you use a constraint solver, like Minion. The following paper shows that they are effective for a related problem:

My thanks to András Salamon for pointing to this information.

You could also try using a SAT solver.

$\endgroup$
  • $\begingroup$ Thanks a lot for your answer. Constraint solver really seems like the best option here $\endgroup$ – somebody32 Jun 7 '14 at 11:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.