7

I want to fill a circle with alternate colors like a lollipop by drawing circumferences of increasing radius on a Cell matrix. I am currently using the Midpoint circle algorithm to get the points. The problem I have is that there are some gaps when filling a circle this way.

In the example below (original is number 1) I used pink and white to highlight the various circumferences. (Notice the black pixels)

The code of my implementation (1) is here: https://gist.github.com/beppe9000/e4a29542a76b8ee3b47f

I am looking for an algorithm that does not produce such gaps.

Update

It is important that the circle is filled using concentric passes because i also update some metadata in the cells as I get them in groups (each one corresponding to a circumference). I tried simplifying the problem, so you didn't get it all, I'm sorry if I'm not a great communicator... ;)

Basically I need the circumferences produced to be perfectly contiguous. That means no gaps between circles of radius n and n+1

Update 2

I tried the brute-force algorithm with some results, still lacking the ability to get individual circumferences. In particular I had great hopes for number 3... enter image description here

  • You have a Moiré pattern there. – user40980 Jun 22 '15 at 3:14
  • Do you want to fill a circle with one color, and showed us the alternating colors above just to highlight how your algorithm works? Or do you really want do draw a circle with alternating (for instance, white and pink) stripes? – Doc Brown Jun 22 '15 at 7:50
  • 3
    Imho, unless some genius proves otherwise, i think you will always face this problem with 1 pixel width ring. Try 2 pink circles then 2 white circles. With 3 I would guess the problem will disappear completely. – Mandrill Jun 22 '15 at 14:39
  • 2
    So what you have is a slow brute-force algorithm which produces the pictures (4) and (5), but you are looking for an efficient algorithm where you input a radius and get as a result exactly list of coordinates of the equally colored cells which correspond to that radius? Is that your question? Please clarify. – Doc Brown Jun 22 '15 at 15:51
  • 3
    Please note, the level of perfection you seem to be looking for probably isn't possible with a Cartesian coordinate system (your graphics card and monitor ...). – svidgen Jun 22 '15 at 16:30
3

The midpoint algorithm gives you the set of points lying "exactely" a given distance from the center.

What you would want to do is to use another algorithm where you test if the distance is lower than (and not equal to) the radius.

The brute force algorithm would be to check every cell in the grid, but if you really want to be efficient, you could perform neighbourhood testing (similar to the midpoint algorithm) and perform some sort of line scan starting from the top (x_start = x_radius; y_start = y_radius + radius).

An example in pseudo-code:

foreach i in i_range:
    foreach j in j_range:
        y = i - ry
        x = j - rx
        if (x^2 + y^2)^0.5 - 0:
           paint_cell(i,j)
  • 2
    One easy optimization to this brute force approach would be to use symmetry: only 1/4 of the points need to be tested. – user22815 Jun 22 '15 at 3:05
  • 1
    A simplified variant of a Scanline fill should be fairly efficent. The start and end points of each line should be easily calculated. – Kelly Thomas Jun 22 '15 at 3:29
  • See the qustion: it has been updated to explain better. – beppe9000 Jun 22 '15 at 13:39
  • Oh, like a lollipop then... That is game changing, of course. – heltonbiker Jun 22 '15 at 14:08
  • @beppe9000 Imagine you draw the inner cicles first, and then the outer ones. The innermost circle, the tinyest one, would be a single pixel. Then the second one would depend on what "contiguous" mean: if you need the pixels to be side-contiguous, then you'd get only squares, unless you accept more than one pixel thickness... Can you visualize it? – heltonbiker Jun 22 '15 at 14:14
3

Not exactly what you asked but I think just a vertical scan is easier:

line((x_center-r,y_center)-(x_center+r,y_center))
for(y=y_center+1;y_center+r;y++) {
    w=sqrt((r+y)(r-y))
    x_min=x_center-w
    x_max=x_center+w
    y_mirror=2*y_center-y
    line((x_min,y)-(x_max,y))
    line((x_min,y_mirror)-(x_max,y_mirror))
}

So if a circle in your screen has 101 pixels diameter, it will require the calculation of 50 square roots and drawing 101 horizontal lines (there are 2 lines of each length).

  • 1
    I don't see why you think this doesn't answer the question - it's an algorithm which draws a filled circle. – Philip Kendall Jun 22 '15 at 5:45
  • @PhilipKendall I need access to the intermediate circumferences to set some metadata. – beppe9000 Jun 22 '15 at 16:12
