#include "graphics.h"
#include "stdio.h"
#include "conio.h"
#include <stdlib.h>
#include <math.h>
#include <cmath>
#include <iostream>
 
using namespace std;
#define MAX_VOL 20
//多邊形的邊的數(shù)據(jù)結(jié)構(gòu)
typedef struct Edge
{
 int y_max, y_min; //該有向邊的y坐標(biāo)的最大值與最小值
 double x, deltax; //該有向邊的x的最小值以及x的變化的量（1/斜率）
 struct Edge* next; //指向下一條邊的指針
 
}Edge;
//活動邊表表項(xiàng)
typedef struct TableItem
{
 int curr_y;  //該表項(xiàng)的y坐標(biāo)值 ymin
 Edge *firstNode; //該表項(xiàng)的首個(gè)節(jié)點(diǎn)，如果沒有，NULL
 struct TableItem *next; //指向下一個(gè)活動邊表表項(xiàng)的指針
}TableItem;
//活動邊表結(jié)構(gòu)體
typedef struct Table
{
 TableItem *itemHeader; //活動邊表的表項(xiàng)header
 int item_count; //活動邊表表項(xiàng)的個(gè)數(shù)
}ET;
 
class Point
{
private:
 int x1, x2, y1, y2;
public:
 Point(int x1, int y1, int x2, int y2)
 {
 this->x1 = x1;
 this->x2 = x2;
 this->y1 = y1;
 this->y2 = y2;
 }
 //返回兩個(gè)點(diǎn)之中的ymax
 int YMax()
 {
 return (y1 > y2 ? y1 : y2);
 }
 //返回ymin
 int YMin()
 {
 return (y1 < y2 ? y1 : y2);
 }
 //返回ymin 端點(diǎn)的x 值
 int x()
 {
 return (y1 < y2 ? x1 : x2);
 }
 //返回直線的斜率,按照傳入的參數(shù)的順序
 double KOfLine()
 {
 return ((y2 - y1)*1.0 / (x2 - x1));
 }
 
};
 
class Solution
{
public:
 //根據(jù)多邊形初始化活動表
 //參數(shù) T 活動邊表
 //參數(shù)edges 用于初始化的邊數(shù)組
 //參數(shù) edge_num 用于初始化的邊的個(gè)數(shù)
 void Init(ET &T, Edge *edges, int edge_num)
 {
 //初始化活動邊表結(jié)構(gòu)體
 T.item_count = 0;
 T.itemHeader = NULL;
 int ymins[20]; //存儲ymin ,決定活動邊表的個(gè)數(shù)以及表項(xiàng)的內(nèi)容
 
 T.item_count = TableItemCount(edges, edge_num, ymins);
 T.itemHeader = (TableItem*)malloc(sizeof(TableItem));
 T.itemHeader->curr_y = ymins[0];
 T.itemHeader->firstNode = NULL;
 T.itemHeader->next = NULL;
 TableItem *p = T.itemHeader; //指向頭結(jié)點(diǎn)
 for (int i = 1; i<T.item_count; ++i)
 {
  //依次創(chuàng)建活動邊表的各個(gè)表項(xiàng)，并連接在一起
  TableItem *e = (TableItem*)malloc(sizeof(TableItem));
  e->curr_y = ymins[i];
  e->firstNode = NULL;
  e->next = NULL;
  p->next = e;
  p = e;
 }
 
 //按照用于初始化的邊數(shù)組初始化活動邊表
 p = T.itemHeader;
 for (int j = 0; j < edge_num; ++j) {
  this->AppendNode(T, edges[j].y_min, edges[j]);
 }
 //方法結(jié)束
 ////////測試區(qū)////////////
 //cout << "遍歷表項(xiàng)。。。。。" << endl;
 //p = T.itemHeader;
 //while (p != NULL) {
 // cout << "當(dāng)前表項(xiàng)y : " << p->curr_y << endl;
 // Edge *ele = p->firstNode;
 // while (ele != NULL) {
 // cout << "表項(xiàng)中的邊： x = " << ele->x << " y_min = " << ele->y_min << " y_max = " << ele->y_max << 
 //  "deltax = " << ele->deltax << endl;
 // ele = ele->next;
 // }
 
 // p = p->next;
 //}
 ////////測試刪除結(jié)點(diǎn)////////
 //p = T.itemHeader;
 //int yMax = 0;
 //while (yMax < 24) {
 // p = T.itemHeader;
 // cout << "-------------------------------" << endl;
 // cout << "當(dāng)前y max :" << yMax << endl;
 // this->DeleteNode(T, yMax);
 // while (p != NULL) {
 // cout << "當(dāng)前表項(xiàng)y : " << p->curr_y << endl;
 // Edge *ele = p->firstNode;
 // while (ele != NULL) {
 //  cout << "表項(xiàng)中的邊： x = " << ele->x << " y_min = " << ele->y_min << " y_max = " << ele->y_max <<
 //  "deltax = " << ele->deltax << endl;
 //  ele = ele->next;
 // }
 // p = p->next;
 // }
 // yMax++;
 //}
 
 /////////////////////////
 
 
 }
 
 
 
