<p>The equation of a line through the circle center and an arc endpoint can be written (Ye-Yo)(X-Xo)-(Xe-Xo)(Y-Yo)=0. [For numerical convenience, you can multiply the constant coefficients by any common factor.]</p>
<p>You can check crossing this line by observing a change of sign of the quantity on the left-hand side. The complete discussion of the handling of the two endpoints combined to the eight octants, though manageable, is out of the scope of this answer.</p>

CC BY-SA 4.0
2024-06-25T15:52:37.050Z
2024-06-25T15:52:37.050Z
Yves Daoust
<p>This morning I was thinking about how I would tackle the problem:</p>

<ol>
<li>Draw a circle of radius R and origin (H, K)</li>
<li>Using integer math</li>
<li>No anti-aliasing</li>
<li>Speed is important</li>
</ol>

<p>The first thing I noticed is if we assume (H, K) is (0,0), there is 8-way symmetry in the problem. That means if I find a pixel (x, y) between 0° and 45°, I already know 7 more pixel locations:</p>

<ul>
<li>pixel (x, y) is between 0° and 45°</li>
<li>pixel (y, x) is between 45° and 90°</li>
<li>pixel (-y, x) is between 90° and 135°</li>
<li>pixel (-x, y) is between 135° and 180°</li>
<li>pixel (-x, -y) is between 180° and 225°</li>
<li>pixel (-y, -x) is between 225° and 270°</li>
<li>pixel (y, -x) is between 270° and 315°</li>
<li>pixel (x, -y) is between 315° and 360°</li>
</ul>

<p>Because the tangent line to the circle between 0° and 45° has as slope less than -1, there is exactly 1 integer x value for any y value in that range. We find the x values for all <span class="math-container">$ y \in [0, \frac{\sqrt{2}}{2} R ]$</span>, plot them using symmetry, and we're done.</p>

<p>In Python it the algorithm would look like this:</p>

<pre><code>def circle(h, k, r):
    d=round( r* math.sqrt(2)/2 ) # find the 45 degree value
    r2=r**2 # square r
    p=r

    for y in range(0, d+1): 
#####   x=round(math.sqrt(r2 - y*y ))
        q=(r2-p*p-y*y)
        if( q &lt; -p):
            p-=1
        x=p
        setPixel(h+x, k+y)
        setPixel(h+y, k+x)
        setPixel(h-y, k+x)
        setPixel(h-x, k+y)
        setPixel(h-x, k-y)
        setPixel(h-y, k-x)
        setPixel(h+y, k-x)
        setPixel(h+x, k-y)

</code></pre>

CC BY-SA 4.0
2020-06-10T20:08:33.127Z
Sorry if my question wasn't clear, I need to draw an arc, not a circle, a segment of the circle. I already have implemented the circle function using the Bresenham's algorithm using integer math and no square root nor floating point operations. I have the start point and end point of the arc in the circle and the problem I face is how to determine if a pixel of the circle belongs to the arc segment to draw it or skip it. As I state in the question the Bresenham's algorithm uses octants (like your answser) what makes difficult to determine it.
Gusman
CC BY-SA 4.0
2020-06-11T00:21:08.963Z
I'm thinking that for any two points on the circumference of a circle, you can draw a bounding rectangle that encloses the minor arc. You can use this bounding rectangle to mask the arc segment you want. E.g., if you want the minor arc, only plot points inside the rectangle and if you want the major arc, only plot points outside the rectangle. The only issue with this technique is if the points are on a diameter. Then a corner of your bounding rectangle will touch the circle.
Ron Jensen
CC BY-SA 4.0
2020-06-11T00:24:06.547Z
More or less that's what I'm testing as Oliver already gave me the idea of using bounding boxes, but instead of many boxes only one per quadrant.
Gusman
CC BY-SA 4.0
2020-06-11T15:47:23.537Z
I came up with another, perhaps better, idea this morning. You can use arc lengths. Math nerds use radians to measure angles because radians directly correspond to arc lengths. For this problem we can measure arc length in pixels to be set and pixels to skip. I may work this up as an answer today if I get a chance.
Ron Jensen
CC BY-SA 4.0
2020-06-10T16:42:35.930Z
2020-06-10T18:53:34.297Z
2020-06-10T18:53:34.297Z
Ron Jensen
<p>I'm trying to create some graphic functions for a ZX Spectrum (Z80) machine in assembler. I already have the basics except for the arc.</p>

