Drawing Circle with Eric Andres Method

[scalion]

My source :

fr.wikipedia.org/wiki/Algorithme_de_trac%C3%A9_de_cercle_d%27Andres

This particular method of tracing a circle uses integers (and not floats) and above all allows to cover the entire tiling of pixels. This is very useful if you need to scan a surface starting from a central point, as is the case in image analysis in the context of image recognition.

Given that at the moment I am doing a little research in artificial intelligence, precisely in deep learning, this function will surely be of great help to me.

The source code file : Tracer Cercle Andres.G32 (3.1 KB)

Same thing as text :

Global Long R
FullW 1
Global Long X, Y
Global Long CenterX = _X / 2
Global Long CenterY = _Y / 2
Do
 GetCercleAndres(CenterX, CenterY, R, X, Y, True)
 While GetCercleAndres(CenterX, CenterY, R, X, Y)
   Plot X, Y
 Wend
 Inc R
 If R > _Y / 2
   R = 0
   RGBColor Rnd * &hffffff
 EndIf
 PeekEvent
Loop Until Me Is Nothing
Function GetCercleAndres(CenterX As Long, CenterY As Long, Radius As Long, ByRef XResult As Long, ByRef YResult As Long, Optional Start As Boolean = False) As Boolean
 
 ' Author : Nicolas Rey
 ' Code GFA-Basic : 18/01/2022
 ' This function is designed to image recognition for define pixel direction
 ' It permit to find fastly the smallest distance around pixel
 ' that indicate the perpendicular direction is the owner segment
 ' using the Eric Andres method.
 ' Usage :
 ' Start a sequence with
 '   GetCercleAndres(CenterX, CenterY, Radius, X, Y, True)
 ' Get each pixels of the circle :
 '   PixelFound = GetCercleAndres(CenterX, CenterY, Radius, X1, Y1)
 '   PixelFound = GetCercleAndres(CenterX, CenterY, Radius, X2, Y2)
 '   etc...
 ' until PixelFound = False.
 ' Each pair of pixels are opposites on circle
 ' that mean they have same direction ;).
 
 Static Long D , X, Y, K
 
 If Start = True
   D = Radius - 1
   X = 0
   Y = Radius - 1
   K = 0
   Return True
 EndIf
 
 If Y >= X
   
   If K = 0
     XResult = CenterX + X, YResult = CenterY + Y
   Else If K = 1
     XResult = CenterX - X, YResult = CenterY - Y
   Else If K = 2
     XResult = CenterX + Y, YResult = CenterY + X
   Else If K = 3
     XResult = CenterX - Y, YResult = CenterY - X
   Else If K = 4
     XResult = CenterX - X, YResult = CenterY + Y
   Else If K = 5
     XResult = CenterX + X, YResult = CenterY - Y
   Else If K = 6
     XResult = CenterX - Y, YResult = CenterY + X
   Else
     XResult = CenterX + Y, YResult = CenterY - X
     If D >= 2 * X
       D -= 2 * X + 1
       Inc X
     Else If D < 2 * (Radius - Y)
       D += 2 * Y - 1
       Dec Y
     Else
       D += 2 * (Y - X - 1)
       Dec Y
       Inc X
     EndIf
     
   EndIf
   
   K = (K + 1) % 8
   
   Return True
   
 Else
   
   Return False
   
 EndIf
 
EndFunc
Proc CercleAndres(CenterX As Long, CenterY As Long, Radius As Long)
 
 ' Trace circle using an Eric Andres method.
 ' Particularity : use integer and can cover all pixels (no holes).
 ' This code is adapted from examples found here :
 ' https://fr.wikipedia.org/wiki/Algorithme_de_trac%C3%A9_de_cercle_d%27Andres
 
 Local Long d = Radius - 1 , X = 0, Y = Radius - 1
 
 While Y >= X
   Plot CenterX + X, CenterY + Y
   Plot CenterX + Y, CenterY + X
   Plot CenterX - X, CenterY + Y
   Plot CenterX - Y, CenterY + X
   Plot CenterX + X, CenterY - Y
   Plot CenterX + Y, CenterY - X
   Plot CenterX - X, CenterY - Y
   Plot CenterX - Y, CenterY - X
   
   If d >= 2 * X
     d -= 2 * X + 1
     Inc X
   Else If d < 2 * (Radius - Y)
     d += 2 * Y - 1
     Dec Y
   Else
     d += 2 * (Y - X - 1)
     Dec Y
     Inc X
   EndIf
   
 Wend
 
