Pick's Theorem serves as a foundational concept in computational geometry, employing a straightforward yet effective approach to calculate the area of a polygon with vertices located exclusively on an integer grid. This theorem was first proposed by Georg Alexander Pick in 1899.
The mathematical principle asserts that for every uncomplicated polygon (a polygon that does not intersect itself) with vertices positioned on a grid, its area can be computed by relying on only two factors: the quantity of grid points strictly contained within the polygon (I) and the quantity of grid points situated on the boundary (B). The expression for the area (A) can be represented as: A=I+(B/2)-1
The theorem offers a practical geometric explanation of this correlation, particularly beneficial in computational scenarios where input data commonly consists of integer coordinates. Pick's algorithm is highly efficient in terms of computation and straightforward to execute.
As each intersection point along the perimeter is commonly shared by neighboring shapes, the impact of the boundary factor on the total area gets divided by two. Pick's Theorem comes into play specifically for shapes featuring lattice vertices in an even quantity, excluding those in three-dimensional or irregular polygon forms. It stands out within its scope for its exceptional ease and effectiveness, making it a top choice for crafting algorithms and tackling computational geometry challenges. Mastering Pick's Theorem aids in grasping the intricate connection between discrete mathematics and geometric principles.
Approach-1: Naive Brute Force Approach
In this approach, we iterate each lattice point within the polygon's bounding box until we find the number of interior points (I) and the number of boundary points (B). The first step is to calculate the bounding box of the polygon, i.e., the smallest rectangle that contains the entire polygon. For each lattice point within the box, it determines if the point lies totally within the polygon or boundary. The method achieves this by performing a point-in-polygon test (ray casting) to find interior points and verifying that the boundary points' points satisfy conditions for lying on the polygon's edges.
Once the number of interior lattice points (```
include <iostream>
include <vector>
include <cmath>
include <algorithm>
include <iomanip> // For formatted output
using namespace std;
struct Point {
int x, y;
};
// Function to determine the bounding box of the polygon
void calculateBoundingBox(const vector<Point>& vertices, int& minX, int& maxX, int& minY, int& maxY) {
minX = maxX = vertices[0].x;
minY = maxY = vertices[0].y;
for (const auto& vertex : vertices) {
minX = min(minX, vertex.x);
maxX = max(maxX, vertex.x);
minY = min(minY, vertex.y);
maxY = max(maxY, vertex.y);
}
}
// Check if a point is on the boundary of a line segment
bool isOnBoundary(Point p, Point a, Point b) {
if ((p.x - a.x) (b.y - a.y) != (p.y - a.y) (b.x - a.x)) {
return false; // Not collinear
}
if (min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x) &&
min(a.y, b.y) <= p.y && p.y <= max(a.y, b.y)) {
return true; // Lies within the bounds of the segment
}
return false;
}
// Ray-casting algorithm to check if a point is inside the polygon
bool isInsidePolygon(Point p, const vector<Point>& vertices) {
int n = vertices.size;
int crossings = 0;
for (int i = 0; i < n; i++) {
Point a = vertices[i];
Point b = vertices[(i + 1) % n];
if ((a.y <= p.y && p.y < b.y) || (b.y <= p.y && p.y < a.y)) {
double slope = (double)(b.x - a.x) / (b.y - a.y);
double xIntersection = a.x + slope * (p.y - a.y);
if (xIntersection > p.x) {
crossings++;
}
}
}
return (crossings % 2 == 1); // Odd crossings => point is inside
}
// Function to visualize the bounding box and lattice points
void visualizeBoundingBox(const vector<Point>& vertices, int minX, int maxX, int minY, int maxY) {
cout << "Bounding Box Visualization:\n";
for (int y = maxY; y >= minY; y--) {
for (int x = minX; x <= maxX; x++) {
Point p = {x, y};
bool isBoundary = false, isInterior = false;
for (int i = 0; i < vertices.size; i++) {
Point a = vertices[i];
Point b = vertices[(i + 1) % vertices.size];
if (isOnBoundary(p, a, b)) {
isBoundary = true;
break;
}
}
if (!isBoundary && isInsidePolygon(p, vertices)) {
isInterior = true;
}
if (isBoundary) {
cout << "* "; // Boundary points
} else if (isInterior) {
cout << "+ "; // Interior points
} else {
cout << ". "; // Empty space
}
}
cout << endl;
}
cout << endl;
}
// Calculate the area of the polygon using Pick's Theorem
void calculateAreaUsingPicksTheorem(const vector<Point>& vertices) {
int minX, maxX, minY, maxY;
calculateBoundingBox(vertices, minX, maxX, minY, maxY)
int interiorPoints = 0, boundaryPoints = 0;
vector<Point> interiorList, boundaryList;
for (int x = minX; x <= maxX; x++) {
for (int y = minY; y <= maxY; y++) {
Point p = {x, y};
bool onBoundary = false;
for (int i = 0; i < vertices.size; i++) {
Point a = vertices[i];
Point b = vertices[(i + 1) % vertices.size];
if (isOnBoundary(p, a, b)) {
onBoundary = true;
boundaryList.push_back(p);
break;
}
}
if (onBoundary) {
boundaryPoints++;
} else if (isInsidePolygon(p, vertices)) {
interiorPoints++;
interiorList.push_back(p);
}
}
}
double area = interiorPoints + (double)boundaryPoints / 2 - 1;
// Output results
cout << "\nBounding Box Dimensions:\n";
cout << "Min X: " << minX << ", Max X: " << maxX << endl;
cout << "Min Y: " << minY << ", Max Y: " << maxY << endl;
cout << "\nBoundary Points (B): " << boundaryPoints << "\nDetails:\n";
for (const auto& p : boundaryList) {
cout << "(" << p.x << ", " << p.y << ") ";
}
cout << "\n\nInterior Points (I): " << interiorPoints << "\nDetails:\n";
for (const auto& p : interiorList) {
cout << "(" << p.x << ", " << p.y << ") ";
}
cout << "\n\nArea of the Polygon: " << area << endl;
// Visualize bounding box
visualizeBoundingBox(vertices, minX, maxX, minY, maxY);
}
// Display menu for user interaction
void displayMenu {
cout << "\nPolygon Area Calculation using Pick's Theorem\n";
cout << "1. Use default polygon\n";
cout << "2. Input custom polygon\n";
cout << "3. Exit\n";
cout << "Enter your choice: ";
}
// Main function
int main {
while (true) {
displayMenu;
int choice;
cin >> choice;
if (choice == 1) {
// Default polygon (Rectangle)
vector<Point> vertices = {
{0, 0},
{4, 0},
{4, 3},
{0, 3}
};
calculateAreaUsingPicksTheorem(vertices);
} else if (choice == 2) {
// User-defined polygon
int n;
cout << "Enter the number of vertices: ";
cin >> n;
vector<Point> vertices(n);
cout << "Enter the vertices (x y):\n";
for (int i = 0; i < n; i++) {
cin >> vertices[i].x >> vertices[i].y;
}
calculateAreaUsingPicksTheorem(vertices);
} else if (choice == 3) {
cout << "Exiting program. Goodbye!\n";
break;
} else {
cout << "Invalid choice. Please try again.\n";
}
}
return 0;
}
Polygon Area Calculation using Pick's Theorem
1. Use default polygon
2. Input custom polygon
3. Exit
Enter your choice: 1
Bounding Box Dimensions:
Min X: 0, Max X: 4
Min Y: 0, Max Y: 3
Boundary Points (B): 14
Details:
(0, 0) (0, 1) (0, 2) (0, 3) (1, 0) (1, 3) (2, 0) (2, 3) (3, 0) (3, 3) (4, 0) (4, 1) (4, 2) (4, 3)
Interior Points (I): 6
Details:
(1, 1) (1, 2) (2, 1) (2, 2) (3, 1) (3, 2)
Area of the Polygon: 12
Bounding Box Visualization:
* * * * *
* + + + *
* + + + *
* * * * *
Polygon Area Calculation using Pick's Theorem
1. Use default polygon
2. Input custom polygon
3. Exit
Enter your choice: 2
Enter the number of vertices: 3
Enter the vertices (x y):
2 3
5 2
1 4
Bounding Box Dimensions:
Min X: 1, Max X: 5
Min Y: 2, Max Y: 4
Boundary Points (B): 4
Details:
(1, 4) (2, 3) (3, 3) (5, 2)
Interior Points (I): 0
Details:
Area of the Polygon: 1
Bounding Box Visualization:
* . . . .
. * * . .
. . . . *
Polygon Area Calculation using Pick's Theorem
1. Use default polygon
2. Input custom polygon
3. Exit
Enter your choice: 3
Exiting program. Goodbye!
While this method may seem straightforward and easy to understand, it can be resource-intensive from a computational standpoint as it involves examining all lattice points within the bounding box. As a result, it serves as a valuable educational tool but is most practical when dealing with small polygonal bounding boxes.
Program:
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip> // For formatted output
using namespace std;
struct Point {
int x, y;
};
// Function to determine the bounding box of the polygon
void calculateBoundingBox(const vector<Point>& vertices, int& minX, int& maxX, int& minY, int& maxY) {
minX = maxX = vertices[0].x;
minY = maxY = vertices[0].y;
for (const auto& vertex : vertices) {
minX = min(minX, vertex.x);
maxX = max(maxX, vertex.x);
minY = min(minY, vertex.y);
maxY = max(maxY, vertex.y);
}
}
// Check if a point is on the boundary of a line segment
bool isOnBoundary(Point p, Point a, Point b) {
if ((p.x - a.x) * (b.y - a.y) != (p.y - a.y) * (b.x - a.x)) {
return false; // Not collinear
}
if (min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x) &&
min(a.y, b.y) <= p.y && p.y <= max(a.y, b.y)) {
return true; // Lies within the bounds of the segment
}
return false;
}
// Ray-casting algorithm to check if a point is inside the polygon
bool isInsidePolygon(Point p, const vector<Point>& vertices) {
int n = vertices.size();
int crossings = 0;
for (int i = 0; i < n; i++) {
Point a = vertices[i];
Point b = vertices[(i + 1) % n];
if ((a.y <= p.y && p.y < b.y) || (b.y <= p.y && p.y < a.y)) {
double slope = (double)(b.x - a.x) / (b.y - a.y);
double xIntersection = a.x + slope * (p.y - a.y);
if (xIntersection > p.x) {
crossings++;
}
}
}
return (crossings % 2 == 1); // Odd crossings => point is inside
}
// Function to visualize the bounding box and lattice points
void visualizeBoundingBox(const vector<Point>& vertices, int minX, int maxX, int minY, int maxY) {
cout << "Bounding Box Visualization:\n";
for (int y = maxY; y >= minY; y--) {
for (int x = minX; x <= maxX; x++) {
Point p = {x, y};
bool isBoundary = false, isInterior = false;
for (int i = 0; i < vertices.size(); i++) {
Point a = vertices[i];
Point b = vertices[(i + 1) % vertices.size()];
if (isOnBoundary(p, a, b)) {
isBoundary = true;
break;
}
}
if (!isBoundary && isInsidePolygon(p, vertices)) {
isInterior = true;
}
if (isBoundary) {
cout << "* "; // Boundary points
} else if (isInterior) {
cout << "+ "; // Interior points
} else {
cout << ". "; // Empty space
}
}
cout << endl;
}
cout << endl;
}
// Calculate the area of the polygon using Pick's Theorem
void calculateAreaUsingPicksTheorem(const vector<Point>& vertices) {
int minX, maxX, minY, maxY;
calculateBoundingBox(vertices, minX, maxX, minY, maxY)
int interiorPoints = 0, boundaryPoints = 0;
vector<Point> interiorList, boundaryList;
for (int x = minX; x <= maxX; x++) {
for (int y = minY; y <= maxY; y++) {
Point p = {x, y};
bool onBoundary = false;
for (int i = 0; i < vertices.size(); i++) {
Point a = vertices[i];
Point b = vertices[(i + 1) % vertices.size()];
if (isOnBoundary(p, a, b)) {
onBoundary = true;
boundaryList.push_back(p);
break;
}
}
if (onBoundary) {
boundaryPoints++;
} else if (isInsidePolygon(p, vertices)) {
interiorPoints++;
interiorList.push_back(p);
}
}
}
double area = interiorPoints + (double)boundaryPoints / 2 - 1;
// Output results
cout << "\nBounding Box Dimensions:\n";
cout << "Min X: " << minX << ", Max X: " << maxX << endl;
cout << "Min Y: " << minY << ", Max Y: " << maxY << endl;
cout << "\nBoundary Points (B): " << boundaryPoints << "\nDetails:\n";
for (const auto& p : boundaryList) {
cout << "(" << p.x << ", " << p.y << ") ";
}
cout << "\n\nInterior Points (I): " << interiorPoints << "\nDetails:\n";
for (const auto& p : interiorList) {
cout << "(" << p.x << ", " << p.y << ") ";
}
cout << "\n\nArea of the Polygon: " << area << endl;
// Visualize bounding box
visualizeBoundingBox(vertices, minX, maxX, minY, maxY);
}
// Display menu for user interaction
void displayMenu() {
cout << "\nPolygon Area Calculation using Pick's Theorem\n";
cout << "1. Use default polygon\n";
cout << "2. Input custom polygon\n";
cout << "3. Exit\n";
cout << "Enter your choice: ";
}
// Main function
int main() {
while (true) {
displayMenu();
int choice;
cin >> choice;
if (choice == 1) {
// Default polygon (Rectangle)
vector<Point> vertices = {
{0, 0},
{4, 0},
{4, 3},
{0, 3}
};
calculateAreaUsingPicksTheorem(vertices);
} else if (choice == 2) {
// User-defined polygon
int n;
cout << "Enter the number of vertices: ";
cin >> n;
vector<Point> vertices(n);
cout << "Enter the vertices (x y):\n";
for (int i = 0; i < n; i++) {
cin >> vertices[i].x >> vertices[i].y;
}
calculateAreaUsingPicksTheorem(vertices);
} else if (choice == 3) {
cout << "Exiting program. Goodbye!\n";
break;
} else {
cout << "Invalid choice. Please try again.\n";
}
}
return 0;
}
Output:
Polygon Area Calculation using Pick's Theorem
1. Use default polygon
2. Input custom polygon
3. Exit
Enter your choice: 1
Bounding Box Dimensions:
Min X: 0, Max X: 4
Min Y: 0, Max Y: 3
Boundary Points (B): 14
Details:
(0, 0) (0, 1) (0, 2) (0, 3) (1, 0) (1, 3) (2, 0) (2, 3) (3, 0) (3, 3) (4, 0) (4, 1) (4, 2) (4, 3)
Interior Points (I): 6
Details:
(1, 1) (1, 2) (2, 1) (2, 2) (3, 1) (3, 2)
Area of the Polygon: 12
Bounding Box Visualization:
* * * * *
* + + + *
* + + + *
* * * * *
Polygon Area Calculation using Pick's Theorem
1. Use default polygon
2. Input custom polygon
3. Exit
Enter your choice: 2
Enter the number of vertices: 3
Enter the vertices (x y):
2 3
5 2
1 4
Bounding Box Dimensions:
Min X: 1, Max X: 5
Min Y: 2, Max Y: 4
Boundary Points (B): 4
Details:
(1, 4) (2, 3) (3, 3) (5, 2)
Interior Points (I): 0
Details:
Area of the Polygon: 1
Bounding Box Visualization:
* . . . .
. * * . .
. . . . *
Polygon Area Calculation using Pick's Theorem
1. Use default polygon
2. Input custom polygon
3. Exit
Enter your choice: 3
Exiting program. Goodbye!
Explanation:
Struct Definition
First, we establish a Point structure that symbolizes lattice points containing integer x and y coordinates and how we express these using whole numbers. Subsequently, this forms the foundation for all computations related to the vertices of the polygon and lattice points.
Bounding Box Calculation
Determine the bounding box function, which provides the minimum and maximum x and y coordinates of the polygon's vertices. These coordinates define the bounding box, representing the smallest possible rectangle that encloses the polygon. It is crucial to iterate through all potential lattice points within the defined area.
Bounding Box Calculation
The calculateBoundingBox method determines the smallest rectangle that encloses the polygon by finding the minimum and maximum x and y coordinates of its vertices. This bounding box is essential for iterating through all potential lattice points within the specified region.
Boundary Point Detection
The function isOnBoundary assesses if a specified point is positioned on an edge of a polygon. It validates the alignment of the point with the segment by applying the slope formula and confirming that the point is within the segment's boundaries. This process is essential for precisely identifying boundary points (B).
Point-in-Polygon Test
The isInsidePolygon function utilizes the ray-casting technique to ascertain whether a given point resides within the polygon boundaries. This algorithm calculates the number of intersections between a horizontal ray extending from the point and the edges of the polygon. Based on the count of crossings (odd or even), it determines if the point is located inside or outside the polygon, respectively.
Visualization
The function visualizeBoundingBox symbolically depicts the bounding box and lattice points with characters: * for boundary points, + for interior points, and "." for empty spaces. This visualization aids in comprehending the bounding box as well as the arrangement of lattice points.
Area Calculation
The software loops through each lattice point, utilizing the bounding rectangle. Points within the polygon are classified as interior (I), while points lying on the perimeter are categorized as boundary points (B). The calculation of the area follows Pick's Theorem formula (Area = I + (B/2) - 1) within the application.
The program outputs:
- Bounding box dimensions.
- Lists of all interior and boundary points.
- The calculated area of the polygon.
- A detailed visualization of the bounding box.
Complexity Analysis:
Time Complexity
The reason for the primary determinant of the time complexity of the program is the iteration over all lattice points of the bounding box. The program looks for each point, to see where the polygon boundary and the within the polygon. Iterating through n polygon edges for each lattice point gives a time complexity of O(A) (where A is the area of the bounding box).
However, it also involves extra tasks such as computing the dimensions of the bounding box and producing output. The primary expense, however, arises from the repeated process of iterating over n edges and A lattice points.
Space Complexity
Space complexity is established based on the storage of polygon vertices, interior points, and boundary points. Nevertheless, we allocate O(n) space for the polygon vertices and an additional O(A) space for the interior and boundary points. Consequently, the total space complexity amounts to O(n+A).
As long as the storage space is utilized effectively, the amount of storage needed for lattice points in extensive polygons with sizable bounding boxes can grow significantly. This means that the quantity of lattice points enclosed within the bounding box, especially in cases of sizable polygons, plays a crucial role in determining the space efficiency.
Approach-2: Scanline Method
Applying the efficient scanline algorithm provides a more streamlined method for calculating the area of a polygon, significantly reducing computational expenses compared to a brute force approach. Rather than evaluating every individual lattice point within the bounding box, this technique involves examining where the polygon intersects with a sequence of horizontal lines (scanlines). By focusing solely on these relevant intersections, the scanline method minimizes superfluous computations.
The algorithm iterates through each scanline, pinpointing where it intersects with the edges of the polygon to track when the polygon crosses the horizontal line. By pinpointing these intersections, the software computes lattice points within them along the scanline, considering them as internal points. To distinguish boundary points, it validates if any lattice points align precisely with a polygon edge.
Reducing the quantity of lattice points to be processed leads to a notably more effective technique, particularly advantageous for polygons with intricate outlines and sparse lattice point distributions, when contrasted with the brute force method.
Program:
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
using namespace std;
// Point structure to represent a lattice point
struct Point {
int x, y;
Point(int x = 0, int y = 0) : x(x), y(y) {}
};
// Utility function to calculate the intersection of a line segment and a scanline
double getIntersection(Point p1, Point p2, int y) {
if (p1.y == p2.y) return -1; // Parallel to the scanline
return p1.x + (double)(y - p1.y) * (p2.x - p1.x) / (p2.y - p1.y);
}
// Function to check if a point lies on the boundary of the polygon
bool isBoundary(Point p, const vector<Point>& polygon) {
int n = polygon.size();
for (int i = 0; i < n; i++) {
Point p1 = polygon[i];
Point p2 = polygon[(i + 1) % n];
// Check if a point lies on the edge of the polygon (collinearity check)
if ((p.y - p1.y) * (p2.x - p1.x) == (p.x - p1.x) * (p2.y - p1.y)) {
if (min(p1.x, p2.x) <= p.x && p.x <= max(p1.x, p2.x) &&
min(p1.y, p2.y) <= p.y && p.y <= max(p1.y, p2.y)) {
return true;
}
}
}
return false;
}
// Function to calculate the area using Pick's Theorem
double calculateArea(const vector<Point>& polygon) {
int n = polygon.size();
// Find the bounding box of the polygon
int minX = polygon[0].x, maxX = polygon[0].x, minY = polygon[0].y, maxY = polygon[0].y;
for (int i = 1; i < n; i++) {
minX = min(minX, polygon[i].x);
maxX = max(maxX, polygon[i].x);
minY = min(minY, polygon[i].y);
maxY = max(maxY, polygon[i].y);
}
int boundaryPoints = 0, interiorPoints = 0;
// Iterate over each scanline (horizontal line at integer y values)
for (int y = minY; y <= maxY; y++) {
vector<double> intersections;
// Find intersections with polygon edges
for (int i = 0; i < n; i++) {
Point p1 = polygon[i];
Point p2 = polygon[(i + 1) % n];
double intersection = getIntersection(p1, p2, y);
if (intersection != -1) {
intersections.push_back(intersection);
}
}
// Sort intersection points for the current scanline
sort(intersections.begin(), intersections.end());
// Count interior points between each pair of intersection points
for (size_t i = 0; i < intersections.size(); i += 2) {
int x1 = floor(intersections[i]);
int x2 = floor(intersections[i + 1]);
for (int x = x1; x <= x2; x++) {
Point p(x, y);
if (isBoundary(p, polygon)) {
boundaryPoints++;
} else {
interiorPoints++;
}
}
}
}
// Apply Pick's Theorem: Area = I + B/2 - 1
double area = interiorPoints + (boundaryPoints / 2.0) - 1;
return area;
}
// Function to input a polygon from the user
void inputPolygon(vector<Point>& polygon) {
int n;
cout << "Enter number of vertices in the polygon: ";
cin >> n;
polygon.clear();
cout << "Enter the coordinates of the vertices (x y):" << endl;
for (int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
polygon.push_back(Point(x, y));
}
}
// Function to display the polygon and results
void displayResults(const vector<Point>& polygon) {
cout << "\nPolygon vertices:" << endl;
for (const auto& p : polygon) {
cout << "(" << p.x << ", " << p.y << ")" << endl;
}
double area = calculateArea(polygon);
cout << "\nArea of the polygon using Pick's Theorem: " << area << endl;
}
int main() {
vector<Point> polygon;
inputPolygon(polygon);
displayResults(polygon);
return 0;
}
Output:
Enter number of vertices in the polygon: 4
Enter the coordinates of the vertices (x y):
2 3
4 3
5 2
4 2
Polygon vertices:
(2, 3)
(4, 3)
(5, 2)
(4, 2)
Area of the polygon using Pick's Theorem: 1.5
Explanation:
Point Structure:
The point structure represents the x and y coordinates of vertices using integers. This simplifies the management of polygon vertices and lattice points.
Intersection Calculation:
The find operation evaluates whether a specified polyline intersects a horizontal scanline defined by a constant y value. When an intersection is detected, it determines the point at which the polyline edge intersects. Calculating the x-coordinate at this intersection involves applying linear interpolation between two vertices of the polygon.
Boundary Point Check:
The isBoundary function identifies whether a given point represents the boundary of a polygon edge. It assesses collinearity by comparing the point with the edge using a specific line equation and validates if the point falls within the segment's limits.
Area Calculation:
The calculateArea method calculates the polygon's area by employing Pick's Theorem. Initially, it determines the polygon's bounding box by computing the minimum and maximum x and y coordinates. Subsequently, it loops through each horizontal scanline (from the minimum y value to the maximum y value) and identifies the intersections of the scanline with the edges of the polygon.
The function gathers points of intersection for each scanline, arranges them in order, and tallies the number of points inside the region bounded by consecutive intersections. It solely considers the grid points located within the boundary or the polygon.
Input and Output:
The vertices of the polygon are provided by the user. Subsequently, the application calculates and showcases the polygon's area utilizing Pick's Theorem, along with displaying the polygon's vertices.
Complexity Analysis:
Time Complexity:
The Optimized Scanline Algorithm's time complexity is based on the quantity of polygon edges and scanlines. When dealing with a polygon containing n vertices, where h represents the bounding box height (maximum y coordinate minus minimum y coordinate), the algorithm determines intersections with the polygon edges for each scanline, requiring O(n) operations. The process of examining all lattice points within the bounding box amounts to O(n×h), while sorting these intersections for each scanline has a time complexity of O(n×h+klogk). This approach proves to be a more effective solution due to its efficiency.
Space Complexity:
This is determined by the storage of polygon vertices, intersections and boundary points, each having their own space complexity. For each scanline, the program stores the intersections in an O(k) sized temporary array , and stores the polygon vertices in an array of size O(n). As a result, the space complexity is O(n+k).
