Topic: [challenge] Sierpinski triangle

[gile]

Hi,

The goal is to draw a Sierpinski triangle.
The paramters should be the boundary triangle and a number of iterations (10 seems to be enough as upper limit with LISP).

Here's an example with two different command inputs.

[Lee Mac]

Here's an old take on the construction of the Sierpinski triangle from the perspective of Iterated Function Systems (IFS):



Effectively yielding an infinite number of iterations, constructed simultaneously.

[gile]

Awesome, Lee (as usual).
I didn't see it before.

[Lee Mac]

Awesome, Lee (as usual).
I didn't see it before.

Many thanks gile - though, it doesn't quite meet the exacting specifications of your challenge. 

Should the triangle be constructed from 3DFACE, TRACE, HATCH, or LWPOLYLINE entities?

[gile]

Should the triangle be constructed from 3DFACE, TRACE, HATCH, or LWPOLYLINE entities?

As you want, the entity type doesn't matter so much. In the shown example they are SOLID.

I posted in the LISP forum, but all languages are welcome.

[Lee Mac]

Here's my first draft:

Code - Auto/Visual Lisp: [Select]

1. (defun sierpinski ( p1 p2 p3 n / m1 m2 m3 )
2.     (if (< n 1)
3.         (entmake (list '(0 . "SOLID") (cons 10 p1) (cons 11 p2) (cons 12 p3) (cons 13 p3)))
4.         (progn
5.             (setq m1 (mid p1 p2)
6.                   m2 (mid p1 p3)
7.                   m3 (mid p2 p3)
8.             )
9.             (mapcar '(lambda ( a b c ) (sierpinski a b c (1- n)))
10.                 (list p1 m1 m2)
11.                 (list m1 p2 m3)
12.                 (list m2 m3 p3)
13.             )
14.         )
15.     )
16. )
17. (defun mid ( a b )
18.     (mapcar '(lambda ( a b ) (/ (+ a b) 2.0)) a b)
19. )

To test:

Code - Auto/Visual Lisp: [Select]

1. (defun c:test1 ( / p1 p2 p3 )
2.     (if (and (setq p1 (getpoint "\nSpecify 1st point of triangle: "))
3.              (setq p2 (getpoint "\nSpecify 2nd point of triangle: " p1))
4.              (setq p3 (getpoint "\nSpecify 3rd point of triangle: " p1))
5.         )
6.         (sierpinski
7.             (trans p1 1 0)
8.             (trans p2 1 0)
9.             (trans p3 1 0)
10.             (progn (initget 6) (cond ((getint "\nSpecify number of iterations <5>: ")) (5)))
11.         )
12.     )
13.     (princ)
14. )

Code - Auto/Visual Lisp: [Select]

1. (defun c:test2 ( / cen rad )
2.     (if (and (setq cen (getpoint "\nSpecify center: "))
3.              (setq rad (getdist  "\nSpecify radius: " cen))
4.         )
5.         (sierpinski
6.             (trans (polar cen (/ (* 3.0  pi) 6.0) rad) 1 0)
7.             (trans (polar cen (/ (* 7.0  pi) 6.0) rad) 1 0)
8.             (trans (polar cen (/ (* 11.0 pi) 6.0) rad) 1 0)
9.             (progn (initget 6) (cond ((getint "\nSpecify number of iterations <5>: ")) (5)))
10.         )
11.     )
12.     (princ)
13. )

[Patriiick]

Now I know what you, guys, are doing while I drink champagne for the new year! 

Happy new year!

[Lee Mac]

Now I know what you, guys, are doing while I drink champagne for the new year! 

Happy new year!

Happy New Year! 


Here's another, to show the progression:

Code - Auto/Visual Lisp: [Select]

1. (defun c:test ( / itr lst pt1 pt2 pt3 tmp )
2.     (if (and (setq pt1 (getpoint "\nSpecify 1st point of triangle: "))
3.              (setq pt2 (getpoint "\nSpecify 2nd point of triangle: " pt1))
4.              (setq pt3 (getpoint "\nSpecify 3rd point of triangle: " pt1))
5.         )
6.         (progn
7.             (foreach sym '(pt1 pt2 pt3) (set sym (trans (eval sym) 1 0)))
8.             (setq tmp (getvar 'millisecs)
9.                   lst (sierpinski pt1 pt2 pt3 1)
10.                   tmp (- (getvar 'millisecs) tmp)
11.                   itr 2
12.             )
13.             (while
14.                 (progn (initget "Yes No")
15.                     (/= "No"
16.                         (getkword
17.                             (strcat
18.                                 "\nThe next iteration will generate "
19.                                 (rtos (expt 3.0 itr) 2 0)
20.                                 " objects in approx. "
21.                                 (rtos (* tmp 0.006) 2 3)
22.                                 " seconds.\nProceed? [Yes/No] <Yes>: "
23.                             )
24.                         )
25.                     )
26.                 )
27.                 (setq tmp (getvar 'millisecs))
28.                 (foreach ent lst (entdel ent))
29.                 (setq lst (sierpinski pt1 pt2 pt3 itr)
30.                       tmp (- (getvar 'millisecs) tmp)
31.                       itr (1+ itr)
32.                 )
33.             )
34.         )
35.     )
36.     (princ)
37. )
38. (defun sierpinski ( p1 p2 p3 n / m1 m2 m3 )
39.     (if (< n 1)
40.         (list (entmakex (list '(0 . "SOLID") (cons 10 p1) (cons 11 p2) (cons 12 p3) (cons 13 p3))))
41.         (progn
42.             (setq m1 (mid p1 p2)
43.                   m2 (mid p1 p3)
44.                   m3 (mid p2 p3)
45.             )
46.             (apply 'append
47.                 (mapcar '(lambda ( a b c ) (sierpinski a b c (1- n)))
48.                     (list p1 m1 m2)
49.                     (list m1 p2 m3)
50.                     (list m2 m3 p3)
51.                 )
52.             )
53.         )
54.     )
55. )
56. (defun mid ( a b )
57.     (mapcar '(lambda ( a b ) (/ (+ a b) 2.0)) a b)
58. )

[gile]

Nice Lee.

My first attempt was written in F#, using a functional style.
It's quite close to the first one posted by Lee except it uses mutual recursion instead of recursive calls within a mapcar expression. I'd post the LISP equivalent if no one do it before.

Code - F#: [Select]

1. module SierpinskiChallenge
2.  
3. open Autodesk.AutoCAD.DatabaseServices
4. open Autodesk.AutoCAD.EditorInput
5. open Autodesk.AutoCAD.Geometry
6. open Autodesk.AutoCAD.Runtime
7.  
8. type AcAp = Autodesk.AutoCAD.ApplicationServices.Application
9.  
10. let drawSierpinski nbi p1 p2 p3 =
11.     let db = AcAp.DocumentManager.MdiActiveDocument.Database
12.     use tr = db.TransactionManager.StartTransaction()
13.     let cSpace = tr.GetObject(db.CurrentSpaceId, OpenMode.ForWrite) :?> BlockTableRecord
14.    
15.     let draw p1 p2 p3 =
16.         let s = new Solid(p1, p2, p3)
17.         cSpace.AppendEntity(s) |> ignore
18.         tr.AddNewlyCreatedDBObject(s, true)
19.    
20.     let mid (p1 : Point3d) p2 = p1 + (p2 - p1) / 2.0
21.    
22.     let rec loop i p1 p2 p3 =
23.         if i > 0 then fract (i - 1) p1 p2 p3
24.         else draw p1 p2 p3
25.    
26.     and fract i p1 p2 p3 =
27.         let m1, m2, m3 = mid p1 p2, mid p2 p3, mid p3 p1
28.         loop i p1 m1 m3
29.         loop i m1 p2 m2
30.         loop i m3 m2 p3
31.    
32.     loop nbi p1 p2 p3
33.     tr.Commit()
34.  
35. [<CommandMethod("CMD1")>]
36. let cmd1() =
37.     let ed = AcAp.DocumentManager.MdiActiveDocument.Editor
38.     let ppr = ed.GetPoint("\nCenter: ")
39.     if ppr.Status = PromptStatus.OK then
40.         let cen = ppr.Value
41.         let pdo = PromptDistanceOptions("\nRadius: ", BasePoint = cen, UseBasePoint = true)
42.         let pdr = ed.GetDistance(pdo)
43.         if pdr.Status = PromptStatus.OK then
44.             let pio =
45.                 PromptIntegerOptions("\nNumber of iterations: ", LowerLimit = 1, UpperLimit = 12, DefaultValue = 8)
46.             let pir = ed.GetInteger(pio)
47.             if pir.Status = PromptStatus.OK then
48.                 let rad = pdr.Value
49.                 let cen = cen.TransformBy(ed.CurrentUserCoordinateSystem)
50.                 let p1 = cen + Vector3d(rad * -sqrt 0.75, rad * -0.5, 0.0)
51.                 let p2 = cen + Vector3d(rad * sqrt 0.75, rad * -0.5, 0.0)
52.                 let p3 = cen + Vector3d(0.0, rad, 0.0)
53.                 drawSierpinski pir.Value p1 p2 p3
54.  
55. [<CommandMethod("CMD2")>]
56. let cmd2() =
57.     let ed = AcAp.DocumentManager.MdiActiveDocument.Editor
58.     let ppo = PromptPointOptions("\nFirst point: ")
59.     let ppr = ed.GetPoint(ppo)
60.     if ppr.Status = PromptStatus.OK then
61.         let p1 = ppr.Value
62.         ppo.UseBasePoint <- true
63.         ppo.BasePoint <- p1
64.         ppo.Message <- "\nSecond point: "
65.         let ppr = ed.GetPoint(ppo)
66.         if ppr.Status = PromptStatus.OK then
67.             let p2 = ppr.Value
68.             ppo.Message <- "\nThird point: "
69.             let ppr = ed.GetPoint(ppo)
70.             if ppr.Status = PromptStatus.OK then
71.                 let p3 = ppr.Value
72.                 let pio =
73.                     PromptIntegerOptions("\nNumber of iterations: ", LowerLimit = 1, UpperLimit = 12, DefaultValue = 8)
74.                 let pir = ed.GetInteger(pio)
75.                 if pir.Status = PromptStatus.OK then
76.                     let ucs = ed.CurrentUserCoordinateSystem
77.                     drawSierpinski pir.Value (p1.TransformBy(ucs)) (p2.TransformBy(ucs)) (p3.TransformBy(ucs))

[gile]

As the number of iterations is known, the computation can be done iteratively.
I'd post a LISP iterative version if no one do it before (with LISP, it should run faster than the recursive one).

Here's a C# implementation using an OOP and imperative (procedural) syle.
The Triangle and SierpinskiTriangle classes provide properties and methods to draw the result.

Code - C#: [Select]

1. using Autodesk.AutoCAD.DatabaseServices;
2. using Autodesk.AutoCAD.EditorInput;
3. using Autodesk.AutoCAD.Geometry;
4. using Autodesk.AutoCAD.Runtime;
5. using System.Collections.Generic;
6. using static System.Math;
7. using AcAp = Autodesk.AutoCAD.ApplicationServices.Application;
8.  
9. namespace SierpinskiTriangleChallenge
10. {
11.     class Triangle
12.     {
13.         Point3d p1, p2, p3;
14.  
15.         public Triangle(Point3d p1, Point3d p2, Point3d p3)
16.         {
17.             this.p1 = p1;
18.             this.p2 = p2;
19.             this.p3 = p3;
20.         }
21.  
22.         public Triangle(Point3d center, double radius)
23.             : this(center + new Vector3d(0.0, radius, 0.0),
24.                    center + new Vector3d(radius * -Sqrt(0.75), radius * -0.5, 0.0),
25.                    center + new Vector3d(radius * Sqrt(0.75), radius * -0.5, 0.0))
26.         { }
27.  
28.         public Point3d P1 => p1;
29.         public Vector3d V1 => p1.GetVectorTo(p2);
30.         public Vector3d V2 => p1.GetVectorTo(p3);
31.  
32.         public IEnumerable<Triangle> Copy(double d)
33.         {
34.             yield return new Triangle(p1 + V1 * d, p2 + V1 * d, p3 + V1 * d);
35.             yield return new Triangle(p1 + V2 * d, p2 + V2 * d, p3 + V2 * d);
36.         }
37.  
38.         public void Draw(BlockTableRecord btr, Transaction tr)
39.         {
40.             var solid = new Solid(p1, p2, p3);
41.             btr.AppendEntity(solid);
42.             tr.AddNewlyCreatedDBObject(solid, true);
43.         }
44.     }
45.  
46.     class SierpinskiTriangle
47.     {
48.         List<Triangle> triangles;
49.  
50.         public SierpinskiTriangle(int numIterations, Triangle boundary)
51.         {
52.             var num = Pow(2.0, numIterations);
53.             var first = new Triangle(
54.                 boundary.P1,
55.                 boundary.P1 + boundary.V1 / num,
56.                 boundary.P1 + boundary.V2 / num);
57.             triangles = new List<Triangle>();
58.             triangles.Add(first);
59.             for (int i = 0; i < numIterations; i++)
60.             {
61.                 var tmp = new List<Triangle>();
62.                 foreach (var triangle in triangles)
63.                     tmp.AddRange(triangle.Copy(Pow(2.0, i)));
64.                 triangles.AddRange(tmp);
65.             }
66.         }
67.  
68.         public void Draw()
69.         {
70.             var db = HostApplicationServices.WorkingDatabase;
71.             using (var tr = db.TransactionManager.StartTransaction())
72.             {
73.                 var curSpace = (BlockTableRecord)tr.GetObject(db.CurrentSpaceId, OpenMode.ForWrite);
74.                 foreach (var triangle in triangles)
75.                     triangle.Draw(curSpace, tr);
76.                 tr.Commit();
77.             }
78.         }
79.     }
80.  
81.     public class Commands
82.     {
83.         [CommandMethod("TEST1")]
84.         public void Test1()
85.         {
86.             var ed = AcAp.DocumentManager.MdiActiveDocument.Editor;
87.             var ppr = ed.GetPoint("\nCenter: ");
88.             if (ppr.Status != PromptStatus.OK)
89.                 return;
90.             var center = ppr.Value;
91.             var pdo = new PromptDistanceOptions("\nRadius: ")
92.             { UseBasePoint = true, BasePoint = center };
93.             var pdr = ed.GetDistance(pdo);
94.             if (pdr.Status != PromptStatus.OK)
95.                 return;
96.             var pio = new PromptIntegerOptions("\nNumber of iterations: ")
97.             { LowerLimit = 1, UpperLimit = 12, DefaultValue = 8 };
98.             var pir = ed.GetInteger(pio);
99.             if (pir.Status != PromptStatus.OK)
100.                 return;
101.             var ucs = ed.CurrentUserCoordinateSystem;
102.             var boundary = new Triangle(center.TransformBy(ucs), pdr.Value);
103.             var sierpinski = new SierpinskiTriangle(pir.Value, boundary);
104.             sierpinski.Draw();
105.         }
106.  
107.         [CommandMethod("TEST2")]
108.         public void Test22()
109.         {
110.             var ed = AcAp.DocumentManager.MdiActiveDocument.Editor;
111.             var ppo = new PromptPointOptions("\nFirst point: ");
112.             var ppr = ed.GetPoint(ppo);
113.             if (ppr.Status != PromptStatus.OK)
114.                 return;
115.             Point3d p1 = ppr.Value;
116.             ppo.Message = ("\nSecond point: ");
117.             ppo.BasePoint = p1;
118.             ppo.UseBasePoint = true;
119.             ppr = ed.GetPoint(ppo);
120.             if (ppr.Status != PromptStatus.OK)
121.                 return;
122.             Point3d p2 = ppr.Value;
123.             ppo.Message = ("\nThird point: ");
124.             ppr = ed.GetPoint(ppo);
125.             if (ppr.Status != PromptStatus.OK)
126.                 return;
127.             Point3d p3 = ppr.Value;
128.             var pio = new PromptIntegerOptions("\nNumber of iterations: ")
129.             { LowerLimit = 1, UpperLimit = 12, DefaultValue = 8 };
130.             var pir = ed.GetInteger(pio);
131.             if (pir.Status != PromptStatus.OK)
132.                 return;
133.             var ucs = ed.CurrentUserCoordinateSystem;
134.             var boundary = new Triangle(p1.TransformBy(ucs), p2.TransformBy(ucs), p3.TransformBy(ucs));
135.             var sierpinski = new SierpinskiTriangle(pir.Value, boundary);
136.             sierpinski.Draw();
137.         }
138.     }
139. }
140.  

[Lee Mac]

Nice one gile 

Here is a 3D version, though the code is becoming cumbersome:

Code - Auto/Visual Lisp: [Select]

1. (defun c:test ( / itr lst pt1 pt2 pt3 pt4 tmp )
2.     (setq pt1'( 0.0 0.0 1.5)
3.           pt2'( 0.0 1.0 0.0)
4.           pt3'( 0.866025 -0.5 0.0)
5.           pt4'(-0.866025 -0.5 0.0)
6.           tmp (getvar 'millisecs)
7.           lst (sierpinski-3D pt1 pt2 pt3 pt4 1)
8.           tmp (- (getvar 'millisecs) tmp)
9.           itr 2
10.     )
11.     (command "_.zoom" "_e")
12.     (while
13.         (progn (initget "Yes No")
14.             (/= "No"
15.                 (getkword
16.                     (strcat
17.                         "\nThe next iteration will generate "
18.                         (rtos (expt 4.0 (1+ itr)) 2 0)
19.                         " objects in approx. "
20.                         (rtos (* tmp 0.006) 2 3)
21.                         " seconds.\nProceed? [Yes/No] <Yes>: "
22.                     )
23.                 )
24.             )
25.         )
26.         (setq tmp (getvar 'millisecs))
27.         (foreach ent lst (entdel ent))
28.         (setq lst (sierpinski-3D pt1 pt2 pt3 pt4 itr)
29.               tmp (- (getvar 'millisecs) tmp)
30.               itr (1+ itr)
31.         )
32.     )
33.     (princ)
34. )
35. (defun sierpinski-3D ( p1 p2 p3 p4 n / m1 m2 m3 m4 m5 m6 )
36.     (if (< n 1)
37.         (progn
38.             (mapcar
39.                '(lambda ( a b c )
40.                     (entmakex
41.                         (cons '(0 . "3DFACE")
42.                             (mapcar 'cons '(10 11 12 13) (list a b c c))
43.                         )
44.                     )
45.                 )
46.                 (list p1 p1 p1 p2)
47.                 (list p2 p3 p2 p3)
48.                 (list p3 p4 p4 p4)
49.             )
50.         )
51.         (progn
52.             (setq m1 (mid p1 p2)
53.                   m2 (mid p1 p3)
54.                   m3 (mid p1 p4)
55.                   m4 (mid p2 p3)
56.                   m5 (mid p2 p4)
57.                   m6 (mid p3 p4)
58.             )
59.             (apply 'append
60.                 (mapcar '(lambda ( a b c d ) (sierpinski-3D a b c d (1- n)))
61.                     (list p1 m1 m2 m3)
62.                     (list m1 p2 m4 m5)
63.                     (list m2 m4 p3 m6)
64.                     (list m3 m5 m6 p4)
65.                 )
66.             )
67.         )
68.     )
69. )
70. (defun mid ( a b )
71.     (mapcar '(lambda ( a b ) (/ (+ a b) 2.0)) a b)
72. )

[gile]

Not so "cumbersome".
Very nice.

[Lee Mac]

Thank you gile 

[Stefan]

Hi all and a Happy New Year!

Code - Auto/Visual Lisp: [Select]

1. (defun c:test ( / f s p1 p2 p3 n a12 a13 d12 d13 i doit)
2.  
3.   (defun f (i / d)
4.     (setq d (expt 2 i))
5.     (list p1 (polar p1 a12 (* d12 d)) (polar p1 a13 (* d13 d)))
6.     )
7.  
8.   (defun s ( / p)
9.     (setq p (f 0))
10.     (entmake (cons '(0 . "SOLID") (mapcar 'cons '(10 11 12 13) (cons (car p) p))))
11.     )
12.  
13.   (if
14.     (and
15.       (setq p1 (getpoint "\nFirst point: "))
16.       (setq p2 (getpoint p1 "\nSecond point: "))
17.       (setq p3 (getpoint p1 "\nThird point: "))
18.       (progn
19.         (initget 7)
20.         (setq n (getint "\nIterations: "))
21.         )
22.       (setq p1 (trans p1 1 0)
23.             p2 (trans p2 1 0)
24.             p3 (trans p3 1 0)
25.             a12 (angle p1 p2)
26.             a13 (angle p1 p3)
27.             d12 (/ (distance p1 p2) (expt 2 n))
28.             d13 (/ (distance p1 p3) (expt 2 n))
29.             i -1
30.             doit '(s)
31.             )
32.       )
33.     (eval
34.       (repeat n
35.         (setq doit (list 'foreach 'p1 (list 'f (setq i (1+ i))) doit))
36.       )
37.     )
38.   )
39.   (princ)
40. )

[gile]

Hi Stefan, nice one !

This is the iterative way I was thinking of. It should run about 2 times faster than the recursive way.

Here's what I wrote in LISP.

The functional way (mutual recursion closed to the first reply of Lee)

Code - Auto/Visual Lisp: [Select]

1. (defun SierpinskiRecursive (p1 p2 p3 nbi / mid fract loop)
2.  
3.   (defun mid (p1 p2)
4.     (mapcar '(lambda (x1 x2) (/ (+ x1 x2) 2.)) p1 p2)
5.   )
6.  
7.   (defun fract (n p1 p2 p3)
8.     (loop n (mid p1 p2) p2 (mid p2 p3))
9.     (loop n (mid p3 p1) (mid p2 p3) p3)
10.     (loop n p1 (mid p1 p2) (mid p3 p1))
11.   )
12.  
13.   (defun loop (n p1 p2 p3)
14.     (if (< 0 n)
15.       (fract (1- n) p1 p2 p3)
16.       (drawTriangle p1 p2 p3)
17.     )
18.   )
19.  
20.   (loop nbi p1 p2 p3)
21. )

the imperative way (iterative, very closed to Stefan's reply)

Code - Auto/Visual Lisp: [Select]

1. (defun SierpinskiIterative (p1 p2 p3 nbi / a1 a2 d1 d2 lst)
2.   (setq a1  (angle p1 p2)
3.         a2  (angle p1 p3)
4.         d1  (/ (distance p1 p2) (expt 2 nbi))
5.         d2  (/ (distance p2 p3) (expt 2 nbi))
6.         lst (list (list p1 (polar p1 a1 d1) (polar p1 a2 d2)))
7.   )
8.   (repeat nbi
9.     (foreach l lst
10.       (setq lst (vl-list*
11.                   (mapcar '(lambda (p) (polar p a1 d1)) l)
12.                   (mapcar '(lambda (p) (polar p a2 d2)) l)
13.                   lst
14.                 )
15.       )
16.     )
17.     (setq d1  (* 2 d1)
18.           d2  (* 2 d2)
19.     )
20.   )
21.   (foreach l lst (drawTriangle (car l) (cadr l) (caddr l)))
22. )

Helpers and testing command functions

Code - Auto/Visual Lisp: [Select]

1. (defun drawTriangle (p1 p2 p3)
2.   (entmake
3.     (list
4.       '(0 . "SOLID")
5.       (cons 10 p1)
6.       (cons 11 p2)
7.       (cons 12 p3)
8.       (cons 13 p3)
9.     )
10.   )
11. )
12.  
13. (defun centerRadius (drawSierpinski / cen rad nbi ms)
14.   (and
15.     (setq cen (getpoint "\nCenter: "))
16.     (setq rad (getdist cen "\nRadius: "))
17.     (setq nbi (getint "\nNumber of iterations: "))
18.     (setq ms (getvar 'millisecs))
19.     (setq cen (trans cen 1 0))
20.     (apply
21.       drawSierpinski
22.       (list
23.         (polar cen (/ pi 2) rad)
24.         (polar cen (/ (* 7 pi) 6) rad)
25.         (polar cen (/ (* 11 pi) 6) rad)
26.         nbi
27.       )
28.     )
29.     (setq ms (- (getvar 'millisecs) ms))
30.     (princ (strcat "\nElapsed milliseconds: " (itoa ms)))
31.   )
32.   (princ)
33. )
34.  
35. (defun threePoints (drawSierpinski / p1 p2 p3 nbi ms)
36.   (and
37.     (setq p1 (getpoint "\nFirst point: "))
38.     (setq p2 (getpoint p1 "\nSecond point:  "))
39.     (setq p3 (getpoint p1 "\nThird point:  "))
40.     (setq nbi (getint "\nNumber of iterations: "))
41.     (setq ms (getvar 'millisecs))
42.     (apply
43.       drawSierpinski
44.       (list
45.         (trans p1 1 0)
46.         (trans p2 1 0)
47.         (trans p3 1 0)
48.         nbi
49.       )
50.     )
51.     (setq ms (- (getvar 'millisecs) ms))
52.     (princ (strcat "\nElapsed milliseconds: " (itoa ms)))
53.   )
54.   (princ)
55. )
56.  
57. (defun c:ITER1 () (centerRadius 'SierpinskiIterative))
58.  
59. (defun c:REC1 () (centerRadius 'SierpinskiRecursive))
60.  
61. (defun c:ITER2 () (threePoints 'SierpinskiIterative))
62.  
63. (defun c:REC2 () (threePoints 'SierpinskiRecursive))

[Lee Mac]

Both interesting methods!

Here is a direct translation of my above recursive solution into an iterative solution:

Code - Auto/Visual Lisp: [Select]

1. (defun sierpinski ( p1 p2 p3 n / lst m1 m2 m3 )
2.     (setq lst (list (list p1 p2 p3)))
3.     (repeat n
4.         (foreach x lst
5.             (setq m1  (mid (car  x) (cadr  x))
6.                   m2  (mid (car  x) (caddr x))
7.                   m3  (mid (cadr x) (caddr x))
8.                   lst (append (cdr lst)
9.                           (list (list (car x)  m1 m2)
10.                                 (list m1 (cadr x) m3)
11.                                 (list m2 m3 (caddr x))
12.                           )
13.                       )
14.             )
15.         )
16.     )
17.     (foreach x lst
18.         (entmake (cons '(0 . "SOLID") (mapcar 'cons '(13 10 11 12) (cons (last x) x))))
19.     )
20. )
21. (defun mid ( a b )
22.     (mapcar '(lambda ( a b ) (/ (+ a b) 2.0)) a b)
23. )

Test program as before:

Code - Auto/Visual Lisp: [Select]

1. (defun c:test1 ( / p1 p2 p3 )
2.     (if (and (setq p1 (getpoint "\nSpecify 1st point of triangle: "))
3.              (setq p2 (getpoint "\nSpecify 2nd point of triangle: " p1))
4.              (setq p3 (getpoint "\nSpecify 3rd point of triangle: " p1))
5.         )
6.         (sierpinski
7.             (trans p1 1 0)
8.             (trans p2 1 0)
9.             (trans p3 1 0)
10.             (progn (initget 6) (cond ((getint "\nSpecify number of iterations <5>: ")) (5)))
11.         )
12.     )
13.     (princ)
14. )

Fun challenge gile! 

[roy_043]

For variety: VBA (I very rarely use it...). Simple recursive solution.

Code: [Select]

Sub Sierpinski_Triangle()
    Dim pt1 As Variant
    Dim pt2 As Variant
    Dim pt3 As Variant
    Dim num As Integer
    pt1 = ThisDrawing.Utility.GetPoint(, "Point 1: ")
    pt2 = ThisDrawing.Utility.GetPoint(pt1, "Point 2: ")
    pt3 = ThisDrawing.Utility.GetPoint(pt1, "Point 3: ")
    num = ThisDrawing.Utility.GetInteger("Number of iterations: ")
    DrawSierpinski pt1, pt2, pt3, num
End Sub

Function DrawSierpinski(pt1 As Variant, pt2 As Variant, pt3 As Variant, num As Integer)
    If num = 0 Then
        DrawTriangle pt1, pt2, pt3
    Else
        DrawSierpinski pt1, MidPoint(pt1, pt2), MidPoint(pt1, pt3), num - 1
        DrawSierpinski pt2, MidPoint(pt1, pt2), MidPoint(pt2, pt3), num - 1
        DrawSierpinski pt3, MidPoint(pt1, pt3), MidPoint(pt2, pt3), num - 1
    End If
End Function

Function DrawTriangle(pt1 As Variant, pt2 As Variant, pt3 As Variant) As AcadSolid
    Set DrawTriangle = ThisDrawing.ModelSpace.AddSolid(pt1, pt2, pt3, pt3)
End Function

Function MidPoint(pt1 As Variant, pt2 As Variant) As Variant
    Dim pt(0 To 2) As Double
    pt(0) = (pt1(0) + pt2(0)) / 2
    pt(1) = (pt1(1) + pt2(1)) / 2
    pt(2) = (pt1(2) + pt2(2)) / 2
    MidPoint = pt()
End Function

[Lee Mac]

This challenge inspired me to publish a dedicated program on my site, with an accompanying write-up: Sierpinski Triangle.

Thank you gile for posting an interesting topic for us to explore