Text on a circle

Question

Write a program or function that prints an input string around the discrete circle that has the minimum possible radius. For example, for input This is an example, your program should output:

  a si   
 n     s 
        i
e       h
x       T
a        
m        
 p       
  le     

Circle generation

You shall use the Midpoint circle algorithm to compute the coordinates of each point of the discrete circle. You can find examples on how to implement this algorithm on this Wikipedia page.

Here is the pseudo code of the algorithm (based on Wikipedia's C example):

integer x = radius
integer y = 0
int decisionCriterion = 1 - x

while y <= x 
    point at coordinates (x,y) belongs to the circle   // Octant 1
    point at coordinates (y,x) belongs to the circle   // Octant 2
    point at coordinates (-x,y) belongs to the circle  // Octant 4
    point at coordinates (-y,x) belongs to the circle  // Octant 3
    point at coordinates (-x,-y) belongs to the circle // Octant 5
    point at coordinates (-y,-x) belongs to the circle // Octant 6
    point at coordinates (x,-y) belongs to the circle  // Octant 7
    point at coordinates (y,-x) belongs to the circle  // Octant 8

    y++
    if decisionCriterion <= 0
        decisionCriterion += 2 * y + 1
    else
        x--
        decisionCriterion += 2 * (y - x) + 1
end while

You may use a different algorithm if and only if it produces the exact same circles that the Midpoint circle algorithm produces, for all radiuses.

The circle must have the smallest possible radius that still allows to write all letters of the input.

If the circle ends up with more points than the number of characters in the string, then the last filling characters will be spaces .

The first character of the input must be printed on the point with coordinates (Radius,0). The subsequent characters are printed in an anticlockwise fashion.

Inputs

The input is a string of any ASCII characters between the space (32) and the tilde ~ (126).

You may assume the input will always be valid, shorter than 256 characters and at least 5 characters long.

The input may be taken from STDIN, or as a function parameter, or anything similar.

Outputs

You may output the result either to STDOUT, or return it as string from a function.

You may have trailing spaces, provided that it does not cause the line to exceed the longest line (the middle one) (as such, the middle line cannot have trailing spaces).

A trailing new line is permitted.

Test cases

Input: Hello, World!
Output:
  ,ol  
     l 
W     e
o     H
r      
 l     
  d!   


Input: 4 8 15 16 23 42
Output:
  51   
     8 
1      
6     4

 2   2 
  3 4  


Input: Programming Puzzles & Code golf
Output:
     gnim    
  uP     ma  
 z         r 
 z         g 
l           o
e           r
s           P

&            

 C           
  od     f   
    e Gol    


Input: Ash nazg durbatuluk, ash nazg gimbatul, ash nazg thrakatuluk agh burzum-ishi krimpatul.
Output:
            zan hsa ,           
           g         ku          
        ig             lu        
      bm                 ta      
     a                     b     
    t                       r    
   u                         u   
   l                         d   
  ,                              
                              g  
 a                             z 
 s                             a 
h                               n

n                               h
a                               s
z                               A
g                                

t                                
h                                
 r                               
 a                             . 
  k                           l  
  a                           u  
   t                         t   
   u                         a   
    l                       p    
     u                     m     
      k                  ri      
        ag              k        
          h          hi          
            burzum-is            

Scoring

This is code-golf, so the shortest answer in bytes wins.

Answer 1

C, 367 Bytes

#include<math.h>
main(){char*m="12345678",b[9999];int p,i,n,q,c,l=strlen(m),r=1,d,f=0;float o,s;for(;!f;r++){f=0;q=r*r;c=r/4;o=6.3,s=o/99.;memset(b,0,q);for(i=0;i<l;i++){p=1;f=0;while(p&&o>0){d=(c-1+(int)(sin(o)*c))*r+c-1+(int)(cos(o)*c);f+=p=b[d];if(!p)b[d]=m[i];o-=s;}}if(f){for(n=p=0;n<q;n++){p+=c=b[n];putchar(c?c:32);if(n%r==r-1){if(!p)n=q;putchar(10);p=0;}}}}}

Test Here

I'm sure it can be golfed much further but it’s starting to give me a headache.

C, 324 Bytes

Smaller code but the results are not the same as OP's

#include<math.h>
main(){char*m="12345678",b[9999];int q,c,l=strlen(m),r=1,d,i=0;float o;for(;i<l;r++){i=0;c=r/2;q=r*r;memset(b,0,q);for(o=6.28;o>=0&&i<l;o-=0.001){d=(c-1+(int)(sin(o)*c))*r+c-1+(int)(cos(o)*c);if(!b[d]){b[d]=m[i++];}}}for(d=i=0,--r;d<q;d++){i+=c=b[d];putchar(c?c:32);if(d%r==r-1){putchar(10);d=i?d:q;i=0;}}}

       an hsa ,k
      gz       ulu
    ig           ta
   bm             br
  ta               ud
 lu                  g
 ,                   z
a                    an
s
h                     h
                      s
n                     A
a
z
g                     l
 t                   tu
 h                   a
 ra                 mp
  ka               ri
   tu              k
    lu           hi
     k a       -is
       gh burzum

Answer 2

Mathematica, 359 357 354

(L=Length;T=Tuples;c=Characters@#;For[r=1,L[p=RotateRight[SortBy[#,ArcTan@@N@#&]+r+1,L@#/4+1]&@(f=1-r;X=1;Y=-2r;x=0;y=r;q={{0,r},{0,-r},{r,0},{-r,0}};While[x<y,If[f>0,y--;f+=Y+=2];x++;f+=X+=2;q=Join[q,T@{{x,-x},{y,-y}},T@{{y,-y},{x,-x}}]];Union@q)]<L@c,r++];R=2r+1;s="";Do[s=s<>({u,v}/.Thread[p~Take~L@c->c]/.{_,_}->" ")<>If[v==R,"\n",""],{u,R},{v,R}];s)&

Ungolfed:

(
  L = Length;
  T = Tuples;
  c = Characters@#;
  For[r = 1,
   L[
     p = RotateRight[
         SortBy[#, ArcTan @@ N@# &] + r + 1, L@#/4 + 1
         ] &@(
        f = 1 - r;
        X = 1;
        Y = -2 r;
        x = 0;
        y = r;
        q = {{0, r}, {0, -r}, {r, 0}, {-r, 0}};
        While[x < y,
         If[f > 0,
          y--;
          f += Y += 2
          ];
         x++;
         f += X += 2;
         q = Join[q, T@{{x, -x}, {y, -y}}, T@{{y, -y}, {x, -x}}]
         ];
        Union@q
        )] < L@c,
   r++];
  R = 2 r + 1;
  s = "";
  Do[s = s <> ({u, v} /. Thread[p ~ Take ~ L@c -> c] /. {_, _} -> " ") <>
      If[v == R, "\n", ""],
   {u, R}, {v, R}];
  s
  ) &

Answer 3

C, 494 Bytes

This one uses the actual Midpoint circle algorithm:

void main(){char s[]="12345678";int a[9999],b[9999],f=0,c,h,x,y,e,q,t,u,v,g,i,d,l,r=0,k=strlen(s);for(;f<k;r++){c=r;e=r*2+1;q=e*e;memset(b,0,q*4);f=0;l=0;for(i=0;i<8;i++){x=r;y=0;d=1-x;for(x=r,y=0,d=1-x;y<=x;y++,d+=2*d>0?y- --x:y+1){t=(i+1)%4>1;u=t?y:x;v=t?x:y;h=(c+v*(i>3?1:-1))*e+(c+u*(i>1&&i<6?-1:1));if(!b[h])b[h]=f<k?s[f]:0,a[f]=h,f++;}if(i%2){for(g=0;g<(f-l)/2;g++)t=b[a[l+g]],b[a[l+g]]=b[a[f-1-g]],b[a[f-1-g]]=t;}l=f;}}for(i=0;i<q;i++){c=b[i];putchar(c?c:32);if(i%e==e-1)putchar(10);}}

De-golfed Code:

void main() {
    char text[]="Ash nazg durbatuluk, ash nazg gimbatul, ash nazg thrakatuluk agh burzum-ishi krimpatul.";

    char points[9999];
    int pos[9999];

    int sl = strlen(text);
    int r = 0;
    int pc = 0; // point count
    int lc = 0; // last count

    int c, h, x, y, e, q, t, u, v, g, i, d;

    // increase radius until number of points => strlen(text)
    for(; pc<sl; r++) {
        c = r;
        e = r * 2 + 1;
        q = e * e;
        memset(points,0,q);
        pc = 0;
        lc = 0;

        // loop through the octants
        for(i=0; i<8; i++) {

            // midpoint loop
            x = r;
            y = 0;
            d = 1 - x;
            while (y <= x) {

                // calc index of point
                t = (i + 1) % 4 > 1;
                u = t ? y : x;
                v = t ? x : y;
                h = (c + v * (i > 3 ? 1 : -1)) * e + (c + u * (i > 1 && i < 6 ? -1 : 1)); 

                // add point if space is empty
                if(!points[h]) { 
                    points[h] = pc < sl ? text[pc] : 0;
                    pos[pc] = h;
                    pc++;
                }

                y++;
                d += 2 * d > 0 ? y- --x : y + 1;
            }

            if(i % 2) {
                // reverse point order for odd octants
                for(g=0; g<(pc-lc)/2; g++)
                {
                    t = points[pos[lc + g]];
                    points[pos[lc + g]] = points[pos[pc - 1 - g]];
                    points[pos[pc - 1 - g]] = t;
                }
            }
            lc = pc;
        }
    }

    // write output
    for(i=0;i<q;i++)
    {
        c = points[i];
        putchar(c ? c : 32);
        if(i % e == e - 1)
            putchar(10);
    }
}