源代碼： https://github.com/ricar0/Weiler-Atherton-Alogrithm/tree/master
什么是多邊形裁剪
通常來說就是利用多邊形來裁剪多邊形的一種方法，一般情況下是利用矩形來裁剪凹凸多邊形
- 凸多邊形
- 凹多邊形
上面紅色劃線部分就是裁剪出的部分
前置知識
- OPENGL基礎(chǔ)語法
基本上就是一些畫線和畫多邊形的操作，難度較低 - 求兩直線交點
較為基礎(chǔ)的數(shù)學知識 - 求一個點是否落在多邊形內(nèi)/外
計算幾何知識 - Weiler-Atherton多邊形裁剪算法
這里著重介紹Weiler-Atherton算法，其余不懂的可以先學會再看。
算法步驟
- 首先繪制兩個相交的多邊形
- 對于多邊形1，我們從一個點出發(fā)，將所有經(jīng)過的點（包含交點）存入新的數(shù)組中，對于多邊形2也是同理
- 對兩個新數(shù)組中的相同點進行點對映射
- 開始對裁剪多邊形1進行遍歷，從任意點出發(fā)，如果改點將從多邊形2的內(nèi)部穿越到外部，我們改變遍歷點的對象，從多邊形2開始遍歷，依次類推…
- 直到當前點被遍歷過，那么之前肯定形成了一個回路，我們將當前回路繪制出來就是裁剪出的多邊形。
- 一直重復(fù)4和5操作，直到所有點都被遍歷
接下來結(jié)合圖片解釋一下
對于如下這個圖，我們利用矩形裁剪凹多邊形。
首先從E點出發(fā)，判斷E到J是否為出點，發(fā)現(xiàn)不是。遍歷到J點，判斷JF是否是出點，發(fā)現(xiàn)是，這時候改變遍歷的對象，通過映射關(guān)系從K點開始。判斷發(fā)現(xiàn)KC又是出點，因此再次改變遍歷對象，遍歷多邊形到E，發(fā)現(xiàn)J已經(jīng)被遍歷過，這時直接繪制出JKE…
程序框圖
代碼實現(xiàn)
建立窗口以及自動調(diào)整大小
void reshape(int w, int h) {
glViewport(0, 0, w, h);
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
gluPerspective(60.0, (GLfloat)w / (GLfloat)h, 0.1, 100000.0);
glMatrixMode(GL_MODELVIEW);
glLoadIdentity();
gluLookAt(0, 0, 25, 0, 0, -1, 0, 1, 0);
}
int main(int argc,char** argv) {
glutInit(&argc, const_cast<char**>(argv));
glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
// 初始化窗口
glutInitWindowSize(500, 500);
glutInitWindowPosition(100, 100);
glutCreateWindow(argv[0]);
init();
glutReshapeFunc(reshape);
glutDisplayFunc(display);
glutMainLoop();
}
建立點和線
struct Point2d {
double x, y;
bool operator < (const Point2d &rhs) const {
if (x==rhs.x) return y < rhs.y;
return x < rhs.x;
}
};
struct Line{
Point2d start;
Point2d end;
};
求兩條線段交點的模板，如果不存在返回-inf
inline Point2d Vector(Point2d a, Point2d b) { //向量ab
return{ b.x - a.x, b.y - a.y };
}
double dis2(Point2d a, Point2d b) { //兩點間的距離的平方
return (b.x - a.x)*(b.x - a.x) + (b.y - a.y)*(b.y - a.y);
}
double cross(Point2d A, Point2d B, Point2d P) { //向量的外積
Point2d AB = Vector(A,B);
Point2d AP = Vector(A,P);
return AB.x*AP.y - AB.y*AP.x;
}
double dot(Point2d A, Point2d B, Point2d P) { //向量的內(nèi)積
Point2d AB = Vector(A,B);
Point2d AP = Vector(A,P);
return AB.x*AP.x + AB.y*AP.y;
}
int dir(Point2d A, Point2d B, Point2d P) { //點與線段方位判定
if (cross(A, B, P) > 0) return -1;
else if (cross(A, B, P)<0) return 1;
else if (dot(A, B, P) < 0) return -2;
else if (dot(A, B, P) >= 0)
{
if (dis2(A, B) < dis2(A, P)) return 2;
else return 0;
}
return 0;
}
double disLine(Point2d A, Point2d B, Point2d P) { //點P到直線AB的距離
return fabs(cross(A, B, P)) / sqrt(dis2(A, B));
}
Point2d intersection(Line u, Line v) {
Point2d A1 = u.start;
Point2d A2 = u.end;
Point2d B1 = v.start;
Point2d B2 = v.end;
if (dir(A1, A2, B1)*dir(A1, A2, B2) <= 0 && dir(B1, B2, A1)*dir(B1, B2, A2) <= 0) {//判斷有無交點
double t = disLine(A1, A2, B1) / (disLine(A1, A2, B1) + disLine(A1, A2, B2));
Point2d B1B2 = Vector(B1, B2);
Point2d inter = { B1.x + B1B2.x*t, B1.y + B1B2.y*t };
return {inter.x, inter.y};
} else {
return {-inf, -inf};
}
}
求兩點距離，用于排序
double dis(Point2d point1, Point2d point2) {
return sqrt((point1.x-point2.x)*(point1.x-point2.x) + (point1.y-point2.y)*(point1.y-point2.y));
}
判斷點是否落在多邊形內(nèi)，這里加了個誤差0.001
bool isPointInsidePoly(Point2d P,const vector<Point2d>& polyVertices) {
std::size_t vertCount = polyVertices.size();
if (vertCount < 2)
return false;
Point2d tmp = P;
for (int l = 0; l < 2; l++) {
for (int r = 0; r < 2; r++) {
P = tmp;
if (l % 2) P.x += 0.001;
else P.x -= 0.001;
if (r % 2) P.y += 0.001;
else P.y -= 0.001;
bool inside = false;
for (unsigned i = 1; i <= vertCount; ++i) {
const Point2d &A = polyVertices[i - 1];
const Point2d &B = polyVertices[i % vertCount];
if ((B.y <= P.y && P.y < A.y) || (A.y <= P.y && P.y < B.y)) {
double t = (P.x - B.x) * (A.y - B.y) - (A.x - B.x) * (P.y - B.y);
if (A.y < B.y)
t = -t;
if (t < 0)
inside = !inside;
}
}
if (inside) return inside;
}
}
return false;
}
求交點以及重新放入數(shù)組
void getIntersections() {//求出所有交點以及按照順序存放在新數(shù)組中
int len1 = poly1.size();//求出new1
for (int i = 0; i < len1; i++) {
new1.push_back(poly1[i]);
vector<Point2d> tmp;
for (auto it2 : p2) {
Point2d p = intersection({{poly1[i].x, poly1[i].y},{poly1[(i+1)%len1].x, poly1[(i+1)%len1].y}}, it2);
if (p.x != -inf && p.y != -inf) tmp.push_back({p.x, p.y});
}
sort(tmp.begin(), tmp.end(), [&](Point2d p1, Point2d p2){
return dis(p1, poly1[i]) < dis(p2, poly1[i]);
});
for (auto it : tmp) new1.push_back(it);
}
int len2 = poly2.size();//求出new2
for (int i = 0; i < len2; i++) {
new2.push_back(poly2[i]);
vector<Point2d> tmp;
for (auto it2 : p1) {
Point2d p = intersection({{poly2[i].x, poly2[i].y},{poly2[(i+1)%len2].x, poly2[(i+1)%len2].y}}, it2);
if (p.x != -inf && p.y != -inf) tmp.push_back({p.x, p.y});
}
sort(tmp.begin(), tmp.end(), [&](Point2d p1, Point2d p2){
return dis(p1, poly2[i]) < dis(p2, poly2[i]);
});
for (auto it : tmp) new2.push_back(it);
}
for (int i = 0; i < new1.size(); i++) {//映射關(guān)系，給定eps為誤差范圍
for (int j = 0; j < new2.size(); j++) {
if (fabs(new1[i].x-new2[j].x)<eps&&fabs(new1[i].y-new2[j].y)<eps) {
pos1[i] = j;
pos2[j] = i;
}
}
}
work();
}
繪制兩個多邊形以及初始化操作
void prework() {
p1.clear();
p2.clear();
new1.clear();
new2.clear();
vis1.clear();
vis2.clear();
pos1.clear();
pos2.clear();
}
void display() {
prework();//初始化
glClear(GL_COLOR_BUFFER_BIT);
glBegin(GL_LINES);
glColor3f(1.0, 1.0, 1.0);
int len1 = poly1.size();//繪制多邊形
for (int i = 0; i < len1; i++) {
glVertex2f(poly1[i].x, poly1[i].y);
glVertex2f(poly1[(i+1)%len1].x, poly1[(i+1)%len1].y);
p1.push_back({{poly1[i].x, poly1[i].y}, {poly1[(i+1)%len1].x, poly1[(i+1)%len1].y}});
}
int len2 = poly2.size();
for (int i = 0; i < len2; i++) {
glVertex2f(poly2[i].x, poly2[i].y);
glVertex2f(poly2[(i+1)%len2].x, poly2[(i+1)%len2].y);
p2.push_back({{poly2[i].x, poly2[i].y}, {poly2[(i+1)%len2].x, poly2[(i+1)%len2].y}});
}
getIntersections();
glEnd();
glFlush();
}
最核心的代碼，遍歷兩個多邊形文章來源：http://www.zghlxwxcb.cn/news/detail-405774.html
void work() {
vector<Point2d> now;//當前選擇到的點
int len1 = new1.size();
int len2 = new2.size();
for (int i = 0; i < new1.size(); i++) {//new1 第一個新多邊形 new2第一個新多邊形
if (vis1[i]) continue;
int ch = 1, nowpos = i;
while (1) {
if (ch == 1) {//遍歷第一個多邊形
if (isPointInsidePoly(new1[nowpos], poly2)) now.push_back(new1[nowpos]);
if (vis1[nowpos]) {//如果該點遍歷過
glBegin(GL_LINES);
glColor3f(1, 0, 0);
for (int j = 0; j < now.size(); j++) {//繪制交多邊形
glVertex2f(now[j].x, now[j].y);
glVertex2f(now[(j+1)%now.size()].x, now[(j+1)%now.size()].y);
}
now.clear();
glEnd();
glFlush();
break;
}
vis1[nowpos] = true;//給當前經(jīng)歷點打上標記
if (isPointInsidePoly(new1[nowpos], poly2) && !isPointInsidePoly(new1[(nowpos+1)%len1], poly2)) {//判斷是否為出點
ch = 2;
nowpos = pos1[nowpos];
nowpos = (nowpos + 1) % len2;
} else {
nowpos = (nowpos + 1) % len1;
}
} else {//遍歷第二個多邊形
if (isPointInsidePoly(new2[nowpos], poly1)) now.push_back(new2[nowpos]);
if (vis2[nowpos]) {//如果該點遍歷過
glBegin(GL_LINES);
glColor3f(1, 0, 0);
for (int j = 0; j < now.size(); j++) {//繪制交多邊形
glVertex2f(now[j].x, now[j].y);
glVertex2f(now[(j+1)%now.size()].x, now[(j+1)%now.size()].y);
}
now.clear();
glEnd();
glFlush();
break;
}
vis2[nowpos] = true;//給當前點打上標記
if (isPointInsidePoly(new2[nowpos], poly1) && !isPointInsidePoly(new2[(nowpos+1)%len2], poly1)) {//判斷是否為出點
ch = 1;
nowpos = pos2[nowpos];
nowpos = (nowpos + 1) % len1;
} else {
nowpos = (nowpos + 1) % len2;
}
}
}
}
}
這里存入需要繪制的兩個多邊形，按順序存文章來源地址http://www.zghlxwxcb.cn/news/detail-405774.html
void init() {
poly1.clear();
poly2.clear();
// poly1.push_back({-5, -5});
// poly1.push_back({-5, 5});
// poly1.push_back({5, 5});
// poly1.push_back({5, -5});
//
// poly2.push_back({-7, 0});
// poly2.push_back({0, 7});
// poly2.push_back({7, 0});
// poly2.push_back({0, -7});
// poly1.push_back({0, -6});
// poly1.push_back({-3, -3});
// poly1.push_back({0, 3});
// poly1.push_back({3, 0});
//
// poly2.push_back({0, -3});
// poly2.push_back({-3, 3});
// poly2.push_back({0, 6});
// poly2.push_back({3, 3});
// poly1.push_back({-8, -6});
// poly1.push_back({-8, 6});
// poly1.push_back({8, 6});
// poly1.push_back({8, -6});
//
// poly2.push_back({-2, 10});
// poly2.push_back({12, -6});
// poly2.push_back({-2, 2});
// poly2.push_back({-12, -6});
poly2.push_back({-6, -3});
poly2.push_back({-6, 3});
poly2.push_back({6, 3});
poly2.push_back({6, -3});
poly1.push_back({-1.98, 0.91});
poly1.push_back({4, 6});
poly1.push_back({12, 6});
poly1.push_back({4, -2});
poly1.push_back({8, 4.7});
glClearColor(0.0, 0.3, 0.7, 0.0);
glShadeModel(GL_SMOOTH);
}
到了這里，關(guān)于【W(wǎng)eiler-Atherton算法】 計算機圖形學多邊形裁剪算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