 //用于根據(jù)邊數(shù)組計(jì)算需要多少個(gè)表項(xiàng)
 //表項(xiàng)的個(gè)數(shù)取決于邊的ymin的個(gè)數(shù)
 //返回值 ymin 數(shù)組
 //返回 item_num 表項(xiàng)的個(gè)數(shù)
 int TableItemCount(Edge *edges, int edge_num, int* ymins)
 {
 int count = 0;
 for (int i = 0; i<edge_num; ++i)
 {
  if (!isInArray(ymins, edges[i].y_min, count))
  {
  ymins[count++] = edges[i].y_min;
  }
 }
 //將ymin 升序排序
 for (int j = 0; j<count - 1; ++j)
 {
  for (int k = j + 1; k<count; ++k)
  {
  if (ymins[k] < ymins[j])
  {
   int tmp = ymins[k];
   ymins[k] = ymins[j];
   ymins[j] = tmp;
  }
  }
 }
 return count;
 
 }
 //判斷一個(gè)整數(shù)是否在整數(shù)數(shù)組中
 bool isInArray(int *array, int e, int array_length)
 {
 for (int i = 0; i<array_length; ++i)
 {
  if (array[i] == e)
  {
  return true;
  }
 }
 return false;
 }
 
 //傳入edges數(shù)組，初始化，返回Edge 結(jié)構(gòu)體數(shù)組
 //因?yàn)樾枰欠忾]圖形，所以，在邊數(shù)組中，最后的點(diǎn)的坐標(biāo)設(shè)為起始點(diǎn)的坐標(biāo)，傳入的edge_num 不變
 Edge* InitEdges(int *edges, int edge_num)
 {
 Edge *newEdges = (Edge*)malloc(sizeof(Edge)*edge_num);
 int j = 0;
 for (int i = 0; i<edge_num; ++i)
 {
  Point point(edges[2 * i], edges[2 * i + 1], edges[2 * (i + 1)], edges[2 * (i + 1) + 1]);
  Edge *newEdge = (Edge*)malloc(sizeof(Edge));
  newEdge->x = (double)point.x();
  newEdge->y_max = point.YMax();
  newEdge->y_min = point.YMin();
  newEdge->deltax = 1.0 / point.KOfLine(); // 斜率分之一
  newEdge->next = NULL;
  newEdges[j++] = *(newEdge);
 }
 return newEdges;
 }
 //刪除所有的小于ymax 的節(jié)點(diǎn)
 //參數(shù) curr_ymax 當(dāng)前掃描線的y值
 void DeleteNode(ET &T, int curr_ymax)
 {
 TableItem *p = T.itemHeader; //指向表項(xiàng)的指針
 while (p != NULL) {
  Edge *item = p->firstNode; //指向表項(xiàng)的鄰接鏈表的指針
  Edge *itempre = p->firstNode;   //指向前一個(gè)邊結(jié)點(diǎn)的指針
  while (item != NULL) {
  if (item->y_max <= curr_ymax) { //刪除該結(jié)點(diǎn)
   T.item_count--; //當(dāng)前活動邊表中的邊的個(gè)數(shù)-1
   //判斷該結(jié)點(diǎn)是否是該鏈表的頭結(jié)點(diǎn)
   if (item == p->firstNode) {
   p->firstNode = (Edge*)malloc(sizeof(Edge));
   p->firstNode = item->next;
   free(item);  //釋放該結(jié)點(diǎn)
   item = p->firstNode; //重新指向firstnode結(jié)點(diǎn)
   itempre = p->firstNode;
   }
   else {
   itempre->next = item->next; //修改前一個(gè)結(jié)點(diǎn)的next的值
   free(item);   //刪除該指針
   item = itempre->next; //繼續(xù)向后遍歷
   }
  }//if (item->y_max < curr_ymax)
  else { 
   itempre = item;
   item = item->next;
  }
  }//while (item != NULL)
  p = p->next;
 }//while (p != NULL)
 
 
 }
 
