API tools faq
paste
Advertisement
Dresmor

gpcs.h

Dresmor
Aug 21st, 2017
99
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 45.46 KB | None | 0 0
raw download clone embed print report
  1. #ifndef __gpc_h
  2. #define __gpc_h
  3. #include<stdio.h>
  4. #include<stdlib.h>
  5. #include<float.h>
  6. #include<math.h>
  7. #define GPC_EPSILON (DBL_EPSILON)
  8. #define GPC_VERSION "2.32"
  9. typedef enum{GPC_DIFF,GPC_INT,GPC_XOR,GPC_UNION}gpc_op;typedef struct{double x;double y;}gpc_vertex;typedef struct{int num_vertices;gpc_vertex*vertex;}gpc_vertex_list;typedef struct{int num_contours;int*hole;gpc_vertex_list*contour;}gpc_polygon;typedef struct{int num_strips;gpc_vertex_list*strip;}gpc_tristrip;void gpc_read_polygon (FILE*infile_ptr, int read_hole_flags,gpc_polygon*polygon);void gpc_write_polygon (FILE*outfile_ptr,int write_hole_flags,gpc_polygon*polygon);void gpc_add_contour (gpc_polygon*polygon,gpc_vertex_list*contour,int hole);void gpc_polygon_clip (gpc_op set_operation,gpc_polygon*subject_polygon,gpc_polygon*clip_polygon,gpc_polygon*result_polygon);void gpc_tristrip_clip (gpc_op set_operation,gpc_polygon*subject_polygon,gpc_polygon*clip_polygon,gpc_tristrip*result_tristrip);void gpc_polygon_to_tristrip (gpc_polygon*polygon,gpc_tristrip*tristrip);void gpc_free_polygon (gpc_polygon*polygon);void gpc_free_tristrip (gpc_tristrip*tristrip);
  10. #ifndef GPC_TRUE
  11. #define GPC_FALSE 0
  12. #define GPC_TRUE 1
  13. #endif
  14. #define GPC_LEFT 0
  15. #define GPC_RIGHT 1
  16. #define GPC_ABOVE 0
  17. #define GPC_BELOW 1
  18. #define GPC_CLIP 0
  19. #define GPC_SUBJ 1
  20. #define GPC_INVERT_TRISTRIPS GPC_FALSE
  21. #define GPC_EQ(a,b) (fabs((a)-(b))<=GPC_EPSILON)
  22. #define GPC_PREV_INDEX(i,n)((i-1+n)%n)
  23. #define GPC_NEXT_INDEX(i,n)((i+1)%n)
  24. #define GPC_OPTIMAL(v,i,n)((v[GPC_PREV_INDEX(i,n)].y!=v[i].y)||(v[GPC_NEXT_INDEX(i,n)].y!=v[i].y))
  25. #define GPC_FWD_MIN(v,i,n)((v[GPC_PREV_INDEX(i,n)].vertex.y>=v[i].vertex.y)&&(v[GPC_NEXT_INDEX(i,n)].vertex.y>v[i].vertex.y))
  26. #define GPC_NOT_FMAX(v,i,n)(v[GPC_NEXT_INDEX(i,n)].vertex.y>v[i].vertex.y)
  27. #define GPC_REV_MIN(v,i,n)((v[GPC_PREV_INDEX(i,n)].vertex.y>v[i].vertex.y)&&(v[GPC_NEXT_INDEX(i,n)].vertex.y>=v[i].vertex.y))
  28. #define GPC_NOT_RMAX(v,i,n)(v[GPC_PREV_INDEX(i,n)].vertex.y>v[i].vertex.y)
  29. #define GPC_VERTEX(e,p,s,x,y){gpc_add_vertex(&((e)->outp[(p)]->v[(s)]),x,y);(e)->outp[(p)]->active++;}
  30. #define GPC_P_EDGE(d,e,p,i,j){(d)=(e);do{(d)=(d)->prev;}while(!(d)->outp[(p)]);(i)=(d)->bot.x+(d)->dx*((j)-(d)->bot.y);}
  31. #define GPC_N_EDGE(d,e,p,i,j){(d)=(e);do{(d)=(d)->next;}while(!(d)->outp[(p)]);(i)=(d)->bot.x+(d)->dx*((j)-(d)->bot.y);}
  32. #define GPC_MALLOC(p,b,s,t){if((b)>0){p=(t*)malloc(b);if(!(p)){fprintf(stderr,"gpc malloc failure: %s\n",s);exit(0);}}else p=NULL;}
  33. #define GPC_FREE(p){if(p){free(p);(p)=NULL;}}
  34. typedef enum{GPC_NUL,GPC_EMX,GPC_ELI,GPC_TED,GPC_ERI,GPC_RED,GPC_IMM,GPC_IMN,GPC_EMN,GPC_EMM,GPC_LED,GPC_ILI,GPC_BED,GPC_IRI,GPC_IMX,GPC_FUL}gpc_vertex_type;typedef enum{GPC_NH,GPC_BH,GPC_TH}gpc_h_state;typedef enum{GPC_UNBUNDLED,GPC_BUNDLE_HEAD,GPC_BUNDLE_TAIL}gpc_bundle_state;typedef struct gpc_v_shape{double x;double y;struct gpc_v_shape*next;}gpc_vertex_node;typedef struct gpc_p_shape{int active;int hole;gpc_vertex_node*v[2];struct gpc_p_shape*next;struct gpc_p_shape*proxy;}gpc_polygon_node;typedef struct gpc_edge_shape{gpc_vertex vertex;gpc_vertex bot;gpc_vertex top;double xb;double xt;double dx;int type;int bundle[2][2];int bside[2];gpc_bundle_state bstate[2];gpc_polygon_node*outp[2];struct gpc_edge_shape*prev;struct gpc_edge_shape*next;struct gpc_edge_shape*pred;struct gpc_edge_shape*succ;struct gpc_edge_shape*next_bound;}gpc_edge_node;typedef struct gpc_lmt_shape{double y;gpc_edge_node*first_bound;struct gpc_lmt_shape*next;}gpc_lmt_node;typedef struct gpc_sbt_t_shape{double y;struct gpc_sbt_t_shape*less;struct gpc_sbt_t_shape*more;}gpc_sb_tree;typedef struct gpc_it_shape{gpc_edge_node*ie[2];gpc_vertex point;struct gpc_it_shape*next;}gpc_it_node;typedef struct gpc_st_shape{gpc_edge_node*edge;double xb;double xt;double dx;struct gpc_st_shape*prev;}gpc_st_node;typedef struct gpc_bbox_shape{double xmin;double ymin;double xmax;double ymax;}gpc_bbox;const gpc_h_state gpc_next_h_state[3][6]={{GPC_BH,GPC_TH,GPC_TH,GPC_BH,GPC_NH,GPC_NH},{GPC_NH,GPC_NH,GPC_NH,GPC_NH,GPC_TH,GPC_TH},{GPC_NH,GPC_NH,GPC_NH,GPC_NH,GPC_BH,GPC_BH}};static void gpc_reset_it(gpc_it_node**it){gpc_it_node*itn;while(*it){itn=(*it)->next;GPC_FREE(*it);*it=itn;}}static void gpc_reset_lmt(gpc_lmt_node**lmt){gpc_lmt_node*lmtn;while(*lmt){lmtn=(*lmt)->next;GPC_FREE(*lmt);*lmt=lmtn;}}static void gpc_insert_bound(gpc_edge_node**b,gpc_edge_node*e){gpc_edge_node*existing_bound;if(!*b){*b=e;}else{if(e[0].bot.x<(*b)[0].bot.x){existing_bound=*b;*b=e;(*b)->next_bound=existing_bound;}else{if(e[0].bot.x==(*b)[0].bot.x){if(e[0].dx<(*b)[0].dx){existing_bound=*b;*b=e;(*b)->next_bound=existing_bound;}else{gpc_insert_bound(&((*b)->next_bound),e);}}else{gpc_insert_bound(&((*b)->next_bound),e);}}}}static gpc_edge_node**gpc_bound_list(gpc_lmt_node**lmt,double y){gpc_lmt_node*existing_node;if(!*lmt){GPC_MALLOC(*lmt,sizeof(gpc_lmt_node),"LMT insertion",gpc_lmt_node);(*lmt)->y=y;(*lmt)->first_bound=NULL;(*lmt)->next=NULL;return &((*lmt)->first_bound);}else if(y<(*lmt)->y){existing_node=*lmt;GPC_MALLOC(*lmt,sizeof(gpc_lmt_node),"LMT insertion",gpc_lmt_node);(*lmt)->y=y;(*lmt)->first_bound=NULL;(*lmt)->next=existing_node;return &((*lmt)->first_bound);}else if(y>(*lmt)->y) return gpc_bound_list(&((*lmt)->next),y);else return &((*lmt)->first_bound);}static void gpc_add_to_sbtree(int*entries,gpc_sb_tree**sbtree,double y){if(!*sbtree){GPC_MALLOC(*sbtree,sizeof(gpc_sb_tree),"scanbeam tree insertion",gpc_sb_tree);(*sbtree)->y=y;(*sbtree)->less=NULL;(*sbtree)->more=NULL;(*entries)++;}else{if((*sbtree)->y>y){gpc_add_to_sbtree(entries,&((*sbtree)->less),y);}else{if((*sbtree)->y<y){gpc_add_to_sbtree(entries,&((*sbtree)->more),y);}}}}static void gpc_build_sbt(int*entries,double*sbt,gpc_sb_tree*sbtree){if(sbtree->less) gpc_build_sbt(entries,sbt,sbtree->less);sbt[*entries]=sbtree->y;(*entries)++;if(sbtree->more) gpc_build_sbt(entries,sbt,sbtree->more);}static void gpc_free_sbtree(gpc_sb_tree**sbtree){if(*sbtree){gpc_free_sbtree(&((*sbtree)->less));gpc_free_sbtree(&((*sbtree)->more));GPC_FREE(*sbtree);}}static int gpc_count_optimal_vertices(gpc_vertex_list c){int result=0,i;if(c.num_vertices>0){for(i=0;i<c.num_vertices;i++) if(GPC_OPTIMAL(c.vertex,i,c.num_vertices)) result++;}return result;}static gpc_edge_node*gpc_build_lmt(gpc_lmt_node**lmt,gpc_sb_tree**sbtree,int*sbt_entries,gpc_polygon*p,int type,gpc_op op){int c,i,min,max,num_edges,v,num_vertices;int total_vertices=0,e_index=0;gpc_edge_node*e,*edge_table;for(c=0;c<p->num_contours;c++) total_vertices+=gpc_count_optimal_vertices(p->contour[c]);GPC_MALLOC(edge_table,total_vertices*sizeof(gpc_edge_node),"edge table creation",gpc_edge_node);for(c=0;c<p->num_contours;c++){if(p->contour[c].num_vertices<0){p->contour[c].num_vertices=-p->contour[c].num_vertices;}else{num_vertices=0;for(i=0;i<p->contour[c].num_vertices;i++) if(GPC_OPTIMAL(p->contour[c].vertex,i,p->contour[c].num_vertices)){edge_table[num_vertices].vertex.x=p->contour[c].vertex[i].x;edge_table[num_vertices].vertex.y=p->contour[c].vertex[i].y;gpc_add_to_sbtree(sbt_entries,sbtree,edge_table[num_vertices].vertex.y);num_vertices++;}for(min=0;min<num_vertices;min++){if(GPC_FWD_MIN(edge_table,min,num_vertices)){num_edges=1;max=GPC_NEXT_INDEX(min,num_vertices);while(GPC_NOT_FMAX(edge_table,max,num_vertices)){num_edges++;max=GPC_NEXT_INDEX(max,num_vertices);}e=&edge_table[e_index];e_index+=num_edges;v=min;e[0].bstate[GPC_BELOW]=GPC_UNBUNDLED;e[0].bundle[GPC_BELOW][GPC_CLIP]=GPC_FALSE;e[0].bundle[GPC_BELOW][GPC_SUBJ]=GPC_FALSE;for(i=0;i<num_edges;i++){e[i].xb=edge_table[v].vertex.x;e[i].bot.x=edge_table[v].vertex.x;e[i].bot.y=edge_table[v].vertex.y;v=GPC_NEXT_INDEX(v,num_vertices);e[i].top.x=edge_table[v].vertex.x;e[i].top.y=edge_table[v].vertex.y;e[i].dx=(edge_table[v].vertex.x-e[i].bot.x)/(e[i].top.y-e[i].bot.y);e[i].type=type;e[i].outp[GPC_ABOVE]=NULL;e[i].outp[GPC_BELOW]=NULL;e[i].next=NULL;e[i].prev=NULL;e[i].succ=((num_edges>1)&&(i<(num_edges-1)))?&(e[i+1]):NULL;e[i].pred=((num_edges>1)&&(i>0))?&(e[i-1]):NULL;e[i].next_bound=NULL;e[i].bside[GPC_CLIP]=(op==GPC_DIFF)?GPC_RIGHT:GPC_LEFT;e[i].bside[GPC_SUBJ]=GPC_LEFT;}gpc_insert_bound(gpc_bound_list(lmt,edge_table[min].vertex.y),e);}}for(min=0;min<num_vertices;min++){if(GPC_REV_MIN(edge_table,min,num_vertices)){num_edges=1;max=GPC_PREV_INDEX(min,num_vertices);while(GPC_NOT_RMAX(edge_table,max,num_vertices)){num_edges++;max=GPC_PREV_INDEX(max,num_vertices);}e=&edge_table[e_index];e_index+=num_edges;v=min;e[0].bstate[GPC_BELOW]=GPC_UNBUNDLED;e[0].bundle[GPC_BELOW][GPC_CLIP]=GPC_FALSE;e[0].bundle[GPC_BELOW][GPC_SUBJ]=GPC_FALSE;for(i=0;i<num_edges;i++){e[i].xb=edge_table[v].vertex.x;e[i].bot.x=edge_table[v].vertex.x;e[i].bot.y=edge_table[v].vertex.y;v=GPC_PREV_INDEX(v,num_vertices);e[i].top.x=edge_table[v].vertex.x;e[i].top.y=edge_table[v].vertex.y;e[i].dx=(edge_table[v].vertex.x-e[i].bot.x)/(e[i].top.y-e[i].bot.y);e[i].type=type;e[i].outp[GPC_ABOVE]=NULL;e[i].outp[GPC_BELOW]=NULL;e[i].next=NULL;e[i].prev=NULL;e[i].succ=((num_edges>1)&&(i<(num_edges-1)))?&(e[i+1]):NULL;e[i].pred=((num_edges>1)&&(i>0))?&(e[i-1]):NULL;e[i].next_bound=NULL;e[i].bside[GPC_CLIP]=(op==GPC_DIFF)?GPC_RIGHT:GPC_LEFT;e[i].bside[GPC_SUBJ]=GPC_LEFT;}gpc_insert_bound(gpc_bound_list(lmt,edge_table[min].vertex.y),e);}}}}return edge_table;}static void gpc_add_edge_to_aet(gpc_edge_node**aet,gpc_edge_node*edge,gpc_edge_node*prev){if(!*aet){*aet=edge;edge->prev=prev;edge->next=NULL;}else{if(edge->xb<(*aet)->xb){edge->prev=prev;edge->next=*aet;(*aet)->prev=edge;*aet=edge;}else{if(edge->xb==(*aet)->xb){if(edge->dx<(*aet)->dx){edge->prev=prev;edge->next=*aet;(*aet)->prev=edge;*aet=edge;}else{gpc_add_edge_to_aet(&((*aet)->next),edge,*aet);}}else{gpc_add_edge_to_aet(&((*aet)->next),edge,*aet);}}}}static void gpc_add_intersection(gpc_it_node**it,gpc_edge_node*edge0,gpc_edge_node*edge1,double x,double y){gpc_it_node*existing_node;if(!*it){GPC_MALLOC(*it,sizeof(gpc_it_node),"IT insertion",gpc_it_node);(*it)->ie[0]=edge0;(*it)->ie[1]=edge1;(*it)->point.x=x;(*it)->point.y=y;(*it)->next=NULL;}else{if((*it)->point.y>y){existing_node=*it;GPC_MALLOC(*it,sizeof(gpc_it_node),"IT insertion",gpc_it_node);(*it)->ie[0]=edge0;(*it)->ie[1]=edge1;(*it)->point.x=x;(*it)->point.y=y;(*it)->next=existing_node;}else gpc_add_intersection(&((*it)->next),edge0,edge1,x,y);}}static void gpc_add_st_edge(gpc_st_node**st,gpc_it_node**it,gpc_edge_node*edge,double dy){gpc_st_node*existing_node;double den,r,x,y;if(!*st){GPC_MALLOC(*st,sizeof(gpc_st_node),"ST insertion",gpc_st_node);(*st)->edge=edge;(*st)->xb=edge->xb;(*st)->xt=edge->xt;(*st)->dx=edge->dx;(*st)->prev=NULL;}else{den=((*st)->xt-(*st)->xb)-(edge->xt-edge->xb);if((edge->xt>=(*st)->xt)||(edge->dx==(*st)->dx)|| (fabs(den)<=DBL_EPSILON)){existing_node=*st;GPC_MALLOC(*st,sizeof(gpc_st_node),"ST insertion",gpc_st_node);(*st)->edge=edge;(*st)->xb=edge->xb;(*st)->xt=edge->xt;(*st)->dx=edge->dx;(*st)->prev=existing_node;}else{r=(edge->xb-(*st)->xb)/den;x=(*st)->xb+r*((*st)->xt-(*st)->xb);y=r*dy;gpc_add_intersection(it,(*st)->edge,edge,x,y);gpc_add_st_edge(&((*st)->prev),it,edge,dy);}}}static void gpc_build_intersection_table(gpc_it_node**it,gpc_edge_node*aet,double dy){gpc_st_node*st,*stp;gpc_edge_node*edge;gpc_reset_it(it);st=NULL;for(edge=aet;edge;edge=edge->next){if((edge->bstate[GPC_ABOVE]==GPC_BUNDLE_HEAD)||edge->bundle[GPC_ABOVE][GPC_CLIP]||edge->bundle[GPC_ABOVE][GPC_SUBJ]) gpc_add_st_edge(&st,it,edge,dy);}while(st){stp=st->prev;GPC_FREE(st);st=stp;}}static int gpc_count_contours(gpc_polygon_node*polygon){int nc,nv;gpc_vertex_node*v,*nextv;for(nc=0;polygon;polygon=polygon->next) if(polygon->active){nv=0;for(v=polygon->proxy->v[GPC_LEFT];v;v=v->next) nv++;if(nv>2){polygon->active=nv;nc++;}else{for(v=polygon->proxy->v[GPC_LEFT];v;v=nextv){nextv=v->next;GPC_FREE(v);}polygon->active=0;}}return nc;}static void gpc_add_left(gpc_polygon_node*p,double x,double y){gpc_vertex_node*nv;GPC_MALLOC(nv,sizeof(gpc_vertex_node),"vertex node creation",gpc_vertex_node);nv->x=x;nv->y=y;nv->next=p->proxy->v[GPC_LEFT];p->proxy->v[GPC_LEFT]=nv;}static void gpc_merge_left(gpc_polygon_node*p,gpc_polygon_node*q,gpc_polygon_node*list){gpc_polygon_node*target;q->proxy->hole=GPC_TRUE;if(p->proxy!=q->proxy){p->proxy->v[GPC_RIGHT]->next=q->proxy->v[GPC_LEFT];q->proxy->v[GPC_LEFT]=p->proxy->v[GPC_LEFT];for(target=p->proxy;list;list=list->next){if(list->proxy==target){list->active=GPC_FALSE;list->proxy=q->proxy;}}}}static void gpc_add_right(gpc_polygon_node*p,double x,double y){gpc_vertex_node*nv;GPC_MALLOC(nv,sizeof(gpc_vertex_node),"vertex node creation",gpc_vertex_node);nv->x=x;nv->y=y;nv->next=NULL;p->proxy->v[GPC_RIGHT]->next=nv;p->proxy->v[GPC_RIGHT]=nv;}static void gpc_merge_right(gpc_polygon_node*p,gpc_polygon_node*q,gpc_polygon_node*list){gpc_polygon_node*target;q->proxy->hole=GPC_FALSE;if(p->proxy!=q->proxy){q->proxy->v[GPC_RIGHT]->next=p->proxy->v[GPC_LEFT];q->proxy->v[GPC_RIGHT]=p->proxy->v[GPC_RIGHT];for(target=p->proxy;list;list=list->next){if(list->proxy==target){list->active=GPC_FALSE;list->proxy=q->proxy;}}}}static void gpc_add_local_min(gpc_polygon_node**p,gpc_edge_node*edge,double x,double y){gpc_polygon_node*existing_min;gpc_vertex_node*nv;existing_min=*p;GPC_MALLOC(*p,sizeof(gpc_polygon_node),"polygon node creation",gpc_polygon_node);GPC_MALLOC(nv,sizeof(gpc_vertex_node),"vertex node creation",gpc_vertex_node);nv->x=x;nv->y=y;nv->next=NULL;(*p)->proxy=(*p);(*p)->active=GPC_TRUE;(*p)->next=existing_min;(*p)->v[GPC_LEFT]=nv;(*p)->v[GPC_RIGHT]=nv;edge->outp[GPC_ABOVE]=*p;}static int gpc_count_tristrips(gpc_polygon_node*tn){int total;for(total=0;tn;tn=tn->next) if(tn->active>2) total++;return total;}static void gpc_add_vertex(gpc_vertex_node**t,double x,double y){if(!(*t)){GPC_MALLOC(*t,sizeof(gpc_vertex_node),"tristrip vertex creation",gpc_vertex_node);(*t)->x=x;(*t)->y=y;(*t)->next=NULL;}else gpc_add_vertex(&((*t)->next),x,y);}static void gpc_new_tristrip(gpc_polygon_node**tn,gpc_edge_node*edge,double x,double y){if(!(*tn)){GPC_MALLOC(*tn,sizeof(gpc_polygon_node),"tristrip node creation",gpc_polygon_node);(*tn)->next=NULL;(*tn)->v[GPC_LEFT]=NULL;(*tn)->v[GPC_RIGHT]=NULL;(*tn)->active=1;gpc_add_vertex(&((*tn)->v[GPC_LEFT]),x,y); edge->outp[GPC_ABOVE]=*tn;}else gpc_new_tristrip(&((*tn)->next),edge,x,y);}static gpc_bbox*gpc_create_contour_bboxes(gpc_polygon*p){gpc_bbox*box;int c,v;GPC_MALLOC(box,p->num_contours*sizeof(gpc_bbox),"Bounding box creation",gpc_bbox);for(c=0;c<p->num_contours;c++){box[c].xmin=DBL_MAX;box[c].ymin=DBL_MAX;box[c].xmax=-DBL_MAX;box[c].ymax=-DBL_MAX;for(v=0;v<p->contour[c].num_vertices;v++){if(p->contour[c].vertex[v].x<box[c].xmin) box[c].xmin=p->contour[c].vertex[v].x;if(p->contour[c].vertex[v].y<box[c].ymin) box[c].ymin=p->contour[c].vertex[v].y;if(p->contour[c].vertex[v].x>box[c].xmax) box[c].xmax=p->contour[c].vertex[v].x;if(p->contour[c].vertex[v].y>box[c].ymax) box[c].ymax=p->contour[c].vertex[v].y;}}return box;}static void gpc_minimax_test(gpc_polygon*subj,gpc_polygon*clip,gpc_op op){gpc_bbox*s_bbox,*c_bbox;int s,c,*o_table,overlap;s_bbox=gpc_create_contour_bboxes(subj);c_bbox=gpc_create_contour_bboxes(clip);GPC_MALLOC(o_table,subj->num_contours*clip->num_contours*sizeof(int),"overlap table creation",int);for(s=0;s<subj->num_contours;s++) for(c=0;c<clip->num_contours;c++) o_table[c*subj->num_contours+s]=(!((s_bbox[s].xmax<c_bbox[c].xmin)||(s_bbox[s].xmin>c_bbox[c].xmax)))&&(!((s_bbox[s].ymax<c_bbox[c].ymin)||(s_bbox[s].ymin>c_bbox[c].ymax)));for(c=0;c<clip->num_contours;c++){overlap=0;for(s=0;(!overlap)&&(s<subj->num_contours);s++) overlap=o_table[c*subj->num_contours+s];if(!overlap) clip->contour[c].num_vertices=-clip->contour[c].num_vertices;} if(op==GPC_INT){ for(s=0;s<subj->num_contours;s++){overlap=0;for(c=0;(!overlap)&&(c<clip->num_contours);c++) overlap=o_table[c*subj->num_contours+s];if(!overlap) subj->contour[s].num_vertices=-subj->contour[s].num_vertices;}}GPC_FREE(s_bbox);GPC_FREE(c_bbox);GPC_FREE(o_table);}void gpc_free_polygon(gpc_polygon*p){int c;for(c=0;c<p->num_contours;c++) GPC_FREE(p->contour[c].vertex);GPC_FREE(p->hole);GPC_FREE(p->contour);p->num_contours=0;}void gpc_read_polygon(FILE*fp,int read_hole_flags,gpc_polygon*p){int c,v;fscanf(fp,"%d",&(p->num_contours));GPC_MALLOC(p->hole,p->num_contours*sizeof(int),"hole flag array creation",int);GPC_MALLOC(p->contour,p->num_contours*sizeof(gpc_vertex_list),"contour creation",gpc_vertex_list);for(c=0;c<p->num_contours;c++){fscanf(fp,"%d",&(p->contour[c].num_vertices));if(read_hole_flags) fscanf(fp,"%d",&(p->hole[c]));else p->hole[c]=GPC_FALSE;GPC_MALLOC(p->contour[c].vertex,p->contour[c].num_vertices*sizeof(gpc_vertex),"vertex creation",gpc_vertex);for(v=0;v<p->contour[c].num_vertices;v++) fscanf(fp,"%lf %lf",&(p->contour[c].vertex[v].x),&(p->contour[c].vertex[v].y));}}void gpc_write_polygon(FILE*fp,int write_hole_flags,gpc_polygon*p){int c,v;fprintf(fp,"%d\n",p->num_contours);for(c=0;c<p->num_contours;c++){fprintf(fp,"%d\n",p->contour[c].num_vertices);if(write_hole_flags) fprintf(fp,"%d\n",p->hole[c]); for(v=0;v<p->contour[c].num_vertices;v++) fprintf(fp,"% .*lf%.*lf\n",DBL_DIG,p->contour[c].vertex[v].x,DBL_DIG,p->contour[c].vertex[v].y);}}void gpc_add_contour(gpc_polygon*p,gpc_vertex_list*new_contour,int hole){int*extended_hole,c,v;gpc_vertex_list*extended_contour;GPC_MALLOC(extended_hole,(p->num_contours+1)*sizeof(int),"contour hole addition",int);GPC_MALLOC(extended_contour,(p->num_contours+1)*sizeof(gpc_vertex_list),"contour addition",gpc_vertex_list);for(c=0;c<p->num_contours;c++){extended_hole[c]=p->hole[c];extended_contour[c]=p->contour[c];}c=p->num_contours;extended_hole[c]=hole;extended_contour[c].num_vertices=new_contour->num_vertices;GPC_MALLOC(extended_contour[c].vertex,new_contour->num_vertices*sizeof(gpc_vertex),"contour addition",gpc_vertex);for(v=0;v<new_contour->num_vertices;v++) extended_contour[c].vertex[v]=new_contour->vertex[v];GPC_FREE(p->contour);GPC_FREE(p->hole);p->num_contours++;p->hole=extended_hole;p->contour=extended_contour;}void gpc_polygon_clip(gpc_op op,gpc_polygon*subj,gpc_polygon*clip,gpc_polygon*result){gpc_sb_tree*sbtree=NULL;gpc_it_node*it=NULL,*intersect;gpc_edge_node*edge,*prev_edge,*next_edge,*succ_edge,*e0,*e1;gpc_edge_node*aet=NULL,*c_heap=NULL,*s_heap=NULL;gpc_lmt_node*lmt=NULL,*local_min;gpc_polygon_node*out_poly=NULL,*p,*q,*poly,*npoly,*cf=NULL;gpc_vertex_node*vtx,*nv;gpc_h_state horiz[2];int in[2],exists[2],parity[2]={GPC_LEFT,GPC_LEFT};int c,v,contributing,search,scanbeam=0,sbt_entries=0;int vclass,bl,br,tl,tr;double*sbt=NULL,xb,px,yb,yt,dy,ix,iy;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_contours=0;result->hole=NULL;result->contour=NULL;return;}if(((op==GPC_INT)||(op==GPC_DIFF))&&(subj->num_contours>0)&&(clip->num_contours>0)) gpc_minimax_test(subj,clip,op);if(subj->num_contours>0) s_heap=gpc_build_lmt(&lmt,&sbtree,&sbt_entries,subj,GPC_SUBJ,op);if(clip->num_contours>0) c_heap=gpc_build_lmt(&lmt,&sbtree,&sbt_entries,clip,GPC_CLIP,op);if(lmt==NULL){result->num_contours=0;result->hole=NULL;result->contour=NULL;gpc_reset_lmt(&lmt);GPC_FREE(s_heap);GPC_FREE(c_heap);return;}GPC_MALLOC(sbt,sbt_entries*sizeof(double),"sbt creation",double);gpc_build_sbt(&scanbeam,sbt,sbtree);scanbeam=0;gpc_free_sbtree(&sbtree);if(subj==result) gpc_free_polygon(subj);if(clip==result) gpc_free_polygon(clip);if(op==GPC_DIFF) parity[GPC_CLIP]=GPC_RIGHT;local_min=lmt;while(scanbeam<sbt_entries){yb=sbt[scanbeam++];if(scanbeam<sbt_entries){yt=sbt[scanbeam];dy=yt-yb;}if(local_min){if(local_min->y==yb){for(edge=local_min->first_bound;edge;edge=edge->next_bound) gpc_add_edge_to_aet(&aet,edge,NULL);local_min=local_min->next;}}px=-DBL_MAX;e0=aet;e1=aet;aet->bundle[GPC_ABOVE][ aet->type]=(aet->top.y!=yb);aet->bundle[GPC_ABOVE][!aet->type]=GPC_FALSE;aet->bstate[GPC_ABOVE]=GPC_UNBUNDLED;for(next_edge=aet->next;next_edge;next_edge=next_edge->next){next_edge->bundle[GPC_ABOVE][ next_edge->type]=(next_edge->top.y!=yb);next_edge->bundle[GPC_ABOVE][!next_edge->type]=GPC_FALSE;next_edge->bstate[GPC_ABOVE]=GPC_UNBUNDLED;if(next_edge->bundle[GPC_ABOVE][next_edge->type]){if(GPC_EQ(e0->xb,next_edge->xb)&&GPC_EQ(e0->dx,next_edge->dx)&&(e0->top.y!=yb)){next_edge->bundle[GPC_ABOVE][ next_edge->type]^= e0->bundle[GPC_ABOVE][ next_edge->type];next_edge->bundle[GPC_ABOVE][!next_edge->type]= e0->bundle[GPC_ABOVE][!next_edge->type];next_edge->bstate[GPC_ABOVE]=GPC_BUNDLE_HEAD;e0->bundle[GPC_ABOVE][GPC_CLIP]=GPC_FALSE;e0->bundle[GPC_ABOVE][GPC_SUBJ]=GPC_FALSE;e0->bstate[GPC_ABOVE]=GPC_BUNDLE_TAIL;}e0=next_edge;}} horiz[GPC_CLIP]=GPC_NH;horiz[GPC_SUBJ]=GPC_NH;for(edge=aet;edge;edge=edge->next){exists[GPC_CLIP]=edge->bundle[GPC_ABOVE][GPC_CLIP]+ (edge->bundle[GPC_BELOW][GPC_CLIP] << 1);exists[GPC_SUBJ]=edge->bundle[GPC_ABOVE][GPC_SUBJ]+ (edge->bundle[GPC_BELOW][GPC_SUBJ] << 1);if(exists[GPC_CLIP]||exists[GPC_SUBJ]){edge->bside[GPC_CLIP]=parity[GPC_CLIP];edge->bside[GPC_SUBJ]=parity[GPC_SUBJ];switch (op){case GPC_DIFF: case GPC_INT: contributing=(exists[GPC_CLIP]&&(parity[GPC_SUBJ]||horiz[GPC_SUBJ]))||(exists[GPC_SUBJ]&&(parity[GPC_CLIP]||horiz[GPC_CLIP]))||(exists[GPC_CLIP]&&exists[GPC_SUBJ]&&(parity[GPC_CLIP]==parity[GPC_SUBJ]));br=(parity[GPC_CLIP])&&(parity[GPC_SUBJ]);bl=(parity[GPC_CLIP]^edge->bundle[GPC_ABOVE][GPC_CLIP])&&(parity[GPC_SUBJ]^edge->bundle[GPC_ABOVE][GPC_SUBJ]);tr=(parity[GPC_CLIP]^(horiz[GPC_CLIP]!=GPC_NH))&&(parity[GPC_SUBJ]^(horiz[GPC_SUBJ]!=GPC_NH));tl=(parity[GPC_CLIP]^(horiz[GPC_CLIP]!=GPC_NH)^edge->bundle[GPC_BELOW][GPC_CLIP]) &&(parity[GPC_SUBJ]^(horiz[GPC_SUBJ]!=GPC_NH)^edge->bundle[GPC_BELOW][GPC_SUBJ]);break;case GPC_XOR: contributing=exists[GPC_CLIP]||exists[GPC_SUBJ];br=(parity[GPC_CLIP])^(parity[GPC_SUBJ]);bl=(parity[GPC_CLIP]^edge->bundle[GPC_ABOVE][GPC_CLIP])^(parity[GPC_SUBJ]^edge->bundle[GPC_ABOVE][GPC_SUBJ]);tr=(parity[GPC_CLIP]^(horiz[GPC_CLIP]!=GPC_NH))^(parity[GPC_SUBJ]^(horiz[GPC_SUBJ]!=GPC_NH));tl=(parity[GPC_CLIP]^(horiz[GPC_CLIP]!=GPC_NH)^edge->bundle[GPC_BELOW][GPC_CLIP]) ^(parity[GPC_SUBJ]^(horiz[GPC_SUBJ]!=GPC_NH)^edge->bundle[GPC_BELOW][GPC_SUBJ]);break;case GPC_UNION: contributing=(exists[GPC_CLIP]&&(!parity[GPC_SUBJ]||horiz[GPC_SUBJ]))||(exists[GPC_SUBJ]&&(!parity[GPC_CLIP]||horiz[GPC_CLIP]))||(exists[GPC_CLIP]&&exists[GPC_SUBJ]&&(parity[GPC_CLIP]==parity[GPC_SUBJ]));br=(parity[GPC_CLIP])||(parity[GPC_SUBJ]);bl=(parity[GPC_CLIP]^edge->bundle[GPC_ABOVE][GPC_CLIP])||(parity[GPC_SUBJ]^edge->bundle[GPC_ABOVE][GPC_SUBJ]);tr=(parity[GPC_CLIP]^(horiz[GPC_CLIP]!=GPC_NH))||(parity[GPC_SUBJ]^(horiz[GPC_SUBJ]!=GPC_NH));tl=(parity[GPC_CLIP]^(horiz[GPC_CLIP]!=GPC_NH)^edge->bundle[GPC_BELOW][GPC_CLIP]) ||(parity[GPC_SUBJ]^(horiz[GPC_SUBJ]!=GPC_NH)^edge->bundle[GPC_BELOW][GPC_SUBJ]);break;}parity[GPC_CLIP]^=edge->bundle[GPC_ABOVE][GPC_CLIP];parity[GPC_SUBJ]^=edge->bundle[GPC_ABOVE][GPC_SUBJ];if(exists[GPC_CLIP])  horiz[GPC_CLIP]=gpc_next_h_state[horiz[GPC_CLIP]] [((exists[GPC_CLIP]-1) << 1)+parity[GPC_CLIP]];if(exists[GPC_SUBJ])  horiz[GPC_SUBJ]=gpc_next_h_state[horiz[GPC_SUBJ]] [((exists[GPC_SUBJ]-1) << 1)+parity[GPC_SUBJ]];vclass=tr+(tl << 1)+(br << 2)+(bl << 3);if(contributing){xb=edge->xb;switch (vclass){case GPC_EMN: case GPC_IMN: gpc_add_local_min(&out_poly,edge,xb,yb);px=xb;cf=edge->outp[GPC_ABOVE];break;case GPC_ERI: if(xb!=px){gpc_add_right(cf,xb,yb);px=xb;}edge->outp[GPC_ABOVE]=cf;cf=NULL;break;case GPC_ELI: gpc_add_left(edge->outp[GPC_BELOW],xb,yb);px=xb;cf=edge->outp[GPC_BELOW];break;case GPC_EMX: if(xb!=px){gpc_add_left(cf,xb,yb);px=xb;}gpc_merge_right(cf,edge->outp[GPC_BELOW],out_poly);cf=NULL;break;case GPC_ILI: if(xb!=px){gpc_add_left(cf,xb,yb);px=xb;}edge->outp[GPC_ABOVE]=cf;cf=NULL;break;case GPC_IRI: gpc_add_right(edge->outp[GPC_BELOW],xb,yb);px=xb;cf=edge->outp[GPC_BELOW];edge->outp[GPC_BELOW]=NULL;break;case GPC_IMX: if(xb!=px){gpc_add_right(cf,xb,yb);px=xb;}gpc_merge_left(cf,edge->outp[GPC_BELOW],out_poly);cf=NULL;edge->outp[GPC_BELOW]=NULL;break;case GPC_IMM: if(xb!=px){gpc_add_right(cf,xb,yb);px=xb;}gpc_merge_left(cf,edge->outp[GPC_BELOW],out_poly);edge->outp[GPC_BELOW]=NULL;gpc_add_local_min(&out_poly,edge,xb,yb);cf=edge->outp[GPC_ABOVE];break;case GPC_EMM: if(xb!=px){gpc_add_left(cf,xb,yb);px=xb;}gpc_merge_right(cf,edge->outp[GPC_BELOW],out_poly);edge->outp[GPC_BELOW]=NULL;gpc_add_local_min(&out_poly,edge,xb,yb);cf=edge->outp[GPC_ABOVE];break;case GPC_LED: if(edge->bot.y==yb) gpc_add_left(edge->outp[GPC_BELOW],xb,yb);edge->outp[GPC_ABOVE]=edge->outp[GPC_BELOW];px=xb;break;case GPC_RED: if(edge->bot.y==yb) gpc_add_right(edge->outp[GPC_BELOW],xb,yb);edge->outp[GPC_ABOVE]=edge->outp[GPC_BELOW];px=xb;break;default: break;}}}}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;if((edge->bstate[GPC_BELOW]==GPC_BUNDLE_HEAD)&&prev_edge){if(prev_edge->bstate[GPC_BELOW]==GPC_BUNDLE_TAIL){prev_edge->outp[GPC_BELOW]=edge->outp[GPC_BELOW];prev_edge->bstate[GPC_BELOW]=GPC_UNBUNDLED;if(prev_edge->prev) if(prev_edge->prev->bstate[GPC_BELOW]==GPC_BUNDLE_TAIL) prev_edge->bstate[GPC_BELOW]=GPC_BUNDLE_HEAD;}}}else{if(edge->top.y==yt) edge->xt=edge->top.x;else edge->xt=edge->bot.x+edge->dx*(yt-edge->bot.y);}}if(scanbeam<sbt_entries){gpc_build_intersection_table(&it,aet,dy);for(intersect=it;intersect;intersect=intersect->next){e0=intersect->ie[0];e1=intersect->ie[1];if((e0->bundle[GPC_ABOVE][GPC_CLIP]||e0->bundle[GPC_ABOVE][GPC_SUBJ])&&(e1->bundle[GPC_ABOVE][GPC_CLIP]||e1->bundle[GPC_ABOVE][GPC_SUBJ])){p=e0->outp[GPC_ABOVE];q=e1->outp[GPC_ABOVE];ix=intersect->point.x;iy=intersect->point.y+yb; in[GPC_CLIP]=( e0->bundle[GPC_ABOVE][GPC_CLIP]&&!e0->bside[GPC_CLIP])||( e1->bundle[GPC_ABOVE][GPC_CLIP]&&e1->bside[GPC_CLIP])||(!e0->bundle[GPC_ABOVE][GPC_CLIP]&&!e1->bundle[GPC_ABOVE][GPC_CLIP]&&e0->bside[GPC_CLIP]&&e1->bside[GPC_CLIP]);in[GPC_SUBJ]=( e0->bundle[GPC_ABOVE][GPC_SUBJ]&&!e0->bside[GPC_SUBJ])||( e1->bundle[GPC_ABOVE][GPC_SUBJ]&&e1->bside[GPC_SUBJ])||(!e0->bundle[GPC_ABOVE][GPC_SUBJ]&&!e1->bundle[GPC_ABOVE][GPC_SUBJ]&&e0->bside[GPC_SUBJ]&&e1->bside[GPC_SUBJ]); switch (op){case GPC_DIFF: case GPC_INT: tr=(in[GPC_CLIP])&&(in[GPC_SUBJ]);tl=(in[GPC_CLIP]^e1->bundle[GPC_ABOVE][GPC_CLIP])&&(in[GPC_SUBJ]^e1->bundle[GPC_ABOVE][GPC_SUBJ]);br=(in[GPC_CLIP]^e0->bundle[GPC_ABOVE][GPC_CLIP])&&(in[GPC_SUBJ]^e0->bundle[GPC_ABOVE][GPC_SUBJ]);bl=(in[GPC_CLIP]^e1->bundle[GPC_ABOVE][GPC_CLIP]^e0->bundle[GPC_ABOVE][GPC_CLIP])&&(in[GPC_SUBJ]^e1->bundle[GPC_ABOVE][GPC_SUBJ]^e0->bundle[GPC_ABOVE][GPC_SUBJ]);break;case GPC_XOR: tr=(in[GPC_CLIP])^(in[GPC_SUBJ]);tl=(in[GPC_CLIP]^e1->bundle[GPC_ABOVE][GPC_CLIP])^(in[GPC_SUBJ]^e1->bundle[GPC_ABOVE][GPC_SUBJ]);br=(in[GPC_CLIP]^e0->bundle[GPC_ABOVE][GPC_CLIP])^(in[GPC_SUBJ]^e0->bundle[GPC_ABOVE][GPC_SUBJ]);bl=(in[GPC_CLIP]^e1->bundle[GPC_ABOVE][GPC_CLIP]^e0->bundle[GPC_ABOVE][GPC_CLIP])^(in[GPC_SUBJ]^e1->bundle[GPC_ABOVE][GPC_SUBJ]^e0->bundle[GPC_ABOVE][GPC_SUBJ]);break;case GPC_UNION: tr=(in[GPC_CLIP])||(in[GPC_SUBJ]);tl=(in[GPC_CLIP]^e1->bundle[GPC_ABOVE][GPC_CLIP])||(in[GPC_SUBJ]^e1->bundle[GPC_ABOVE][GPC_SUBJ]);br=(in[GPC_CLIP]^e0->bundle[GPC_ABOVE][GPC_CLIP])||(in[GPC_SUBJ]^e0->bundle[GPC_ABOVE][GPC_SUBJ]);bl=(in[GPC_CLIP]^e1->bundle[GPC_ABOVE][GPC_CLIP]^e0->bundle[GPC_ABOVE][GPC_CLIP])||(in[GPC_SUBJ]^e1->bundle[GPC_ABOVE][GPC_SUBJ]^e0->bundle[GPC_ABOVE][GPC_SUBJ]);break;} vclass=tr+(tl << 1)+(br << 2)+(bl << 3);switch (vclass){case GPC_EMN: gpc_add_local_min(&out_poly,e0,ix,iy);e1->outp[GPC_ABOVE]=e0->outp[GPC_ABOVE];break;case GPC_ERI: if(p){gpc_add_right(p,ix,iy);e1->outp[GPC_ABOVE]=p;e0->outp[GPC_ABOVE]=NULL;}break;case GPC_ELI: if(q){gpc_add_left(q,ix,iy);e0->outp[GPC_ABOVE]=q;e1->outp[GPC_ABOVE]=NULL;}break;case GPC_EMX: if(p&&q){gpc_add_left(p,ix,iy);gpc_merge_right(p,q,out_poly);e0->outp[GPC_ABOVE]=NULL;e1->outp[GPC_ABOVE]=NULL;}break;case GPC_IMN: gpc_add_local_min(&out_poly,e0,ix,iy);e1->outp[GPC_ABOVE]=e0->outp[GPC_ABOVE];break;case GPC_ILI: if(p){gpc_add_left(p,ix,iy);e1->outp[GPC_ABOVE]=p;e0->outp[GPC_ABOVE]=NULL;}break;case GPC_IRI: if(q){gpc_add_right(q,ix,iy);e0->outp[GPC_ABOVE]=q;e1->outp[GPC_ABOVE]=NULL;}break;case GPC_IMX: if(p&&q){gpc_add_right(p,ix,iy);gpc_merge_left(p,q,out_poly);e0->outp[GPC_ABOVE]=NULL;e1->outp[GPC_ABOVE]=NULL;}break;case GPC_IMM: if(p&&q){gpc_add_right(p,ix,iy);gpc_merge_left(p,q,out_poly);gpc_add_local_min(&out_poly,e0,ix,iy);e1->outp[GPC_ABOVE]=e0->outp[GPC_ABOVE];}break;case GPC_EMM: if(p&&q){gpc_add_left(p,ix,iy);gpc_merge_right(p,q,out_poly);gpc_add_local_min(&out_poly,e0,ix,iy);e1->outp[GPC_ABOVE]=e0->outp[GPC_ABOVE];}break;default: break;}}if(e0->bundle[GPC_ABOVE][GPC_CLIP]) e1->bside[GPC_CLIP]=!e1->bside[GPC_CLIP];if(e1->bundle[GPC_ABOVE][GPC_CLIP]) e0->bside[GPC_CLIP]=!e0->bside[GPC_CLIP];if(e0->bundle[GPC_ABOVE][GPC_SUBJ]) e1->bside[GPC_SUBJ]=!e1->bside[GPC_SUBJ];if(e1->bundle[GPC_ABOVE][GPC_SUBJ]) e0->bside[GPC_SUBJ]=!e0->bside[GPC_SUBJ];prev_edge=e0->prev;next_edge=e1->next;if(next_edge) next_edge->prev=e0;if(e0->bstate[GPC_ABOVE]==GPC_BUNDLE_HEAD){search=GPC_TRUE;while(search){prev_edge=prev_edge->prev;if(prev_edge){if(prev_edge->bstate[GPC_ABOVE]!=GPC_BUNDLE_TAIL) search=GPC_FALSE;}else search=GPC_FALSE;}}if(!prev_edge){aet->prev=e1;e1->next=aet;aet=e0->next;}else{prev_edge->next->prev=e1;e1->next=prev_edge->next;prev_edge->next=e0->next;}e0->next->prev=prev_edge;e1->next->prev=e1;e0->next=next_edge;}for(edge=aet;edge;edge=next_edge){next_edge=edge->next;succ_edge=edge->succ;if((edge->top.y==yt)&&succ_edge){succ_edge->outp[GPC_BELOW]=edge->outp[GPC_ABOVE];succ_edge->bstate[GPC_BELOW]=edge->bstate[GPC_ABOVE];succ_edge->bundle[GPC_BELOW][GPC_CLIP]=edge->bundle[GPC_ABOVE][GPC_CLIP];succ_edge->bundle[GPC_BELOW][GPC_SUBJ]=edge->bundle[GPC_ABOVE][GPC_SUBJ];prev_edge=edge->prev;if(prev_edge) prev_edge->next=succ_edge;else aet=succ_edge;if(next_edge) next_edge->prev=succ_edge;succ_edge->prev=prev_edge;succ_edge->next=next_edge;}else{edge->outp[GPC_BELOW]=edge->outp[GPC_ABOVE];edge->bstate[GPC_BELOW]=edge->bstate[GPC_ABOVE];edge->bundle[GPC_BELOW][GPC_CLIP]=edge->bundle[GPC_ABOVE][GPC_CLIP];edge->bundle[GPC_BELOW][GPC_SUBJ]=edge->bundle[GPC_ABOVE][GPC_SUBJ];edge->xb=edge->xt;}edge->outp[GPC_ABOVE]=NULL;}}}result->contour=NULL;result->hole=NULL;result->num_contours=gpc_count_contours(out_poly);if(result->num_contours>0){GPC_MALLOC(result->hole,result->num_contours*sizeof(int),"hole flag table creation",int);GPC_MALLOC(result->contour,result->num_contours*sizeof(gpc_vertex_list),"contour creation",gpc_vertex_list);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;GPC_MALLOC(result->contour[c].vertex,result->contour[c].num_vertices*sizeof(gpc_vertex),"vertex creation",gpc_vertex); v=result->contour[c].num_vertices-1;for(vtx=poly->proxy->v[GPC_LEFT];vtx;vtx=nv){nv=vtx->next;result->contour[c].vertex[v].x=vtx->x;result->contour[c].vertex[v].y=vtx->y;GPC_FREE(vtx);v--;}c++;}GPC_FREE(poly);}}else{for(poly=out_poly;poly;poly=npoly){npoly=poly->next;GPC_FREE(poly);}}gpc_reset_it(&it);gpc_reset_lmt(&lmt);GPC_FREE(c_heap);GPC_FREE(s_heap);GPC_FREE(sbt);}void gpc_free_tristrip(gpc_tristrip*t){int s;for(s=0;s<t->num_strips;s++) GPC_FREE(t->strip[s].vertex);GPC_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){gpc_sb_tree*sbtree=NULL;gpc_it_node*it=NULL,*intersect;gpc_edge_node*edge,*prev_edge,*next_edge,*succ_edge,*e0,*e1;gpc_edge_node*aet=NULL,*c_heap=NULL,*s_heap=NULL,*cf;gpc_lmt_node*lmt=NULL,*local_min;gpc_polygon_node*tlist=NULL,*tn,*tnn,*p,*q;gpc_vertex_node*lt,*ltn,*rt,*rtn;gpc_h_state horiz[2];gpc_vertex_type cft;int in[2],exists[2],parity[2]={GPC_LEFT,GPC_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;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;}if(((op==GPC_INT)||(op==GPC_DIFF))&&(subj->num_contours>0)&&(clip->num_contours>0)) gpc_minimax_test(subj,clip,op);if(subj->num_contours>0) s_heap=gpc_build_lmt(&lmt,&sbtree,&sbt_entries,subj,GPC_SUBJ,op);if(clip->num_contours>0) c_heap=gpc_build_lmt(&lmt,&sbtree,&sbt_entries,clip,GPC_CLIP,op);if(lmt==NULL){result->num_strips=0;result->strip=NULL;gpc_reset_lmt(&lmt);GPC_FREE(s_heap);GPC_FREE(c_heap);return;}GPC_MALLOC(sbt,sbt_entries*sizeof(double),"sbt creation",double);gpc_build_sbt(&scanbeam,sbt,sbtree);scanbeam=0;gpc_free_sbtree(&sbtree);if(op==GPC_DIFF) parity[GPC_CLIP]=GPC_RIGHT;local_min=lmt;while(scanbeam<sbt_entries){yb=sbt[scanbeam++];if(scanbeam<sbt_entries){yt=sbt[scanbeam];dy=yt-yb;}if(local_min){if(local_min->y==yb){for(edge=local_min->first_bound;edge;edge=edge->next_bound) gpc_add_edge_to_aet(&aet,edge,NULL);local_min=local_min->next;}}px=-DBL_MAX;e0=aet;e1=aet;aet->bundle[GPC_ABOVE][ aet->type]=(aet->top.y!=yb);aet->bundle[GPC_ABOVE][!aet->type]=GPC_FALSE;aet->bstate[GPC_ABOVE]=GPC_UNBUNDLED;for(next_edge=aet->next;next_edge;next_edge=next_edge->next){next_edge->bundle[GPC_ABOVE][ next_edge->type]=(next_edge->top.y!=yb);next_edge->bundle[GPC_ABOVE][!next_edge->type]=GPC_FALSE;next_edge->bstate[GPC_ABOVE]=GPC_UNBUNDLED;if(next_edge->bundle[GPC_ABOVE][next_edge->type]){if(GPC_EQ(e0->xb,next_edge->xb)&&GPC_EQ(e0->dx,next_edge->dx)&&(e0->top.y!=yb)){next_edge->bundle[GPC_ABOVE][ next_edge->type]^= e0->bundle[GPC_ABOVE][ next_edge->type];next_edge->bundle[GPC_ABOVE][!next_edge->type]= e0->bundle[GPC_ABOVE][!next_edge->type]; next_edge->bstate[GPC_ABOVE]=GPC_BUNDLE_HEAD;e0->bundle[GPC_ABOVE][GPC_CLIP]=GPC_FALSE;e0->bundle[GPC_ABOVE][GPC_SUBJ]=GPC_FALSE;e0->bstate[GPC_ABOVE]=GPC_BUNDLE_TAIL;}e0=next_edge;}}horiz[GPC_CLIP]=GPC_NH;horiz[GPC_SUBJ]=GPC_NH;for(edge=aet;edge;edge=edge->next){exists[GPC_CLIP]=edge->bundle[GPC_ABOVE][GPC_CLIP]+ (edge->bundle[GPC_BELOW][GPC_CLIP] << 1);exists[GPC_SUBJ]=edge->bundle[GPC_ABOVE][GPC_SUBJ]+ (edge->bundle[GPC_BELOW][GPC_SUBJ] << 1);if(exists[GPC_CLIP]||exists[GPC_SUBJ]){edge->bside[GPC_CLIP]=parity[GPC_CLIP];edge->bside[GPC_SUBJ]=parity[GPC_SUBJ];switch (op){case GPC_DIFF: case GPC_INT: contributing=(exists[GPC_CLIP]&&(parity[GPC_SUBJ]||horiz[GPC_SUBJ]))||(exists[GPC_SUBJ]&&(parity[GPC_CLIP]||horiz[GPC_CLIP]))||(exists[GPC_CLIP]&&exists[GPC_SUBJ]&&(parity[GPC_CLIP]==parity[GPC_SUBJ]));br=(parity[GPC_CLIP])&&(parity[GPC_SUBJ]);bl=(parity[GPC_CLIP]^edge->bundle[GPC_ABOVE][GPC_CLIP])&&(parity[GPC_SUBJ]^edge->bundle[GPC_ABOVE][GPC_SUBJ]);tr=(parity[GPC_CLIP]^(horiz[GPC_CLIP]!=GPC_NH))&&(parity[GPC_SUBJ]^(horiz[GPC_SUBJ]!=GPC_NH));tl=(parity[GPC_CLIP]^(horiz[GPC_CLIP]!=GPC_NH)^edge->bundle[GPC_BELOW][GPC_CLIP]) &&(parity[GPC_SUBJ]^(horiz[GPC_SUBJ]!=GPC_NH)^edge->bundle[GPC_BELOW][GPC_SUBJ]);break;case GPC_XOR: contributing=exists[GPC_CLIP]||exists[GPC_SUBJ];br=(parity[GPC_CLIP])^(parity[GPC_SUBJ]);bl=(parity[GPC_CLIP]^edge->bundle[GPC_ABOVE][GPC_CLIP])^(parity[GPC_SUBJ]^edge->bundle[GPC_ABOVE][GPC_SUBJ]);tr=(parity[GPC_CLIP]^(horiz[GPC_CLIP]!=GPC_NH))^(parity[GPC_SUBJ]^(horiz[GPC_SUBJ]!=GPC_NH));tl=(parity[GPC_CLIP]^(horiz[GPC_CLIP]!=GPC_NH)^edge->bundle[GPC_BELOW][GPC_CLIP])^(parity[GPC_SUBJ]^(horiz[GPC_SUBJ]!=GPC_NH)^edge->bundle[GPC_BELOW][GPC_SUBJ]);break;case GPC_UNION: contributing=(exists[GPC_CLIP]&&(!parity[GPC_SUBJ]||horiz[GPC_SUBJ]))||(exists[GPC_SUBJ]&&(!parity[GPC_CLIP]||horiz[GPC_CLIP]))||(exists[GPC_CLIP]&&exists[GPC_SUBJ]&&(parity[GPC_CLIP]==parity[GPC_SUBJ]));br=(parity[GPC_CLIP])||(parity[GPC_SUBJ]);bl=(parity[GPC_CLIP]^edge->bundle[GPC_ABOVE][GPC_CLIP])||(parity[GPC_SUBJ]^edge->bundle[GPC_ABOVE][GPC_SUBJ]);tr=(parity[GPC_CLIP]^(horiz[GPC_CLIP]!=GPC_NH))||(parity[GPC_SUBJ]^(horiz[GPC_SUBJ]!=GPC_NH));tl=(parity[GPC_CLIP]^(horiz[GPC_CLIP]!=GPC_NH)^edge->bundle[GPC_BELOW][GPC_CLIP])||(parity[GPC_SUBJ]^(horiz[GPC_SUBJ]!=GPC_NH)^edge->bundle[GPC_BELOW][GPC_SUBJ]);break;}parity[GPC_CLIP]^=edge->bundle[GPC_ABOVE][GPC_CLIP];parity[GPC_SUBJ]^=edge->bundle[GPC_ABOVE][GPC_SUBJ];if(exists[GPC_CLIP])  horiz[GPC_CLIP]=gpc_next_h_state[horiz[GPC_CLIP]] [((exists[GPC_CLIP]-1) << 1)+parity[GPC_CLIP]];if(exists[GPC_SUBJ])  horiz[GPC_SUBJ]=gpc_next_h_state[horiz[GPC_SUBJ]] [((exists[GPC_SUBJ]-1) << 1)+parity[GPC_SUBJ]]; vclass=tr+(tl << 1)+(br << 2)+(bl << 3);if(contributing){xb=edge->xb;switch (vclass){case GPC_EMN: gpc_new_tristrip(&tlist,edge,xb,yb);cf=edge;break;case GPC_ERI: edge->outp[GPC_ABOVE]=cf->outp[GPC_ABOVE];if(xb!=cf->xb) GPC_VERTEX(edge,GPC_ABOVE,GPC_RIGHT,xb,yb);cf=NULL;break;case GPC_ELI: GPC_VERTEX(edge,GPC_BELOW,GPC_LEFT,xb,yb);edge->outp[GPC_ABOVE]=NULL;cf=edge;break;case GPC_EMX: if(xb!=cf->xb) GPC_VERTEX(edge,GPC_BELOW,GPC_RIGHT,xb,yb);edge->outp[GPC_ABOVE]=NULL;cf=NULL;break;case GPC_IMN: if(cft==GPC_LED){if(cf->bot.y!=yb) GPC_VERTEX(cf,GPC_BELOW,GPC_LEFT,cf->xb,yb);gpc_new_tristrip(&tlist,cf,cf->xb,yb);}edge->outp[GPC_ABOVE]=cf->outp[GPC_ABOVE];GPC_VERTEX(edge,GPC_ABOVE,GPC_RIGHT,xb,yb);break;case GPC_ILI: gpc_new_tristrip(&tlist,edge,xb,yb);cf=edge;cft=GPC_ILI;break;case GPC_IRI: if(cft==GPC_LED){if(cf->bot.y!=yb) GPC_VERTEX(cf,GPC_BELOW,GPC_LEFT,cf->xb,yb);gpc_new_tristrip(&tlist,cf,cf->xb,yb);}GPC_VERTEX(edge,GPC_BELOW,GPC_RIGHT,xb,yb);edge->outp[GPC_ABOVE]=NULL;break;case GPC_IMX: GPC_VERTEX(edge,GPC_BELOW,GPC_LEFT,xb,yb);edge->outp[GPC_ABOVE]=NULL;cft=GPC_IMX;break;case GPC_IMM: GPC_VERTEX(edge,GPC_BELOW,GPC_LEFT,xb,yb);edge->outp[GPC_ABOVE]=cf->outp[GPC_ABOVE];if(xb!=cf->xb) GPC_VERTEX(cf,GPC_ABOVE,GPC_RIGHT,xb,yb);cf=edge;break;case GPC_EMM: GPC_VERTEX(edge,GPC_BELOW,GPC_RIGHT,xb,yb);edge->outp[GPC_ABOVE]=NULL;gpc_new_tristrip(&tlist,edge,xb,yb);cf=edge;break;case GPC_LED: if(edge->bot.y==yb) GPC_VERTEX(edge,GPC_BELOW,GPC_LEFT,xb,yb);edge->outp[GPC_ABOVE]=edge->outp[GPC_BELOW];cf=edge;cft=GPC_LED;break;case GPC_RED: edge->outp[GPC_ABOVE]=cf->outp[GPC_ABOVE];if(cft==GPC_LED){if(cf->bot.y==yb){GPC_VERTEX(edge,GPC_BELOW,GPC_RIGHT,xb,yb);}else{if(edge->bot.y==yb){GPC_VERTEX(cf,GPC_BELOW,GPC_LEFT,cf->xb,yb);GPC_VERTEX(edge,GPC_BELOW,GPC_RIGHT,xb,yb);}}}else{GPC_VERTEX(edge,GPC_BELOW,GPC_RIGHT,xb,yb);GPC_VERTEX(edge,GPC_ABOVE,GPC_RIGHT,xb,yb);}cf=NULL;break;default: break;}}}}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;if((edge->bstate[GPC_BELOW]==GPC_BUNDLE_HEAD)&&prev_edge){if(prev_edge->bstate[GPC_BELOW]==GPC_BUNDLE_TAIL){prev_edge->outp[GPC_BELOW]=edge->outp[GPC_BELOW];prev_edge->bstate[GPC_BELOW]=GPC_UNBUNDLED;if(prev_edge->prev) if(prev_edge->prev->bstate[GPC_BELOW]==GPC_BUNDLE_TAIL) prev_edge->bstate[GPC_BELOW]=GPC_BUNDLE_HEAD;}}}else{if(edge->top.y==yt) edge->xt=edge->top.x;else edge->xt=edge->bot.x+edge->dx*(yt-edge->bot.y);}}if(scanbeam<sbt_entries){gpc_build_intersection_table(&it,aet,dy);for(intersect=it;intersect;intersect=intersect->next){e0=intersect->ie[0];e1=intersect->ie[1];if((e0->bundle[GPC_ABOVE][GPC_CLIP]||e0->bundle[GPC_ABOVE][GPC_SUBJ])&&(e1->bundle[GPC_ABOVE][GPC_CLIP]||e1->bundle[GPC_ABOVE][GPC_SUBJ])){p=e0->outp[GPC_ABOVE];q=e1->outp[GPC_ABOVE];ix=intersect->point.x;iy=intersect->point.y+yb;in[GPC_CLIP]=( e0->bundle[GPC_ABOVE][GPC_CLIP]&&!e0->bside[GPC_CLIP])||( e1->bundle[GPC_ABOVE][GPC_CLIP]&&e1->bside[GPC_CLIP])||(!e0->bundle[GPC_ABOVE][GPC_CLIP]&&!e1->bundle[GPC_ABOVE][GPC_CLIP]&&e0->bside[GPC_CLIP]&&e1->bside[GPC_CLIP]);in[GPC_SUBJ]=( e0->bundle[GPC_ABOVE][GPC_SUBJ]&&!e0->bside[GPC_SUBJ])||( e1->bundle[GPC_ABOVE][GPC_SUBJ]&&e1->bside[GPC_SUBJ])||(!e0->bundle[GPC_ABOVE][GPC_SUBJ]&&!e1->bundle[GPC_ABOVE][GPC_SUBJ]&&e0->bside[GPC_SUBJ]&&e1->bside[GPC_SUBJ]);switch (op){case GPC_DIFF: case GPC_INT: tr=(in[GPC_CLIP])&&(in[GPC_SUBJ]);tl=(in[GPC_CLIP]^e1->bundle[GPC_ABOVE][GPC_CLIP])&&(in[GPC_SUBJ]^e1->bundle[GPC_ABOVE][GPC_SUBJ]);br=(in[GPC_CLIP]^e0->bundle[GPC_ABOVE][GPC_CLIP])&&(in[GPC_SUBJ]^e0->bundle[GPC_ABOVE][GPC_SUBJ]);bl=(in[GPC_CLIP]^e1->bundle[GPC_ABOVE][GPC_CLIP]^e0->bundle[GPC_ABOVE][GPC_CLIP])&&(in[GPC_SUBJ]^e1->bundle[GPC_ABOVE][GPC_SUBJ]^e0->bundle[GPC_ABOVE][GPC_SUBJ]);break;case GPC_XOR: tr=(in[GPC_CLIP])^(in[GPC_SUBJ]);tl=(in[GPC_CLIP]^e1->bundle[GPC_ABOVE][GPC_CLIP])^(in[GPC_SUBJ]^e1->bundle[GPC_ABOVE][GPC_SUBJ]);br=(in[GPC_CLIP]^e0->bundle[GPC_ABOVE][GPC_CLIP])^(in[GPC_SUBJ]^e0->bundle[GPC_ABOVE][GPC_SUBJ]);bl=(in[GPC_CLIP]^e1->bundle[GPC_ABOVE][GPC_CLIP]^e0->bundle[GPC_ABOVE][GPC_CLIP])^(in[GPC_SUBJ]^e1->bundle[GPC_ABOVE][GPC_SUBJ]^e0->bundle[GPC_ABOVE][GPC_SUBJ]);break;case GPC_UNION: tr=(in[GPC_CLIP])||(in[GPC_SUBJ]);tl=(in[GPC_CLIP]^e1->bundle[GPC_ABOVE][GPC_CLIP])||(in[GPC_SUBJ]^e1->bundle[GPC_ABOVE][GPC_SUBJ]);br=(in[GPC_CLIP]^e0->bundle[GPC_ABOVE][GPC_CLIP])||(in[GPC_SUBJ]^e0->bundle[GPC_ABOVE][GPC_SUBJ]);bl=(in[GPC_CLIP]^e1->bundle[GPC_ABOVE][GPC_CLIP]^e0->bundle[GPC_ABOVE][GPC_CLIP])||(in[GPC_SUBJ]^e1->bundle[GPC_ABOVE][GPC_SUBJ]^e0->bundle[GPC_ABOVE][GPC_SUBJ]);break;}vclass=tr+(tl << 1)+(br << 2)+(bl << 3);switch (vclass){case GPC_EMN: gpc_new_tristrip(&tlist,e1,ix,iy);e0->outp[GPC_ABOVE]=e1->outp[GPC_ABOVE];break;case GPC_ERI: if(p){GPC_P_EDGE(prev_edge,e0,GPC_ABOVE,px,iy);GPC_VERTEX(prev_edge,GPC_ABOVE,GPC_LEFT,px,iy);GPC_VERTEX(e0,GPC_ABOVE,GPC_RIGHT,ix,iy);e1->outp[GPC_ABOVE]=e0->outp[GPC_ABOVE];e0->outp[GPC_ABOVE]=NULL;}break;case GPC_ELI: if(q){GPC_N_EDGE(next_edge,e1,GPC_ABOVE,nx,iy);GPC_VERTEX(e1,GPC_ABOVE,GPC_LEFT,ix,iy);GPC_VERTEX(next_edge,GPC_ABOVE,GPC_RIGHT,nx,iy);e0->outp[GPC_ABOVE]=e1->outp[GPC_ABOVE];e1->outp[GPC_ABOVE]=NULL;}break;case GPC_EMX: if(p&&q){GPC_VERTEX(e0,GPC_ABOVE,GPC_LEFT,ix,iy);e0->outp[GPC_ABOVE]=NULL;e1->outp[GPC_ABOVE]=NULL;}break;case GPC_IMN: GPC_P_EDGE(prev_edge,e0,GPC_ABOVE,px,iy);GPC_VERTEX(prev_edge,GPC_ABOVE,GPC_LEFT,px,iy);GPC_N_EDGE(next_edge,e1,GPC_ABOVE,nx,iy);GPC_VERTEX(next_edge,GPC_ABOVE,GPC_RIGHT,nx,iy);gpc_new_tristrip(&tlist,prev_edge,px,iy); e1->outp[GPC_ABOVE]=prev_edge->outp[GPC_ABOVE];GPC_VERTEX(e1,GPC_ABOVE,GPC_RIGHT,ix,iy);gpc_new_tristrip(&tlist,e0,ix,iy);next_edge->outp[GPC_ABOVE]=e0->outp[GPC_ABOVE];GPC_VERTEX(next_edge,GPC_ABOVE,GPC_RIGHT,nx,iy);break;case GPC_ILI: if(p){GPC_VERTEX(e0,GPC_ABOVE,GPC_LEFT,ix,iy);GPC_N_EDGE(next_edge,e1,GPC_ABOVE,nx,iy);GPC_VERTEX(next_edge,GPC_ABOVE,GPC_RIGHT,nx,iy);e1->outp[GPC_ABOVE]=e0->outp[GPC_ABOVE];e0->outp[GPC_ABOVE]=NULL;}break;case GPC_IRI: if(q){GPC_VERTEX(e1,GPC_ABOVE,GPC_RIGHT,ix,iy);GPC_P_EDGE(prev_edge,e0,GPC_ABOVE,px,iy);GPC_VERTEX(prev_edge,GPC_ABOVE,GPC_LEFT,px,iy);e0->outp[GPC_ABOVE]=e1->outp[GPC_ABOVE];e1->outp[GPC_ABOVE]=NULL;}break;case GPC_IMX: if(p&&q){GPC_VERTEX(e0,GPC_ABOVE,GPC_RIGHT,ix,iy);GPC_VERTEX(e1,GPC_ABOVE,GPC_LEFT,ix,iy);e0->outp[GPC_ABOVE]=NULL;e1->outp[GPC_ABOVE]=NULL;GPC_P_EDGE(prev_edge,e0,GPC_ABOVE,px,iy);GPC_VERTEX(prev_edge,GPC_ABOVE,GPC_LEFT,px,iy);gpc_new_tristrip(&tlist,prev_edge,px,iy);GPC_N_EDGE(next_edge,e1,GPC_ABOVE,nx,iy);GPC_VERTEX(next_edge,GPC_ABOVE,GPC_RIGHT,nx,iy);next_edge->outp[GPC_ABOVE]=prev_edge->outp[GPC_ABOVE];GPC_VERTEX(next_edge,GPC_ABOVE,GPC_RIGHT,nx,iy);}break;case GPC_IMM: if(p&&q){GPC_VERTEX(e0,GPC_ABOVE,GPC_RIGHT,ix,iy);GPC_VERTEX(e1,GPC_ABOVE,GPC_LEFT,ix,iy);GPC_P_EDGE(prev_edge,e0,GPC_ABOVE,px,iy);GPC_VERTEX(prev_edge,GPC_ABOVE,GPC_LEFT,px,iy);gpc_new_tristrip(&tlist,prev_edge,px,iy);GPC_N_EDGE(next_edge,e1,GPC_ABOVE,nx,iy);GPC_VERTEX(next_edge,GPC_ABOVE,GPC_RIGHT,nx,iy);e1->outp[GPC_ABOVE]=prev_edge->outp[GPC_ABOVE];GPC_VERTEX(e1,GPC_ABOVE,GPC_RIGHT,ix,iy);gpc_new_tristrip(&tlist,e0,ix,iy);next_edge->outp[GPC_ABOVE]=e0->outp[GPC_ABOVE];GPC_VERTEX(next_edge,GPC_ABOVE,GPC_RIGHT,nx,iy);}break;case GPC_EMM: if(p&&q){GPC_VERTEX(e0,GPC_ABOVE,GPC_LEFT,ix,iy);gpc_new_tristrip(&tlist,e1,ix,iy);e0->outp[GPC_ABOVE]=e1->outp[GPC_ABOVE];}break;default: break;}}if(e0->bundle[GPC_ABOVE][GPC_CLIP]) e1->bside[GPC_CLIP]=!e1->bside[GPC_CLIP];if(e1->bundle[GPC_ABOVE][GPC_CLIP]) e0->bside[GPC_CLIP]=!e0->bside[GPC_CLIP];if(e0->bundle[GPC_ABOVE][GPC_SUBJ]) e1->bside[GPC_SUBJ]=!e1->bside[GPC_SUBJ];if(e1->bundle[GPC_ABOVE][GPC_SUBJ]) e0->bside[GPC_SUBJ]=!e0->bside[GPC_SUBJ];prev_edge=e0->prev;next_edge=e1->next;if(e1->next) e1->next->prev=e0;if(e0->bstate[GPC_ABOVE]==GPC_BUNDLE_HEAD){search=GPC_TRUE;while(search){prev_edge=prev_edge->prev;if(prev_edge){if(prev_edge->bundle[GPC_ABOVE][GPC_CLIP]||prev_edge->bundle[GPC_ABOVE][GPC_SUBJ]||(prev_edge->bstate[GPC_ABOVE]==GPC_BUNDLE_HEAD)) search=GPC_FALSE;}else search=GPC_FALSE;}}if(!prev_edge){e1->next=aet;aet=e0->next;}else{e1->next=prev_edge->next;prev_edge->next=e0->next;}e0->next->prev=prev_edge;e1->next->prev=e1;e0->next=next_edge;}for(edge=aet;edge;edge=next_edge){next_edge=edge->next;succ_edge=edge->succ;if((edge->top.y==yt)&&succ_edge){succ_edge->outp[GPC_BELOW]=edge->outp[GPC_ABOVE];succ_edge->bstate[GPC_BELOW]=edge->bstate[GPC_ABOVE];succ_edge->bundle[GPC_BELOW][GPC_CLIP]=edge->bundle[GPC_ABOVE][GPC_CLIP];succ_edge->bundle[GPC_BELOW][GPC_SUBJ]=edge->bundle[GPC_ABOVE][GPC_SUBJ];prev_edge=edge->prev;if(prev_edge) prev_edge->next=succ_edge;else aet=succ_edge;if(next_edge) next_edge->prev=succ_edge;succ_edge->prev=prev_edge;succ_edge->next=next_edge;}else{edge->outp[GPC_BELOW]=edge->outp[GPC_ABOVE];edge->bstate[GPC_BELOW]=edge->bstate[GPC_ABOVE];edge->bundle[GPC_BELOW][GPC_CLIP]=edge->bundle[GPC_ABOVE][GPC_CLIP];edge->bundle[GPC_BELOW][GPC_SUBJ]=edge->bundle[GPC_ABOVE][GPC_SUBJ];edge->xb=edge->xt;}edge->outp[GPC_ABOVE]=NULL;}}}result->strip=NULL;result->num_strips=gpc_count_tristrips(tlist);if(result->num_strips>0){GPC_MALLOC(result->strip,result->num_strips*sizeof(gpc_vertex_list),"tristrip list creation",gpc_vertex_list);s=0;for(tn=tlist;tn;tn=tnn){tnn=tn->next;if(tn->active>2){result->strip[s].num_vertices=tn->active;GPC_MALLOC(result->strip[s].vertex,tn->active*sizeof(gpc_vertex),"tristrip creation",gpc_vertex);v=0;if(GPC_INVERT_TRISTRIPS){lt=tn->v[GPC_RIGHT];rt=tn->v[GPC_LEFT];}else{lt=tn->v[GPC_LEFT];rt=tn->v[GPC_RIGHT];}while(lt||rt){if(lt){ltn=lt->next;result->strip[s].vertex[v].x=lt->x;result->strip[s].vertex[v].y=lt->y;v++;GPC_FREE(lt);lt=ltn;}if(rt){rtn=rt->next;result->strip[s].vertex[v].x=rt->x;result->strip[s].vertex[v].y=rt->y;v++;GPC_FREE(rt);rt=rtn;}}s++;}else{for(lt=tn->v[GPC_LEFT];lt;lt=ltn){ltn=lt->next;GPC_FREE(lt);}for(rt=tn->v[GPC_RIGHT];rt;rt=rtn){rtn=rt->next;GPC_FREE(rt);}}GPC_FREE(tn);}}gpc_reset_it(&it);gpc_reset_lmt(&lmt);GPC_FREE(c_heap);GPC_FREE(s_heap);GPC_FREE(sbt);}
  35. #endif
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!