Algorithm to fill rectangle with squares?

[ADSK2007]

Hello

 

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

 

 

Regards

[BIGAL]

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

Edited October 7, 2016 by BIGAL

[Roy_043]

The (gcd) function is available.

[Stefan BMR]

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)
 )

[ADSK2007]

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

Edited October 8, 2016 by ADSK2007

[ADSK2007]

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

Great respect

[ADSK2007]

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

 

 

Cheers

[David Bethel]

The (gcd) function is available.

 

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

 

-David

[Roy_043]

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).

[Commandobill]

No doubt you mean pallet (and not palette).

 

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

[ADSK2007]

No doubt you mean pallet (and not palette).

You are absolutely correct - Thanks to both of you, I learned 2 things today

[Lee Mac]

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

 

:lol:

[BIGAL]

Fixed the typo got the semi lined up ready to load.

[ADSK2007]

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

[David Bethel]

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

[Stefan BMR]

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.

[ADSK2007]

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

[Stefan BMR]

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))
     (< 0 (cadr 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)
)

[Lee Mac]

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)

[Stefan BMR]

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...