Pixels inside a circumference

Question

I have a bitmap and I need to draw a circle on it. For now I've only drawn the pixels of the circumference. How can I get the other pixels without use the distance function that is expansive? This is my code

public void FindMostIntenityPixelInCircle(int x0, int y0, int radius, List<Point> intensities)
{
  Bitmap bitmap = ((Bitmap)(_smartLabForm.pictureBoxGreenImage.Image));
  int x = radius;
  int y = 0;
  int radiusError = 1 - x;
  while (x >= y)
  {
    intensities.Add(new Point(x + x0, y + y0));
    intensities.Add(new Point(y + x0, x + y0));
    intensities.Add(new Point(-x + x0, y + y0));
    intensities.Add(new Point(-y + x0, x + y0));
    intensities.Add(new Point(-x + x0, -y + y0));
    intensities.Add(new Point(-y + x0, -x + y0));
    intensities.Add(new Point(x + x0, -y + y0));
    intensities.Add(new Point(y + x0, -x + y0));
    if (radiusError < 0)
    {
      radiusError += 2 * y + 1;
    }
    else
    {
      x--;
      radiusError += 2 * (y - x) + 1;
    }
  }
}

"Most" in the function name suggests you should be comparing values (perhaps after colorspace conversion), not adding all of them into a list. — Ben Voigt, Mar 03 '15 at 15:28
Yes, I have a MarchingSquare path and for each point of the path I need to draw a circle with the center in that point and a given ray. Inside that circle I should find the pixel with the biggest intensity of green — Martina, Mar 03 '15 at 15:30
Is there a reason to not use the draw and fill methods in the graphics object? [See here](http://stackoverflow.com/questions/28830821/preserve-painting-after-resize-or-refresh/28834298#28834298) In your case you use a Graphics created from the Bitmap, probably! Also [here](http://stackoverflow.com/questions/27337825/picturebox-paintevent-with-other-method/27341797?s=2|0.6933#27341797) for the difference of drawing on a control and into a bitmap.. — TaW, Mar 03 '15 at 16:09
..If you only want to __find__ the pixels inside I suggest using a FloodFill function. [Here](http://stackoverflow.com/questions/28373615/create-custom-shape-for-button/28376826?s=2|0.2668#28376826) is one that is non-recursive. Note that it will&must change the pixels in the process, so to get only the pixel coordinates without changing them you may use a dummy Btimap to use the floodfill on.. — TaW, Mar 03 '15 at 16:17
..but if it will always be a circle you could simply scan the pixels line by line going through your list.. — TaW, Mar 03 '15 at 16:29

TaW · Accepted Answer · 2015-03-03T19:33:26.847

To get a List<Point> of points inside a given circle you can let GDI+ do the work for you:

List<Point> PointsInCircle(int diameter)
{
    List<Point> points = new List<Point>();
    Color black = Color.FromArgb(255, 0, 0, 0);
    using (Bitmap bmp = new Bitmap(diameter, diameter))
    using (Graphics g = Graphics.FromImage(bmp))
    {
        g.Clear(Color.White);
        g.FillEllipse(Brushes.Black, 0, 0, diameter, diameter);
        for (int y = 0; y < diameter; y++)
            for (int x = 0; x < diameter; x++)
                if (bmp.GetPixel(x, y) == black) points.Add(new Point(x, y));
    }
    return points;
}

To use the list on a circle somewhere inside a bitmap you will simply have to add the offsets of the circle center to the list points..

To make the routine faster you can use LockBits:

List<Point> PointsInCircleFast(int diameter)
{
    List<Point> points = new List<Point>();
    Color black = Color.FromArgb(255, 0, 0, 0);
    using (Bitmap bmp = new Bitmap(diameter, diameter,PixelFormat.Format32bppArgb))
    {
        using (Graphics g = Graphics.FromImage(bmp))
        {
            g.Clear(Color.White);
            g.FillEllipse(Brushes.Black, 0, 0, diameter, diameter);
        }
        Size size0 = bmp.Size;
        Rectangle rect = new Rectangle(Point.Empty, size0);
        BitmapData bmpData = bmp.LockBits(rect, ImageLockMode.ReadOnly, bmp.PixelFormat);

        int size1 = bmpData.Stride * bmpData.Height;
        byte[] data = new byte[size1];
        System.Runtime.InteropServices.Marshal.Copy(bmpData.Scan0, data, 0, size1);

        for (int y = 0; y < diameter; y++)
            for (int x = 0; x < diameter; x++)
            {
                int index =  y * bmpData.Stride + x * 4;
                if (data[index] == 0 ) points.Add(new Point(x, y));
            }
    }
    return points;
}

But for really large circles the creation of the large list may be the bottleneck. You can either optimize by creating only a quarter of the points or you can inline the processing..

The color of a pixel inside the inner LockBits loop is accessed like this:

Color c = Color.FromArgb(data[index + 3], data[index + 2], data[index + 1], data[index]);

Hi Taw, I did something like that but the problem is that GetPixel function is very slow... — Martina, Mar 03 '15 at 17:40
Well, two options. If the circles all have the same diameter you only need to call it once. If you need varying diameters then you can easily change it to use Lockbits. I'll show you if you are interested.. — TaW, Mar 03 '15 at 17:48
I need the second option, colud you explain me the method please? — Martina, Mar 03 '15 at 18:02

score 2 · Answer 2 · answered Mar 04 '15 at 14:30

This should be a significantly faster method. It uses only fast operations, no square roots.

List<int> indices = new List<int>();

for (int x = 0; x < width; x++)
{
    for (int y = 0; y < height; y++)
    {
        double dx = x - m1;
        double dy = y - m2;
        double distanceSquared = dx * dx + dy * dy;

        if (distanceSquared <= radiusSquared)
        {
            indices.Add(x + y * width);
        }
    }
}

This code was taken from this answer.

score 1 · Answer 3 · answered Mar 03 '15 at 20:22

1

You could take your existing list with the border pixels and loop through it's y coords taking the coord of the left side and the right side of the circle. From that you can calculate the coords of all the middle pixels by looping through the all the x coords from left to right. This should be significantly faster and less memory intensive than relying on GDI.

answered Mar 03 '15 at 20:22

Bradley Uffner

16,641
3
39
76

That is what I meant in my last comment to the question, but it relies on already having the list and creating that list to me looks a lot more expensive than leaving the circle algorithm to GDI.. – TaW Mar 03 '15 at 21:44
Using GDI is certainly easier to code, but I've got to think it's pretty memory and CPU intensive. It has to allocate a new bitmap every time you call it, plus it has to draw the circle, then you have to loop through the entire bitmap looking for pixels. It might be ok if you are only doing small circles, but larger ones will be a bottleneck. Some quick calculations show that a 1024x1024 circle would use over 32mb of memory. That all has to be allocated and initialized before you can even start drawing to it. – Bradley Uffner Mar 04 '15 at 14:27
You may want to take a look at this answer https://stackoverflow.com/questions/14487322/get-all-pixel-array-inside-circle. as it can do all the math using only addition and multiplication it should be SIGNIFICANTLY faster. – Bradley Uffner Mar 04 '15 at 14:27
You are quite right, except that I guess from the OP that only one size will be needed. And that will be fast enough for anything. Still +1 for digging up the fast circle! – TaW Mar 04 '15 at 17:44

Pixels inside a circumference

3 Answers3