 //將指定y值的節(jié)點(diǎn)添加到該表項(xiàng), 該方法插入的順序取決于調(diào)用該方法傳入?yún)?shù)的順序
 //該方法將新節(jié)點(diǎn)插入到對應(yīng)表項(xiàng)的鄰接鏈表的末尾
 void AppendNode(ET &T, int place_y, Edge &e)
 {
 ////////測試區(qū)//////////
 //cout << "In Append , place_y = " << place_y << " e.ymin = " << e.y_min << endl;
 //cout << "item count" << T.item_count << endl;
 
 ///////////////////////
 TableItem *p = T.itemHeader; //指向活動邊表的頭結(jié)點(diǎn)
 //將邊e插入到對應(yīng)的表項(xiàng)
 //之后在該表項(xiàng)中按照x的大小確定插入的位置
 for (int i = 0; i < T.item_count; ++i) {
  if (p->curr_y == e.y_min)
  break;
  p = p->next;
 }
 //將邊插入到該表項(xiàng)的鄰接鏈表中
 Edge *egp = p->firstNode; //egp 指向該表項(xiàng)的首個(gè)鄰接節(jié)點(diǎn)
 if (egp == NULL) { //如果該表項(xiàng)還沒有節(jié)點(diǎn)，直接插入
  egp = (Edge*)malloc(sizeof(Edge));
  *(egp) = e;
  egp->next = NULL;
  p->firstNode = egp;
 }
 else {
  Edge *pre = egp;
  while (egp != NULL) {
  pre = egp;
  egp = egp->next;
  }
  Edge *newedge = (Edge*)malloc(sizeof(Edge));
  *(newedge) = e;
  pre->next = newedge;
  newedge->next = NULL;
 }
 
 
 }
 
