Jump to content
ADSK2007

Algorithm to fill rectangle with squares?

Recommended Posts

ADSK2007

Hello

 

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

 

 

Regards

Share this post


Link to post
Share on other sites
BIGAL

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

Edited by BIGAL

Share this post


Link to post
Share on other sites
Roy_043

The (gcd) function is available.

Share this post


Link to post
Share on other sites
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)
 )

Share this post


Link to post
Share on other sites
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 by ADSK2007

Share this post


Link to post
Share on other sites
ADSK2007

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

Great respect

Share this post


Link to post
Share on other sites
ADSK2007

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

 

 

Cheers

Share this post


Link to post
Share on other sites
David Bethel
The (gcd) function is available.

 

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

 

-David

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
Commandobill
No doubt you mean pallet (and not palette).

 

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

Share this post


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

Share this post


Link to post
Share on other sites
Lee Mac
Unless they meant tool palettes, and the boxes where metaphoric.

 

:lol::lol:

Share this post


Link to post
Share on other sites
BIGAL

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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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)
)

Share this post


Link to post
Share on other sites
Lee Mac

Nice code Stefan :thumbsup:

 

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 this post


Link to post
Share on other sites
Stefan BMR
Nice code Stefan :thumbsup:

 

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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×