polygon_intersection_gpc.cpp

这是一个GPS相关的程序

            next_edge->prev= succ_edge;
          succ_edge->prev= prev_edge;
          succ_edge->next= next_edge;
        }
        else
        {
          /* Update this edge */
          edge->outp[BELOW]= edge->outp[ABOVE];
          edge->bstate[BELOW]= edge->bstate[ABOVE];
          edge->bundle[BELOW][CLIP]= edge->bundle[ABOVE][CLIP];
          edge->bundle[BELOW][SUBJ]= edge->bundle[ABOVE][SUBJ];
          edge->xb= edge->xt;
	}
        edge->outp[ABOVE]= NULL;
      }
    }
  } /* === END OF SCANBEAM PROCESSING ================================== */

  /* Generate result polygon from out_poly */
  result->contour= NULL;
  result->hole= NULL;
  result->num_contours= count_contours(out_poly);
  if (result->num_contours > 0)
  {
    _MALLOC(result->hole, result->num_contours
           * sizeof(int), "hole flag table creation");
    _MALLOC(result->contour, result->num_contours
           * sizeof(gpc_vertex_list), "contour creation");

    c= 0;
    for (poly= out_poly; poly; poly= npoly)
    {
      npoly= poly->next;
      if (poly->active)
      {
        result->hole[c]= poly->proxy->hole;
        result->contour[c].num_vertices= poly->active;
        _MALLOC(result->contour[c].vertex,
          result->contour[c].num_vertices * sizeof(gpc_vertex),
          "vertex creation");
      
        v= result->contour[c].num_vertices - 1;
        for (vtx= poly->proxy->v[LEFT]; vtx; vtx= nv)
        {
          nv= vtx->next;
          result->contour[c].vertex[v].x= vtx->x;
          result->contour[c].vertex[v].y= vtx->y;
          FREE(vtx);
          v--;
        }
        c++;
      }
      FREE(poly);
    }
  }

  /* Tidy up */
  reset_it(&it);
  reset_lmt(&lmt);
  FREE(c_heap);
  FREE(s_heap);
  FREE(sbt);
}


void gpc_free_tristrip(gpc_tristrip *t)
{
  int s;

  for (s= 0; s < t->num_strips; s++)
    FREE(t->strip[s].vertex);
  FREE(t->strip);
  t->num_strips= 0;
}


void gpc_polygon_to_tristrip(gpc_polygon *s, gpc_tristrip *t)
{
  gpc_polygon c;

  c.num_contours= 0;
  c.hole= NULL;
  c.contour= NULL;
  gpc_tristrip_clip(GPC_DIFF, s, &c, t);
}


