Jump to content

Algorithm to fill rectangle with squares?


Recommended Posts

  • Replies 20
  • Created
  • Last Reply

Top Posters In This Topic

  • ADSK2007

    8

  • Stefan BMR

    4

  • BIGAL

    2

  • Roy_043

    2

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

Link to post
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 :)

Edited by ADSK2007
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

Link to post
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).
Link to post
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 :)
Link to post
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

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

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.

Link to post
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

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

Link to post
Share on other sites

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)

;)

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:

Link to post
Share on other sites

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.

Guest
Reply to this topic...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.


×
×
  • Create New...