Calculate the overlapping area of two polygons (C++)

Calculate the overlapping area of two polygons (C++)

Method One

#include <iostream>//input and output
#include <vector>//Dynamic number
#include <cmath>//mathematical calculation
#include <iomanip>//formatted output

using namespace std;

class Polygon {<!-- -->
public:
    Polygon(float* polygon, int vertex) : polygon(polygon), vertex(vertex) {<!-- -->};
    float* polygon; // coordinates in the form of [x, y, x, y, ...., ]
    int vertex; // number of vertices
};

float intersection(const Polygon & amp; A, const Polygon & amp; B) {<!-- -->
    // Compute the overlapping area of polygons A and B
    // Simple area superposition method is used here

    float area = 0;// initialize the overlapping area to 0
    for (int i = 0; i < A.vertex; i ++ ) {<!-- -->// traverse all sides of polygon A
        int j = (i + 1) % A.vertex;
        int j = (i + 1) % A.vertex;
        float ax1 = A.polygon[i * 2], ay1 = A.polygon[i * 2 + 1];
        float ax2 = A.polygon[j * 2], ay2 = A.polygon[j * 2 + 1];

        for (int k = 0; k < B.vertex; k ++ ) {<!-- -->// traverse all sides of polygon B
            int l = (k + 1) % B.vertex;
            float bx1 = B.polygon[k * 2], by1 = B.polygon[k * 2 + 1];
            float bx2 = B.polygon[l * 2], by2 = B.polygon[l * 2 + 1];

            // Determine whether the edge of A intersects with the edge of B
            float d = (ay2 - ay1) * (bx2 - bx1) - (ax2 - ax1) * (by2 - by1);// Determine whether the edge of A and the edge of B intersect
            if (d == 0) {<!-- -->// Skip if disjoint
                continue;
            }
            // Calculate the intersection coordinates of sides A and B
            float u = ((ax1 - bx1) * (by2 - by1) - (ay1 - by1) * (bx2 - bx1)) / d;
            float v = ((ax1 - bx1) * (ay2 - ay1) - (ay1 - by1) * (ax2 - ax1)) / d;
            // If the intersection coordinates are between the endpoints of sides A and B, calculate the overlapping area
            if (u >= 0 & amp; & amp; u <= 1 & amp; & amp; v >= 0 & amp; & amp; v <= 1) {<!-- -->
                // Calculate intersection coordinates
                float x = ax1 + u * (ax2 - ax1);
                float y = ay1 + u * (ay2 - ay1);
                // Calculate the overlapping area
                area + = x * (by2 - by1) + bx1 * (ay2 - ay1) - bx2 * (ay2 - ay1) - x * (by1 - ay1);
            }
        }
    }

    return fabs(area) / 2;// returns the absolute value of the overlapping area divided by 2
}

int main() {<!-- -->
    int n;
    cout << "Please enter the number of vertices of polygon A: ";
    cin >> n;
    float* coordsA = new float[n * 2];// Create a float array with length n*2 to store the vertex coordinates of polygon A
    cout << "Please enter the vertex coordinates of polygon A (input in order, the x and y coordinates of each vertex are separated by spaces):" << endl;
    for (int i = 0; i < n; i ++ ) {<!-- -->
        cin >> coordsA[i * 2] >> coordsA[i * 2 + 1];// Read in the coordinates of each vertex of polygon B in sequence
    }
    Polygon a(coordsA, n);

    cout << "Please enter the vertex coordinates of polygon A (input in order, the x and y coordinates of each vertex are separated by spaces):" << endl;
    int m;
    cout << "Please enter the number of vertices of polygon B: ";
    cin >> m;
    float* coordsB = new float[m * 2];
    cout << "Please enter the vertex coordinates of polygon B (input in order, the x and y coordinates of each vertex are separated by spaces):" << endl;
    for (int i = 0; i < m; i ++ ) {<!-- -->
        cin >> coordsB[i * 2] >> coordsB[i * 2 + 1];
    }
    Polygon b(coordsB, m);// Create a Polygon object b, initialized with the vertex coordinates of polygon B

    cout << "The overlapping area of the two polygons is:" << intersection(a, b) << endl;// Call the intersection function to calculate the overlapping area of the two polygons and output the result


    delete[] coordsA;// release the array memory
    delete[] coordsB;
    return 0;
}

Method Two

#include <iostream>//input and output
#include <vector>//Dynamic number
#include <cmath>//mathematical calculation
#include <iomanip>//formatted output

using namespace std;
// Define the point class on the 2D plane
class Vertex
{<!-- -->
public:
    float x, y;
    Vertex() {<!-- -->}
    Vertex(float x, float y) : x(x), y(y) {<!-- -->}
};
// Define the polygon class, which consists of a set of vertices
class Polygon
{<!-- -->
public:
    Polygon(const vector<Vertex> & amp;vertexs) : vertexs(vertexs) {<!-- -->}
    // return all vertices of the polygon
    const vector<Vertex> & get_vertexs() const
    {<!-- -->
        return vertex;
    }

private:
    vector<Vertex> vertex;
};

