// Copyright (C) 2010, Guy Barrand. All rights reserved.
// See the file tools.license for terms.

#ifndef tools_zb_polygon
#define tools_zb_polygon

#include "edge_table"
#include "../mnmx"

namespace tools {
namespace zb {

class polygon {

  static const int NUMPTSTOBUFFER = 200;

  typedef struct _POINTBLOCK {
      point pts[NUMPTSTOBUFFER];
      struct _POINTBLOCK* next;
  } POINTBLOCK;

  int             m_pETEn;
  EdgeTableEntry* m_pETEs;
  int             m_numAllocPtBlocks;
  POINTBLOCK      m_FirstPtBlock;
public:
  polygon():m_pETEn(0),m_pETEs(NULL),m_numAllocPtBlocks(0){}
  virtual ~polygon(){clear();}
protected:
  polygon(const polygon&){}
  polygon& operator=(const polygon&){return *this;}
public:
  void clear(){
    POINTBLOCK* curPtBlock;
    cmem_free(m_pETEs);
    m_pETEn = 0;
    for(curPtBlock = m_FirstPtBlock.next; --m_numAllocPtBlocks >= 0;){
        POINTBLOCK* tmpPtBlock;
        tmpPtBlock  = curPtBlock->next;
        cmem_free(curPtBlock);
        curPtBlock  = tmpPtBlock;
    }
    m_numAllocPtBlocks = 0;
  }

  typedef void (*scan_func)(void*,int,int,int);

