Function imageFilledPolygon

mapgd.c:140–291

** Polygon fill. Based on "Concave Polygon Scan Conversion" by Paul ** Heckbert from "Graphics Gems", Academic Press, 1990. ** */

**
*/
static void imageFilledPolygon(gdImagePtr im, shapeObj *p, int c)
{
  typedef struct {     /* a polygon edge */
    double x;          /* x coordinate of edge's intersection with current scanline */
    double dx;         /* change in x with respect to y */
    int i;             /* point index  */
    int l;             /* line number */
    int s;             /* scanline */
  } pEdge;
     
  pointObj *point1, *point2;
     
  int k, l, i, j, xl, xr, ymin, ymax, y, n,nvert, nact, m;
  int wrong_order;
     
  pEdge *edge, *temp;
  pEdge  **active;
  int *yhist, *edgeindex;
     
  if(p->numlines == 0) return;
  n=0;
     
  for(i=0; i<p->numlines; i++) {
   n += p->line[i].numpoints;
  }
     
  if(n == 0)   return;

  edge = (pEdge *) msSmallCalloc(n,sizeof(pEdge));           /* All edges in the polygon */
  edgeindex =  (int *) msSmallCalloc(n,sizeof(int));         /* Index to edges sorted by scanline */
  active = (pEdge **) msSmallCalloc(n,sizeof(pEdge*));       /* Pointers to active edges for current scanline */
    
  nvert=0;
     
  ymin= (int) ceil(p->line[0].point[0].y-0.5);
  ymax= (int) floor(p->line[0].point[0].y-0.5);
     
  /* populate the edge table */
  for(l=0; l<p->numlines; l++) {
    for(i=0; i < p->line[l].numpoints; i++) {
      j = i < p->line[l].numpoints -1 ? i+1 : 0;
      if (p->line[l].point[i].y  < p->line[l].point[j].y ) {
        point1 = &(p->line[l].point[i]);
        point2 = &(p->line[l].point[j]);
      } else {
        point2 = &(p->line[l].point[i]);
        point1 = &(p->line[l].point[j]);
      }
               
      edge[nvert].dx  = point2->y == point1->y ? 0 :  (point2->x - point1->x) / (point2->y - point1->y);
      edge[nvert].s = MS_NINT( p->line[l].point[i].y );  /* ceil( p->line[l].point[i].y  - 0.5 ); */
      edge[nvert].x = point1->x;
      edge[nvert].i = nvert;
      edge[nvert].l = l;
               
      ymin = MS_MIN(ymin,edge[nvert].s);
      ymax = MS_MAX(ymax,edge[nvert].s);