0
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\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

0

Reset to default

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.