在OpenGL中填充自相交多邊形

Question

我有一個自交多邊形，我嘗試使用奇偶規則來填充，如下所示： 我使用掃描線，當檢測到多邊形的邊緣時，我更改填充顏色。這裏是我到目前爲止的代碼：

編輯的代碼：

#include<GL/glut.h> 
#include<vector> 
#include<fstream> 
#include<algorithm> 
#include<cmath> 
#include<limits> 
using namespace std; 
const int n = 7; 

class Point{ 
public: 
    int x, y; 
    Point(){ 
    }; 
    Point(int a, int b){ 
     x = a; 
     y = b; 
    }; 
    void set(int a, int b){ 
     x = a; 
     y = b; 
    }; 
}; 
Point P[n]; 
int min(int x, int y) 
{ 
    if (x <= y) return x; 
    else return y; 
} 
int max(int x, int y) 
{ 
    if (x >= y) return x; 
    else return y; 
} 

Point solve(Point A, Point B, Point C, Point D) 
{ //returns the intersection point between line segments [AB] and [CD] 
    Point rez; 
    rez.x = -1; 
    rez.y = -1; 
    //[AB] 
    int A1 = B.y - A.y, B1 = A.x - B.x, C1 = (A1 * A.x) + (B1 * A.y); 
    //[CD] 
    int A2 = D.y - C.y, B2 = C.x - D.x, C2 = (A2 * C.x) + (B2 * C.y); 

    int det = A1*B2 - A2*B1; 
    if (det == 0){ 
     return Point(-1, -1); 
    } 
    else 
    { 
     rez.x = (B2*C1 - B1*C2)/det; 
     rez.y = (A1*C2 - A2*C1)/det; 
    } 
    if (!(rez.x >= min(A.x, B.x) && rez.x <= max(A.x, B.x) && rez.x >= min(C.x, D.x) && rez.x <= max(C.x, D.x))) 
    { 
     rez.x = -1; 
     rez.y = -1; 
    } 

    return rez; 
} 
bool intComparison(int i, int j) { return (i < j); } 
void scanfill() 
{ 
    int i, j, color = 1, k; //alb 
    vector<int> inter[501]; 
    Point T; 



    for (j = 0; j < 500; j++) //go line by line 
    { 
     for (k = 0; k < n - 1; k++) //loop through all the line segments 
     { 
      T = solve(Point(0, j), Point(499, j), P[k], P[k + 1]); 
      if (!(T.x == -1 && T.y == -1)) 
      { 
       inter[j].push_back(T.x); // save the x coord. of the intersection point between the line and the sweep line when y = j 
      } 
     } 
     T = solve(Point(0, j), Point(499, j), P[n - 1], P[0]); 
     if (!(T.x == -1 && T.y == -1)) 
     { 
      inter[j].push_back(T.x); 
     } 
    } 
    for (j = 0; j < 500; j++) 
    { 
     sort(inter[j].begin(), inter[j].end(), intComparison); 
    } 

    for (j = 0; j < 500; j++) 
    { 
     glColor3f(0.0, 0.0, 1.0); 
     glBegin(GL_LINES); 
     for (vector<int>::iterator it = inter[j].begin(); it != inter[j].end(); it++) 
     { 
      glVertex2i(*it, j); //draw the actual lines 
     } 
     glEnd(); 

    } 



} 


void display() 
{ 
    glClear(GL_COLOR_BUFFER_BIT); 
    glColor3f(0.0, 0.0, 0.0); 

    P[0] = Point(100, 235); 
    P[1] = (Point(100, 100)); 
    P[2] = (Point(230, 140)); 
    P[3] = (Point(40, 200)); 
    P[4] = (Point(20, 60)); 
    P[5] = (Point(300, 150)); 
    P[6] = (Point(150, 111)); 
    glBegin(GL_LINE_LOOP); 
    for (int i = 0; i < n; i++) 
    { 
     glVertex2i(P[i].x, P[i].y); 
    } 
    glEnd(); 

    scanfill(); 


    glFlush(); 
} 


