How to determine the area of a polygon in an Image

Question

If I am having a convex polygon vertices, then my area calculation in image is not coming accurate by the standard formula.

(For simiplicity) if I am having 3x3 square, and the vertices are (1,1) (1,3) (3,3) (3,1)

by polygon area calculation method depicted here

and dividing the summation by 2 we get the Area.

So for the 3 x 3 data above, we'll get area as 4 instead of 9.

This is happening because vertices are not points but a pixel.

this is the corresponding code. The coordinates are cyclic.

int X[] = { 1, 1, 3, 3, 1};
int Y[] = { 1, 3, 3, 1, 1};
double Sum1 = 0;
double Sum2 = 0;
int numElements = 5;

    for (int k = 0; k < numElements-1; k++)
    {
        Sum1 += X[k] * Y[k + 1];
        Sum2 += Y[k] * X[k + 1];
    }

    double area = std::abs((double)(Sum1 - Sum2))/2;

For square, we can do +1 to width and height and get the area correct. But what about the irregular polygons in the image? I hope the question makes sense.

Answer 1

The area can be calculated in following steps:

1) fetching the pixels between the vertices

2) sorting the pixels by x coordinates (or y coordinates)

3) taking the difference between min and max y coordinates (or x) for a particular x (or y) value and adding one to the difference

4) summing up the total difference

NOTE: the area might vary (if there are slanted edges in the polygon) depending on the line drawing method chosen

int compare(const void * a, const void * b)
{
  return (((Point*)a)->x() - ((Point*)b)->x());
}


double CalculateConvexHullArea(vector<int> ConvexHullX, vector<int> ConvexHullY)
{
    float Sum1 = 0;
    float Sum2 = 0;
    std::vector<Point> FillPoints;


        for (int k = 0; k < ConvexHullX.size() - 1; k++)
        {
            drawLine(ConvexHullX[k], ConvexHullX[k+1], ConvexHullY[k], ConvexHullY[k+1], FillPoints);
        }

        //sorting coordinates
        qsort(FillPoints.data(), FillPoints.size(), sizeof(Point), compare);

        double area = 0;
        int startY = FillPoints[0].y(), endY = FillPoints[0].y();
        int currX = FillPoints[0].x();


        // traversing x and summing up diff of min and max Y
        for (int cnt = 0; cnt < FillPoints.size(); cnt++)
        {
            if (FillPoints[cnt].x() == currX)
            {
                startY = startY > FillPoints[cnt].y() ? FillPoints[cnt].y() : startY;
                endY = endY < FillPoints[cnt].y() ? FillPoints[cnt].y() : endY;
            }
            else
            {
                int diffY = endY - startY + 1;
                area += diffY;
                currX = FillPoints[cnt].x();
                startY = endY = FillPoints[cnt].y();
            }
        }

        return area + endY - startY + 1;
}

Answer 2

If you don't want to work with pixel corners as vertices, consider next method (works for simple figures - all convex ones, some concave ones):

Add additional fake pixel at right side of every right-border pixel, at bottom side of every bottom-border pixel, at right-bottom of right-bottom corner pixel. Here gray pixels are initial, light blues ones - fake.