<p>I need a fast algorithm to draw an arc, ideally one that uses integer or fixed point math.</p>

<p>I know there must be some way to draw an arc using the Bresenham's circle algorithm but I'm unable to find concrete info about it, there are sentences like "set the pixels only if they fall into the wanted interval" but I have no clue on how to determine if the pixels fall within it.</p>

<p>I only miss how to determine if a pixel lies in the arc, if the algorithm were completely linear (start at 0º and sweep to 360º) it would be easy to skip pixels until the start point and then continue drawing until the last point is reached, but the Bresenham's algorithm is drawn in octants simultaneously so I have no idea on how to do it. Also I had the idea to compute the circle's area in pixels and then divide 360 by the number of pixels to know how many degrees a pixel represents so I could use the start and end angle and check if a pixel must be drawn or not, but it does not work as the computed area is ideal and not the real one that Bresenham's algorithm generates.</p>

<p>As input data I have the circle's center and radius and the start and end points of the arc in the circle (I can derive the start and end angle from those, no problem), I'm not tied to anything so any other algorithm is welcome, no need to be specifically for the spectrum, just any assembler algorithm to draw an arc using integer or fixed point math  will be enough even if I need different info (like the three point arc algorithm).</p>

<p>Cheers.</p>

<p><em>EDIT</em>: I already have the circle's implementation, in C and assembler, I only need to determine what pixels of the circle belong to the arc to skip the ones that doesn't belong.</p>

<p>Here is the assembler implementation:</p>

<pre><code>;--------------CIRCLE ROUTINE
; Plot function isn't included as it's very specific for the ZX Spectrum
;because of the way the video memory is mapped and it's irrelevant to the question

CENTER_X: .defb 0        ;Input parameter
CENTER_Y: .defb 0        ;Input parameter
RADII: .defb 0           ;Input parameter

CIRCLE_D: .defw 0        ;Temp variable
CIRCLE_D_SIGN: .defb 0   ;Temp variable


Draw_Circle:            ;D = X, E = Y

LD DE, 5
LD A, (RADII)
LD L, A
LD H, 0


OR A
ADD HL, HL 
ADD HL, HL
EX DE, HL
SBC HL, DE
JP P, POS_VAL
LD A, -1
LD (CIRCLE_D_SIGN), A

;NEG HL
xor a
sub l
ld l,a
sbc a,a
sub h
ld h,a


LD C, 4
CALL HL_Div_C

;NEG HL
xor a
sub l
ld l,a
sbc a,a
sub h
ld h,a

JR D_DONE
POS_VAL:
LD A, 1
LD (CIRCLE_D_SIGN), A
LD C, 4
CALL HL_Div_C
D_DONE:
LD (CIRCLE_D), HL


LD D, 0
LD A, (RADII)
LD E, A

CIRCLE_LOOP:

LD A, (CENTER_X)
LD H, A
LD A, (CENTER_Y)
LD L, A

;seq x.X/y.Y

LD A, H             ;center_x
ADD A, D                ;x
LD C, A             ;point_x
LD A, L             ;center_y
ADD A, E                ;y
LD B, A             ;point_y

PUSH HL
PUSH DE
CALL Plot
POP DE
POP HL

LD A, H             ;center_x
ADD A, D                ;x
LD C, A             ;point_x
LD A, L             ;center_y
SUB A, E                ;y
LD B, A             ;point_y

PUSH HL
PUSH DE
CALL Plot
POP DE
POP HL