1

It is important that the circle is filled using concentric passes

You can't draw anything "perfect" using "concentric passes" on Cartesian coordinate system, which is ultimately what you need to do. The pixels just don't align with your N-step-radius circles. But, you can make a good approximate. And the method you use should depend on what your ultimate goal.

... because i also update some metadata in the cells as I get them in groups (each one corresponding to a circumference).

This makes it sounds like you need to operate point-by-point on all points that could be part of the circle, determining each one's "relationship to the center" of the circle as you go.

So, what you'll end up with is something very similar to heltonbiker's solution, but that paints and/or sets meta-data for every point as it passes. You may want two functions:

// a simple distance function
var distanceFrom = function(x, y, cx, cy) {
    return Math.sqrt(
        Math.pow(cx - x, 2) + Math.pow(cy - y, 2)
    );
};

// something to determine the "value" of a pixel, based on the circle center
var getValue = function(x, y) {

    // in your real application, these three vars will be parameters ...
    var radius = 7;
    var center_x = 7;
    var center_y = 7;

    var d = distanceFrom(x, y, center_x, center_y);
    if (d <= radius) {
        return d / radius;
    } else {
        return 1; // white/off
    }
}; // getValue()

And a simple loop ... somewhere in an appropriately named method:

// something that loops through all the relevant pixels.
// ... this does NOT need to look at every pixel. it only
// needs to look at the pixels within the box that bounds
// your circle.
for (var y = 0; y < 15; y++) {
    for (var x = 0; x < 15; x++) {
        paint(x, y, getValue(x, y));
    }
}

See this fiddle, scaled up by 32 to show the "pixels."

pixelated circle gradient

I think you can see from the result drawing concentric circles would force matches between pixels and circles that are just ugly. The pixel-by-pixel approach not only ensure that every pixel is valued and drawn, but that each pixel can be associated with the most-relevant circle or radius.

If you're looking for a non-gradient pattern, you just need to update your value function:

// alternating / concentric-ish circles ....
var getValue = function(x, y) {
    var radius = 7;
    var center_x = 7;
    var center_y = 7;
    var d = distanceFrom(x, y, center_x, center_y);
    if (d <= radius) {
        return Math.floor(d) % 2 === 0 ? 0 : 0.5;
    } else {
        return 1; // white/off
    }
}; // getValue()

Visible as a fiddle here. And here's what it produces:

concentric-ish circles

And, of course, if you're looking to color a single "circle" that is compatible with your other circles, you could start with the unoptimized approach of scanning the whole circle area, and just drawing the pixels whose floored or rounded distance from the center matches an integer (or floored/rounded) radius.

var getValue = function(x, y) {
    var radius = 7;
    var center_x = 7;
    var center_y = 7;

    // the radius of the "circle" we're drawing (should be parametized)
    var draw_only = 5;

    var d = distanceFrom(x, y, center_x, center_y);

    // the new condition is tacked on here:
    if (d <= radius && Math.floor(d) === draw_only) {
        return Math.floor(d) % 2 === 0 ? 0 : 0.5;
    } else {
        return 1; // white/off
    }
}; // getValue()

It's not efficient, but the rings it draws should align with those from the example with the alternating colors:

enter image description here

See the fiddle.

If you're looking to do what I've done the last example, drawing only a single ring at a time, it can potentially be optimized (for large circles) by walking around the circle and processing blocks of pixels that are "probably" going to be colored. Something similar to this totally untested code ...

// radius of the circle we want to draw
var radius = 5;
for (var deg = 0; deg < 360; deg++) {
  var radians = 2 * Math.PI * deg/360;

  var focus_x = Math.floor(radius * Math.cos(radians));
  var focus_y = Math.floor(radius * Math.sin(radians));

  // i'm not sure how much "fuzz" you need ... play with it:
  var x1 = focus_x - 2;
  var x2 = focus_x + 2;
  var y1 = focus_y - 2;
  var y2 = focus_y + 2;

  for (var y = y1; y < y2; y++) {
    for (var x = x1; x < x2; x++) {
      paint(x, y, getValue(x, y), radius); // again, radius needs to be parametized
    }
  }
}

