How To Get The Area Of Shape Filled Using Turtle

I graphed a fractal shape in Python using turtle, and am trying to get the area of this fractal after a sufficiently high iteration. This fractal is related to the Koch snowflake,

Solution 1:

the complexity of the image drawn shouldn't affect the time it takes to count black pixels

Unfortunately, in this case it does. If we lookup an earlier source of the get_pixel_color() code, we find the telling text, "is slow". But it's worse than that, it actually slows down!

This code is built atop canvas.find_overlapping() which is looking for high level objects that sit over X,Y. In the case of tkinter filling an object for turtle, there is overlap, up to three layers in the code below. This increases as the factal gets more complex. Here's my code to demonstrate this:

from turtle import Screen, Turtle
from math import floor, ceil
from time import time

def koch_curve(turtle, iterations, length):
    if iterations == 0:
        turtle.forward(length)
    else:
        for angle in [60, -120, 60, 0]:
            koch_curve(turtle, iterations - 1, length / 3)
            turtle.left(angle)

def koch_snowflake(turtle, iterations, length):
    turtle.begin_poly()
    turtle.begin_fill()

    for _ in range(3):
        koch_curve(turtle, iterations, length)
        turtle.right(120)

    turtle.end_fill()
    turtle.end_poly()

    return turtle.get_poly()

def bounding_box(points):
    x_coordinates, y_coordinates = zip(*points)
    return [(min(x_coordinates), min(y_coordinates)), (max(x_coordinates), max(y_coordinates))]

def get_pixel_color(x, y):
    ids = canvas.find_overlapping(x, y, x, y)  # This is our bottleneck!

    if ids: # if list is not empty
        index = ids[-1]
        return canvas.itemcget(index, 'fill')

    return 'white' # default color

screen = Screen()
screen.setup(500, 500)
turtle = Turtle(visible=False)
turtle.color('red')

canvas = screen.getcanvas()
width, height = screen.window_width(), screen.window_height()

for iterations in range(1, 7):
    screen.clear()
    turtle.clear()

    screen.tracer(False)

    polygon_start_time = time()
    polygon = koch_snowflake(turtle, iterations, 200)
    polygon_elapsed = round((time() - polygon_start_time) * 1000)  # milliseconds

    screen.tracer(True)

    ((x_min, y_min), (x_max, y_max)) = bounding_box(polygon)
    screen.update()

    # Convert from turtle coordinates to tkinter coordinates
    x1, y1 = floor(x_min), floor(-y_max)
    x2, y2 = ceil(x_max), ceil(-y_min)

    canvas.create_rectangle((x1, y1, x2, y2))

    count = 0

    pixel_count_start_time = time()
    for x in range(x1, x2 + 1):
        for y in range(y1, y2 + 1):
            if get_pixel_color(x, y) == 'red':
                count += 1
    pixel_count_elapsed = round((time() - pixel_count_start_time) * 1000)

    print(iterations, count, polygon_elapsed, pixel_count_elapsed, ((x1, y1), (x2, y2)))

screen.exitonclick()

CONSOLE OUTPUT

> python3 test.py
1 23165 1 493 ((-1, -58), (201, 174))
2 26064 4 1058 ((-1, -58), (201, 174))
3 27358 9 1347 ((-1, -58), (201, 174))
4 28159 29 2262 ((0, -58), (201, 174))
5 28712 104 5925 ((0, -58), (201, 174))
6 28881 449 19759 ((0, -58), (200, 174))
> 

The fields are as follows:

1. Iterations
2. Pixels counted
3. Time to draw image in ms
4. Time to count pixels in ms
5. Computed bounding box (in tkinter coordinates)

FINAL ITERATION SCREEN OUTPUT

Note that the fractal is drawn by turtle but the bounding box is drawn by the underlying tkinter to verify that we converted coordinates correctly.

POSSIBLE SOLUTION

Find an approach that doesn't rely on find_overlapping(). I think the next thing to investigate would be either to convert the canvas to a bitmap image, and pixel count it, or draw a bitmap image in the first place. There are several discusions on SO about converting a canvas to a bitmap, either directly or indirectly via Postscript. You could then load in that image and use one of the Python image libraries to count the pixels. Although more complicated, it should provide a constant time way of counting pixels. Alternately, there are libraries to draw bitmaps, which you could load into tkinter for visual verfication, but could then pixel count directly. Good luck!