void gpc_tristrip_clip(gpc_op op, gpc_polygon *subj, gpc_polygon *clip,
                       gpc_tristrip *result)
{
  sb_tree       *sbtree= NULL;
  it_node       *it= NULL, *intersect;
  edge_node     *edge, *prev_edge, *next_edge, *succ_edge, *e0, *e1;
  edge_node     *aet= NULL, *c_heap= NULL, *s_heap= NULL, *cf;
  lmt_node      *lmt= NULL, *local_min;
  polygon_node  *tlist= NULL, *tn, *tnn, *p, *q;
  vertex_node   *lt, *ltn, *rt, *rtn;
  h_state        horiz[2];
  vertex_type    cft;
  int            in[2], exists[2], parity[2]= {LEFT, LEFT};
  int            s, v, contributing, search, scanbeam= 0, sbt_entries= 0;
  int            vclass, bl, br, tl, tr;
  double        *sbt= NULL, xb, px, nx, yb, yt, dy, ix, iy;

  /* Test for trivial NULL result cases */
  if (((subj->num_contours == 0) && (clip->num_contours == 0))
   || ((subj->num_contours == 0) && ((op == GPC_INT) || (op == GPC_DIFF)))
   || ((clip->num_contours == 0) &&  (op == GPC_INT)))
  {
    result->num_strips= 0;
    result->strip= NULL;
    return;
  }

  /* Identify potentialy contributing contours */
  if (((op == GPC_INT) || (op == GPC_DIFF))
   && (subj->num_contours > 0) && (clip->num_contours > 0))
    minimax_test(subj, clip, op);

  /* Build LMT */
  if (subj->num_contours > 0)
    s_heap= build_lmt(&lmt, &sbtree, &sbt_entries, subj, SUBJ, op);
  if (clip->num_contours > 0)
    c_heap= build_lmt(&lmt, &sbtree, &sbt_entries, clip, CLIP, op);

  /* Return a NULL result if no contours contribute */
  if (lmt == NULL)
  {
    result->num_strips= 0;
    result->strip= NULL;
    reset_lmt(&lmt);
    FREE(s_heap);
    FREE(c_heap);
    return;
  }

  /* Build scanbeam table from scanbeam tree */
  _MALLOC(sbt, sbt_entries * sizeof(double), "sbt creation");
  build_sbt(&scanbeam, sbt, sbtree);
  scanbeam= 0;
  free_sbtree(&sbtree);

  /* Invert clip polygon for difference operation */
  if (op == GPC_DIFF)
    parity[CLIP]= RIGHT;

  local_min= lmt;

  /* Process each scanbeam */
  while (scanbeam < sbt_entries)
  {
    /* Set yb and yt to the bottom and top of the scanbeam */
    yb= sbt[scanbeam++];
    if (scanbeam < sbt_entries)
    {
      yt= sbt[scanbeam];
      dy= yt - yb;
    }

    /* === SCANBEAM BOUNDARY PROCESSING ================================ */

    /* If LMT node corresponding to yb exists */
    if (local_min)
    {
      if (local_min->y == yb)
      {
        /* Add edges starting at this local minimum to the AET */
        for (edge= local_min->first_bound; edge; edge= edge->next_bound)
          add_edge_to_aet(&aet, edge, NULL);

        local_min= local_min->next;
      }
    }

    /* Set dummy previous x value */
    px= -DBL_MAX;

    /* Create bundles within AET */
    e0= aet;
    e1= aet;

    /* Set up bundle fields of first edge */
    aet->bundle[ABOVE][ aet->type]= (aet->top.y != yb);
    aet->bundle[ABOVE][!aet->type]= FALSE;
    aet->bstate[ABOVE]= UNBUNDLED;

    for (next_edge= aet->next; next_edge; next_edge= next_edge->next)
    {
      /* Set up bundle fields of next edge */
      next_edge->bundle[ABOVE][ next_edge->type]= (next_edge->top.y != yb);
      next_edge->bundle[ABOVE][!next_edge->type]= FALSE;
      next_edge->bstate[ABOVE]= UNBUNDLED;

      /* Bundle edges above the scanbeam boundary if they coincide */
      if (next_edge->bundle[ABOVE][next_edge->type])
      {
        if (EQ(e0->xb, next_edge->xb) && EQ(e0->dx, next_edge->dx)
	 && (e0->top.y != yb))
        {
          next_edge->bundle[ABOVE][ next_edge->type]^= 
            e0->bundle[ABOVE][ next_edge->type];
          next_edge->bundle[ABOVE][!next_edge->type]= 
            e0->bundle[ABOVE][!next_edge->type]; 
          next_edge->bstate[ABOVE]= BUNDLE_HEAD;
          e0->bundle[ABOVE][CLIP]= FALSE;
          e0->bundle[ABOVE][SUBJ]= FALSE;
          e0->bstate[ABOVE]= BUNDLE_TAIL;
        }
        e0= next_edge;
      }
    }

    horiz[CLIP]= NH;
    horiz[SUBJ]= NH;

    /* Process each edge at this scanbeam boundary */
    for (edge= aet; edge; edge= edge->next)
    {
      exists[CLIP]= edge->bundle[ABOVE][CLIP] + 
                   (edge->bundle[BELOW][CLIP] << 1);
      exists[SUBJ]= edge->bundle[ABOVE][SUBJ] + 
                   (edge->bundle[BELOW][SUBJ] << 1);

      if (exists[CLIP] || exists[SUBJ])
      {
        /* Set bundle side */
        edge->bside[CLIP]= parity[CLIP];
        edge->bside[SUBJ]= parity[SUBJ];

        /* Determine contributing status and quadrant occupancies */
        switch (op)
        {
        case GPC_DIFF:
        case GPC_INT:
          contributing= (exists[CLIP] && (parity[SUBJ] || horiz[SUBJ]))
                     || (exists[SUBJ] && (parity[CLIP] || horiz[CLIP]))
                     || (exists[CLIP] && exists[SUBJ]
                     && (parity[CLIP] == parity[SUBJ]));
          br= (parity[CLIP])
           && (parity[SUBJ]);
          bl= (parity[CLIP] ^ edge->bundle[ABOVE][CLIP])
           && (parity[SUBJ] ^ edge->bundle[ABOVE][SUBJ]);
          tr= (parity[CLIP] ^ (horiz[CLIP]!=NH))
           && (parity[SUBJ] ^ (horiz[SUBJ]!=NH));
          tl= (parity[CLIP] ^ (horiz[CLIP]!=NH) ^ edge->bundle[BELOW][CLIP]) 
           && (parity[SUBJ] ^ (horiz[SUBJ]!=NH) ^ edge->bundle[BELOW][SUBJ]);
          break;
        case GPC_XOR:
          contributing= exists[CLIP] || exists[SUBJ];
          br= (parity[CLIP])
            ^ (parity[SUBJ]);
          bl= (parity[CLIP] ^ edge->bundle[ABOVE][CLIP])
            ^ (parity[SUBJ] ^ edge->bundle[ABOVE][SUBJ]);
          tr= (parity[CLIP] ^ (horiz[CLIP]!=NH))
            ^ (parity[SUBJ] ^ (horiz[SUBJ]!=NH));
          tl= (parity[CLIP] ^ (horiz[CLIP]!=NH) ^ edge->bundle[BELOW][CLIP])
            ^ (parity[SUBJ] ^ (horiz[SUBJ]!=NH) ^ edge->bundle[BELOW][SUBJ]);
          break;
        case GPC_UNION:
          contributing= (exists[CLIP] && (!parity[SUBJ] || horiz[SUBJ]))
                     || (exists[SUBJ] && (!parity[CLIP] || horiz[CLIP]))
                     || (exists[CLIP] && exists[SUBJ]
                     && (parity[CLIP] == parity[SUBJ]));
          br= (parity[CLIP])
           || (parity[SUBJ]);
          bl= (parity[CLIP] ^ edge->bundle[ABOVE][CLIP])
           || (parity[SUBJ] ^ edge->bundle[ABOVE][SUBJ]);
          tr= (parity[CLIP] ^ (horiz[CLIP]!=NH))
           || (parity[SUBJ] ^ (horiz[SUBJ]!=NH));
          tl= (parity[CLIP] ^ (horiz[CLIP]!=NH) ^ edge->bundle[BELOW][CLIP])
           || (parity[SUBJ] ^ (horiz[SUBJ]!=NH) ^ edge->bundle[BELOW][SUBJ]);
          break;
        }

        /* Update parity */
        parity[CLIP]^= edge->bundle[ABOVE][CLIP];
        parity[SUBJ]^= edge->bundle[ABOVE][SUBJ];

        /* Update horizontal state */
        if (exists[CLIP])         
          horiz[CLIP]=
            next_h_state[horiz[CLIP]]
                        [((exists[CLIP] - 1) << 1) + parity[CLIP]];
        if (exists[SUBJ])         
          horiz[SUBJ]=
            next_h_state[horiz[SUBJ]]
                        [((exists[SUBJ] - 1) << 1) + parity[SUBJ]];
        
        vclass= tr + (tl << 1) + (br << 2) + (bl << 3);

        if (contributing)
        {
          xb= edge->xb;

          switch (vclass)
          {
          case EMN:
            new_tristrip(&tlist, edge, xb, yb);
            cf= edge;
            break;
          case ERI:
            edge->outp[ABOVE]= cf->outp[ABOVE];
            if (xb != cf->xb)
              VERTEX(edge, ABOVE, RIGHT, xb, yb);
            cf= NULL;
            break;
          case ELI:
            VERTEX(edge, BELOW, LEFT, xb, yb);
            edge->outp[ABOVE]= NULL;
            cf= edge;
            break;
          case EMX:
            if (xb != cf->xb)
              VERTEX(edge, BELOW, RIGHT, xb, yb);
            edge->outp[ABOVE]= NULL;
            cf= NULL;
            break;
          case IMN:
            if (cft == LED)
	    {
              if (cf->bot.y != yb)
                VERTEX(cf, BELOW, LEFT, cf->xb, yb);
              new_tristrip(&tlist, cf, cf->xb, yb);
	    }
            edge->outp[ABOVE]= cf->outp[ABOVE];
            VERTEX(edge, ABOVE, RIGHT, xb, yb);
            break;
          case ILI:
            new_tristrip(&tlist, edge, xb, yb);
            cf= edge;
            cft= ILI;
            break;
          case IRI:
            if (cft == LED)
	    {
              if (cf->bot.y != yb)
                VERTEX(cf, BELOW, LEFT, cf->xb, yb);
              new_tristrip(&tlist, cf, cf->xb, yb);
	    }
            VERTEX(edge, BELOW, RIGHT, xb, yb);
            edge->outp[ABOVE]= NULL;
            break;
          case IMX:
            VERTEX(edge, BELOW, LEFT, xb, yb);
            edge->outp[ABOVE]= NULL;
            cft= IMX;
            break;
	  case IMM:
            VERTEX(edge, BELOW, LEFT, xb, yb);
            edge->outp[ABOVE]= cf->outp[ABOVE];
            if (xb != cf->xb)
              VERTEX(cf, ABOVE, RIGHT, xb, yb);
            cf= edge;
            break;
          case EMM:
            VERTEX(edge, BELOW, RIGHT, xb, yb);
            edge->outp[ABOVE]= NULL;
            new_tristrip(&tlist, edge, xb, yb);
            cf= edge;
            break;
          case LED:
            if (edge->bot.y == yb)
              VERTEX(edge, BELOW, LEFT, xb, yb);
            edge->outp[ABOVE]= edge->outp[BELOW];
            cf= edge;
            cft= LED;
            break;
          case RED:
            edge->outp[ABOVE]= cf->outp[ABOVE];
            if (cft == LED)
	    {
              if (cf->bot.y == yb)
	      {
                VERTEX(edge, BELOW, RIGHT, xb, yb);
	      }
              else
	      {
                if (edge->bot.y == yb)
		{
                  VERTEX(cf, BELOW, LEFT, cf->xb, yb);
                  VERTEX(edge, BELOW, RIGHT, xb, yb);
		}
	      }
	    }
            else
	    {
              VERTEX(edge, BELOW, RIGHT, xb, yb);
              VERTEX(edge, ABOVE, RIGHT, xb, yb);
	    }
            cf= NULL;
            break;
          default:
            break;
          } /* End of switch */
        } /* End of contributing conditional */
      } /* End of edge exists conditional */
    } /* End of AET loop */

    /* Delete terminating edges from the AET, otherwise compute xt */
    for (edge= aet; edge; edge= edge->next)
    {
      if (edge->top.y == yb)
      {
        prev_edge= edge->prev;
        next_edge= edge->next;
        if (prev_edge)
          prev_edge->next= next_edge;
        else
          aet= next_edge;
        if (next_edge)
          next_edge->prev= prev_edge;

        /* Copy bundle head state to the adjacent tail edge if required */
        if ((edge->bstate[BELOW] == BUNDLE_HEAD) && prev_edge)
	{
          if (prev_edge->bstate[BELOW] == BUNDLE_TAIL)
          {
            prev_edge->outp[BELOW]= edge->outp[BELOW];