LD A, H             ;center_x
SUB A, D                ;x
LD C, A             ;point_x
LD A, L             ;center_y
ADD A, E                ;y
LD B, A             ;point_y

PUSH HL
PUSH DE
CALL Plot
POP DE
POP HL

LD A, H             ;center_x
SUB A, D                ;x
LD C, A             ;point_x
LD A, L             ;center_y
SUB A, E                ;y
LD B, A             ;point_y

PUSH HL
PUSH DE
CALL Plot
POP DE
POP HL

;seq x.Y/y.X

LD A, H             ;center_x
ADD A, E                ;y
LD C, A             ;point_x
LD A, L             ;center_y
ADD A, D                ;x
LD B, A             ;point_y

PUSH HL
PUSH DE
CALL Plot
POP DE
POP HL


LD A, H             ;center_x
ADD A, E                ;y
LD C, A             ;point_x
LD A, L             ;center_y
SUB A, D                ;x
LD B, A             ;point_y

PUSH HL
PUSH DE
CALL Plot
POP DE
POP HL

LD A, H             ;center_x
SUB A, E                ;y
LD C, A             ;point_x
LD A, L             ;center_y
ADD A, D                ;x
LD B, A             ;point_y

PUSH HL
PUSH DE
CALL Plot
POP DE
POP HL

LD A, H             ;center_x
SUB A, E                ;y
LD C, A             ;point_x
LD A, L             ;center_y
SUB A, D                ;x
LD B, A             ;point_y

PUSH DE
CALL Plot
POP DE


LD HL, (CIRCLE_D)               ;if (d &lt; 0)
LD A, (CIRCLE_D_SIGN)
CP -1
JR Z, NEGATIVE_D



POSITIVE_D:                     ;no
PUSH DE
PUSH HL
LD L, D
LD H, 0
LD D, 0
XOR A
SBC HL, DE
ADD HL, HL
INC HL
POP DE
ADD HL, DE
POP DE

LD A, H                         ;is negative?
CP #FF
JP NZ, POS_VAL_POS
LD A, -1                        ;yes
LD (CIRCLE_D_SIGN), A
JP DEC_Y

POS_VAL_POS:                    ;no
LD A, 1
LD (CIRCLE_D_SIGN), A

DEC_Y:
DEC E
JP STORE_D

NEGATIVE_D:
PUSH HL
LD L, D
LD H,0
ADD HL, HL
INC HL

LD A, D                     ;2 * x
ADD A, A
INC A                       ; + 1

LD C, A
LD B, 0
POP HL
ADD HL, BC                  ;d = d +

LD A, H                     ;is negative?
CP #FF
JP NZ, POS_VAL_NEG

LD A, -1                    ;yes
LD (CIRCLE_D_SIGN), A
JP STORE_D

POS_VAL_NEG:
LD A, 1                 ;no
LD (CIRCLE_D_SIGN), A

STORE_D:
INC D
LD (CIRCLE_D), HL


TEST_LOOP:
LD A, E
CP D
JP P, CIRCLE_LOOP

RET
</code></pre>

