Making a Sierpinski Triangle
The Sierpinski Triangle (also called the Sierpinski gasket or the
Sierpinski Sieve) is a very simple fractal to make and it can be made
in different ways. I am going to show some source code to make them
using logical AND, logical XOR, an iterative method and one method using Pascal's triangle. The source code
is shown in Java and for the Casio calculators. Note that the Casio
programs are slow.
Logical AND method
You can create a right-angled triangle by doing a logical AND of the
coordinates of x and y of the screen.
Here is an extract in Java to draw it (it can be converted to C++):
void myDrawingMethod(Graphics g)
{
int x,y;
Rectangle r = getBounds();
for(y=0;y<r.height;y++)
{
for(x=0;x<r.width;x++)
{
if((x&y)==0)g.drawLine(x,y,x,y); /* x&y means do a
logical AND of x and y
//the g.drawLine is used to plot a pixel
(I do not have a plotpixel command) */
}
}
}
This produces:
I programmed a version in to my Casio CFX-9850G PLUS calculator:
AxesOff
Cls
For 0→T To 62
For 0→S To 125
S→A
T→B
Prog "BITAND"
C=0⇒PxlOn T+1,S+1
Next
Next
AxesOn
Remember the PxlOn command takes Row,Column rather than x,y
and the upper-left corner is (1,1)
The
above requires a program called BITAND which needs to be put in a BASE
format or it will not work (I press F2 when I created the file)
AandB→C
Logical XOR method
The image at the top of the page was
produced with the logical XOR method (exclusive-or). You plot a pixel
on the top of the screen then scan across underneath line by line,
plotting a pixel if the upper-left and upper-right pixel produces a 1
when a XOR operation is performed.
Plot at X when xor(A,B) produces a 1
Unfortunately in Java, I couldn't get the colour of the screen pixel so
I had to use an array of bytes:
public void paintComponent(Graphics
g)
{
int x,y,FrameWidth,FrameHeight;
FrameWidth=getWidth();
FrameHeight=getHeight();
byte CurrentLine[]=new byte[FrameWidth];
byte NextLine[]=new byte[FrameWidth];
CurrentLine[FrameWidth/2]=1;//set the initial pixel in the middle of
the screen
g.drawLine(FrameWidth/2, 0, FrameWidth/2, 0);//plot it on screen
for(y=1;y<FrameHeight;y++)//start at y=1 (one line lower)
{
for(x=1;x<FrameWidth-2;x++)
{
/*start
one pixel in because the array is looking at x-1 and x+1*/
if(((CurrentLine[x-1])^(CurrentLine[x+1]))>0)
{
/*A^B means perform an ExclusiveOr on A and B*/ NextLine[x]=1;
g.drawLine(x,y,x,y);
}
else NextLine[x]=0; }
System.arraycopy(NextLine, 0, CurrentLine, 0,FrameWidth); //make the
next line the current one
}
}
On my calculator:
AxesOff
Cls
64→G~H
PxlOn 1,G
For 2→T To 63
G-1→G
H+1→H
For G→S To H
PxlTest T-1,S-1
Ans→A
PxlTest T-1,S+1
Ans→B
Prog "BITXOR"
C⇒PxlOn T,S
Next
Next
AxesOn
Again this needs another file in the BASE format called BITXOR:
AxorB→C
Iterative Function method (also called the chaos game)
There
is a simple way of producing it by iterating multiple times. Given any
three points of a triangle in complex number format, you choose one of
them, choose another and halve the distance between them. Plot a point
and then choose another point at random, repeating the process.
Here is a bit of pseudo-code to illustrate what I mean:
Set points P1, P2, P3 to the coordinates of your triangle in complex
number format e.g. P1 = 30 + 20i
CurrentPoint = P1 (or any point)
StartOfLoop
{
R = a random point chosen from P1, P2, P3
CurrentPoint = (R + CurrentPoint) / 2
PlotPixel (CurrentPoint)
}Loop until a key is pressed
The
code can be simplified for speed purposes. My Java code halves by doing
a bit shift right (which is FAR quicker than a division by two) and the
points are halved at the start. It also does not use complex numbers.
Here is the ENTIRE applet for a web page:
SierpinskiIT.class
import java.awt.Graphics;
public class SierpinskiIT extends java.applet.Applet
{
public void init(){}
public void paint(Graphics g){myDrawingMethod(g);}
void myDrawingMethod(Graphics g)
{
int x,y,iterations,decision;
x=0;y=0;//start at 0,0 in this case
/* The other points are at (400,600) and (800,0) which are already
halved for speed */
for(iterations=0;iterations<100000;iterations++)
{
decision=(int)(Math.random()*3.0);//this makes "decision" equal to 0, 1 or 2
x=x>>1;y=y>>1; // halve the
point
if(decision==1){x+=200;y+=300;}//(200,300) is half of (400,600)
if(decision==2){x+=400;}//(400,0) is half of (800,0)
g.drawLine(x,599-y,x,599-y);
/*plot a pixel and invert the image (otherwise it displays upside-down)
by 599-y which flips the y coordinate */
}
}//myDrawingMethod()
}
This produces (after 100000 iterations):
Here's the source code for the calculator (using complex numbers):
ClrGraph
0→P
For 1→K To 3000
Int (3Ran#)→N
.5×P→P
N=1⇒P+31+31i→P
N=2⇒P+62→P
PxlOn 63-Int ImP P, 1+Int ReP P
Next
Text 1,1,"FINISHED"
Pascal's triangle
Pascal's triangle is a triangle
formed by adding the numbers up on the upper left and the upper right
of the number you are examining. I have programmed one way of doing it.
It is not efficient but it is written in a way that you can see how it
is done (I could have incorporated two loops in one, the for (x= ...)
I
colour only the odd numbers black. I have also not put the triangle in
the middle but squashed it to one side. You can modify the code if you
wish but it will just look like the XOR method above.
Another
modification is to use the combination equation to generate it (from
the Binomial Theorem) but I did not use that because the factorial
numbers would be very large.
class PascalSierpinskiPanel extends JPanel
{
public void paintComponent(Graphics g)
{
int x,y,FrameWidth,FrameHeight;
FrameWidth=getWidth();
FrameHeight=getHeight();
int CurrentLine[]=new int[FrameWidth];
int NextLine[]=new int[FrameWidth];
CurrentLine[0]=1;//The top of the triangle is a 1
g.drawLine(0, 0, 0, 0);//draw it
for(y=1;y<FrameHeight;y++)
{
NextLine[0]=CurrentLine[0];
/*This really is CurrentLine[0] + CurrentLine[-1] which would give an
error. The number at CurrentLine[-1] should be a 0
*/
for(x=1;x<FrameWidth;x++)
{
NextLine[x]=CurrentLine[x-1]+CurrentLine[x];//add the numbers above
}
for(x=0;x<FrameWidth;x++)
{
if((CurrentLine[x]&1)==1)//if the number is odd
{
g.drawLine(x,y,x,y);
}
}
System.arraycopy(NextLine, 0, CurrentLine, 0, FrameWidth);
}
}//paintComponent
}//PascalSierpinskiPanel
Note: The symbol & here is a logical AND operation. CurrentLine[x]&1 means get bit 1. Bit one is a one if the number is odd.
There are other ways to generate the triangle. You could use a
recursive method and divide it repeatedly. You can make one in 3D too. I have just provided some of the simple
ones I know.
Have you found an error or do you want to add more
information to these pages?
You can contact me at the bottom of the home page.
|
