Koch snowflake implementation in python using pygame

Question

I would like to implement Koch Koch snow flake using pygame.

I am working with the following series of images from http://en.wikipedia.org/wiki/File:KochFlake.svg

My algorithm is this

1. Draw a triangle
2. Calculate the points of a triangle one-third its size and delete the centre line
3. Find out the outer points (as show in the second figure of the above image)
4. Make a list of all end points
5. Using polygon join all points

I've done up to the second step. But I'm struggling on the third step - as I can't work out how to find the outer points - any tips?

Here is my code up to second step

import pygame

from pygame.locals import *


pygame.init()

fpsClock = pygame.time.Clock()


screen = pygame.display.set_mode((600,600))

pygame.display.set_caption('Koch snowflake')


white = (255, 255, 255)

black = (0, 0 ,0)



def midpoints(pt1 , pt2):
   (x1, y1) = pt1
   (x2, y2) = pt2
   return ((x1+x2)/2, (y1 + y2)/2)

def midline(pt1, pt2):
(x1, y1) = pt1
(x2, y2) = pt2
return [(x1 + float(x2-x1)/3.0,y1 + float(y2-y1)/3.0), (x1 + float(x2-x1)*2.0/3,y1+ float(y2-y1)*2.0/3)]

def drawline(pt1, pt2):
   pygame.draw.line(screen, white, pt1, pt2)

def clearline(pt1,pt2):
   pygame.draw.line(screen, black, pt1, pt2, 4)

a = [(150,150), (450,150), (300,410), (150,150)]



pygame.draw.polygon(screen, white ,(a[0], a[1], a[2]), 1)
i = 0
order = 0
length = len(a)
while order < length - 1:
   pts = midline(a[i], a[i+1])
   clearline(pts[0], pts[1])
   a = a[:i+1] + pts + a[i+1:]
   print a
   if order < 3:
      i = i+3
   order = order + 1
#pygame.draw.polygon(screen, white ,Tup, 1)



pygame.display.update()

Answer 1

To calculate the points, I'd use a vector approach. If the triangle's corners are a1, a2 and a3, then you can get an equation for all points on the line a1 to a2. Using that equation, you can find the points at 1/3 and 2/3 between a1 and a2. The distance between those points gives you the side of the new triangle you're going to create. Using that information, and the point at 1/2 between a1 and a2 you can work out the coordinates of the third new point.

Answer 2

Not exactly an answer but something relevant to your larger question.

L-system fractals (like what you're trying to draw here) are best done using a rudimentary L-system parser. For a Koch snowflake, the 'axiom' (which is a description of the initial shape is something like this) D++D++D++. The D stands for "move forward by one unit" and the + for "turn clockwise by 30 degrees". The instructions will be "interpreted" by a turtle like cursor. It's not very hard to do this.

Once the axiom is drawn, you have a segment that replaces the D. For the koch flake, it is D-D++D-D meaning "move forward one unit, turn anticlockwise 30 degrees, forward, clockwise 60, forward, anticlockwise 30 and forward". This gives you the _/\_ shape that replaces the sides of the initial triangle. One "unit" reduces by to one third of the original length on every iteration.

Now, repeat this as many times as you want and you're looking for. This was one of my earliest Python programs and I have a crude parser/interpreter for it on github. It doesn't use pygame but you should be able to swap that part out quite easily.