Draw-circle

Drawing Circle

  Given an image with width $w$ and height $h$. Then any pixel $P=(x,y)$ in the image satisfies that $0\leq x<w$, $0\leq y<h$, and $x$, $y$ are integers.

  Let $C$ be the circle of radius $r_0$ with center at $(x_0,y_0)$

$$(x-x_{0})^{2}+(y-y_{0})^{2}=r_{0}^{2}. \quad \quad \quad \quad (1)$$

  Let $x=x_{0}-r_{0}, x_{0}-r_{0}+1,\dots ,x_{0}+r_{0}$, we can obtain

$$y=y_{0}\pm \sqrt{r_{0}^{2}-(x-x_{0})^{2}}. \quad \quad \quad \quad (2)$$

  Furthermore,

$$y_{1} = [y_{0}-\sqrt{r_{0}^{2}-(x-x_{0})^{2}}+0.5], \quad \quad \quad \quad (3)$$ $$y_{2} = [y_{0}+\sqrt{r_{0}^{2}-(x-x_{0})^{2}}+0.5], \quad \quad \quad \quad (4)$$

in which $[\cdot ]$ is the rounding operation.

  Since we are drawing the circle $C$ of the formula $(1)$ in a discrete space, the allowing error is $\varepsilon = 0.5$, then it gets

$$(r_{0}-\varepsilon)^{2} \leq (x-x_{0})^{2} + (y-y_{0})^{2} \leq (r_{0}-\varepsilon)^{2}. \quad \quad \quad \quad (5)$$

  Let $(x-x_{0})^{2}=(y-y_{0})^{2}$, combine with formula $(1)$, we can obtain 4 points in the space $R \times R$, i.e.

$$A_{0} = (x_{0}-\sqrt {\frac {r_{0}^{2}}{2}}, y_{0}+\sqrt {\frac {r_{0}^{2}}{2}}),$$ $$A_{1} = (x_{0}-\sqrt {\frac {r_{0}^{2}}{2}}, y_{0}-\sqrt {\frac {r_{0}^{2}}{2}}),$$ $$A_{2} = (x_{0}+\sqrt {\frac {r_{0}^{2}}{2}}, y_{0}-\sqrt {\frac {r_{0}^{2}}{2}}),$$ $$A_{3} = (x_{0}+\sqrt {\frac {r_{0}^{2}}{2}}, y_{0}+\sqrt {\frac {r_{0}^{2}}{2}}).$$

  They divide the circle $C$ into four arcs in counter-clockwise direction, i.e. $\widehat{A_{0}A_{1}}$, $\widehat{A_{1}A_{2}}$, $\widehat{A_{2}A_{3}}$, $\widehat{A_{0}A_{3}}$.

  Now let us consider arc $\widehat{A_{0}A{1}}$, we know that $x = x_{0}-r_{0},x_{0}-r_{0}+1, \cdots, x_{0}-\sqrt {\frac {r_{0}^{2}}{2}}$, according to formula $(5)$, it has

$$y_{0}+s(x) \leq y \leq y_{0}+e(x), \quad \quad \quad \quad (6)$$ $$y_{0}-e(x) \leq y \leq y_{0}-s(x), \quad \quad \quad \quad (7)$$

in which

$$s(x)=[\sqrt{r_{0}^{2}-(x-x_{0})^{2}-r_{0}}],x > x_{0}-r_{0}, \quad \quad \quad \quad (8)$$ $$s(x_{0}-r_{0})=0, \quad \quad \quad \quad (9)$$ $$e(x)=[\sqrt{r_{0}^{2}-(x-x_{0})^{2}+r_{0}}], \quad \quad \quad \quad (10)$$

and $[\cdot ]$ is the rounding operation.

  Formula $(6)-(10)$ determine all the edge points(pixels) in the arc $\widehat{A_{0}A{1}}$.

  Notice that $\widehat{A_{0}A_{1}}$ is symmetric to $\widehat{A_{1}A_{2}}$ with respect to the straight line $(x-x_{0})-(y-y_{0})=0$, $\widehat{A_{0}A_{1}}$ is symmetric to $\widehat{A_{2}A_{3}}$ with respect to the center $(x_{0},y_{0})$, and $\widehat{A_{0}A_{1}}$ is symmetric to $\widehat{A_{0}A_{3}}$ with respect to the straight line $(x-x_{0})+(y-y_{0})=0$, then it can determine all the edge points of the other three arcs on the basis of formula $(6)-(10)$.

  Explicitly, for an arbitrary point $P=(x,y)$ in the arc $\widehat{A_{0}A_{1}}$, then $P_{1}$ is on the arc $\widehat{A_{1}A_{2}}$, $P_{2}$ is on the arc $\widehat{A_{2}A_{3}}$, and $P_{3}$ is on the arc $\widehat{A_{0}A_{3}}$, in which

$$P_{1}=(x_{0}+y_{0}-y,x_{0}+y_{0}-x),$$ $$P_{2}=(x_{0}+y_{0}-x,x_{0}+y_{0}-y),$$ $$P_{3}=(x_{0}-y_{0}+y,y_{0}-x_{0}+x),$$

