<p>A generalised circle is either a circle in the plane or a line. The general equation of one is:</p>
<p><span class="math-container">$$A(x^2 + y^2) + Bx + Cy + D=0,$$</span></p>
<p>where <span class="math-container">$4AD - B^2 - C^2 \leq 0$</span>. This can be checked by completing the square on <span class="math-container">$x$</span> and <span class="math-container">$y$</span>, and checking that the minimum value of the LHS is <span class="math-container">$4AD - B^2 - C^2$</span>.</p>
<p>My question is: What algorithm would you use to draw it?</p>
<p>Seems there are different approaches:</p>
<ol>
<li>Break it into the circle case and line case. Draw each using a dedicated routine. This way, you can use pre-existing drawing routines. There is a problem here, which is that out of many possible floating point values, only one of them is exactly <span class="math-container">$0$</span>. So the line case happens in one case out of <span class="math-container">$2^{64}$</span> (if you use <span class="math-container">$64$</span>-bit floats). And on top of that, thanks to rounding errors, what <em>should</em> be a line can become a circle. The circle case requires finding the centre and radius, but these can both be large values, subject to floating-point rounding errors. You can use a threshold instead of checking whether <span class="math-container">$A = 0$</span>, but which threshold should get used?</li>
<li>Traverse each value of <span class="math-container">$x$</span> in the viewport, and compute the (at most) <span class="math-container">$2$</span> different values of <span class="math-container">$y$</span>, and draw those points. Then do the same again, but traversing each value of <span class="math-container">$y$</span> and finding <span class="math-container">$x$</span>.</li>
<li>A generalised circle determines a constant-speed motion along it. Use this somehow.</li>
<li>A generalised circle determines an <a href="https://en.wikipedia.org/wiki/Inversive_geometry" rel="nofollow noreferrer">inversion</a> through it. Use this fact somehow.</li>
</ol>
<p>Approach 2 explicitly uses the viewport. Approaches 3 and 4 are vague, but depend on knowing it as well.</p>
<p>What approaches are there?</p>

CC BY-SA 4.0
2022-10-09T09:56:03.547Z
I don't know whether this counts as a computer graphics question. This is cross-posted from Maths SE, because I'm not sure whether it's appropriate for there either.
wlad
CC BY-SA 4.0
2022-10-09T17:47:40.953Z
@lightxbulb You haven't read my question. That's my suggestion 1. I've commented on it.
wlad
CC BY-SA 4.0
2022-10-09T17:58:25.480Z
As you noted, I am suggesting the first case, as zero can be represented exactly in a computer, so it's either a circle or it is a line, there is no middle ground. If the above is a circle then the following decomposition should be valid: $(x-x_0)^2 + (y-y_0)^2 = R^2$, where $x_0 = -\frac{B}{2A}$, $y_0 = -\frac{C}{2A}$, $R^2 = -D + x_0^2 + y_0^2$, and you can use some standard algorithm to draw the circle. If you're worried about the division you can check for infs and nans, and if that occurs I would just deem it to inaccurate to draw.
lightxbulb
CC BY-SA 4.0
2022-10-09T18:48:12.460Z
If $A$ is slightly bigger than zero then this is still a circle mathematically. However due to finite precision $x_0, y_0, R$ will be very inaccurate (e.g. potentially even infs or nans). This is the reality of using a finite precision machine for computations - it cannot handle close to singular situations. Notably what occurs is that the radius becomes closer and closer to infinite, and finite precision does not allow to bridge this gap in a continuous manner. A computer cannot represent a circle with an arbitrarily large radius. Purely visually you can swap it for the line though.
lightxbulb
CC BY-SA 4.0
2022-10-09T18:52:06.620Z
I have a typo btw, $R^2$ should read: $R^2 = -D/A + x_0^2 + y_0^2$.
lightxbulb
<computational-geometry><drawing>
Algorithm for drawing generalised circles
wlad
# Algorithm for drawing generalised circles

(Asked by: username_0 on 2022-10-09)

A generalised circle is either a circle in the plane or a line. The general equation of one is:

$$A(x^2 + y^2) + Bx + Cy + D=0,$$

where $4AD - B^2 - C^2 \leq 0$. This can be checked by completing the square on $x$ and $y$, and checking that the minimum value of the LHS is $4AD - B^2 - C^2$.

My question is: What algorithm would you use to draw it?

Seems there are different approaches:

1. Break it into the circle case and line case. Draw each using a dedicated routine. This way, you can use pre-existing drawing routines. There is a problem here, which is that out of many possible floating point values, only one of them is exactly $0$. So the line case happens in one case out of $2^{64}$ (if you use $64$-bit floats). And on top of that, thanks to rounding errors, what *should* be a line can become a circle. The circle case requires finding the centre and radius, but these can both be large values, subject to floating-point rounding errors. You can use a threshold instead of checking whether $A = 0$, but which threshold should get used?
2. Traverse each value of $x$ in the viewport, and compute the (at most) $2$ different values of $y$, and draw those points. Then do the same again, but traversing each value of $y$ and finding $x$.
3. A generalised circle determines a constant-speed motion along it. Use this somehow.
4. A generalised circle determines an [inversion](https://en.wikipedia.org/wiki/Inversive_geometry) through it. Use this fact somehow.

Approach 2 explicitly uses the viewport. Approaches 3 and 4 are vague, but depend on knowing it as well.

What approaches are there?

**Tags:** computational-geometry, drawing

> **Comments:**
> **username_0**: I don't know whether this counts as a computer graphics question. This is cross-posted from Maths SE, because I'm not sure whether it's appropriate for there either.  
> **username_0**: @username_1 You haven't read my question. That's my suggestion 1. I've commented on it.  
> **username_1**: As you noted, I am suggesting the first case, as zero can be represented exactly in a computer, so it's either a circle or it is a line, there is no middle ground. If the above is a circle then the following decomposition should be valid: $(x-x_0)^2 + (y-y_0)^2 = R^2$, where $x_0 = -\frac{B}{2A}$, $y_0 = -\frac{C}{2A}$, $R^2 = -D + x_0^2 + y_0^2$, and you can use some standard algorithm to draw the circle. If you're worried about the division you can check for infs and nans, and if that occurs I would just deem it to inaccurate to draw.  
> **username_1**: If $A$ is slightly bigger than zero then this is still a circle mathematically. However due to finite precision $x_0, y_0, R$ will be very inaccurate (e.g. potentially even infs or nans). This is the reality of using a finite precision machine for computations - it cannot handle close to singular situations. Notably what occurs is that the radius becomes closer and closer to infinite, and finite precision does not allow to bridge this gap in a continuous manner. A computer cannot represent a circle with an arbitrarily large radius. Purely visually you can swap it for the line though.  
> **username_1**: I have a typo btw, $R^2$ should read: $R^2 = -D/A + x_0^2 + y_0^2$.  

---

## 0 answers

