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 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?

  • $\begingroup$ 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. $\endgroup$
    – wlad
    Oct 9, 2022 at 9:56
  • $\begingroup$ @lightxbulb You haven't read my question. That's my suggestion 1. I've commented on it. $\endgroup$
    – wlad
    Oct 9, 2022 at 17:47
  • $\begingroup$ 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. $\endgroup$
    – lightxbulb
    Oct 9, 2022 at 17:58
  • $\begingroup$ 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. $\endgroup$
    – lightxbulb
    Oct 9, 2022 at 18:48
  • $\begingroup$ I have a typo btw, $R^2$ should read: $R^2 = -D/A + x_0^2 + y_0^2$. $\endgroup$
    – lightxbulb
    Oct 9, 2022 at 18:52


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.