113 lines
3.8 KiB
C++
113 lines
3.8 KiB
C++
#include <iostream>
|
|
|
|
using namespace std;
|
|
|
|
struct point2D { float x, y; };
|
|
|
|
const int N = 99; // clipped (new) polygon size
|
|
|
|
// check if a point is on the LEFT side of an edge
|
|
bool inside(point2D p, point2D p1, point2D p2)
|
|
{
|
|
return (p2.y - p1.y) * p.x + (p1.x - p2.x) * p.y + (p2.x * p1.y - p1.x * p2.y) < 0;
|
|
}
|
|
|
|
// calculate intersection point
|
|
point2D intersection(point2D cp1, point2D cp2, point2D s, point2D e)
|
|
{
|
|
point2D dc = { cp1.x - cp2.x, cp1.y - cp2.y };
|
|
point2D dp = { s.x - e.x, s.y - e.y };
|
|
|
|
float n1 = cp1.x * cp2.y - cp1.y * cp2.x;
|
|
float n2 = s.x * e.y - s.y * e.x;
|
|
float n3 = 1.0 / (dc.x * dp.y - dc.y * dp.x);
|
|
|
|
return { (n1 * dp.x - n2 * dc.x) * n3, (n1 * dp.y - n2 * dc.y) * n3 };
|
|
}
|
|
|
|
// Sutherland-Hodgman clipping
|
|
void SutherlandHodgman(point2D *subjectPolygon, int &subjectPolygonSize, point2D *clipPolygon, int &clipPolygonSize, point2D (&newPolygon)[N], int &newPolygonSize)
|
|
{
|
|
point2D cp1, cp2, s, e, inputPolygon[N];
|
|
|
|
// copy subject polygon to new polygon and set its size
|
|
for(int i = 0; i < subjectPolygonSize; i++)
|
|
newPolygon[i] = subjectPolygon[i];
|
|
|
|
newPolygonSize = subjectPolygonSize;
|
|
|
|
for(int j = 0; j < clipPolygonSize; j++)
|
|
{
|
|
// copy new polygon to input polygon & set counter to 0
|
|
for(int k = 0; k < newPolygonSize; k++){ inputPolygon[k] = newPolygon[k]; }
|
|
int counter = 0;
|
|
|
|
// get clipping polygon edge
|
|
cp1 = clipPolygon[j];
|
|
cp2 = clipPolygon[(j + 1) % clipPolygonSize];
|
|
|
|
for(int i = 0; i < newPolygonSize; i++)
|
|
{
|
|
// get subject polygon edge
|
|
s = inputPolygon[i];
|
|
e = inputPolygon[(i + 1) % newPolygonSize];
|
|
|
|
// Case 1: Both vertices are inside:
|
|
// Only the second vertex is added to the output list
|
|
if(inside(s, cp1, cp2) && inside(e, cp1, cp2))
|
|
newPolygon[counter++] = e;
|
|
|
|
// Case 2: First vertex is outside while second one is inside:
|
|
// Both the point of intersection of the edge with the clip boundary
|
|
// and the second vertex are added to the output list
|
|
else if(!inside(s, cp1, cp2) && inside(e, cp1, cp2))
|
|
{
|
|
newPolygon[counter++] = intersection(cp1, cp2, s, e);
|
|
newPolygon[counter++] = e;
|
|
}
|
|
|
|
// Case 3: First vertex is inside while second one is outside:
|
|
// Only the point of intersection of the edge with the clip boundary
|
|
// is added to the output list
|
|
else if(inside(s, cp1, cp2) && !inside(e, cp1, cp2))
|
|
newPolygon[counter++] = intersection(cp1, cp2, s, e);
|
|
|
|
// Case 4: Both vertices are outside
|
|
else if(!inside(s, cp1, cp2) && !inside(e, cp1, cp2))
|
|
{
|
|
// No vertices are added to the output list
|
|
}
|
|
}
|
|
// set new polygon size
|
|
newPolygonSize = counter;
|
|
}
|
|
}
|
|
|
|
int main(int argc, char** argv)
|
|
{
|
|
// subject polygon
|
|
point2D subjectPolygon[] = {
|
|
{50,150}, {200,50}, {350,150},
|
|
{350,300},{250,300},{200,250},
|
|
{150,350},{100,250},{100,200}
|
|
};
|
|
int subjectPolygonSize = sizeof(subjectPolygon) / sizeof(subjectPolygon[0]);
|
|
|
|
// clipping polygon
|
|
point2D clipPolygon[] = { {100,100}, {300,100}, {300,300}, {100,300} };
|
|
int clipPolygonSize = sizeof(clipPolygon) / sizeof(clipPolygon[0]);
|
|
|
|
// define the new clipped polygon (empty)
|
|
int newPolygonSize = 0;
|
|
point2D newPolygon[N] = { 0 };
|
|
|
|
// apply clipping
|
|
SutherlandHodgman(subjectPolygon, subjectPolygonSize, clipPolygon, clipPolygonSize, newPolygon, newPolygonSize);
|
|
|
|
// print clipped polygon points
|
|
cout << "Clipped polygon points:" << endl;
|
|
for(int i = 0; i < newPolygonSize; i++)
|
|
cout << "(" << newPolygon[i].x << ", " << newPolygon[i].y << ")" << endl;
|
|
|
|
return 0;
|
|
}
|