EndProc


[scalion]

Next Step : Define a direction.

To classify identified line in an image i imagine some things : Lenght, position in image and .... direction.

To parsing this qualifier i need simplify direction by vertical to horizontal orientation.

I writed this function :


Function GetOctant(X%, Y%) As Long Naked
 
 ' Author : Nicolas Rey - email : [e-mail]
 ' Code GFA-Basic32 : 19/01/2022
 '
 ' This Function is designed to simplify convolution layer in image recognition.
 ' The returned value is an orientation qualifier for an identified line in an image.
 ' Return an integer indicating the direction of integer vector X,Y
 '
 ' 0 = Vertical        4 = horizontal
 ' 1 = rapid ascent    5 = slow descent
 ' 2 = normal ascent   6 = normal descent
 ' 3 = slow ascent     7 = rapid descent
 '
 ' Nearest orientation are easy to found
 ' (Octant+1) % 8 or (Octant+7) % 8 is the closest
 ' (Octant+2) % 8 or (Octant+6) % 8 is little closer
 ' (Octant+3) % 8 or (Octant+5) % 8 is even closer
 ' (Octant+4) % 8 is the perpendicular.
 '
 
 Static Double F, F6 = 2 / 3
 
 If X = 0 Return 0
 
 F = Y / X
 
 If F <= -5 Return 0
 If F <= -1.5 Return 7
 If F <= -F6 Return 6
 If F <= -0.2 Return 5
 If F <= 0.2 Return 4
 If F <= F6 Return 3
 If F <= 1.5  Return 2
 If F < 5 Return 1
 
 Return 0
 
EndFunc

A little demonstration using this function : Demo Octant.G32 (4.15 KB)

That' all today

[(X)]

Very slick! (efficient, smooth, smooth-running, polished, well organized, well run, streamlined, skillful, deft, adroit, dexterous, masterly, professional)

[scalion]

In the same vein as drawing a circle with integers, here is a method to draw a line with integers. I specify that I entirely invented this method.

Proc DrawLineNicolasRey(x1%, y1%, X2%, y2%) Naked
 
 ' Author : Nicolas Rey
 ' Code GFA-BASIC32 :  20/01/2022
 ' Subject : Draw a line using integer
 ' This algorithm is faster than Brensenham algorithm.
 ' This is a simple demonstration using GDI drawing who is not fast.
 ' To see it in complete power try it with Direct2D or DIB poking ;).
 ' Working principle :
 ' I consider the pixel as a reduced version of the line segment
 ' and its dimension equal to the longest dimension in X or Y.
 ' If the longest length is X, at each pixel (X*X) , a virtual
 ' line of length X is drawn and we increment in Y.
 ' If Y exceeds the virtual screen of the pixel, when Y>= LX,
 ' I go to the line above or below and Y is readjusted by subtracting LX.
 ' Same thing in the case where Y is larger going from one column to another.
 
 Local Long X = Abs(X2 - x1) + 1
 Local Long Y = Abs(y2 - y1) + 1
 Local Long A = 0
 Local Long PX = Sgn(X2 - x1)
 Local Long PY = Sgn(y2 - y1)
 
 If X > Y
   
   Do
     Plot x1, y1
     Exit If x1 = X2
     A = A + Y
     If A >= X
       A = A - X
       y1 = y1 + PY
     EndIf
     x1 = x1 + PX
   Loop
   
 Else
   
   Do
     Plot x1, y1
     Exit If y1 = y2
     A = A + X
     If A >= Y
       A = A - Y
       x1 = x1 + PX
     EndIf
     y1 = y1 + PY
   Loop
   
 EndIf
 
EndProc

[scalion]

Benchmark report for lines drawing GDI / Poke in DIB / Direct2D :

GDI FPS = 18.5809021366948
DIB FPS = 62.1862702480724
D2D FPS = 87.0471724547467

Benchmark integer lines.G32 (13.17 KB)