#include <iostream>
#include <GLUT/GLUT.h>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;
int hmin,hmax;     //記錄掃描線開始和結(jié)束的位置
struct Line {     //定義線段的結(jié)構(gòu)體
 float dx,x,y,ym;    //不用記錄K直接記錄dx和x即可
 Line(float x1,float y1,float x2,float y2) {
 if(y1==y2){    //單獨討論橫直線的情況
  this->y = y1;
  this->ym = y1;
  if(x1 < x2){
  dx = x1; x = x2;
  }else{
  dx =x2;x = x1;}
 }else if(y2<y1){   //選擇靠上者的x值
  this -> x = x2;   //記錄上方的x值一方便處理關(guān)鍵時刻（用于插入AET排序）
  this ->y = y2;   //記錄上方的y值，用于排序
  this -> ym = y1;   //靠下者ym
 }else{
  this -> x = x1;
  this ->y = y1;
  this -> ym = y2;
 }
 dx = (x2-x1)/(y2-y1);
 }
};
typedef list<Line> TESTLIST;
vector<vector<Line>> con; //記錄重要事件表（有序），當然這個也可以使用優(yōu)先隊列
list<Line> AET;   //滾動記錄活動邊表,這里將
      //該邊表完整存儲的意義不大所以采用滾動存儲的方式
map<int, int> mapper;  //用于數(shù)據(jù)（y值）離散化處理
int x1,y1,x2,y2;   //描述構(gòu)成直線的兩個端點
int x0,y0;    //記錄圖形開始位置
float h_min,h_max;  //畫線開始和結(jié)束的位置
int flag = 1;    //用于記錄用戶點擊的次數(shù)，單次畫點，雙次畫線。
int if_drawable = 1;  //當用戶再次點擊鼠標時不在更改信息
int window_size=600;  //這是我們顯示界面的大小
vector<vector<Line>> con2;
int level = 1;
/*
 操作說明：算法沒有嚴格的圖形繪制檢查。僅為了圖形學(xué)算法的演示。
 您使用鼠標【左鍵】進行繪制點，請您保證沒有線是交叉的。
 當您點擊鼠標【右鍵】繪制最后一個點。系統(tǒng)會自動將其與起始點相連。
 整體思路描述：使用map將y的值離散化，用有序表記錄“關(guān)鍵事件”主要
 是加入邊（一條或者兩條）刪除邊操作。在用一個滾動的活動邊表進行遍歷畫線。
 */
void show_v(Line a){
 /*
 函數(shù)說明：顯示點的信息
 */
 cout << "(" <<a.x << "," << a.y <<")";
 cout << " (" <<a.dx<<")" << "下限："<<a.ym;
 cout << " -- "<<endl;
}
bool higher(const vector<Line> & l1, const vector<Line>& l2) {
 //將關(guān)鍵事件表中的line按照y值進行排序；
 //注意我們的畫布是從上到下不斷遞增從左到右不斷遞增
 return l1[0].y < l2[0].y;//可以保證一定至少有一個不然map不會映射到
}
bool AET_lefter(const Line & l1, const Line & l2) {
 //將AET表中的line按照x值進行排序；
 return l1.x < l2.x;//可以保證一定至少有一個不然map不會映射到
}
bool lefter(const Line & l1, const Line & l2) {
 /*
 函數(shù)說明：將關(guān)鍵事件表中的line按照x值以及dx進行排序；
 */
 if(l1.x < l2.x){
 return 1;
 }else if (l1.x == l2.x){
 if(l1.dx<0&&l2.dx>0)
  return 1;
 else
  return 0;
 }else
 return 0;
}
void sort_con(){
 /*
 函數(shù)說明：對關(guān)鍵事件表進行排序處理
 其中y從小到大遞增，x方向按照斜率和x大小由左到右排序
 */
 for (int i = 0 ; i < con.size(); i++)
 if (con[i].size()>=2)
  sort(con[i].begin(),con[i].end(),lefter);
 for (int i = 0;i < con.size(); i++) {
 vector<Line> a;
 for (int j =0; j < con[i].size(); j++)
  a.push_back(con[i][j]);
 con2.push_back(a);   //這里將事件表進行拷貝，另一種方式是將map的映射對應(yīng)改變
 }
 sort(con.begin(), con.end(), higher);
}
void draw_lines(float x1,float y1,float x2,float y2){
 glBegin(GL_LINES);
 glColor3f(1.0,1.0,0.0);
 glVertex2f(x1,window_size-y1);
 glVertex2f(x2,window_size-y2);
 glEnd();
 glFlush();
}
void show_con(){
 //輸出排序后的關(guān)鍵事件表
 for (int i = 0; i < con.size(); i++) {
 cout <<"number : "<<i <<endl;
 for (int j = 0; j < con[i].size(); j++) {
  vector<Line> a = con[i];
  show_v (a[j]);
 }cout <<"================"<<endl;
 }
}
void lines_filling(){    //真正的掃描線填充過程
 if (con.empty())    //為了展示過程細節(jié)，部分功能沒有使用函數(shù)ti
 return;
 int h_leveler = 0;    //高度遍歷器
 map<int,int>::iterator iter;  //定義一個迭代指針iter
 for(h_leveler = h_min;h_leveler <= h_max;h_leveler++){//開始掃描
 int id = mapper[h_leveler];
 if (!id) {     //說明沒有到達關(guān)鍵節(jié)點，我們只需要進行繪制和更新即可；
  float xx = 0.0; flag = 1; //flag用于控制每兩組畫一次線
  for(list<Line> ::iterator it=AET.begin();it!=AET.end();)
  { if (flag%2==0) {  //該畫線了！
   draw_lines(xx, h_leveler,it->x,h_leveler);
   for (TESTLIST::iterator pl = AET.begin(); pl != AET.end();)
   if (pl->ym == h_leveler)
    AET.erase(pl++);
   else
    pl++;  //這個負責(zé)刪除的for循環(huán)在畫線后執(zhí)行可以避免留白情況
   it->x = it->x +it->dx;
  }else{
   if (it->y == it->ym) {
   xx = x1;
   }else{
   xx =it->x;
   it->x = it->x +it->dx;
   }
  }flag++;it++;}
 }else{     //如果到了關(guān)鍵事件，那么加線、去線
  list<Line> ::iterator it;
  float xx = 0.0;int counter = 1;
  for(it=AET.begin();it!=AET.end();it++)
  { Line temp= *it;
  if (counter%2==0)  //該畫線了！
   draw_lines(xx, h_leveler,temp.x,h_leveler);
  else
   xx =temp.x;   //刪除邊前先畫好線避免留白
  counter++;
  }
  for (TESTLIST::iterator it = AET.begin(); it != AET.end();)
  if (it->ym == h_leveler)
   AET.erase(it++);
  else
   it++;    //關(guān)鍵時間刪除邊
  for (int i =0 ; i < con2[id-1].size(); i++)
  if (con2[id-1][i].y == con2[id-1][i].ym)
   continue;   //如果是橫線直接不用添加該橫線
  else
   AET.push_back(con2[id-1][i]);
  AET.sort(AET_lefter);  //維持滾動活動邊表的有序性
 }}}
