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:

Face (1)
Eyes (2)
Nose (1)
Right of face (1)

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

[start with the formula for finding the area of a polygon](http://en.wikipedia.org/wiki/Polygon#Area_and_centroid) — Servy, Sep 25 '12 at 18:51
think of pixels enclosing your regions as of polygons then see http://stackoverflow.com/questions/2034540/calculating-area-of-irregular-polygon-in-c-sharp on how to get polygon area — m0s, Sep 25 '12 at 18:55
Sorry, something got lost in translation...I need to figure out the number of Regions (5) not the area of them. — user873432, Sep 26 '12 at 16:15

score 2 · Answer 1 · edited May 23 '17 at 11:54

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.

Ivan Kochurkin · Accepted Answer · 2012-10-02T07:40:12.870

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.

Connectedness

Nice, useful for another area I was working on, but any idea how to determine the number of enclosed areas? — user873432, Sep 26 '12 at 17:19
You can use my algorithm for each not background color (black on your example image) pixel for region detecting. After each fill, this regions will be not detected forth (because of they'll be filled) and you will have to increase number of finded regions. Off course, this method is suitable for linked regions. Thus, for another cases use OpenCV, how @Jason Hermann has answered. — Ivan Kochurkin, Sep 26 '12 at 17:53
@KvanTTT - this works perfectly with pixel widths of 2 or greater, however, if the pixel width is 1px, it always comes back as only 1 enclosed region. Is there a way to modify the code above to handle this? — user873432, Oct 01 '12 at 22:42

score 1 · Answer 3 · answered Sep 25 '12 at 18:57

There are a couple special cases in the sample image. You would have to decide how to deal with them.

Generally you will start by converting the raster image into a series of polygons. Then it is a fairly trivial matter to calculate area (See Servy's comment)

The special cases would be the side of the face and the mouth. Both are open shapes, not closed. You need to figure out how to close them.

score 1 · Answer 4 · answered Sep 25 '12 at 19:02

I think this comes down to counting the number of (non-black) pixels in each region. If you choose one pixel that is not black, add it to a HashSet<>, see if the pixels over, under, to the left of and to the right of your chosen pixel, are also non-black.

Everytime you find new non-black pixels (by going up/down/left/right), add them to your set. When you have found them all, count them.

Your region's area is count / (pixelWidthOfTotalDrawing * pixelHeightOfTotalDrawing) multiplied by the area of the full rectangle (depending on the units you want).

Comment: I don't think this looks like a polygon. That's why I was having the "fill with paint" function of simple drawing software on my mind.

Find area given a set of points

4 Answers4