Disclaimer: Neither this answer nor the associated fiddle are intended to demonstrate good or proper usage of the HTML5 canvas.

1

The most simple approach I can think of is: start with a fully filled circle in pink, and (use @Mandrill's answer for example), and draw only the white circles afterwards over the pink circle, using your existing Midpoint algorithm. That will leave no black spots, all the black spots get the color you started with.

However, if you do not want to draw anything twice, here is an idea how to approach this:

  • draw the "circumferences" in the order of increasing radius

  • modify the midpoint algorithm the following way: whenever you set a cell in the left half of your circle to a specific color, test if there are black spots next to the right of that cell, in the same row. If that is the case, fill them with the current color, too, until you reach a non-black spot or the middle column. Do the same if you are coloring a cell in the right half, but for those cells fill the black spots to the left in the current row.

For example:

enter image description here

The advantage of this approach is that your "intermediate circles" always fulfill your requirements, not just the final result. And the "black spots" are not filled all with the the same "preferred color", but you get a more evenly distributed ratio of white-to-pink. The running time is still proportional to number of colored cells.

This can be easily modified to create an algorithm which produces the coordinates of "circumference" of a specific radius in any order you like. Create a function

  IEnumerable<Point> MidpointCircle(int radius,Point center){...}

Then use it like this way (rough outline in C#, beware, air code):

  IEnumerable<Point> Circumference(int radius,Point center)
  {
       if(radius==0)
          yield break;
       var points = MidpointCircle(radius,center);
       var innerPoints =new Hashset(MidpointCircle(radius-1,center));
       foreach(var p in points)
       {
            yield return p;
            if(p.X<center.X)
            {
               Point q = new Point(p.X+1,p.Y);
               while(q.X<center.X && !innerPoints.Contain(q))
               {
                  yield return q;
                  q = new Point(p.X+1,p.Y);
               }
            }
            else
            {
               // similar code for points right from the center
            }
       }
  }

This should produce you the result you are looking for.

  • I have updated the question with some results. I will be trying this... – beppe9000 Jun 22 '15 at 13:38
1

Late to the party, but I have found Tony Barrera's "4-connected" circle algorithm in Will Perone's site, it seems to fill the gaps and be the fastest at the same time, Javascript code below or in fiddle. This answer may apply also to Circle with thickness drawing algorithm.

var canvas = document.querySelector('canvas')
var ctx = canvas.getContext('2d');
ctx.fillStyle = 'blue';

var DrawPixel = function (x, y) {
    ctx.fillRect(x, y, 1, 1);
}

function Barrera4(x0, y0, radius) {
    var x = 0;
    var y = radius;
    var d = -(radius >>> 1);

    while(x <= y) {
        DrawPixel(x + x0, y + y0);
        DrawPixel(y + x0, x + y0);
        DrawPixel(-x + x0, y + y0);
        DrawPixel(-y + x0, x + y0);
        DrawPixel(-x + x0, -y + y0);
        DrawPixel(-y + x0, -x + y0);
        DrawPixel(x + x0, -y + y0);
        DrawPixel(y + x0, -x + y0);

        if(d <= 0) {
            x++;
            d += x;
        } else {
            y--;
            d -= y;
        }
    }
}

for(var r = 100; 0 < r; r--) {
    ctx.fillStyle = (r%8 < 4) ? 'pink' : 'white';
    //DrawCirle(120, 120, r);
    Barrera4(120, 120, r);
    //Barrera8(120, 120, r);
}
canvas {
  background-color: black;
}
<canvas width=300 height=300></canvas>
0

If you are interested in drawing concentric circles and don't mind performing a broard sweep of the AABB then the test to perform on each pixel is:

distanceFromCenter <= radius && distanceFromCenter > (radius - someThreshold)

Or as a more concrete example:

void drawCircle(Point center, int radius, int thickness, Color color) {
    for (var x = center.x - radius; x < center.x + radius; x++) {
        for (var y = center.y - radius; y < center.y + radius; y++) {
            float distance = distanceFrom(x, y, center.x, center.y);
            if (distance <= radius && distance > radius - thickness) {
                drawPixel(x, y, color);
            }
        }
    }
}

If these circles will need to be updated frequently and performance becomes an issue, then the relevant pixels could be stored a point array or a mask.

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.