Removing duplicate points in circle fill algorithm

Question

I'm using the following algorithm to plot a filled circle. However, it generates duplicate points and I'm not sure where I'm going wrong.

Any advice appreciated.

def get_filled_circle(radius):
    d = (5 - radius * 4) / 4.0
    x = 0
    y = radius

    points = []

    while True:
        for idx in range(-x, x+1, 1):
            points.append((idx, y))
            if y != 0: 
                points.append((idx,-y))

        for idx in range(-y, y+1, 1):
            points.append((idx, x))
            if x != 0: 
                points.append((idx,-x))

        if (d < 0):
            d += 2 * x + 1
        else:
            d += 2 * (x - y) + 1
            y -= 1

        x += 1

        if (y < x):
            break


    return points

The output below shows the plotted points, where "!" indicates a duplicate:

   *!!!*
 !!!!!!!!!
 *********
***********
***********
***********
***********
***********
 *********
 !!!!!!!!!
   *!!!*

see [Is there a more efficient way of texturing a circle?](https://stackoverflow.com/a/61097673/2521214) — Spektre, Jul 13 '22 at 05:34

score 0 · Answer 1 · answered Jul 21 '22 at 09:57

I made some code changes. It is working upto 11 radius as expected. This code has not the complete solution. Maybe this will guide you to write perfect one.

def get_filled_circle(radius):
    d = (5 - radius * 4) / 4.0
    x = 0
    y = radius

    points = []

    run = True

    while run:
        for idx in range(-y, y+1, 1):
            points.append((idx, x))
            if x != 0: 
                points.append((idx,-x))

        if (d < 0):
            d += 2 * x + 1
        else:
            for idx in range(-x, x+1, 1):
                points.append((idx, y))
                if y != 0: 
                    points.append((idx,-y))
            if (y-x == 1):
                break

            d += 2 * (x - y) + 1
            y -= 1

        x += 1

        if (y < x):
            run = False 
    else:
        x -= 1 
        for idx in range(-x, x+1, 1):
            points.append((idx, y))
            if y != 0: 
                points.append((idx,-y))


    return points

Removing duplicate points in circle fill algorithm

1 Answers1