目录
一、算法介绍
二、算法描述
三、计算细节补充
四、算法总结
一、算法介绍
我们使用Sutherland–Hodgman算法来裁剪多边形的边,一般是给你一个多边形顶点序列(P1,P2,P3,P4,…Pn)让你裁剪,最终裁剪掉裁剪多边形的外部部分(下图黑框就是裁剪多边形)。像这样:
二、算法描述
首先,我们需要了解多边形的各条边与裁剪线的位置关系,一共只有四种:
① 仅输出顶点Pk
② 输出为空
③ 输出交点和Pk
④ 仅输出交点
每次裁剪完,输出一个顶点序列,作为下一次裁剪的输入。于是我们便可以按照如下顺序,对多边形进行裁剪:
综上,即可完成对多边形的裁剪。
三、计算细节补充
1、如何判断一个点,在裁剪多边形其中一条线的内部还是外部(可见侧还是不可见侧)
解:设你要拿来判断的裁剪多边形的其中一条线段,它的两个端点坐标分别是(x1,y1),(x2,y2),你要拿来判断的点的坐标为(x,y),则可以通过下列公式判断:
如果 P < 0,则这个点位于线的右边
如果 P = 0,则这个点位于线上
如果 P > 0,则这个点位于线的左边
这个公式的使用前提是,题目给你提供的裁剪多边形的顶点序列是顺时针的,这样的话右边就是内部(可见侧),左边就是外部(不可见侧)。
2、如何求得线段与裁剪多边形其中一条线段的交点
解:设线段两个端点为(x1,y1),(x2,y2),裁剪多边形其中一点线段两端点为(x3,y3),(x4,y4),则可以通过以下公式求解:
四、算法总结
代码如下,来源(Polygon Clipping | Sutherland–Hodgman Algorithm - GeeksforGeeks)
// C++ program for implementing Sutherland–Hodgman
// algorithm for polygon clipping
#include<iostream>
using namespace std;
const int MAX_POINTS = 20;
// Returns x-value of point of intersection of two
// lines
int x_intersect(int x1, int y1, int x2, int y2,
int x3, int y3, int x4, int y4)
{
int num = (x1*y2 - y1*x2) * (x3-x4) -
(x1-x2) * (x3*y4 - y3*x4);
int den = (x1-x2) * (y3-y4) - (y1-y2) * (x3-x4);
return num/den;
}
// Returns y-value of point of intersection of
// two lines
int y_intersect(int x1, int y1, int x2, int y2,
int x3, int y3, int x4, int y4)
{
int num = (x1*y2 - y1*x2) * (y3-y4) -
(y1-y2) * (x3*y4 - y3*x4);
int den = (x1-x2) * (y3-y4) - (y1-y2) * (x3-x4);
return num/den;
}
// This functions clips all the edges w.r.t one clip
// edge of clipping area
void clip(int poly_points[][2], int &poly_size,
int x1, int y1, int x2, int y2)
{
int new_points[MAX_POINTS][2], new_poly_size = 0;
// (ix,iy),(kx,ky) are the co-ordinate values of
// the points
for (int i = 0; i < poly_size; i++)
{
// i and k form a line in polygon
int k = (i+1) % poly_size;
int ix = poly_points[i][0], iy = poly_points[i][1];
int kx = poly_points[k][0], ky = poly_points[k][1];
// Calculating position of first point
// w.r.t. clipper line
int i_pos = (x2-x1) * (iy-y1) - (y2-y1) * (ix-x1);
// Calculating position of second point
// w.r.t. clipper line
int k_pos = (x2-x1) * (ky-y1) - (y2-y1) * (kx-x1);
// Case 1 : When both points are inside
if (i_pos < 0 && k_pos < 0)
{
//Only second point is added
new_points[new_poly_size][0] = kx;
new_points[new_poly_size][1] = ky;
new_poly_size++;
}
// Case 2: When only first point is outside
else if (i_pos >= 0 && k_pos < 0)
{
// Point of intersection with edge
// and the second point is added
new_points[new_poly_size][0] = x_intersect(x1,
y1, x2, y2, ix, iy, kx, ky);
new_points[new_poly_size][1] = y_intersect(x1,
y1, x2, y2, ix, iy, kx, ky);
new_poly_size++;
new_points[new_poly_size][0] = kx;
new_points[new_poly_size][1] = ky;
new_poly_size++;
}
// Case 3: When only second point is outside
else if (i_pos < 0 && k_pos >= 0)
{
//Only point of intersection with edge is added
new_points[new_poly_size][0] = x_intersect(x1,
y1, x2, y2, ix, iy, kx, ky);
new_points[new_poly_size][1] = y_intersect(x1,
y1, x2, y2, ix, iy, kx, ky);
new_poly_size++;
}
// Case 4: When both points are outside
else
{
//No points are added
}
}
// Copying new points into original array
// and changing the no. of vertices
poly_size = new_poly_size;
for (int i = 0; i < poly_size; i++)
{
poly_points[i][0] = new_points[i][0];
poly_points[i][1] = new_points[i][1];
}
}
// Implements Sutherland–Hodgman algorithm
void suthHodgClip(int poly_points[][2], int poly_size,
int clipper_points[][2], int clipper_size)
{
//i and k are two consecutive indexes
for (int i=0; i<clipper_size; i++)
{
int k = (i+1) % clipper_size;
// We pass the current array of vertices, it's size
// and the end points of the selected clipper line
clip(poly_points, poly_size, clipper_points[i][0],
clipper_points[i][1], clipper_points[k][0],
clipper_points[k][1]);
}
// Printing vertices of clipped polygon
for (int i=0; i < poly_size; i++)
cout << '(' << poly_points[i][0] <<
", " << poly_points[i][1] << ") ";
}
//Driver code
int main()
{
// Defining polygon vertices in clockwise order
int poly_size = 3;
int poly_points[20][2] = {{100,150}, {200,250},
{300,200}};
// Defining clipper polygon vertices in clockwise order
// 1st Example with square clipper
int clipper_size = 4;
int clipper_points[][2] = {{150,150}, {150,200},
{200,200}, {200,150} };
// 2nd Example with triangle clipper
/*int clipper_size = 3;
int clipper_points[][2] = {{100,300}, {300,300},
{200,100}};*/
//Calling the clipping function
suthHodgClip(poly_points, poly_size, clipper_points,
clipper_size);
return 0;
}
Sutherland–Hodgman算法的缺点:仅适用于凸多边形,对于凹多边形的裁剪将如图所示显示出一条多余的直线。 文章来源:https://www.toymoban.com/news/detail-794879.html
如果想避免此问题,需要使用Weiler-Atherton算法,该算法可以避免残留。 文章来源地址https://www.toymoban.com/news/detail-794879.html
到了这里,关于Sutherland–Hodgman 算法介绍(简单易懂)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!