void InitEnvironment()   //對環(huán)境進行初始化操作
{ glClearColor(0.0,0.0,0.0,0);
 glClear(GL_COLOR_BUFFER_BIT);
 glPointSize(7);
 glMatrixMode(GL_MODELVIEW);
 glLoadIdentity();
 gluOrtho2D(0,window_size,0,window_size);
}
void myDisplay(void)
{ glClear(GL_COLOR_BUFFER_BIT);
 glFlush();
}
void OnMouse(int button,int state,int x,int y)
/*
 函數(shù)說明：進行用戶交互的操作
 每兩個點一組進行操作。設(shè)置左鍵、右鍵手勢動作
 */
{if(button==GLUT_LEFT_BUTTON&&state==GLUT_DOWN&&if_drawable)
 {if (flag ==1 &&if_drawable) {
  glColor3f(1,0,0);
  glBegin(GL_POINTS);
  glVertex2f(x,window_size-y);
  x0 = x;y0 =y;
  x1 = x;y1 = y;
  h_min = y0;
  h_max = y0;
  glEnd();
  glFlush();
  flag++;
 }else{
  glColor3f(1,0,0);
  glBegin(GL_POINTS);
  glVertex2f(x,window_size-y);
  glEnd();
  x2 = x;y2 = y;
  glBegin(GL_LINES);
  glColor3f(1.0,0.0,0.0);
  glVertex2f(x1,window_size-y1);
  glVertex2f(x2,window_size-y2);
  if (y1 !=y2) {
  Line a(x1,y1,x2,y2);
  int r_y = min (y1,y2);
  if (y1 < h_min)
   h_min = y1;
  if (y2 < h_min)
   h_min = y2;
  if (y1 > h_max)
   h_max = y1;
  if (y2 >h_max)
   h_max = y2;
  int pos = mapper[r_y];
  if (pos==0) {  //說明該變量還沒有離散化
  mapper[r_y] = level++;
  vector<Line> lines;
  lines.push_back(a);
  con.push_back(lines);}
  else
  con[pos-1].push_back(a);
  }
  x1 = x2; y1 = y2;
  glEnd();
  glFlush();
 }
 }
 if(button==GLUT_RIGHT_BUTTON&&state==GLUT_DOWN&&if_drawable)
 { //點擊右鍵
 glColor3f(1,0,0);
 glBegin(GL_POINTS);
 glVertex2f(x,window_size-y);
 glEnd();
 x2 = x;y2 = y;
 glBegin(GL_LINES);
 glColor3f(1.0,0.0,0.0);
 glVertex2f(x1,window_size-y1);
 glVertex2f(x2,window_size-y2);
 Line a(x1,y1,x2,y2);
 int r_y = min (y1,y2);
 int pos = mapper[r_y];
 if (pos==0) {  //說明該變量還沒有離散化
  mapper[r_y] = level++;
  vector<Line> lines;
  lines.push_back(a);
  con.push_back(lines);}
 else
  con[pos-1].push_back(a);
 glEnd();
 glFlush();
 glBegin(GL_LINES);
 glColor3f(1.0,0.0,0.0);
 glVertex2f(x0,window_size-y0);
 glVertex2f(x2,window_size-y2);
 glEnd();
 glFlush();
 Line aa(x0,y0,x2,y2);
 r_y = min (y0,y2);
 pos = mapper[r_y];
 if (pos==0) {  //說明該變量還沒有離散化
  mapper[r_y] = level++;
  vector<Line> lines;
  lines.push_back(aa);
  con.push_back(lines);}
 else
  con[pos-1].push_back(aa);
 sort_con();
 lines_filling();
 if_drawable = 0;
 }
}

int main(int argc, char *argv[])
{ glutInit(&argc, argv); //初始化GLUT
 glutInitDisplayMode(GLUT_RGB | GLUT_SINGLE);
 glutInitWindowPosition(300, 100);
 glutInitWindowSize(window_size, window_size);
 glutCreateWindow("hw2_filling_line");
 InitEnvironment(); //初始化
 glutMouseFunc(&OnMouse); //注冊鼠標事件
 glutDisplayFunc(&myDisplay); //回調(diào)函數(shù)
 glutMainLoop(); //持續(xù)顯示，當窗口改變會重新繪制圖形
 return 0;
}