2
\$\begingroup\$

in last couple of days i was struggling with this drawing circle algorithm using bresenham’s method. This is my solution, im looking forward for better ones and definitely the faster ones, i dont know how to improve this algorithm, without using try/except method.

My code:

def bresenhamCircleNoTry(x, y, r):
   xc = x
   yc = y
   RGB = np.zeros((200, 200, 3), dtype = np.uint8)
   RGB.fill(255)
   d = 3 - 2 * r
   y = r
   i = 0
   while i <= y:
       indices = np.array([[xc + i, yc + y], [xc + i, yc - y], [xc - i, yc + y], [xc - i, yc - y], 
                           [xc + y, yc + i], [xc + y, yc - i], [xc - y, yc - i], [xc - y, yc + i]])

       for j in range(indices.shape[0]):
           if (indices[j, 0] >= 0).all() and (indices[j, 0] <= 199).all() and (indices[j, 1] >= 0).all() and (indices[j, 1] <= 199).all():
               RGB[indices[j, 0], indices[j, 1]] = [0, 0, 0]
       else:
           if (indices[:, 0] >= 0).all() and (indices[:, 0] <= 199).all() and (indices[:, 1] >= 0).all() and (indices[:, 1] <= 199).all():
               RGB[indices[:, 0], indices[:, 1]] = [0, 0, 0]
       if d < 0:
           d = d + 4 * i + 6
       else:
           d = d + 4 * (i - y) + 10
           y = y - 1
       i = i + 1
   return RGB 

Time of no try/except: 0.005274584293365478

vs try/except: 0.001818143129348755

Using Python 3.9

\$\endgroup\$

2 Answers 2

2
\$\begingroup\$

First of all, I'll mention that you didn't include the required import in your code snippet, which can't run as is. In this case, one should add the following line at the beginning:

import numpy as np

Some more information about the algorithm you're trying to implement could also be useful.

Now, let's review your code:

Good things

Your code works as expected. It draws a circle at the expected location, and is robust. I tried tripping it with all sort of edge cases (circle partially or totally outside of the frame, 0 or negative radii, center outside of the frame...) and failed. Nice!

Conventions

PEP 8 provides style guidelines for Python code. Adhering to these guidelines makes the code easier to read, as most Python code look similar.

Your code breaks a lot of these guidelines, mainly naming styles: variable and function names should be snake_case, where you use a mix of camelCase, lowercase and ALL_CAPS. Importantly, ALL_CAPS should be reserved for constants, but you name one of your variables RGB, which breaks expectations.

Some lines are also too long, and should be split, such as:

if ((indices[j, 0] >= 0).all()
        and (indices[j, 0] <= 199).all()
        and (indices[j, 1] >= 0).all()
        and (indices[j, 1] <= 199).all()):
    # Do things

I'd also argue that splitting the definition of indices with one sub-array per line not only allows to keep within the recommended 80-character line length, but is also more readable as the visual layout of the definition matches the shape of the array:

indices = np.array([[xc + i, yc + y],
                    [xc + i, yc - y],
                    [xc - i, yc + y],
                    [xc - i, yc - y],
                    [xc + y, yc + i],
                    [xc + y, yc - i],
                    [xc - y, yc - i],
                    [xc - y, yc + i]])

Naming

Your variable and function names could be improved. The function's name include irrelevant information about an implementation detail, and the variables inside the function are confusing.

draw_bresenham_circle would probably be a better name for the function, or image_data for your RBG variable, for example.

Also, some variables are redefined to another mean something else along the way, such as y which starts as the y-coordinate of the circle's center, then is used as some kind of upper bound for the loop counter.

It makes the logic hard to follow, and in fact, I gave up on this, so I won't try to suggest better names for the most part.

Reusability

Your function is quite limited, drawing a black circle on a white, 200x200px canvas. Letting the caller specify the canvas size and background color (or an image to draw onto) or the circle's color would make the function much more appealing, and as such would make it much more reusable.

I suppose the following stub would fit most needs for circle-drawing:

def draw_bresenham_circle(xc, yx, radius, image_data=None, color=[0, 0, 0]):
    if image_data=None:
        image_data = np.full((200, 200, 3), 255, dtype=np.uint8)
    # draw circle

Documentation

Add a docstring right after your function definition, describing the function's purpose, the argument it takes, what data it returns, possibly a reference to the algorithm it implements, and usage examples.