it’s obvious that these four arcs form a complete circle.

  Suppose we plot a black circle in a white background image. Next, we need to deal with the anti-aliasing problem. We have discussed that the circle is symmetrical, so it only have to settle the staircase artifact of the arc $\widehat{A_{0}A_{1}}$, and the other three will be resolved in the same way.

  And the arc is determined by $(6)-(10)$. Let $\ell _{1}$ and $\ell _{2}$ denote the arcs determined by the formulas of $(6)$ and $(7)$ respectively. Moreover, $\ell _{1}$ is symmetric to $\ell _{2}$ with respect to the straight line $y = y_{0}$.

  We will see that arc $\ell _{1}$ consists of vertical straight line segments.

  For

$$\forall x_{n} \in S=\{ x_{0}-r_{0},x_{0}-r_{0}+1, \cdots, x_{0}-\sqrt {\frac {r_{0}^{2}}{2}} \},$$

we obtain the following straight line segment

$$x = x_{n}, \quad y_{0}+s(x_{n}) \leq y \leq y_{0}+e(x_{n}). \quad \quad \quad \quad (11)$$

  Let $B_{0}=(x-1,y)$, $B_{1}=(x,y)$, $B_{2}=(x+1,y)$, in which $B_{1}$ is an arbitrary point in the straight line segment $(11)$.

  For an arbitrary pixel $P$ in the image, its color was denoted by $rgb(P)=(r,g,b)$ (Notice: We only discuss the three channels image here).

  In order to settle the staircase artifact, we need to find a proper color of $B_{0}$ and $B_{2}$ which make the transition between the circle and the white background more smooth.

  We set $v_{b}=(255,255,255)$ be the background color (white) and $v_{f}=(0,0,0)$ be the front color (black), then $rgb(B_{1})=v_{f}$ is a black pixel.

  Here, we give a simple solution, we just let $rgb(B_{0})=rgb(B_{1})=\frac{1}{3}(v_{f}+v_{b})=(85,85,85)$.

   Asserstion 1:
  Arc $\widehat{A_{0}A_{1}}$ and arc $\widehat{A_{2}A_{3}}$ consist of vertical straight line segments respectively.

   Assertion 2:
  Arc $\widehat{A_{1}A_{2}}$ and arc $\widehat{A_{0}A_{3}}$ consist of horizontal straight line segments respectively.

  By the symmetrical of the circle, we just need to consider arc $\widehat{A_{0}A_{1}}$. And if we can proof that $\ell _{1}$ consists of vertical straight line segments, then the above assertions are correct.

   Assertion 3:
  Arc $\ell _{1}$ is make up of vertical straight line segments.

  Given two adjacent straight line segments of arc $\ell _{1}$ which are determined by $(6)$ as follow

$$x = x_{1}, \quad \quad s_{1} \leq y \leq e_{1},$$ $$x = x_{2} = x_{1} + 1, \quad \quad s_{2} \leq y \leq e_{2},$$

if we can verify $\mid s_{2}-e_{1} \mid \leq 1$, then the assertion 3 is correct.

  Let

$$x(k)=x_{0}-r_{0} + k, \quad k=0,1,\cdots , [\frac{r_{0}}{\sqrt{2}}+0.5].$$

  Define the difference value as follow:

$$\triangle \ell (k)= s(x_{0}-r_{0}+k)-e(x_{0}-r_{0}+k-1), \quad k=1,\cdots , [\frac{r_{0}}{\sqrt{2}}+0.5]. \quad \quad \quad \quad (12)$$

  According to formula $(8)-(10)$, it gets

$$\triangle \ell (k)=\frac{-2k+1}{\sqrt{f(k)}+\sqrt{f(k)+2k-1}}, \quad \quad \quad \quad (13)$$

where $f(k)=-2k^{2}+2r_{0}k-r_{0}$.

  Then we have

$$\mid {\triangle {\ell {(k)}}} \mid \leq \frac {2k-1}{2 \sqrt{f(k)}}. \quad \quad \quad \quad (14)$$

  Let

$$F(x)=4f(k)-(2k-1)^{2}, \quad 1 \leq k \leq \frac{r_{0}}{\sqrt{2}}, \quad \quad \quad \quad (15)$$

it is easy to show that $F(x)$ is monotonic increasing, then

$$F(x) \geq F(0), \quad \quad \quad \quad (16)$$

in which $F(0)=4r_{0}-5$, combine formula $(13)-(16)$, and if $r_{0} \geq 2$, we obtain

$$\mid \triangle \ell (k) \mid \leq 1.$$

  Hence, $\mid s_{2}-e_{1} \mid \leq 1$ for any $x \in S=\{ x_{0}-r_{0},x_{0}-r_{0}+1, \cdots, x_{0}-\sqrt {\frac {r_{0}^{2}}{2}} \}$.

  Let $C_{1}=(x_{0}-r_{0},y_{0})$, $C_{2}=(x_{0},y_{0}-r_{0})$, $C_{3}=(x_{0}+r_{0},y_{0})$,$C_{4}=(x_{0},y_{0}+r_{0})$, if $r_{0}=1$, then the circle is formed by these four points.

  It is obivious that $\ell _{1}$ and $\ell _{2}$ is connected by point $(x_{0}-r_{0},y_{0})$, and $A_{0}, A_{1}, A_{2}, A_{3}$ joint the four arcs together, so it have formed a complete circle.

Done !

Elliptic Curve

  I just want to show the elliptic curve here.

$$y^2=x^3+ax+b,$$

in which

$$4a^{3}+27b^{2}\neq 0.$$

本文作者： SpongeDog
本文链接： https://spongedog20.github.io/2019/12/17/draw-circle/
版权声明： 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处！

赏

谢谢您请我吃糖果

微信