// Compute the cross product of vector OA and vector OB
float cross(const Vertex & amp;A, const Vertex & amp;B, const Vertex & amp;C)
{<!-- -->
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
// Determine whether the line segment AB intersects with the line segment CD
bool is_intersect(const Vertex & amp; A, const Vertex & amp; B, const Vertex & amp; C, const Vertex & amp; D)
{<!-- -->
    float c1 = cross(A, B, C);
    float c2 = cross(A, B, D);
    float c3 = cross(C, D, A);
    float c4 = cross(C, D, B);
    if (c1 * c2 < 0 & & c3 * c4 < 0)
    {<!-- -->
        return true;
    }
    if (c1 == 0 & amp; & amp; B.x >= C.x & amp; & amp; B.x <= D.x & amp; & amp; B.y >= C.y & amp; & amp; B.y <= D.y)
    {<!-- -->
        return true;
    }
    if (c2 == 0 & amp; & amp; A.x >= C.x & amp; & amp; A.x <= D.x & amp; & amp; A.y >= C.y & amp; & amp; A.y <= D.y)
    {<!-- -->
        return true;
    }
    if (c3 == 0 & amp; & amp; D.x >= A.x & amp; & amp; D.x <= B.x & amp; & amp; D.y >= A.y & amp; & amp; D.y <= B.y)
    {<!-- -->
        return true;
    }
    if (c4 == 0 & amp; & amp; C.x >= A.x & amp; & amp; C.x <= B.x & amp; & amp; C.y >= A.y & amp; & amp; C.y <= B.y)
    {<!-- -->
        return true;
    }
    return false;
}
// Calculate the intersection point of line segment AB and line segment CD
Vertex intersection(const Vertex & amp;A, const Vertex & amp;B, const Vertex & amp;C, const Vertex & amp;D)
{<!-- -->
    float x1 = A.x, y1 = A.y;
    float x2 = B.x, y2 = B.y;
    float x3 = C.x, y3 = C.y;
    float x4 = D.x, y4 = D.y;
    float k1 = (y2 - y1) / (x2 - x1); // Calculate the slope of AB
    float k2 = (y4 - y3) / (x4 - x3); // Calculate the slope of CD
    float b1 = y1 - k1 * x1; // Calculate the intercept of AB
    float b2 = y3 - k2 * x3; // Calculate the intercept of CD
    float x = (b2 - b1) / (k1 - k2); // Calculate the x coordinate of the intersection point
    float y = k1 * x + b1; // Calculate the y coordinate of the intersection point
    return Vertex(x, y);
}

// Calculate the area of the triangle ABC
float triangle_area(const Vertex & amp;A, const Vertex & amp;B, const Vertex & amp;C)
{<!-- -->
    float a = hypot(A.x - B.x, A.y - B.y);
    float b = hypot(B.x - C.x, B.y - C.y);
    float c = hypot(C.x - A.x, C.y - A.y);
    // Check if the three sides of the triangle are valid
    if (a <= 0 || b <= 0 || c <= 0) {<!-- -->
        return 0.0f;
    }
    float s = (a + b + c) / 2;// calculate the half perimeter of the triangle
    float area = sqrt(s * (s - a) * (s - b) * (s - c));// Calculate the area of the triangle
    if (std::isnan(area) || std::isinf(area)) {<!-- -->// Check if the area of the triangle is NaN or infinite, and return 0.0f if it is
        return 0.0f;
    }
    return area;// return the area of the triangle
}
// Calculate the intersection area of two polygons
float intersection_area(const Polygon & amp;A, const Polygon & amp;B)
{<!-- -->

    float area = 0.0f; // initialize the intersection area to 0
    const auto & amp;vertexsA = A.get_vertexs(); // Get the vertices of polygons A and B
    const auto & vertexsB = B. get_vertexs();
    int n = vertexsA.size(); // Get the number of vertices of polygons A and B
    int m = vertexsB. size();
    for (int i = 0; i < n; i ++ ) // traverse all sides of polygon A
    {<!-- -->
        int j = (i + 1) % n; // Get the ith edge of polygon A
        Vertex A1 = vertexsA[i];
        Vertex A2 = vertexsA[j];
        for (int k = 0; k < m; k ++ ) // traverse all sides of polygon B
        {<!-- -->
            int l = (k + 1) % m; // Get the kth edge of polygon B
            Vertex B1 = vertex B[k];
            Vertex B2 = vertex B[l];
            if (is_intersect(A1, A2, B1, B2)) // Determine whether the i-th side of polygon A intersects the k-th side of polygon B
            {<!-- -->
                Vertex P = intersection(A1, A2, B1, B2); // Calculate the area of the intersection of polygons A and B, and add it to the intersection area
                float triangle1 = triangle_area(A1, P, B1);
                float triangle2 = triangle_area(P, A2, B1);
                float triangle3 = triangle_area(A1, P, B2);
                float triangle4 = triangle_area(P, A2, B2);
                area + = triangle1 + triangle2 + triangle3 + triangle4;
               
            }
        }
    }
    return area / 2.0f; // The intersection area is equal to half of the sum of the areas of the intersection of polygons A and B
}

int main()
{<!-- -->

    vector<Vertex> vertexsA, vertexsB; // Create empty vertex vectors
    float x, y; // initialize variables
    int n, m;
    cout << "Enter the number of vertices for polygon A: "; // Enter the number of vertices for polygon A
    cin >> n;
    cout << "Enter the coordinates of the vertices of polygon A (x y x y ...): "; // Enter the coordinates of the vertices of polygon A
    for (int i = 0; i < n; i ++ )
    {<!-- -->
        cin >> x >> y;
        vertexsA. push_back(Vertex(x, y));
    }
    cout << "Enter the number of vertices for polygon B: "; // Enter the number of vertices for polygon B
    cin >> m;
    cout << "Enter the coordinates of the vertices of polygon B (x y x y ...): "; // Enter the coordinates of the vertices of polygon B
    for (int i = 0; i < m; i ++ )
    {<!-- -->
        cin >> x >> y;
        vertexsB. push_back(Vertex(x, y));
    }
    Polygon A(vertexsA); // create polygon objects A and B
    Polygon B(vertex B);
    cout << "The intersection area of the two polygons is " <<fixed<<setprecision(3)<< intersection_area(A, B) << endl; // output the intersection of the two polygons
    return 0;
}