  void scan(int    Count,         /* number of pts  */
            const point* Pts,	  /* the pts        */
            int	   rule,          /* winding rule   */
            scan_func a_proc,void* a_tag,
            unsigned int a_width,unsigned int a_height){
    // polytoregion
    //   Scan converts a polygon by returning a run-length
    //   encoding of the resultant bitmap -- the run-length
    //   encoding is in the form of an array of rectangles.

    EdgeTableEntry* pAET;   /* Active Edge Table       */
    int y;                  /* current scanline        */
    int iPts = 0;           /* number of pts in buffer */
    EdgeTableEntry* pWETE;  /* Winding Edge Table Entry*/
    ScanLineList*   pSLL;   /* current scanLineList    */

    EdgeTableEntry* pPrevAET;        /* ptr to previous AET     */
    EdgeTable ET;                    /* header node for ET      */
    EdgeTableEntry AET;              /* header node for AET     */
    ScanLineListBlock SLLBlock;      /* header for scanlinelist */
    int         fixWAET = 0;
    POINTBLOCK* curPtBlock;
    int         numFullPtBlocks = 0;

    if(a_proc==NULL) return;
    if(Count==0)  return;

    if(Count==3)  {
      point pts[3];
      pts[0] = Pts[0];
      pts[1] = Pts[1];
      pts[2] = Pts[2];

      point vp_down[3];
      vp_down[0] = point(0,0,0);
      vp_down[1] = point(a_width,0,0);
      vp_down[2] = point(a_width,a_height,0);
      if(triangles_overlap(pts,vp_down)) {
      } else {
        point vp_up[3];
        vp_up[0] = point(0,0,0);
        vp_up[1] = point(a_width,a_height,0);
        vp_up[2] = point(0,a_height,0);
        if(!triangles_overlap(pts,vp_up)) return;
      }
    }

    int pts_xmin = Pts[0].x;
    int pts_xmax = pts_xmin;
    int pts_ymin = Pts[0].y;
    int pts_ymax = pts_ymin;
   {for(int count=1;count<Count;count++) {
      if(Pts[count].x<pts_xmin) pts_xmin = Pts[count].x;
      if(Pts[count].x>pts_xmax) pts_xmax = Pts[count].x;
      if(Pts[count].y<pts_ymin) pts_ymin = Pts[count].y;
      if(Pts[count].y>pts_ymax) pts_ymax = Pts[count].y;
    }}

    /* special case a rectangle */
    point* pts = (point*)Pts;
    if (((Count == 4) ||
	 ((Count == 5) && (pts[4].x == pts[0].x) && (pts[4].y == pts[0].y))) &&
	(((pts[0].y == pts[1].y) &&
	  (pts[1].x == pts[2].x) &&
	  (pts[2].y == pts[3].y) &&
	  (pts[3].x == pts[0].x)) ||
	 ((pts[0].x == pts[1].x) &&
	  (pts[1].y == pts[2].y) &&
	  (pts[2].x == pts[3].x) &&
	  (pts[3].y == pts[0].y))))
      {
        int  xmin,xmax,ymin,ymax;
	xmin = (int)min_of(pts[0].x, pts[2].x);
	ymin = (int)min_of(pts[0].y, pts[2].y);
	xmax = (int)max_of(pts[0].x, pts[2].x);
	ymax = (int)max_of(pts[0].y, pts[2].y);
	if ((xmin != xmax) && (ymin != ymax))
	    {
              for(y=ymin;y<=ymax;y++)  a_proc(a_tag,xmin  ,xmax  ,y);
	    }
	return;
    }

    if(Count>m_pETEn)
      {
	cmem_free(m_pETEs);
	m_pETEn = Count;
	m_pETEs = cmem_alloc<EdgeTableEntry>(m_pETEn);
	if(m_pETEs==NULL)
	  {
	    m_pETEn = 0;
	    return;
	  }
      }

    ET.scanlines.next = (ScanLineList*)NULL;
    ET.ymax = pts_ymin;
    ET.ymin = pts_ymax;
    
    AET.next = (EdgeTableEntry*)NULL;
    AET.back = (EdgeTableEntry*)NULL;
    AET.nextWETE = (EdgeTableEntry*)NULL;
    AET.bres.minor_axis = pts_xmin;
    
    SLLBlock.next = (ScanLineListBlock*)NULL;
    
    CreateETandAET (Count,(point*)Pts, &ET, &AET, m_pETEs, &SLLBlock,pts_xmin,pts_ymin,pts_ymax);

    pSLL           = ET.scanlines.next;

    curPtBlock     = &m_FirstPtBlock;
    pts            =  m_FirstPtBlock.pts;


    if (rule==0)
      {
        /*
         *  for each scanline
         */
        for (y = ET.ymin; y < ET.ymax; y++) {
            /*
             *  Add a new edge to the active edge table when we
             *  get to the next edge.
             */
            if (pSLL != NULL && y == pSLL->scanline)
	      {
                LoadAET(&AET, pSLL->edgelist);
                pSLL = pSLL->next;
	      }
            pPrevAET = &AET;
            pAET = AET.next;

            /*
             *  for each active edge
             */
            while (pAET) {
                pts->x = pAET->bres.minor_axis;
                pts->y = y;
                pts++;
                iPts++;

                /*
                 *  send out the buffer
                 */
                if (iPts == NUMPTSTOBUFFER)
		  {
                    if(numFullPtBlocks < m_numAllocPtBlocks)
                      {
                        curPtBlock = curPtBlock->next;
                      }
		    else
		      {
			POINTBLOCK* tmpPtBlock = cmem_alloc<POINTBLOCK>(1);
                        if(tmpPtBlock==NULL)
			  {
			    FreeStorage(SLLBlock.next);
			    return;
			  }
			tmpPtBlock->next = NULL; /*Barrand*/
			curPtBlock->next = tmpPtBlock;
			curPtBlock       = tmpPtBlock;
			m_numAllocPtBlocks++;
		      }
		    numFullPtBlocks++;
		    pts  = curPtBlock->pts;
                    iPts = 0;
		  }

                EVALUATEEDGEEVENODD(pAET, pPrevAET, y)
            }
            (void) InsertAndSort(&AET);
        }
      }
    else
      {
        /*
         *  for each scanline
         */
        for (y = ET.ymin; y < ET.ymax; y++) {
            /*
             *  Add a new edge to the active edge table when we
             *  get to the next edge.
             */
            if (pSLL != NULL && y == pSLL->scanline)
	      {
                LoadAET(&AET, pSLL->edgelist);
                ComputeWAET(&AET);
                pSLL = pSLL->next;
	      }
            pPrevAET = &AET;
            pAET = AET.next;
            pWETE = pAET;

            /*
             *  for each active edge
             */
            while (pAET) {
                /*
                 *  add to the buffer only those edges that
                 *  are in the Winding active edge table.
                 */
                if (pWETE == pAET) {
                    pts->x = pAET->bres.minor_axis;
                    pts->y = y;
                    pts++;
		    iPts++;

                    /*
                     *  send out the buffer
                     */
		    if (iPts == NUMPTSTOBUFFER)
		      {
			if(numFullPtBlocks < m_numAllocPtBlocks)
			  {
			    curPtBlock = curPtBlock->next;
			  }
			else
			  {
			    POINTBLOCK* tmpPtBlock = cmem_alloc<POINTBLOCK>(1);
                            if(tmpPtBlock==NULL)
			      {
				FreeStorage(SLLBlock.next);
				return;
			      }
			    tmpPtBlock->next = NULL; /*Barrand*/
			    curPtBlock->next = tmpPtBlock;
			    curPtBlock       = tmpPtBlock;
			    m_numAllocPtBlocks++;
			  }
			numFullPtBlocks++;
			pts  = curPtBlock->pts;
			iPts = 0;
		      }
                    pWETE = pWETE->nextWETE;
                }
                EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET)
            }

            /*
             *  recompute the winding active edge table if
             *  we just resorted or have exited an edge.
             */
            if ( (InsertAndSort(&AET)!=0) || (fixWAET!=0) )
	      {
                ComputeWAET(&AET);
                fixWAET = 0;
	      }
        }
      }
    FreeStorage   (SLLBlock.next);