CC BY-SA 4.0
2020-06-09T12:38:48.883Z
Here is a link to a related question: [click me](https://computergraphics.stackexchange.com/questions/9733/bresenham-circle-drawing-algorithm-compute-the-distance/9735#9735) - In my answer, I also linked a tutorial. Maybe that helps.
wychmaster
CC BY-SA 4.0
2020-06-09T13:59:05.780Z
Have you considered working with 2D bounds for each quadrant? Generating those for every possible case will involve some logic (more than I have time to hash out in a full answer) but only simple integer math.
Olivier
CC BY-SA 4.0
2020-06-09T14:12:49.003Z
@Olivier Sorry, I don't understand, how would it help me to determine which pixels I must draw?
Gusman
CC BY-SA 4.0
2020-06-09T14:37:15.323Z
By only drawing the pixels inside the 2D bounds. Try splitting your circle in 4 quadrants. Draw a random arc on the circle. Now draw a tight box around the part of the arc in each quadrant. You'll see that you can fully define any arc that way. And the coordinates of the boxes all correspond to your circle center, center +/- radius or start/end point. You just need the logic to pick the right numbers for each case.
Olivier
CC BY-SA 4.0
2020-06-09T14:42:55.817Z
@Olivier Hmmm, ok, I think I start to understand it... I'm going to do some visual tests and see if I understood everything to code it. Thanks a lot!
Gusman
<drawing><assembly>
Using Bresenham's circle algorithm (or another alternative algorithm) to draw an arc
Gusman
# Using Bresenham's circle algorithm (or another alternative algorithm) to draw an arc

(Asked by: username_0 on 2020-06-09)

I'm trying to create some graphic functions for a ZX Spectrum (Z80) machine in assembler. I already have the basics except for the arc.

I need a fast algorithm to draw an arc, ideally one that uses integer or fixed point math.

I know there must be some way to draw an arc using the Bresenham's circle algorithm but I'm unable to find concrete info about it, there are sentences like "set the pixels only if they fall into the wanted interval" but I have no clue on how to determine if the pixels fall within it.

I only miss how to determine if a pixel lies in the arc, if the algorithm were completely linear (start at 0º and sweep to 360º) it would be easy to skip pixels until the start point and then continue drawing until the last point is reached, but the Bresenham's algorithm is drawn in octants simultaneously so I have no idea on how to do it. Also I had the idea to compute the circle's area in pixels and then divide 360 by the number of pixels to know how many degrees a pixel represents so I could use the start and end angle and check if a pixel must be drawn or not, but it does not work as the computed area is ideal and not the real one that Bresenham's algorithm generates.

As input data I have the circle's center and radius and the start and end points of the arc in the circle (I can derive the start and end angle from those, no problem), I'm not tied to anything so any other algorithm is welcome, no need to be specifically for the spectrum, just any assembler algorithm to draw an arc using integer or fixed point math will be enough even if I need different info (like the three point arc algorithm).

Cheers.

*EDIT*: I already have the circle's implementation, in C and assembler, I only need to determine what pixels of the circle belong to the arc to skip the ones that doesn't belong.

Here is the assembler implementation:

```
;--------------CIRCLE ROUTINE
; Plot function isn't included as it's very specific for the ZX Spectrum
;because of the way the video memory is mapped and it's irrelevant to the question

CENTER_X: .defb 0        ;Input parameter
CENTER_Y: .defb 0        ;Input parameter
RADII: .defb 0           ;Input parameter

CIRCLE_D: .defw 0        ;Temp variable
CIRCLE_D_SIGN: .defb 0   ;Temp variable

Draw_Circle:            ;D = X, E = Y

LD DE, 5
LD A, (RADII)
LD L, A
LD H, 0

OR A
ADD HL, HL 
ADD HL, HL
EX DE, HL
SBC HL, DE
JP P, POS_VAL
LD A, -1
LD (CIRCLE_D_SIGN), A

;NEG HL
xor a
sub l
ld l,a
sbc a,a
sub h
ld h,a

LD C, 4
CALL HL_Div_C

;NEG HL
xor a
sub l
ld l,a
sbc a,a
sub h
ld h,a

JR D_DONE
POS_VAL:
LD A, 1
LD (CIRCLE_D_SIGN), A
LD C, 4
CALL HL_Div_C
D_DONE:
LD (CIRCLE_D), HL

LD D, 0
LD A, (RADII)
LD E, A

CIRCLE_LOOP:

LD A, (CENTER_X)
LD H, A
LD A, (CENTER_Y)
LD L, A

;seq x.X/y.Y

LD A, H             ;center_x
ADD A, D                ;x
LD C, A             ;point_x
LD A, L             ;center_y
ADD A, E                ;y
LD B, A             ;point_y

PUSH HL
PUSH DE
CALL Plot
POP DE
POP HL

LD A, H             ;center_x
ADD A, D                ;x
LD C, A             ;point_x
LD A, L             ;center_y
SUB A, E                ;y
LD B, A             ;point_y

PUSH HL
PUSH DE
CALL Plot
POP DE
POP HL

LD A, H             ;center_x
SUB A, D                ;x
LD C, A             ;point_x
LD A, L             ;center_y
ADD A, E                ;y
LD B, A             ;point_y

PUSH HL
PUSH DE
CALL Plot
POP DE
POP HL

LD A, H             ;center_x
SUB A, D                ;x
LD C, A             ;point_x
LD A, L             ;center_y
SUB A, E                ;y
LD B, A             ;point_y

PUSH HL
PUSH DE
CALL Plot
POP DE
POP HL

;seq x.Y/y.X

LD A, H             ;center_x
ADD A, E                ;y
LD C, A             ;point_x
LD A, L             ;center_y
ADD A, D                ;x
LD B, A             ;point_y

PUSH HL
PUSH DE
CALL Plot
POP DE
POP HL

LD A, H             ;center_x
ADD A, E                ;y
LD C, A             ;point_x
LD A, L             ;center_y
SUB A, D                ;x
LD B, A             ;point_y

PUSH HL
PUSH DE
CALL Plot
POP DE
POP HL

LD A, H             ;center_x
SUB A, E                ;y
LD C, A             ;point_x
LD A, L             ;center_y
ADD A, D                ;x
LD B, A             ;point_y

PUSH HL
PUSH DE
CALL Plot
POP DE
POP HL

LD A, H             ;center_x
SUB A, E                ;y
LD C, A             ;point_x
LD A, L             ;center_y
SUB A, D                ;x
LD B, A             ;point_y

PUSH DE
CALL Plot
POP DE

LD HL, (CIRCLE_D)               ;if (d < 0)
LD A, (CIRCLE_D_SIGN)
CP -1
JR Z, NEGATIVE_D

POSITIVE_D:                     ;no
PUSH DE
PUSH HL
LD L, D
LD H, 0
LD D, 0
XOR A
SBC HL, DE
ADD HL, HL
INC HL
POP DE
ADD HL, DE
POP DE

LD A, H                         ;is negative?
CP #FF
JP NZ, POS_VAL_POS
LD A, -1                        ;yes
LD (CIRCLE_D_SIGN), A
JP DEC_Y

POS_VAL_POS:                    ;no
LD A, 1
LD (CIRCLE_D_SIGN), A

DEC_Y:
DEC E
JP STORE_D

NEGATIVE_D:
PUSH HL
LD L, D
LD H,0
ADD HL, HL
INC HL

LD A, D                     ;2 * x
ADD A, A
INC A                       ; + 1

LD C, A
LD B, 0
POP HL
ADD HL, BC                  ;d = d +

LD A, H                     ;is negative?
CP #FF
JP NZ, POS_VAL_NEG

LD A, -1                    ;yes
LD (CIRCLE_D_SIGN), A
JP STORE_D

POS_VAL_NEG:
LD A, 1                 ;no
LD (CIRCLE_D_SIGN), A

STORE_D:
INC D
LD (CIRCLE_D), HL

TEST_LOOP:
LD A, E
CP D
JP P, CIRCLE_LOOP

RET

```

**Tags:** drawing, assembly

> **Comments:**
> **username_1**: Here is a link to a related question: [click me](https://computergraphics.stackexchange.com/questions/9733/bresenham-circle-drawing-algorithm-compute-the-distance/9735#9735) - In my answer, I also linked a tutorial. Maybe that helps.  
> **username_2**: Have you considered working with 2D bounds for each quadrant? Generating those for every possible case will involve some logic (more than I have time to hash out in a full answer) but only simple integer math.  
> **username_0**: @username_2 Sorry, I don't understand, how would it help me to determine which pixels I must draw?  
> **username_2**: By only drawing the pixels inside the 2D bounds. Try splitting your circle in 4 quadrants. Draw a random arc on the circle. Now draw a tight box around the part of the arc in each quadrant. You'll see that you can fully define any arc that way. And the coordinates of the boxes all correspond to your circle center, center +/- radius or start/end point. You just need the logic to pick the right numbers for each case.  
> **username_0**: @username_2 Hmmm, ok, I think I start to understand it... I'm going to do some visual tests and see if I understood everything to code it. Thanks a lot!  

---

## 2 answers

### Answer by username_3 on 2024-06-25. Score: 0

The equation of a line through the circle center and an arc endpoint can be written (Ye-Yo)(X-Xo)-(Xe-Xo)(Y-Yo)=0. [For numerical convenience, you can multiply the constant coefficients by any common factor.]

You can check crossing this line by observing a change of sign of the quantity on the left-hand side. The complete discussion of the handling of the two endpoints combined to the eight octants, though manageable, is out of the scope of this answer.


---

### Answer by username_4 on 2020-06-10. Score: 0

This morning I was thinking about how I would tackle the problem:

1. Draw a circle of radius R and origin (H, K)
2. Using integer math
3. No anti-aliasing
4. Speed is important

The first thing I noticed is if we assume (H, K) is (0,0), there is 8-way symmetry in the problem. That means if I find a pixel (x, y) between 0° and 45°, I already know 7 more pixel locations:

* pixel (x, y) is between 0° and 45°
* pixel (y, x) is between 45° and 90°
* pixel (-y, x) is between 90° and 135°
* pixel (-x, y) is between 135° and 180°
* pixel (-x, -y) is between 180° and 225°
* pixel (-y, -x) is between 225° and 270°
* pixel (y, -x) is between 270° and 315°
* pixel (x, -y) is between 315° and 360°

Because the tangent line to the circle between 0° and 45° has as slope less than -1, there is exactly 1 integer x value for any y value in that range. We find the x values for all $ y \in [0, \frac{\sqrt{2}}{2} R ]$, plot them using symmetry, and we're done.

In Python it the algorithm would look like this:

```
def circle(h, k, r):
    d=round( r* math.sqrt(2)/2 ) # find the 45 degree value
    r2=r**2 # square r
    p=r

    for y in range(0, d+1): 
#####   x=round(math.sqrt(r2 - y*y ))
        q=(r2-p*p-y*y)
        if( q < -p):
            p-=1
        x=p
        setPixel(h+x, k+y)
        setPixel(h+y, k+x)
        setPixel(h-y, k+x)
        setPixel(h-x, k+y)
        setPixel(h-x, k-y)
        setPixel(h-y, k-x)
        setPixel(h+y, k-x)
        setPixel(h+x, k-y)

```

> **Comments:**
> **username_0**: Sorry if my question wasn't clear, I need to draw an arc, not a circle, a segment of the circle. I already have implemented the circle function using the Bresenham's algorithm using integer math and no square root nor floating point operations. I have the start point and end point of the arc in the circle and the problem I face is how to determine if a pixel of the circle belongs to the arc segment to draw it or skip it. As I state in the question the Bresenham's algorithm uses octants (like your answser) what makes difficult to determine it.  
> **username_4**: I'm thinking that for any two points on the circumference of a circle, you can draw a bounding rectangle that encloses the minor arc. You can use this bounding rectangle to mask the arc segment you want. E.g., if you want the minor arc, only plot points inside the rectangle and if you want the major arc, only plot points outside the rectangle. The only issue with this technique is if the points are on a diameter. Then a corner of your bounding rectangle will touch the circle.  
> **username_0**: More or less that's what I'm testing as Oliver already gave me the idea of using bounding boxes, but instead of many boxes only one per quadrant.  
> **username_4**: I came up with another, perhaps better, idea this morning. You can use arc lengths. Math nerds use radians to measure angles because radians directly correspond to arc lengths. For this problem we can measure arc length in pixels to be set and pixels to skip. I may work this up as an answer today if I get a chance.  

---

