Delphi: Sierpinski triangle: the procedure does not work completely

Question

I do not understand why this code draws this:

Apparently, only the lower left triangles are drawn, however, the internal triangles appear only at the first depth of the upper and lower right triangles. I want the procedure to be recursive, but this is somehow the reason for my clever programming skills, not recursive ones. I really want to understand what I'm doing wrong.

implementation {$R *.dfm} var count : integer = 0; procedure DrawTriangle(aCanvas: TCanvas;x,y,size : extended;n : integer); var h : extended; w : extended; i : integer; x1,x2,x3,y1,y2,y3 : extended; begin w := size; h := size; x1 := x; y1 := y; //ShowMessage(FloatToStr(w)+' '+FloatToStr(h)); if aCanvas<>nil then try //1st - left aCanvas.MoveTo(Round(x1),Round(y1)); aCanvas.LineTo(Round(x1+w*2),Round(y1)); aCanvas.LineTo(Round(x1+w),Round(y1-h)); aCanvas.LineTo(Round(x1),Round(y1)); //2nd - right x2 := x1+w*2; y2 := y1; aCanvas.MoveTo(Round(x2),Round(y2)); aCanvas.LineTo(Round(x2+w*2),Round(y2)); aCanvas.LineTo(Round(x2+w),Round(y2-h)); aCanvas.LineTo(Round(x2),Round(y2)); //3rd - top x3 := x2-w; y3 := y2-h; aCanvas.MoveTo(Round(x3),Round(y3)); aCanvas.LineTo(Round(x3+w*2),Round(y3)); aCanvas.LineTo(Round(x3+w),Round(y3-h)); aCanvas.LineTo(Round(x3),Round(y3)); //Run itself inc(count); if count < n then begin DrawTriangle(aCanvas,x1,y1,size/2,n); DrawTriangle(aCanvas,x2,y2,size/2,n); DrawTriangle(aCanvas,x3,y3,size/2,n); end; except on e: exception do raise e; end; end; procedure TForm1.Button1Click(Sender: TObject); var size : extended; i : integer; x,y : extended; begin size := 100; x := 100; y := 400; DrawTriangle(Image1.Canvas,x,y,size,10); end; end. 

Answer 1

Your attempt to limit the recursion depth contains an error.

You draw each of the three inner triangles and increment count , then call DrawTriangle again to draw the triangles in those triangles. Each call increments the count again, which means that the counter does not reflect the depth of the recursion, but simply how many times DrawTriangle . As a result of setting the limit of 10, you will find that 10 sets of triangles were displayed in your results.

Instead of increasing count to track the recursion depth, you should decrease n for each call to n = 0 .

To make this intention clearer, you can use a nested procedure in which an external call takes the maximum number of recursion levels specified with an internal, nested procedure that performs the actual recursion, indicating the number of remaining levels and decreasing this number for the recursive calls itself:

 procedure DrawTriangle(aCanvas: TCanvas;x,y,size : extended; maxLevels: integer); procedure Draw(x,y,size: extended; levelsLeft: integer); var h : extended; w : extended; i : integer; x1,x2,x3,y1,y2,y3 : extended; begin w := size; h := size; x1 := x; y1 := y; //1st - left aCanvas.MoveTo(Round(x1),Round(y1)); aCanvas.LineTo(Round(x1+w*2),Round(y1)); aCanvas.LineTo(Round(x1+w),Round(y1-h)); aCanvas.LineTo(Round(x1),Round(y1)); //2nd - right x2 := x1+w*2; y2 := y1; aCanvas.MoveTo(Round(x2),Round(y2)); aCanvas.LineTo(Round(x2+w*2),Round(y2)); aCanvas.LineTo(Round(x2+w),Round(y2-h)); aCanvas.LineTo(Round(x2),Round(y2)); //3rd - top x3 := x2-w; y3 := y2-h; aCanvas.MoveTo(Round(x3),Round(y3)); aCanvas.LineTo(Round(x3+w*2),Round(y3)); aCanvas.LineTo(Round(x3+w),Round(y3-h)); aCanvas.LineTo(Round(x3),Round(y3)); //Run itself if (levelsLeft > 0) then begin Draw(x1, y1, size/2, levelsLeft - 1); Draw(x2, y2, size/2, levelsLeft - 1); Draw(x3, y3, size/2, levelsLeft - 1); end; end; begin if Assigned(aCanvas) then Draw(x, y, size, maxLevels); end; 

It also allows testing the preconditions more clearly, in which case it is currently limited to guaranteeing that the canvas has been specified, but may also include normalizing or checking other parameters that may be required before starting the recursive call.