    ScanPoints (numFullPtBlocks, iPts, &m_FirstPtBlock,a_proc,a_tag);

  }
protected:
  void ScanPoints (int  numFullPtBlocks,
                   int  iCurPtBlock,
                   POINTBLOCK* FirstPtBlock,
                   scan_func a_proc,void* a_tag) {
    point*  pts;
    POINTBLOCK* CurPtBlock;
    int         i;
    CurPtBlock = FirstPtBlock;
    for ( ; numFullPtBlocks >= 0; numFullPtBlocks--)
      {
        /* the loop uses 2 points per iteration */
        i = numFullPtBlocks!=0 ? NUMPTSTOBUFFER >> 1 : iCurPtBlock >> 1 ;
        for (pts = CurPtBlock->pts; i--; pts += 2)
  	{
  	  a_proc (a_tag,(int)(pts->x),(int)pts[1].x,(int)pts->y);
  	}
        CurPtBlock = CurPtBlock->next;
      }
  }

  // from: https://rosettacode.org/wiki/Determine_if_two_triangles_overlap#C++
  static double det_2D(const point& a_p1,const point& a_p2,const point& a_p3) {
    return a_p1.x*(a_p2.y-a_p3.y)+a_p2.x*(a_p3.y-a_p1.y)+a_p3.x*(a_p1.y-a_p2.y);
  }

  static void check_winding(point& a_p1,point& a_p2,point& a_p3) {
    double detTri = det_2D(a_p1, a_p2, a_p3);
    if(detTri < 0.0) { //swap p2 and p3:
      point a = a_p3;
      a_p3 = a_p2;
      a_p2 = a;
    }
  }

  static bool check_boundary_overlap(point& a_p1,point& a_p2,point& a_p3) {return det_2D(a_p1, a_p2, a_p3) < 0.0;}

  static bool triangles_overlap(point* a_t1,point* a_t2) {
    //Trangles must be expressed anti-clockwise
    check_winding(a_t1[0], a_t1[1], a_t1[2]);
    check_winding(a_t2[0], a_t2[1], a_t2[2]);

    //For edge E of trangle 1,
    for(int i=0; i<3; i++) {
      int j=(i+1)%3;

      //Check all points of trangle 2 lay on the external side of the edge E. If
      //they do, the triangles do not overlap.
      if (check_boundary_overlap(a_t1[i], a_t1[j], a_t2[0]) &&
          check_boundary_overlap(a_t1[i], a_t1[j], a_t2[1]) &&
          check_boundary_overlap(a_t1[i], a_t1[j], a_t2[2])) return false;
    }

    //For edge E of trangle 2,
    for(int i=0; i<3; i++) {
      int j=(i+1)%3;

      //Check all points of trangle 1 lay on the external side of the edge E. If
      //they do, the triangles do not overlap.
      if (check_boundary_overlap(a_t2[i], a_t2[j], a_t1[0]) &&
          check_boundary_overlap(a_t2[i], a_t2[j], a_t1[1]) &&
          check_boundary_overlap(a_t2[i], a_t2[j], a_t1[2])) return false;
    }

    return true; //the triangles overlap.
  }

};

}}

#endif