 //繪圖的方法
 void Draw(ET T) {
 //首先取出ymin 值小于當(dāng)前掃描線y 的邊
 //按照順序配對
 int curr_y = 0, curr_edge_num = 0, curr_gy = graphy(curr_y); //圖形坐標(biāo)的掃描線的y坐標(biāo)
 Edge *currEdges = (Edge*)malloc(sizeof(Edge) * 20); //用于存放指針的數(shù)組
 //將每條邊的記錄的x 化為圖形上的坐標(biāo)
 TableItem *p = T.itemHeader;
 while (p != NULL) {
  Edge *q = p->firstNode;
  while (q != NULL) {
  q->x = graphx(q->x);
  q = q->next;
  }
  p = p->next;
 }
 
 
 
 for (; curr_y < 30; curr_gy--, curr_y = realy(curr_gy)) {
  this->DeleteNode(T, curr_y); //刪除當(dāng)前掃描過的邊（ymax 小于 curr_y）
  currEdges = this->GetCurrEdges(T, curr_y, curr_edge_num); //獲取當(dāng)前與掃描線相交的邊
  //對獲取到的邊進(jìn)行排序、配對
  for (int i = 0; i < curr_edge_num - 1; ++i) {
  for (int j = i + 1; j < curr_edge_num; ++j) {
   if (this->IsRightTo(currEdges[i], currEdges[j])) {
   Edge tmp = currEdges[i];
   currEdges[i] = currEdges[j];
   currEdges[j] = tmp;
   }
  }
 
  }
 
 
  ////
 // getchar();
 // cout << "------------------------------" << endl;
 
  setcolor(BLUE);
  for (int j = 0; j < curr_edge_num / 2; ++j) {
 
  ///
  
  // cout << "line :" << (int)currEdges[2 * j].x << " , " << curr_y << "----->" << (int)currEdges[2 * j + 1].x << " , " << curr_y <<
  // " edge_num = " << curr_edge_num << endl;
 
  line((int)currEdges[2 * j].x, curr_gy, (int)currEdges[2 * j + 1].x, curr_gy);
  Edge *curr_edge1 = this->GetThisEdge(T, currEdges[2 * j].x, currEdges[2 * j].y_min,
   currEdges[2 * j].y_max); //獲取當(dāng)前邊的指針，修改x值，保存修改
  curr_edge1->x += curr_edge1->deltax;
  Edge *curr_edge2 = this->GetThisEdge(T, currEdges[2 * j + 1].x, currEdges[2 * j + 1].y_min,
   currEdges[2 * j + 1].y_max);
  curr_edge2->x += curr_edge2->deltax;
  
  
  //line((int)currEdges[2 * j].x, curr_gy, (int)currEdges[2 * j + 1].x, curr_gy); //在兩條直線之間劃線
  //currEdges[2 * j].x += currEdges[2 * j].deltax;
  //currEdges[2 * j + 1].x += currEdges[2 * j + 1].deltax; //更新x 的坐標(biāo)值
  }
 
  //////////測試模擬輸出劃線///////////////
  /*cout << "------------------------------------------" << endl;
  cout << "curr_y = " << curr_y << endl;
  cout << "當(dāng)前掃描的邊的個(gè)數(shù) = " << curr_edge_num << endl;
  for (int i = 0; i < curr_edge_num / 2; ++i) {
  cout << "draw line bwtwen :" << endl;
  cout << "直線1 x = " << currEdges[2 * i].x << " ymin = " << currEdges[2 * i].y_min <<
   " ymax = " << currEdges[2 * i].y_max << endl;
  cout << "直線2 x = " << currEdges[2 * i + 1].x << " ymin = " << currEdges[2 * i + 1].y_min <<
   " ymax = " << currEdges[2 * i + 1].y_max << endl;
  
  }*/
 
 
  ////////////////////////////////////
  //在1,2 3,4 ... 邊之間劃線
  //TODO 坐標(biāo)轉(zhuǎn)換以及劃線
 
  
 }
 
 
 ///////測試區(qū)/////////////////
 //cout << "-------------------------------------" << endl;
 //cout << "當(dāng)前取出的邊。。。。。。。。。。" << endl;
 //cout << "curr_edge_num = " << curr_edge_num << endl;
 //for (int i = 0; i < curr_edge_num; ++i) {
 // cout << "x = " << currEdges[i].x << " y_min = " << currEdges[i].y_min << " y_max = " << currEdges[i].y_max << endl;
 //}
 
 ////////////////////////////////
 
 }
 
 //返回某個(gè)邊的指針
 //可通過此指針修改原結(jié)構(gòu)體中邊的x的值
 Edge* GetThisEdge(ET T, double x, int y_min, int y_max) {
 TableItem *p = T.itemHeader;
 while (p != NULL) {
  Edge *q = p->firstNode;
  while (q != NULL) {
  if ((q->x == x) && (q->y_max == y_max) && (q->y_min == y_min)) {
   return q;
  }
  q = q->next;
  }
  p = p->next;
 }
 
 return NULL;
 }
 
 
 //用于坐標(biāo)轉(zhuǎn)換的函數(shù)
 double graphx(double x) {
 return x * 10 + 100;
 }
 
