1
\$\begingroup\$

According to Rosetta Code:

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.

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 between 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.

Here is my solution in Python:

"""This module performs the Chaos Game."""

from random import choice
from PIL import Image


def midpoint(p1, p2):
    """
    Takes 2 points and calculates the midpoint.
    Args:
        p1 (real, real): A point in space.
        p2 (real, real): Another point in space.
    Returns:
        (real, real): The midpoint between p1 and p2.
    """
    return (p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2


def translate(point, screen_size):
    """
    Takes a point and converts it to the appropriate coordinate system.
    Note that PIL uses upper left as 0, we want the center.
    Args:
        point (real, real): A point in space.
        screen_size (int): Size of an N x N screen.
    Returns:
        (real, real): Translated point for Pillow coordinate system.
    """
    return point[0] + screen_size / 2, point[1] + screen_size / 2


def image_rep(point, img_size):
    """
    Returns a representation of the point that can be used by Pillow.
    Args:
        point (real, real): A point in space.
        img_size (int): The size of an N x N image
    """
    # Convert the point to the correct coordinate system.
    translated = translate((point[0], point[1]), img_size)
    # Make it an integer so Pillow can use it.
    return int(translated[0]), int(translated[1])


def play_chaos(guiders, seed, img, steps=1000):
    """
    Play the Chaos Game:
    1. Have a collection of n (ordered) "guider" points.
    2. Start with a random seed some where on the screen.
    3. Roll die that has n sides
    4. Make a new point that is halfway between the appropriate gudier and the
       previous point.
    5. Repeat the game from the new point
    Args:
        guiders ([(real, real)]): List of guider points
        seed (real, real): Initial seed, be sure to be within the screens range
        img (Image): Image to write spiral to.
        steps (int): The amount of times the process is repeated.
        (default: 1000)
    """
    prev_point = seed
    for _ in range(steps):
        # Select the next guider to move closer to
        guider = choice(guiders)
        new_point = midpoint(prev_point, guider)
        img.putpixel(image_rep(new_point, img.size[0]), 1)
        prev_point = new_point


def main():
    """
    Main method, start of the program. Creates an image and populates it with
    chaos.
    """
    IMAGE_SIZE = 300, 300
    img = Image.new('1', IMAGE_SIZE)
    SEED = (0.0, 0.0)
    GUIDERS = [(-100.0, -100.0),
               (100.0, -100.0),
               (0.0, 100.0)]
    play_chaos(GUIDERS, SEED, img)
    img.save('chaos.png')


if __name__ == '__main__':
    main()
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

midpoint()

This function could be written more elegantly using zip(), and it would work for any number of dimensions. (I suspect it might be slower, though.)

def midpoint(p1, p2):
    """
    Find the midpoint of two cartesian points.
    """
    return tuple((c1 + c2) / 2 for c1, c2 in zip(p1, p2))

translate() and image_rep()

Since translate() gives a result in Pillow coordinates, I think that the result should be quantized as integers. You should round to the nearest integer rather than truncating.

Pillow coordinates increase towards the right and towards the bottom. Conventionally, cartesian coordinates increase towards the right and towards the top. I would therefore incorporate a reflection of the vertical axis in the translation.

I don't see why the image must be square.

You can just pass point instead of packing it into a new tuple.

translated = translate(point, img_size)

I suggest hiding these two helper functions inside a plotting routine. (See below.)

play_chaos()

I would split this into the mathematical concept and its visualization.

def chaos_points(attractors, start_point):
    attractor_stream = (random.choice(attractors) for _ in itertools.count())
    return itertools.accumulate(itertools.chain([start_point], attractor_stream), midpoint)

def plot(img, points):
    half_width, half_height = img.size[0] / 2, img.size[1] / 2
    to_pillow = lambda p: (int(round(half_width + p[0])), int(round(half_height - p[1])))
    for point in points:
        img.putpixel(to_pillow(point), 1)

Demo

Your GUIDERS don't form an equilateral triangle as suggested.

def main():
    """
    Create an image and populate it with chaos.
    """
    IMAGE_SIZE = 300, 300
    SEED = (0.0, 0.0)
    GUIDERS = [(-100.0, -50 * 3**.5),
               (+100.0, -50 * 3**.5),
               (   0.0, +50 * 3**.5)]
    img = Image.new('1', IMAGE_SIZE)
    plot(img, itertools.islice(chaos_points(GUIDERS, SEED), 1000))
    img.save('chaos.png')


if __name__ == '__main__':
    main()
\$\endgroup\$
3
  • \$\begingroup\$ Thank you for the answer! The only thing I'm not sure about is making the image_rep a lambda. Is there a particular motivation for this? (Note: I wrote another program that used sort of used image_rep and almost considered making it a separate util file. This contrasts sharply with the lambda notion, which is why I am curious about that choice.) Thanks again! \$\endgroup\$
    – Dair
    Oct 14, 2016 at 19:10
  • \$\begingroup\$ You could write it as a nested def instead. \$\endgroup\$ Oct 14, 2016 at 19:11
  • \$\begingroup\$ Oh, wait, upon further reflection, it makes sense why you are hiding image_rep as you are encompassing everything in plot. Thanks! \$\endgroup\$
    – Dair
    Oct 14, 2016 at 19:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.