How to clip against an edge of clipping area?
To clip a polygon against an edge of the clipping area, we need to compare each vertex of the polygon with the clipping edge. Let's consider a clipping edge defined by two points: (x1, y1) & (x2, y2). We can determine the position of a vertex (x, y) relative to this edge with the help of below mentioned steps:
1. Calculate the equation of the clipping edge using the two points:
- Slope: m = (y2 - y1) / (x2 - x1)
- Y-intercept: b = y1 - m * x1
2. Substitute the vertex coordinates (x, y) into the edge equation:
- Edge equation: y = m * x + b
- If y > m * x + b, the vertex is above the edge (outside).
- If y < m * x + b, the vertex is below the edge (inside).
- If y = m * x + b, the vertex is on the edge.
3. If the vertex is inside the clipping edge, add it to the output list.
4. If the vertex is outside the clipping edge, check if the edge formed by the current vertex & the previous vertex intersects with the clipping edge:
- If the previous vertex was inside, calculate the intersection point & add it to the output list.
- If the previous vertex was outside, do nothing.
5. Move to the next vertex & repeat steps 2-4 until all vertices have been processed.
By using these steps for each clipping edge (left, right, top, & bottom), we can clip the polygon against the entire clipping rectangle. The output list will contain the vertices of the clipped polygon.
It's important to handle special cases, such as vertical or horizontal clipping edges, by using appropriate comparisons based on the edge's orientation. Additionally, when calculating intersection points, be cautious of floating-point precision issues & use appropriate tolerance values if necessary.
Code Implementation
- C++
- Python
- Java
- JavaScript
C++
#include <iostream>
#include <vector>
struct Point {
double x, y;
};
std::vector<Point> clipPolygon(const std::vector<Point>& polygon, double x1, double y1, double x2, double y2) {
std::vector<Point> clippedPolygon;
for (size_t i = 0; i < polygon.size(); i++) {
Point current = polygon[i];
Point previous = polygon[(i + polygon.size() - 1) % polygon.size()];
if (current.y >= y1) {
if (previous.y < y1) {
double x = previous.x + (y1 - previous.y) * (current.x - previous.x) / (current.y - previous.y);
clippedPolygon.push_back({x, y1});
}
clippedPolygon.push_back(current);
} else if (previous.y >= y1) {
double x = previous.x + (y1 - previous.y) * (current.x - previous.x) / (current.y - previous.y);
clippedPolygon.push_back({x, y1});
}
}
return clippedPolygon;
}
// Usage example
int main() {
std::vector<Point> polygon = {{0, 0}, {100, 0}, {100, 100}, {0, 100}};
double x1 = 20, y1 = 20, x2 = 80, y2 = 80;
std::vector<Point> clippedPolygon = clipPolygon(polygon, x1, y1, x2, y2);
for (const Point& p : clippedPolygon) {
std::cout << "(" << p.x << ", " << p.y << ")" << std::endl;
}
return 0;
}
You can also try this code with Online C++ Compiler
Python
def clip_polygon(polygon, x1, y1, x2, y2):
clipped_polygon = []
for i in range(len(polygon)):
current = polygon[i]
previous = polygon[(i - 1) % len(polygon)]
if current[1] >= y1:
if previous[1] < y1:
x = previous[0] + (y1 - previous[1]) * (current[0] - previous[0]) / (current[1] - previous[1])
clipped_polygon.append((x, y1))
clipped_polygon.append(current)
elif previous[1] >= y1:
x = previous[0] + (y1 - previous[1]) * (current[0] - previous[0]) / (current[1] - previous[1])
clipped_polygon.append((x, y1))
return clipped_polygon
# Usage example
polygon = [(0, 0), (100, 0), (100, 100), (0, 100)]
x1, y1, x2, y2 = 20, 20, 80, 80
clipped_polygon = clip_polygon(polygon, x1, y1, x2, y2)
for point in clipped_polygon:
print(f"({point[0]}, {point[1]})")
def clip_polygon(polygon, x1, y1, x2, y2):
clipped_polygon = []
for i in range(len(polygon)):
current = polygon[i]
previous = polygon[(i - 1) % len(polygon)]
if current[1] >= y1:
if previous[1] < y1:
x = previous[0] + (y1 - previous[1]) * (current[0] - previous[0]) / (current[1] - previous[1])
clipped_polygon.append((x, y1))
clipped_polygon.append(current)
elif previous[1] >= y1:
x = previous[0] + (y1 - previous[1]) * (current[0] - previous[0]) / (current[1] - previous[1])
clipped_polygon.append((x, y1))
return clipped_polygon
# Usage example
polygon = [(0, 0), (100, 0), (100, 100), (0, 100)]
x1, y1, x2, y2 = 20, 20, 80, 80
clipped_polygon = clip_polygon(polygon, x1, y1, x2, y2)
for point in clipped_polygon:
print(f"({point[0]}, {point[1]})")
You can also try this code with Online Python Compiler
Java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class PolygonClipping {
static class Point {
double x, y;
Point(double x, double y) {
this.x = x;
this.y = y;
}
}
static List<Point> clipPolygon(List<Point> polygon, double x1, double y1, double x2, double y2) {
List<Point> clippedPolygon = polygon;
clippedPolygon = clipSide(clippedPolygon, x1, y1, x2, y2, "left");
clippedPolygon = clipSide(clippedPolygon, x1, y1, x2, y2, "right");
clippedPolygon = clipSide(clippedPolygon, x1, y1, x2, y2, "bottom");
clippedPolygon = clipSide(clippedPolygon, x1, y1, x2, y2, "top");
return clippedPolygon;
}
static List<Point> clipSide(List<Point> polygon, double x1, double y1, double x2, double y2, String side) {
List<Point> clippedPolygon = new ArrayList<>();
for (int i = 0; i < polygon.size(); i++) {
Point current = polygon.get(i);
Point previous = polygon.get((i + polygon.size() - 1) % polygon.size());
boolean currentInside = isInside(current, x1, y1, x2, y2, side);
boolean previousInside = isInside(previous, x1, y1, x2, y2, side);
if (currentInside) {
if (!previousInside) {
clippedPolygon.add(intersection(previous, current, x1, y1, x2, y2, side));
}
clippedPolygon.add(current);
} else if (previousInside) {
clippedPolygon.add(intersection(previous, current, x1, y1, x2, y2, side));
}
}
return clippedPolygon;
}
static boolean isInside(Point p, double x1, double y1, double x2, double y2, String side) {
switch (side) {
case "left": return p.x >= x1;
case "right": return p.x <= x2;
case "bottom": return p.y >= y1;
case "top": return p.y <= y2;
default: return false;
}
}
static Point intersection(Point p1, Point p2, double x1, double y1, double x2, double y2, String side) {
double x = 0, y = 0;
switch (side) {
case "left":
x = x1;
y = p1.y + (p2.y - p1.y) * (x1 - p1.x) / (p2.x - p1.x);
break;
case "right":
x = x2;
y = p1.y + (p2.y - p1.y) * (x2 - p1.x) / (p2.x - p1.x);
break;
case "bottom":
x = p1.x + (p2.x - p1.x) * (y1 - p1.y) / (p2.y - p1.y);
y = y1;
break;
case "top":
x = p1.x + (p2.x - p1.x) * (y2 - p1.y) / (p2.y - p1.y);
y = y2;
break;
}
return new Point(x, y);
}
public static void main(String[] args) {
List<Point> polygon = Arrays.asList(
new Point(0, 0), new Point(100, 0),
new Point(100, 100), new Point(0, 100)
);
double x1 = 20, y1 = 20, x2 = 80, y2 = 80;
List<Point> clippedPolygon = clipPolygon(polygon, x1, y1, x2, y2);
for (Point p : clippedPolygon) {
System.out.println("(" + p.x + ", " + p.y + ")");
}
}
}
You can also try this code with Online Java Compiler
JavaScript
function clipPolygon(polygon, x1, y1, x2, y2) {
const clippedPolygon = [];
for (let i = 0; i < polygon.length; i++) {
const current = polygon[i];
const previous = polygon[(i + polygon.length - 1) % polygon.length];
if (current[1] >= y1) {
if (previous[1] < y1) {
const x = previous[0] + (y1 - previous[1]) * (current[0] - previous[0]) / (current[1] - previous[1]);
clippedPolygon.push([x, y1]);
}
clippedPolygon.push(current);
} else if (previous[1] >= y1) {
const x = previous[0] + (y1 - previous[1]) * (current[0] - previous[0]) / (current[1] - previous[1]);
clippedPolygon.push([x, y1]);
}
}
return clippedPolygon;
}
// Usage example
const polygon = [[0, 0], [100, 0], [100, 100], [0, 100]];
const [x1, y1, x2, y2] = [20, 20, 80, 80];
const clippedPolygon = clipPolygon(polygon, x1, y1, x2, y2);
for (const [x, y] of clippedPolygon) {
console.log(`(${x}, ${y})`);
}
You can also try this code with Online Javascript Compiler
Output
(20.0, 80.0)
(20.0, 20.0)
(80.0, 20.0)
(80.0, 80.0)
Frequently Asked Questions
Can the Sutherland-Hodgman algorithm handle concave polygons?
Yes, the algorithm can handle both convex & concave polygons effectively.
Is the Sutherland-Hodgman algorithm efficient for complex polygons?
The algorithm has a time complexity of O(n), where n is the number of vertices in the polygon, making it efficient for most practical scenarios.
Can the algorithm be extended to 3D clipping?
While the Sutherland-Hodgman algorithm is primarily used for 2D clipping, the concepts can be extended to handle 3D clipping by considering additional dimensions & clipping planes.
Conclusion
In this article, we explained the Sutherland-Hodgman polygon clipping algorithm, which is widely used in computer graphics to clip polygons against a clipping area. We discussed the overview of the algorithm, how it clips against an edge of the clipping area, & saw code implementation in C++, Python, Java, & JavaScript.
You can also check out our other blogs on Code360.
19+ registered 