 double realx(double gx) {
 return (gx - 100)*1.0 / 10;
 }
 
 int graphy(int y) {
 return 400 - y * 10;
 }
 
 int realy(int gy) {
 return (400 - gy) / 10;
 }
 
 //繪制坐標(biāo)系
 void DrawCoordinate(int edges[], int edge_num) {
 line(100, 100, 100, 400);
 line(100, 400, 400, 400);
 outtextxy(85, 95, "y↑");
 outtextxy(400, 393, "→x");
 
 for (int i = 0; i < 30; ++i) {
  if (i % 2 != 0)
  continue;
  //TODO 字符轉(zhuǎn)換
  outtextxy(i * 10 + 100, 390, "|");
  char *text = (char*)malloc(sizeof(char) * 10);
  itoa(i,text,10);
  outtextxy(i * 10 + 100, 410, text);
  free(text);
 }
 
 for (int j = 0; j < 30; ++j) {
  if (j % 2 != 0)
  continue;
  outtextxy(100, 400 - j * 10, "_");
  char *str = (char*)malloc(sizeof(char)*10);
  itoa(j,str,10);
  outtextxy(100, 400 - j * 10,str);
  free(str);
 }
 
 //繪制原多邊形
 for (int k = 0; k < edge_num; ++k) {
  setcolor(YELLOW);
  int x1 = 0, x2 = 0, y1 = 0, y2 = 0;
  x1 = edges[2 * k] * 10 + 100;
  y1 = 400 - edges[2 * k + 1] * 10;
  x2 = edges[2 * (k + 1)] * 10 + 100;
  y2 = 400 - edges[2 * (k + 1) + 1] * 10;
  line(x1, y1, x2, y2);
 }
 
 }
 
 //獲取當(dāng)前的涉及的掃描線的邊
 //即取出當(dāng)前ymin 小于curr_y的邊
 //通過參數(shù)返回取出的邊的個(gè)數(shù)
 Edge* GetCurrEdges(ET T, int curr_y, int &edge_num) {
 Edge *currEdges = (Edge*)malloc(sizeof(Edge) * 20); //分配最大容量
 int i = 0;
 TableItem *p = T.itemHeader;
 while (p != NULL) {
  Edge *q = p->firstNode;
  while (q != NULL) {
  if (q->y_min <= curr_y) { //等于號很重要，否則會在圖形中出現(xiàn)空白區(qū)
   currEdges[i++] = *q; //將當(dāng)前邊的值取出（不改變原活動表）
  }
  q = q->next;
  }
  p = p->next;
 }
 edge_num = i; //保存取出的邊的個(gè)數(shù)
 return currEdges;
 }
 
 //判斷edge1 是否在edge2 的右邊的方法
 bool IsRightTo(Edge edge1, Edge edge2) {
 if (edge1.x > edge2.x) //如果edge1最低點(diǎn)的x坐標(biāo)小于edge2的最低點(diǎn)的x的坐標(biāo)，則edge1在edge2的右邊
  return true;
 else {
  if (edge1.x < edge2.x)
  return false;
  double x_max1 = (edge1.y_max - (edge1.y_min - 1.0 / edge1.deltax*edge1.x))*edge1.deltax;
  double x_max2 = (edge2.y_max - (edge2.y_min - 1.0 / edge2.deltax*edge2.x))*edge2.deltax;
  if (x_max1 > x_max2)
  return true;
 }
 return false;
 }
 
};
 
int main()
{
 //TODO 測試活動邊表初始化
 Solution solution;
 int edges[] = { 4,18,14,14,26,22,26,10,14,2,4,6,4,18 };
 Edge* newEdges = solution.InitEdges(edges, 6);
 ET T;
 solution.Init(T, newEdges, 6); //初始化活動邊表
 
 
 
 initgraph(800, 800, SHOWCONSOLE);
 solution.DrawCoordinate(edges, 6);
 solution.Draw(T);
 getchar();
 closegraph();
 return 0;
}