Since the original parameters remain in the scope for the nested procedure, this also means that you can limit the parameters in the calls to the recursive procedure only to those that actually change with each call. (I updated the code in my answer to include this).

By the way, a try..except , which simply raises any caught exceptions, is exactly equivalent to the absence of a try..except block, so I removed it from this implementation.

You can also consider adding an additional condition to stop the recursion if the size value reaches certain lows (where the inner triangles are fuzzy, for example, size <2 ).

Answer 2

The problem is that you draw the first triangle, then call DrawTriangle to draw the lower left side, which does this, and then call DrawTriangle to draw a new lower left side, and so on, until count reaches n . Then we return one procedure at a time to the original procedure, and at each step we draw the remaining two triangles only once.

The following logic works as intended. (Delete the global variable count .)

 procedure DrawTriangle(aCanvas: TCanvas; x, y, size: extended; n: integer); var h: extended; w: extended; x1, x2, x3, y1, y2, y3: extended; begin w := size; h := size; x1 := x; y1 := y; //1st - left aCanvas.MoveTo(Round(x1), Round(y1)); aCanvas.LineTo(Round(x1+w*2), Round(y1)); aCanvas.LineTo(Round(x1+w), Round(y1-h)); aCanvas.LineTo(Round(x1), Round(y1)); //2nd - right x2 := x1+w*2; y2 := y1; aCanvas.MoveTo(Round(x2), Round(y2)); aCanvas.LineTo(Round(x2+w*2), Round(y2)); aCanvas.LineTo(Round(x2+w), Round(y2-h)); aCanvas.LineTo(Round(x2), Round(y2)); //3rd - top x3 := x2-w; y3 := y2-h; aCanvas.MoveTo(Round(x3), Round(y3)); aCanvas.LineTo(Round(x3+w*2), Round(y3)); aCanvas.LineTo(Round(x3+w), Round(y3-h)); aCanvas.LineTo(Round(x3), Round(y3)); //Run itself if n > 0 then begin DrawTriangle(aCanvas, x1, y1, size/2, n-1); DrawTriangle(aCanvas, x2, y2, size/2, n-1); DrawTriangle(aCanvas, x3, y3, size/2, n-1); end; end; 

I leave this as an exercise to understand why it works.

Also note that I deleted the completely unnecessary try..except block.

Finally, you can write code much more efficiently than Sir Rufo demonstrated.

Answer 3

As an addition to these answers, here is the DRY version:

 procedure DrawTriangleDRY( aCanvas: TCanvas; CenterX, CenterY, Width, Height: extended; n: integer ); begin aCanvas.MoveTo( Round( CenterX ), Round( CenterY - Height / 2 ) ); // top aCanvas.LineTo( Round( CenterX + Width / 2 ), Round( CenterY + Height / 2 ) ); // bottom right aCanvas.LineTo( Round( CenterX - Width / 2 ), Round( CenterY + Height / 2 ) ); // bottom left aCanvas.LineTo( Round( CenterX ), Round( CenterY - Height / 2 ) ); // top // draw childs if n > 0 then begin // top DrawTriangleDRY( aCanvas, CenterX, CenterY - Height / 4, Width / 2, Height / 2, n - 1 ); // left DrawTriangleDRY( aCanvas, CenterX - Width / 4, CenterY + Height / 4, Width / 2, Height / 2, n - 1 ); // right DrawTriangleDRY( aCanvas, CenterX + Width / 4, CenterY + Height / 4, Width / 2, Height / 2, n - 1 ); end; end; 

---

Update

I just realized that this can be optimized to only draw the last children

 procedure DrawTriangleDRY( aCanvas: TCanvas; CenterX, CenterY, Width, Height: extended; n: integer ); begin // draw childs if n > 0 then begin DrawTriangleDRY( aCanvas, CenterX, CenterY - Height / 4, Width / 2, Height / 2, n - 1 ); // top DrawTriangleDRY( aCanvas, CenterX - Width / 4, CenterY + Height / 4, Width / 2, Height / 2, n - 1 ); // left DrawTriangleDRY( aCanvas, CenterX + Width / 4, CenterY + Height / 4, Width / 2, Height / 2, n - 1 ); // right end else begin aCanvas.MoveTo( Round( CenterX ), Round( CenterY - Height / 2 ) ); // top aCanvas.LineTo( Round( CenterX + Width / 2 ), Round( CenterY + Height / 2 ) ); // bottom right aCanvas.LineTo( Round( CenterX - Width / 2 ), Round( CenterY + Height / 2 ) ); // bottom left aCanvas.LineTo( Round( CenterX ), Round( CenterY - Height / 2 ) ); // top end end;