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:
- Iterations
- Pixels counted
- Time to draw image in ms
- Time to count pixels in ms
- 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!
