Fill Polygon with scan line algorithm

void FillPolygon(int *x,int *y,int cornerno,unsigned short color)
{
int max,min,j;
max=min=y[0];



      //--------找出polygon 的 y line range--------
for(int i=0;i<cornerno;i++)
 if(max<y[i])
  max=y[i];
 else if(min>y[i])
  min=y[i];

//--------開始一條一條 Y line 的scan and draw --------
for(int line=min;line<=max;line++){

 int sno=0;
 int slist[1000];   // 所以有1000個 intersect points 的限制

              //--------找出所有 polygon 與 y line 的 intersect points-----
 for(j=0;j<cornerno;j++){
  int np=(j+1)%cornerno;
  if(y[j]==line){           // 點在 yline 上要特別處理
   int pp=j-1;
   if(pp<0)
    pp+=cornerno;
   if((y[np]>line)&&(y[pp]<line) || (y[np]<line) && (y[pp]>line) ){
    slist[sno]=x[j];
    sno++;
   }
  }else if((y[j]>line && y[np]<line) || (y[j]<line && y[np]>line)){
   slist[sno]=(line-y[j])*(x[np]-x[j])/(y[np]-y[j])+x[j];
   sno++;
  }
 }
            
 //--------Sort intersect points--------
 for(int sorti=0;sorti<sno;sorti++)
  for(int n=sorti;n<sno;n++)
   if(slist[sorti]>slist[n]){
    int tmp=slist[sorti];
    slist[sorti]=slist[n];
    slist[n]=tmp;
   }

              //--------兩兩 intersect points 畫出一條 y line--------
 if(sno>1)
  for(int sect=0;sect<sno;sect+=2)
   VLineWoLock(slist[sect],slist[sect+1],line,color);
}


}

是 reference google 到的一些 fill polygon 的教學網站寫的，因為那些網站好像都沒有真正copy-paste就可以用的 code。
http://alienryderflex.com/polygon_fill/

---

"找出 一條 y line 的所有 intersects" 這一段大概可以 optimize，就是把所有edge (corner-to-corner, 也就是'邊')的斜率先記下來，這樣每一條 y line 在計算時就不用重算 斜率。


但是要注意 round-off error (example 是先乘後除)，所以可能要學 FFE?的方法，先 shift 16 bit，算出斜率。到時候乘完再 shift 回去。

還有更多optimize 的空間：利用 "相鄰scanline的inersect會相近" 這個概念，加入 "Active Edges" 的資料結構，只有在scan line 碰到 vertex (corner point)時， "Active Edges" 的內容才會改變。

這樣可以加速計算 intersects[] 的速度。