Find area given a set of points

Question

Given a list of x,y coordinates and a known width & height how can the NUMBER of the enclosed areas be determined (in C#)?

For Example:

In this image 5 ENCLOSED AREAS are defined:

1. Face (1)
2. Eyes (2)
3. Nose (1)
4. Right of face (1)

The list of x,y points would be any pixel in black, including the mouth.

Answer 1

You can use this simple algorithm, based on idea of flood fill with helper bitmap:

// backColor is an INT representation of color at fillPoint in the beginning.
// result in pixels of enclosed shape.
private int GetFillSize(Bitmap b, Point fillPoint)
{
   int count = 0;
   Point p;
   Stack pixels = new Stack();
   var backColor = b.GetPixel(fillPoint.X, fillPoint.Y);
   pixels.Push(fillPoint);
   while (pixels.Count != 0)
   {
       count++;

       p = (Point)pixels.Pop();
       b.SetPixel(p.X, p.Y, backColor);

       if (b.GetPixel(p.X - 1, p.Y).ToArgb() == backColor)
           pixels.Push(new Point(p.X - 1, p.Y));

       if (b.GetPixel(p.X, p.Y - 1).ToArgb() == backColor)
           pixels.Push(new Point(p.X, p.Y - 1));

       if (b.GetPixel(p.X + 1, p.Y).ToArgb() == backColor)
           pixels.Push(new Point(p.X + 1, p.Y));

       if (b.GetPixel(p.X, p.Y + 1).ToArgb() == backColor)
           pixels.Push(new Point(p.X, p.Y + 1));
   }

   return count;
}

UPDATE

The code above works only this quadruply-linked enclosed areas. The following code works with octuply-linked enclosed areas.

// offset points initialization.
Point[] Offsets = new Point[]
{
    new Point(-1, -1),
    new Point(-0, -1),
    new Point(+1, -1),
    new Point(+1, -0),
    new Point(+1, +1),
    new Point(+0, +1),
    new Point(-1, +1),
    new Point(-1, +0),
};

...

private int Fill(Bitmap b, Point fillPoint)
{
    int count = 0;
    Point p;
    Stack<Point> pixels = new Stack<Point>();
    var backColor = b.GetPixel(fillPoint.X, fillPoint.Y).ToArgb();
    pixels.Push(fillPoint);
    while (pixels.Count != 0)
    {
        count++;

        p = (Point)pixels.Pop();
        b.SetPixel(p.X, p.Y, Color.FromArgb(backColor));

        foreach (var offset in Offsets)
            if (b.GetPixel(p.X + offset.X, p.Y + offset.Y).ToArgb() == backColor)
                pixels.Push(new Point(p.X + offset.X, p.Y + offset.Y));
    }

    return count;
}

The picture below clearly demonstates what I mean. Also one could add more far points to offset array in order to able to fill areas with gaps.

Answer 2

I've had great success using OpenCV. There is a library for .net called Emgu CV

Here is a question covering alternatives to Emgu CV: .Net (dotNet) wrappers for OpenCV?

That library contains functions for identifying contours and finding properties about them. You can search for cvContourArea to find more information.

If you are looking for a quick solution to this specific problem and want to write your own code rather than reusing others, I do not have an algorithm I could give that does that. Sorry.