def draw_bresenham_circle(xc, yx, radius, image_data=None, color=[0, 0, 0]):
    '''
    Draws a circle on an image using Besenham's circle algorithm.

    Parameters
    ----------
    xc : int
        x-coordinate of the circle center, in pixels, with 0 being on the left.
    yc : int
        y-coordinate of the circle center, in pixels, with 0 being on the top.
    radius : int
        Circle radius, in pixels.
    image_data : numpy.array, optional
        A numpy array with a shape of (width, height, 3), representing the
        image to draw onto. If None, a blank 200x200px image will be used.
        The default is None.
    color : array, optional
        The circle's color, in RGB format. The default is [0, 0, 0].

    Returns
    -------
    image_data : numpy.array
        The image with the circle drawn.
    '''
    # draw circle

This will make it many more times easier to reuse this function in the future. Even if you have this information in your head right now, you can't expect that from others or yourself in the future.

You should try very hard to document all of the code you write.

Useless else

My code analyzer tells me that the else statement after the for loop will always be called, as the loop doesn't have a break statement. As such, the else should be removed and the code inside unindented one level.

Performance

Finally getting to what you ask for. Running the code in my profiler shows that about half of the time is spent calling the built-in all() function.

Looking at your code, this is always called on expressions that evaluate to boolean, resolving to either True.all() or False.all(), and can safely be removed:

if ((indices[j, 0] >= 0)
        and (indices[j, 0] <= 199)
        and (indices[j, 1] >= 0)
        and (indices[j, 1] <= 199)):

An easy fix for a 50% performance speed-up :)

Other than that, there are no obvious improvement showing up in the profiler. There might be something to gain on the algorithm, but as I said, I didn't try too hard to understand the algorithm, so I'll leave this part as an exercise for you.

\$\endgroup\$
2
\$\begingroup\$

General

gazoh's answer already covers most of the points. I agree with their answer and will not repeat the things pointed out.

Performance

Because you specifically mention you want to improve the performance of your code I have looked into it some more.

As gazoh mentions in their answer, the else block of the for loop is run every time. Having a closer look at it shows that this block is only redrawing pixels that were already drawn. It can therefor be removed, reducing the time for drawing a circle at (100, 100) with radius 50 from 2.0ms to 1.67ms on my machine.

       else:
           if (indices[:, 0] >= 0).all() and (indices[:, 0] <= 199).all() and (indices[:, 1] >= 0).all() and (indices[:, 1] <= 199).all():
               RGB[indices[:, 0], indices[:, 1]] = [0, 0, 0]

The second place for improvement is the inner for loop:

       for j in range(indices.shape[0]):
           if (indices[j, 0] >= 0).all() and (indices[j, 0] <= 199).all() and (indices[j, 1] >= 0).all() and (indices[j, 1] <= 199).all():
               RGB[indices[j, 0], indices[j, 1]] = [0, 0, 0]

Here you use a python loop to iterate over a numpy array. When optimizing for performance this should always be avoided because the python iteration is much slower than using numpy functions.

Inside the for loop you check if the indices are valid and use the valid ones to set the corresponding pixels. This can be done more efficiently using numpy:

       mask = (indices[:, 0] >= 0) & (indices[:, 0] <= 199) & (indices[:, 1] >= 0) & (indices[:, 1] <= 199)
       RGB[indices[mask, 0], indices[mask, 1]] = [0, 0, 0]

The & operator is in this case the numpy.logical_and function. The mask array contains True for each valid index and False for the invalid ones. This boolean array is then used to index the indices, masking all the invalid indices.

This modification further improves the runtime from ~1.67ms to ~350us.

def bresenhamCircleNoTry(x, y, r):
    xc = x
    yc = y
    RGB = np.zeros((200, 200, 3), dtype = np.uint8)
    RGB.fill(255)
    d = 3 - 2 * r
    y = r
    i = 0
    while i <= y:
        indices = np.array([[xc + i, yc + y], [xc + i, yc - y], [xc - i, yc + y], [xc - i, yc - y],
                            [xc + y, yc + i], [xc + y, yc - i], [xc - y, yc - i], [xc - y, yc + i]])
 
        mask = (indices[:, 0] >= 0) & (indices[:, 0] <= 199) & (indices[:, 1] >= 0) & (indices[:, 1] <= 199)
        RGB[indices[mask, 0], indices[mask, 1]] = [0, 0, 0]
 
        if d < 0:
            d = d + 4 * i + 6
        else:
            d = d + 4 * (i - y) + 10
            y = y - 1
        i = i + 1
    return RGB
\$\endgroup\$

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.