Polygon splitted by 4 parts

Question

I have an arbitrary convex polygon. And it is splitted by 2 perpendicular lines (vectors of them are (0,1) and (1,0)). Is there any algorithm that can calculate area by smaller figures (S1, S2, S3, S4). All I can do is to calculate points where lines cross the polygon and then calculate areas, but is there something better optimized?

I store all vertexes in array double **v; And then I calculate all points, where my polygon crosses X and Y axises:

void cross() {       //calculates buf (crossing with Y)
    act = 0;
    for (int i = 0; i < n; ++i) {
        buf[act][0]=v[i][0];
        buf[act][1]=v[i][1];
        act++;
        if (v[i][0]*v[(i+1)%n][0] < 0) {
            buf[act][0] = 0;
            buf[act][1] = v[i][1] + std::abs(v[i][0])*(v[(i+1)%n][1]-v[i][1])/(std::abs(v[i][0])+std::abs(v[(i+1)%n][0]));
        act++;
        }
    }

}

void vert() {      /calculates buf2 (crossing with X)
    act2 =0;
    for (int i = 0; i < act; ++i) {
        buf2[act2][0]=buf[i][0];
        buf2[act2][1]=buf[i][1];
        act2++;
        if (buf[i][1]*buf[(i+1)%act][1] < 0) {
            buf2[act2][1] = 0;
            buf2[act2][0] = buf[i][0] + std::abs(buf[i][1])*(buf[(i+1)%act][0] - buf[i][0])/ (std::abs(buf[i][1])+std::abs(buf[(i+1)%act][1]));
            act2++;

        }

    }
}

After calling cross(); vert(); I get an array buf2 and number of elements there is act2; After this I'am triangilating polygon and detect in what squad does traingle lay.

 double s_trian (double a, double b, double c, double d) { 
//area of triangle
double s =0;
s=0.5*std::abs((a)*(d)-(c)*(b));
return s;
} 
void triang() {  //calculate areas of s1,s2,s3,s4 by  
                 //triangulating
bool rotation;
double temror;
s1=0, s2 =0, s3 =0, s4 =0;
int a,b;
for (int i =0; i < act2; ++i) {
 a=i%act2;
 b=(i+1)%act2;
 temror = s_trian(buf2[a][0], buf2[a][1], buf2[b][0], buf2[b][1]);
 if ((buf2[a][0]+buf2[b][0]) > 0) {
     if((buf2[a][1]+buf2[b][1] > 0)) 
         s1+=temror;
     else
         s4+=temror;
 } else {
      if ((buf2[a][1]+buf2[b][1] > 0))  
         s2+=temror;
      else
         s3+=temror;
  }

}
}

Can I optimize something here?

Answer 1

[Following up on my comment yesterday; has much in common with Dan Bystrom's answer.]

Loop over all sides, and compute the area of the triangle made of the side and the origin. Add to the appropriate quad area. Where a side crosses the axis, compute the intercept and split the triangle. Compute both triangle areas parts and add each to the appropriate quad.

Using the origin as a point for a triangle vertex makes the cross product based formula for a triangle area very fast and simple. You don't even need the call to fabs() if you take care to pass the parameters in the right order.

This code has not handled the problem where a vertex lies on an axis or cases where no point lies in a given quadrant.

struct Point
{
    double x;
    double y;
};

double areaOfTriangle(double ax, double ay, double bx, double by)
{
    return fabs(by*ax - bx *ay)/2;
}

unsigned getQuad(double x, double y)
{
    int xPos = (x > 0) ? 0 : 1;
    int yPos = (y > 0) ? 0 : 1 ;
    int quad = xPos + yPos;
    if (!xPos && yPos)
        quad = 3;
    return quad;

}

Point getIntercept(const Point& a, const Point& b)
{
    Point intercept;
    if ( (a.x * b.x) < 0)
    {
        // Crosses y axis.
        intercept.x = 0;
        intercept.y = a.y - (b.y - a.y) / (b.x - a.x)*a.x;
    }
    else
    {   
        // Crosses x axis.
        intercept.y = 0;
        intercept.x = a.x - (b.x - a.x) / (b.y - a.y)*a.y;
    }
    return intercept;
}

void getAreaOfQuads(double* retQuadArea, const Point* points, unsigned numPts)
{
    for (unsigned i = 0; i != 4; ++i)
        retQuadArea[i] = 0;
    const Point* a = &points[numPts - 1];
    unsigned quadA = getQuad(a->x, a->y);
    for (unsigned i = 0; i != numPts; ++i)
    {


        const Point* b = &points[i];
        unsigned quadB = getQuad(b->x, b->y);
        if (quadA == quadB)
        {
            retQuadArea[quadA] += areaOfTriangle(a->x, a->y, b->x, b->y);
        }
        else
        {
            // The side a->b crosses an axis.
            // First, find out where.
            Point c = getIntercept(*a, *b);
            retQuadArea[quadA] += areaOfTriangle(a->x, a->y, c.x, c.y);
            retQuadArea[quadB] += areaOfTriangle(c.x, c.y, b->x, b->y);
        }
        a = b;
        quadA = quadB;
    }
}

void test(Point* polygon, unsigned n)
{
    double areas[4] = {};
    getAreaOfQuads(areas, polygon, n);
    for (unsigned i = 0; i != 4; ++i)
        std::cout << areas[i] << ",  ";
    std::cout << std::endl;
}

Point polygon[]
{
    {0.6, 0.2},
    { 0.2, 0.8 },
    { -0.2, 0.7 },
    { -0.6, 0.6 },
    { -1.0, 0.1 },
    { -0.6, -0.5 },
    { 0.1, -0.5 },
    { 0.9, -0.1 }

};
Point square[]
{
    {1, 1},
    { -1, 1 },
    { -1, -1 },
    { 1, -1 }

};

int main()
{
    test(square, 4);
    test(polygon, 8);
    return 0;
}

Answer 2

You can do slightly better.

Ignore X to begin with.

Project horizontally every vertex on Y. This way, you define trapezoids. The sum of the algebraic areas of these trapezoids gives the total surface. Add the positive and negative areas in separate accumulators, this will give you the areas on both sides of Y. But some trapezoids will cross Y and be skewed: compute the areas of the two triangles and accumulate where appropriate.

Now to deal with the horizontal axis, similarly you will add the contributions to a positive/negative accumulator, or to both.

In total there will be four accumulators, for all sign combinations, giving you the four requested areas.

This procedure will cost you a little more than one accumulation per side, instead of four. It can be done in a single loop, avoiding the need to compute and store the four subpolygons.

Answer 3

Given that your polygon is convex, just select an arbitrary point P inside the polygon and split it up in triangles with one corner in P.

Then calculate the area of each triangle: http://www.mathopenref.com/heronsformula.html and sum them up.