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;
}