void init() 
{ 
    glClearColor(1.0, 1.0, 1.0, 1.0); 
    glMatrixMode(GL_PROJECTION); 
    glLoadIdentity(); 
    gluOrtho2D(0.0, 499.0, 0.0, 499.0); 
} 

void main(int argc, char **argv) 
{ 
    glutInit(&argc, argv); 
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB); 
    glutInitWindowSize(500, 500); 

    glutCreateWindow("scanline"); 
    glutDisplayFunc(display); 

    init(); 
    glutMainLoop(); 
} 

看來，以檢測掃描線和實際線比它應該出於某種原因與以上交點。 結果與上面的代碼：

所需的結果：

Answer 1

我設法解決這個問題。下面的代碼，如果其他人有興趣：

#include<GL/glut.h> 
#include<vector> 
#include<fstream> 
#include<algorithm> 
#include<cmath> 
#include<limits> 
using namespace std; 
const int n = 7; 

class Point{ 
public: 
    int x, y; 
    Point(){ 
    }; 
    Point(int a, int b){ 
     x = a; 
     y = b; 
    }; 
    void set(int a, int b){ 
     x = a; 
     y = b; 
    }; 
}; 
Point P[n]; 
int min(int x, int y) 
{ 
    if (x <= y) return x; 
    else return y; 
} 
int max(int x, int y) 
{ 
    if (x >= y) return x; 
    else return y; 
} 
double solve(int y, Point A, Point B) 
{ 
    if (y >= min(A.y, B.y) && y <= max(A.y, B.y)) 
    { 
     return ((y * B.x) - (y * A.x) - (A.y * B.x) + (A.x * B.y))/(B.y - A.y); 
    } 
    else return -1; 
} 

bool doubleComparison(double i, double j) { return (i < j); } 
bool isVertex(int x, int y) 
{ 
    for (int i = 0; i < n; i++) 
    { 
     if (P[i].x == x && P[i].y == y) return 1; 
    } 
    return 0; 
} 
void scanfill() 
{ 
    int i, j, color = 1, k; 
    double x; 
    vector<double> inter[501]; 

    for (j = 0; j < 500; j++) 
    { 
     for (k = 0; k < n - 1; k++) 
     { 
      x = solve(j, P[k], P[k + 1]); 
      if (x != -1 && !isVertex(x,j)) 
      { 
       inter[j].push_back(x); 
      } 
     } 
     x = solve(j, P[n - 1], P[0]); 
     if (x != -1 && !isVertex(x, j)) 
     { 
      inter[j].push_back(x); 
     } 
    } 
    for (j = 0; j < 500; j++) 
    { 
     sort(inter[j].begin(), inter[j].end(), doubleComparison); 
    } 

    for (j = 0; j < 500; j++) 
    { 
     glColor3f(0.0, 0.0, 1.0); 
     glBegin(GL_LINES); 
     for (vector<double>::iterator it = inter[j].begin(); it != inter[j].end(); it++) 
     { 
      glVertex2d(*it, j); 
     } 
     glEnd(); 

    } 



} 


void display() 
{ 
    glClear(GL_COLOR_BUFFER_BIT); 
    glColor3f(0.0, 0.0, 0.0); 

    P[0] = Point(100, 235); 
    P[1] = (Point(100, 100)); 
    P[2] = (Point(230, 140)); 
    P[3] = (Point(40, 200)); 
    P[4] = (Point(20, 60)); 
    P[5] = (Point(300, 150)); 
    P[6] = (Point(150, 111)); 
    glBegin(GL_LINE_LOOP); 
    for (int i = 0; i < n; i++) 
    { 
     glVertex2i(P[i].x, P[i].y); 
    } 
    glEnd(); 

    scanfill(); 


    glFlush(); 
} 


void init() 
{ 
    glClearColor(1.0, 1.0, 1.0, 1.0); 
    glMatrixMode(GL_PROJECTION); 
    glLoadIdentity(); 
    gluOrtho2D(0.0, 499.0, 0.0, 499.0); 
} 

void main(int argc, char **argv) 
{ 
    glutInit(&argc, argv); 
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB); 
    glutInitWindowSize(500, 500); 

    glutCreateWindow("scanline"); 
    glutDisplayFunc(display); 

    init(); 
    glutMainLoop(); 
}