# Algorithm to fill rectangle with squares?

## Recommended Posts

Hello

Euclid's algorithm: tiling a rectangle (any size) with squares - Can this be done with lisp routine?

Regards

##### Share on other sites

Is it for "Tiling a floor" or how many internet online shipping boxes I can get on a pallet ?

Edited by BIGAL

##### Share on other sites

The (gcd) function is available.

##### Share on other sites

The trivial solution is simple. It does not give the minimum number of squares.

```;Stefan M. 07.10.2016
;filling XY rectangle with squares
(defun c:squares ( / x y s p a q)
(if
(and
(setq x (getint "\nSpecify X size of the rectangle: "))
(setq y (getint "\nSpecify Y size of the rectangle: "))
(setq p (getpoint "\nSpecify insertion point: "))
(setq s 0 a (* x y))
)
(while (< s a)
(setq q (min x y)
s (+ s (* q q))
)
(command "_rectangle" "_non" p "_non" (mapcar '+ p (list q q)))
(if
(= q x)
(setq y (- y x) p (mapcar '+ p (list 0 q)))
(setq x (- x y) p (mapcar '+ p (list q 0)))
)
)
)
(princ)
)```

##### Share on other sites
Is it for "Tiling a floor" or how many internet online shipping boxes I can get on a pallet ?

Hi BIGAL - Did my floor 2 months ago - It's time to fit the boxes on a pallet

##### Share on other sites

Thank you Stefan - I will give it a try as soon as I am in the office

Great respect

##### Share on other sites

Thanks Roy, didn't know about that, I will look it up

Cheers

##### Share on other sites
The (gcd) function is available.

A gottcha with this is that it only deals with integers ( whole numbers).

-David

##### Share on other sites
Hi BIGAL - Did my floor 2 months ago - It's time to fit the boxes on a pallete
No doubt you mean pallet (and not palette).

##### Share on other sites
No doubt you mean pallet (and not palette).

Unless they meant tool palettes, and the boxes where metaphoric.

##### Share on other sites
No doubt you mean pallet (and not palette).
You are absolutely correct - Thanks to both of you, I learned 2 things today

##### Share on other sites
Unless they meant tool palettes, and the boxes where metaphoric.

:lol:

##### Share on other sites

Hello again

Ok, so I tried the code and it does well with integers - and I do understand why the code is asking me to type a real number instead of picking two points

Now my question: is it possible to pick points (instead of typing numbers for X and Y) then round up the number to nearest integer number? The reason for asking this is simple - I have many rectangle shapes to apply this code to

I need to find the highest common factor squares for each rectangle and picking points will make it much faster

A bonus operation to the code would be if it could create a grid (in a specific layer, ex. GRID) from the picking point the size of the final square

Regards

##### Share on other sites

I take it you changed getint to getreal. If so change getreal to getdist.

As to rounding up, a simple version could be :

```[b][color=BLACK]([/color][/b]defun rndup [b][color=FUCHSIA]([/color][/b]r / i[b][color=FUCHSIA])[/color][/b]
[b][color=FUCHSIA]([/color][/b]setq i [b][color=NAVY]([/color][/b]cond [b][color=MAROON]([/color][/b][b][color=GREEN]([/color][/b]= r [b][color=BLUE]([/color][/b]fix r[b][color=BLUE])[/color][/b][b][color=GREEN])[/color][/b] r[b][color=MAROON])[/color][/b]
[b][color=MAROON]([/color][/b]T           [b][color=GREEN]([/color][/b]1+ [b][color=BLUE]([/color][/b]fix r[b][color=BLUE])[/color][/b][b][color=GREEN])[/color][/b][b][color=MAROON])[/color][/b][b][color=NAVY])[/color][/b][b][color=FUCHSIA])[/color][/b]
i[b][color=BLACK])[/color][/b]
```

-David

##### Share on other sites

Here we go again...

So, you are not interested in Euclid's algorithm, but to create a grid. Well, good luck with that.

Anyway, my son has just learned this algorithm to school, so my effort was not in vain.

He was quite amazed to actually see the "miracle" behind Euclid's algorithm.

##### Share on other sites

Stefan

I think you misunderstood me - Perhaps I should have explained better, my apologies

I was going to use the concept (Euclid's algorithm) to get to smallest common factor square for each rectangle - What you did was exactly that

I just thought It is possible to create a grid using the final square

Anyway, Thank you very much for your help

Great respect

##### Share on other sites

Of course it is possible, but you don't have to use the algorithm to find the last square length.

Your goal is to draw a grid having the space between lines the great common divisor of rectangle Length and Width, for which (gcd X Y) is enough.

My point is, you asked for a partial solution for your problem, which is not even required for the final solution.

Here is the lisp for drawing the grid

```(defun c:test ( / roundup draw_grid p1 p2 i d)
(defun roundup (x) (if (> x (setq x (fix x))) (1+ x) x))
(defun draw_grid (p l a b)
(repeat (1- (fix (/ l i)))
(entmakex
(list
'(0 . "LINE")
'(8 . "Grid")
(cons 10 (trans (setq p (mapcar '+ p a)) 1 0))
(cons 11 (trans (mapcar '+ p b)) 1 0))
)
)
)
)
(if
(and
(setq p1 (getpoint "\nSpecify first corner: "))
(setq p2 (getcorner p1 "\nSpecify oposite corner: "))
(setq d (mapcar '(lambda (a b) (roundup (abs (- a b)))) p1 p2))
(< 0 (car  d))
(setq p1 (apply 'mapcar (cons 'min (list p1 p2))))
)
(progn
(setq i (gcd (car d) (cadr d)))
(draw_grid p1 (car d) (list i 0) (list 0 (cadr d)))
(draw_grid p1 (cadr d) (list 0 i) (list (car d) 0))
)
)
(princ)
)```

##### Share on other sites

Nice code Stefan

A couple of minor points:

Additional closing parenthesis on line 10:

`(mapcar '+ p b)[highlight])[/highlight]`

```(apply 'mapcar (cons 'min (list p1 p2)))
==
(apply 'mapcar (list 'min p1 p2))
==
(mapcar 'min p1 p2)```

##### Share on other sites
Nice code Stefan

A couple of minor points:

Additional closing parenthesis on line 10:

`(mapcar '+ p b)[highlight])[/highlight]`

```(apply 'mapcar (cons 'min (list p1 p2)))
==
(apply 'mapcar (list 'min p1 p2))
==
(mapcar 'min p1 p2)```

Ha ha ... Edited in place, for my excuse. I hope ADSK can get it right.

For the min, well...

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.