📄 polygon_intersection_gpc.cpp
字号:
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:
case IMN:
add_local_min(&out_poly, edge, xb, yb);
px= xb;
cf= edge->outp[ABOVE];
break;
case ERI:
if (xb != px)
{
add_right(cf, xb, yb);
px= xb;
}
edge->outp[ABOVE]= cf;
cf= NULL;
break;
case ELI:
add_left(edge->outp[BELOW], xb, yb);
px= xb;
cf= edge->outp[BELOW];
break;
case EMX:
if (xb != px)
{
add_left(cf, xb, yb);
px= xb;
}
merge_right(cf, edge->outp[BELOW], out_poly);
cf= NULL;
break;
case ILI:
if (xb != px)
{
add_left(cf, xb, yb);
px= xb;
}
edge->outp[ABOVE]= cf;
cf= NULL;
break;
case IRI:
add_right(edge->outp[BELOW], xb, yb);
px= xb;
cf= edge->outp[BELOW];
edge->outp[BELOW]= NULL;
break;
case IMX:
if (xb != px)
{
add_right(cf, xb, yb);
px= xb;
}
merge_left(cf, edge->outp[BELOW], out_poly);
cf= NULL;
edge->outp[BELOW]= NULL;
break;
case IMM:
if (xb != px)
{
add_right(cf, xb, yb);
px= xb;
}
merge_left(cf, edge->outp[BELOW], out_poly);
edge->outp[BELOW]= NULL;
add_local_min(&out_poly, edge, xb, yb);
cf= edge->outp[ABOVE];
break;
case EMM:
if (xb != px)
{
add_left(cf, xb, yb);
px= xb;
}
merge_right(cf, edge->outp[BELOW], out_poly);
edge->outp[BELOW]= NULL;
add_local_min(&out_poly, edge, xb, yb);
cf= edge->outp[ABOVE];
break;
case LED:
if (edge->bot.y == yb)
add_left(edge->outp[BELOW], xb, yb);
edge->outp[ABOVE]= edge->outp[BELOW];
px= xb;
break;
case RED:
if (edge->bot.y == yb)
add_right(edge->outp[BELOW], xb, yb);
edge->outp[ABOVE]= edge->outp[BELOW];
px= xb;
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];
prev_edge->bstate[BELOW]= UNBUNDLED;
if (prev_edge->prev)
if (prev_edge->prev->bstate[BELOW] == BUNDLE_TAIL)
prev_edge->bstate[BELOW]= 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)
{
/* === SCANBEAM INTERIOR PROCESSING ============================== */
build_intersection_table(&it, aet, dy);
/* Process each node in the intersection table */
for (intersect= it; intersect; intersect= intersect->next)
{
e0= intersect->ie[0];
e1= intersect->ie[1];
/* Only generate output for contributing intersections */
if ((e0->bundle[ABOVE][CLIP] || e0->bundle[ABOVE][SUBJ])
&& (e1->bundle[ABOVE][CLIP] || e1->bundle[ABOVE][SUBJ]))
{
p= e0->outp[ABOVE];
q= e1->outp[ABOVE];
ix= intersect->point.x;
iy= intersect->point.y + yb;
in[CLIP]= ( e0->bundle[ABOVE][CLIP] && !e0->bside[CLIP])
|| ( e1->bundle[ABOVE][CLIP] && e1->bside[CLIP])
|| (!e0->bundle[ABOVE][CLIP] && !e1->bundle[ABOVE][CLIP]
&& e0->bside[CLIP] && e1->bside[CLIP]);
in[SUBJ]= ( e0->bundle[ABOVE][SUBJ] && !e0->bside[SUBJ])
|| ( e1->bundle[ABOVE][SUBJ] && e1->bside[SUBJ])
|| (!e0->bundle[ABOVE][SUBJ] && !e1->bundle[ABOVE][SUBJ]
&& e0->bside[SUBJ] && e1->bside[SUBJ]);
/* Determine quadrant occupancies */
switch (op)
{
case GPC_DIFF:
case GPC_INT:
tr= (in[CLIP])
&& (in[SUBJ]);
tl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP])
&& (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ]);
br= (in[CLIP] ^ e0->bundle[ABOVE][CLIP])
&& (in[SUBJ] ^ e0->bundle[ABOVE][SUBJ]);
bl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP] ^ e0->bundle[ABOVE][CLIP])
&& (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ] ^ e0->bundle[ABOVE][SUBJ]);
break;
case GPC_XOR:
tr= (in[CLIP])
^ (in[SUBJ]);
tl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP])
^ (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ]);
br= (in[CLIP] ^ e0->bundle[ABOVE][CLIP])
^ (in[SUBJ] ^ e0->bundle[ABOVE][SUBJ]);
bl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP] ^ e0->bundle[ABOVE][CLIP])
^ (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ] ^ e0->bundle[ABOVE][SUBJ]);
break;
case GPC_UNION:
tr= (in[CLIP])
|| (in[SUBJ]);
tl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP])
|| (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ]);
br= (in[CLIP] ^ e0->bundle[ABOVE][CLIP])
|| (in[SUBJ] ^ e0->bundle[ABOVE][SUBJ]);
bl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP] ^ e0->bundle[ABOVE][CLIP])
|| (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ] ^ e0->bundle[ABOVE][SUBJ]);
break;
}
vclass= tr + (tl << 1) + (br << 2) + (bl << 3);
switch (vclass)
{
case EMN:
add_local_min(&out_poly, e0, ix, iy);
e1->outp[ABOVE]= e0->outp[ABOVE];
break;
case ERI:
if (p)
{
add_right(p, ix, iy);
e1->outp[ABOVE]= p;
e0->outp[ABOVE]= NULL;
}
break;
case ELI:
if (q)
{
add_left(q, ix, iy);
e0->outp[ABOVE]= q;
e1->outp[ABOVE]= NULL;
}
break;
case EMX:
if (p && q)
{
add_left(p, ix, iy);
merge_right(p, q, out_poly);
e0->outp[ABOVE]= NULL;
e1->outp[ABOVE]= NULL;
}
break;
case IMN:
add_local_min(&out_poly, e0, ix, iy);
e1->outp[ABOVE]= e0->outp[ABOVE];
break;
case ILI:
if (p)
{
add_left(p, ix, iy);
e1->outp[ABOVE]= p;
e0->outp[ABOVE]= NULL;
}
break;
case IRI:
if (q)
{
add_right(q, ix, iy);
e0->outp[ABOVE]= q;
e1->outp[ABOVE]= NULL;
}
break;
case IMX:
if (p && q)
{
add_right(p, ix, iy);
merge_left(p, q, out_poly);
e0->outp[ABOVE]= NULL;
e1->outp[ABOVE]= NULL;
}
break;
case IMM:
if (p && q)
{
add_right(p, ix, iy);
merge_left(p, q, out_poly);
add_local_min(&out_poly, e0, ix, iy);
e1->outp[ABOVE]= e0->outp[ABOVE];
}
break;
case EMM:
if (p && q)
{
add_left(p, ix, iy);
merge_right(p, q, out_poly);
add_local_min(&out_poly, e0, ix, iy);
e1->outp[ABOVE]= e0->outp[ABOVE];
}
break;
default:
break;
} /* End of switch */
} /* End of contributing intersection conditional */
/* Swap bundle sides in response to edge crossing */
if (e0->bundle[ABOVE][CLIP])
e1->bside[CLIP]= !e1->bside[CLIP];
if (e1->bundle[ABOVE][CLIP])
e0->bside[CLIP]= !e0->bside[CLIP];
if (e0->bundle[ABOVE][SUBJ])
e1->bside[SUBJ]= !e1->bside[SUBJ];
if (e1->bundle[ABOVE][SUBJ])
e0->bside[SUBJ]= !e0->bside[SUBJ];
/* Swap e0 and e1 bundles in the AET */
prev_edge= e0->prev;
next_edge= e1->next;
if (next_edge)
next_edge->prev= e0;
if (e0->bstate[ABOVE] == BUNDLE_HEAD)
{
search= TRUE;
while (search)
{
prev_edge= prev_edge->prev;
if (prev_edge)
{
if (prev_edge->bstate[ABOVE] != BUNDLE_TAIL)
search= FALSE;
}
else
search= 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;
} /* End of IT loop*/
/* Prepare for next scanbeam */
for (edge= aet; edge; edge= next_edge)
{
next_edge= edge->next;
succ_edge= edge->succ;
if ((edge->top.y == yt) && succ_edge)
{
/* Replace AET edge by its successor */
succ_edge->outp[BELOW]= edge->outp[ABOVE];
succ_edge->bstate[BELOW]= edge->bstate[ABOVE];
succ_edge->bundle[BELOW][CLIP]= edge->bundle[ABOVE][CLIP];
succ_edge->bundle[BELOW][SUBJ]= edge->bundle[ABOVE][SUBJ];
prev_edge= edge->prev;
if (prev_edge)
prev_edge->next= succ_edge;
else
aet= succ_edge;
if (next_edge)
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -