Chaos game
The Chaos Game is a method of generating the attractor of an iterated function system (IFS). One of the best-known and simplest examples creates a fractal, using a polygon and an initial point selected at random.
The task: play the Chaos Game using the corners of an equilateral triangle as the reference points. Add a starting point at random (preferably inside the triangle). Then add the next point halfway the starting point and one of the reference points. This reference point is chosen at random.
After a sufficient number of iterations, the image of a Sierpinski Triangle should emerge.
See also
C++
This program will generate the Sierpinski Triangle and save it to your hard drive. <lang cpp>
- include <windows.h>
- include <ctime>
- include <string>
- include <iostream>
const int BMP_SIZE = 600;
class myBitmap { public:
myBitmap() : pen( NULL ), brush( NULL ), clr( 0 ), wid( 1 ) {} ~myBitmap() { DeleteObject( pen ); DeleteObject( brush ); DeleteDC( hdc ); DeleteObject( bmp ); } bool create( int w, int h ) { BITMAPINFO bi; ZeroMemory( &bi, sizeof( bi ) ); bi.bmiHeader.biSize = sizeof( bi.bmiHeader ); bi.bmiHeader.biBitCount = sizeof( DWORD ) * 8; bi.bmiHeader.biCompression = BI_RGB; bi.bmiHeader.biPlanes = 1; bi.bmiHeader.biWidth = w; bi.bmiHeader.biHeight = -h; HDC dc = GetDC( GetConsoleWindow() ); bmp = CreateDIBSection( dc, &bi, DIB_RGB_COLORS, &pBits, NULL, 0 ); if( !bmp ) return false; hdc = CreateCompatibleDC( dc ); SelectObject( hdc, bmp ); ReleaseDC( GetConsoleWindow(), dc ); width = w; height = h; return true; } void clear( BYTE clr = 0 ) { memset( pBits, clr, width * height * sizeof( DWORD ) ); } void setBrushColor( DWORD bClr ) { if( brush ) DeleteObject( brush ); brush = CreateSolidBrush( bClr ); SelectObject( hdc, brush ); } void setPenColor( DWORD c ) { clr = c; createPen(); } void setPenWidth( int w ) { wid = w; createPen(); } void saveBitmap( std::string path ) { BITMAPFILEHEADER fileheader; BITMAPINFO infoheader; BITMAP bitmap; DWORD wb; GetObject( bmp, sizeof( bitmap ), &bitmap ); DWORD* dwpBits = new DWORD[bitmap.bmWidth * bitmap.bmHeight]; ZeroMemory( dwpBits, bitmap.bmWidth * bitmap.bmHeight * sizeof( DWORD ) ); ZeroMemory( &infoheader, sizeof( BITMAPINFO ) ); ZeroMemory( &fileheader, sizeof( BITMAPFILEHEADER ) ); infoheader.bmiHeader.biBitCount = sizeof( DWORD ) * 8; infoheader.bmiHeader.biCompression = BI_RGB; infoheader.bmiHeader.biPlanes = 1; infoheader.bmiHeader.biSize = sizeof( infoheader.bmiHeader ); infoheader.bmiHeader.biHeight = bitmap.bmHeight; infoheader.bmiHeader.biWidth = bitmap.bmWidth; infoheader.bmiHeader.biSizeImage = bitmap.bmWidth * bitmap.bmHeight * sizeof( DWORD ); fileheader.bfType = 0x4D42; fileheader.bfOffBits = sizeof( infoheader.bmiHeader ) + sizeof( BITMAPFILEHEADER ); fileheader.bfSize = fileheader.bfOffBits + infoheader.bmiHeader.biSizeImage; GetDIBits( hdc, bmp, 0, height, ( LPVOID )dwpBits, &infoheader, DIB_RGB_COLORS ); HANDLE file = CreateFile( path.c_str(), GENERIC_WRITE, 0, NULL, CREATE_ALWAYS, FILE_ATTRIBUTE_NORMAL, NULL ); WriteFile( file, &fileheader, sizeof( BITMAPFILEHEADER ), &wb, NULL ); WriteFile( file, &infoheader.bmiHeader, sizeof( infoheader.bmiHeader ), &wb, NULL ); WriteFile( file, dwpBits, bitmap.bmWidth * bitmap.bmHeight * 4, &wb, NULL ); CloseHandle( file ); delete [] dwpBits; } HDC getDC() const { return hdc; } int getWidth() const { return width; } int getHeight() const { return height; }
private:
void createPen() { if( pen ) DeleteObject( pen ); pen = CreatePen( PS_SOLID, wid, clr ); SelectObject( hdc, pen ); } HBITMAP bmp; HDC hdc; HPEN pen; HBRUSH brush; void *pBits; int width, height, wid; DWORD clr;
}; class chaos { public:
void start() { POINT org; fillPts(); initialPoint( org ); initColors(); int cnt = 0, i; bmp.create( BMP_SIZE, BMP_SIZE ); bmp.clear( 255 );
while( cnt++ < 1000000 ) { switch( rand() % 6 ) { case 0: case 3: i = 0; break; case 1: case 5: i = 1; break; case 2: case 4: i = 2; } setPoint( org, myPoints[i], i ); } // --- edit this path --- // bmp.saveBitmap( "F:/st.bmp" ); }
private:
void setPoint( POINT &o, POINT v, int i ) { POINT z; o.x = ( o.x + v.x ) >> 1; o.y = ( o.y + v.y ) >> 1; SetPixel( bmp.getDC(), o.x, o.y, colors[i] ); } void fillPts() { int a = BMP_SIZE - 1; myPoints[0].x = BMP_SIZE >> 1; myPoints[0].y = 0; myPoints[1].x = 0; myPoints[1].y = myPoints[2].x = myPoints[2].y = a; } void initialPoint( POINT& p ) { p.x = ( BMP_SIZE >> 1 ) + rand() % 2 ? rand() % 30 + 10 : -( rand() % 30 + 10 ); p.y = ( BMP_SIZE >> 1 ) + rand() % 2 ? rand() % 30 + 10 : -( rand() % 30 + 10 ); } void initColors() { colors[0] = RGB( 255, 0, 0 ); colors[1] = RGB( 0, 255, 0 ); colors[2] = RGB( 0, 0, 255 ); } myBitmap bmp; POINT myPoints[3]; COLORREF colors[3];
}; int main( int argc, char* argv[] ) {
srand( ( unsigned )time( 0 ) ); chaos c; c.start(); return 0;
} </lang>
Java
<lang java>import java.awt.*; import java.awt.event.*; import java.util.*; import javax.swing.*; import javax.swing.Timer;
public class ChaosGame extends JPanel {
class ColoredPoint extends Point { int colorIndex;
ColoredPoint(int x, int y, int idx) { super(x, y); colorIndex = idx; } }
Stack<ColoredPoint> stack = new Stack<>(); Point[] points = new Point[3]; Color[] colors = {Color.red, Color.green, Color.blue}; Random r = new Random();
public ChaosGame() { Dimension dim = new Dimension(640, 640); setPreferredSize(dim); setBackground(Color.white);
int margin = 60; int size = dim.width - 2 * margin;
points[0] = new Point(dim.width / 2, margin); points[1] = new Point(margin, size); points[2] = new Point(margin + size, size);
stack.push(new ColoredPoint(-1, -1, 0));
new Timer(10, (ActionEvent e) -> { if (stack.size() < 50_000) { for (int i = 0; i < 1000; i++) addPoint(); repaint(); } }).start(); }
private void addPoint() { try { int colorIndex = r.nextInt(3); Point p1 = stack.peek(); Point p2 = points[colorIndex]; stack.add(halfwayPoint(p1, p2, colorIndex)); } catch (EmptyStackException e) { System.out.println(e); } }
void drawPoints(Graphics2D g) { for (ColoredPoint p : stack) { g.setColor(colors[p.colorIndex]); g.fillOval(p.x, p.y, 1, 1); } }
ColoredPoint halfwayPoint(Point a, Point b, int idx) { return new ColoredPoint((a.x + b.x) / 2, (a.y + b.y) / 2, idx); }
@Override public void paintComponent(Graphics gg) { super.paintComponent(gg); Graphics2D g = (Graphics2D) gg; g.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
drawPoints(g); }
public static void main(String[] args) { SwingUtilities.invokeLater(() -> { JFrame f = new JFrame(); f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); f.setTitle("Chaos Game"); f.setResizable(false); f.add(new ChaosGame(), BorderLayout.CENTER); f.pack(); f.setLocationRelativeTo(null); f.setVisible(true); }); }
}</lang>
zkl
This is a half assed animated process - a bunch of pixels are drawn every couple of seconds and the pixmap written [to the file system]. So, if you open the output file ("chaosGame.jpg") it will [auto] update and show the progression of the image.
Uses the PPM class from http://rosettacode.org/wiki/Bitmap/Bresenham%27s_line_algorithm#zkl
<lang zkl>w,h:=640,640; bitmap:=PPM(w,h,0xFF|FF|FF); // White background colors:=T(0xFF|00|00,0x00|FF|00,0x00|00|FF); // red,green,blue
margin,size:=60, w - 2*margin; points:=T(T(w/2, margin), T(margin,size), T(margin + size,size) ); N,done:=Atomic.Int(0),Atomic.Bool(False);
Thread.HeartBeat('wrap(hb){ // a thread
var a=List(-1,-1);
if(N.inc()<50){ do(500){
colorIndex:=(0).random(3); // (0..2) b,p:=points[colorIndex], halfwayPoint(a,b); x,y:=p; bitmap[x,y]=colors[colorIndex]; a=p;
} bitmap.writeJPGFile("chaosGame.jpg",True); } else{ hb.cancel(); done.set(); } // stop thread and signal done
},2).go(); // run every 2 seconds, starting now
fcn halfwayPoint([(ax,ay)], [(bx,by)]){ T((ax + bx)/2, (ay + by)/2) }
done.wait(); // don't exit until thread is done println("Done");</lang>