?? trmonot.cpp
字號:
traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
}
}
else
{
retval = SP_NOSPLIT; /* Just traverse all neighbours */
traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
}
}
else if ((t->u0 > 0) && (t->u1 > 0))
{
if ((t->d0 > 0) && (t->d1 > 0)) /* downward + upward cusps */
{
v0 = tr[t->d1].lseg;
v1 = tr[t->u0].rseg;
retval = SP_2UP_2DN;
if (((dir == TR_FROM_DN) && (t->d1 == from)) ||
((dir == TR_FROM_UP) && (t->u1 == from)))
{
do_switch = TRUE;
mnew = make_new_monotone_poly(mcur, v1, v0);
traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
}
else
{
mnew = make_new_monotone_poly(mcur, v0, v1);
traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
}
}
else /* only downward cusp */
{
if (_equal_to(&t->lo, &seg[t->lseg].v1))
{
v0 = tr[t->u0].rseg;
v1 = MODULO_NEXT(t->lseg + 1, global.nseg);
retval = SP_2UP_LEFT;
if ((dir == TR_FROM_UP) && (t->u0 == from))
{
do_switch = TRUE;
mnew = make_new_monotone_poly(mcur, v1, v0);
traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
}
else
{
mnew = make_new_monotone_poly(mcur, v0, v1);
traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
}
}
else
{
v0 = t->rseg;
v1 = tr[t->u0].rseg;
retval = SP_2UP_RIGHT;
if ((dir == TR_FROM_UP) && (t->u1 == from))
{
do_switch = TRUE;
mnew = make_new_monotone_poly(mcur, v1, v0);
traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
}
else
{
mnew = make_new_monotone_poly(mcur, v0, v1);
traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
}
}
}
}
else if ((t->u0 > 0) || (t->u1 > 0)) /* no downward cusp */
{
if ((t->d0 > 0) && (t->d1 > 0)) /* only upward cusp */
{
if (_equal_to(&t->hi, &seg[t->lseg].v0))
{
v0 = tr[t->d1].lseg;
v1 = t->lseg;
retval = SP_2DN_LEFT;
if (!((dir == TR_FROM_DN) && (t->d0 == from)))
{
do_switch = TRUE;
mnew = make_new_monotone_poly(mcur, v1, v0);
traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
}
else
{
mnew = make_new_monotone_poly(mcur, v0, v1);
traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
}
}
else
{
v0 = tr[t->d1].lseg;
v1 = MODULO_NEXT(t->rseg + 1, global.nseg);
retval = SP_2DN_RIGHT;
if ((dir == TR_FROM_DN) && (t->d1 == from))
{
do_switch = TRUE;
mnew = make_new_monotone_poly(mcur, v1, v0);
traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
}
else
{
mnew = make_new_monotone_poly(mcur, v0, v1);
traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
}
}
}
else /* no cusp */
{
if (_equal_to(&t->hi, &seg[t->lseg].v0) &&
_equal_to(&t->lo, &seg[t->rseg].v0))
{
v0 = t->rseg;
v1 = t->lseg;
retval = SP_SIMPLE_LRDN;
if (dir == TR_FROM_UP)
{
do_switch = TRUE;
mnew = make_new_monotone_poly(mcur, v1, v0);
traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
}
else
{
mnew = make_new_monotone_poly(mcur, v0, v1);
traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
}
}
else if (_equal_to(&t->hi, &seg[t->rseg].v1) &&
_equal_to(&t->lo, &seg[t->lseg].v1))
{
v0 = MODULO_NEXT(t->rseg + 1, global.nseg);
v1 = MODULO_NEXT(t->lseg + 1, global.nseg);
retval = SP_SIMPLE_LRUP;
if (dir == TR_FROM_UP)
{
do_switch = TRUE;
mnew = make_new_monotone_poly(mcur, v1, v0);
traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
}
else
{
mnew = make_new_monotone_poly(mcur, v0, v1);
traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
}
}
else /* no split possible */
{
retval = SP_NOSPLIT;
traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
}
}
}
return retval;
}
int triangulate_monotone_polygons(int nmonpoly, int op[][3])
{
register int i;
point_t ymax, ymin;
int p, vfirst, posmax, posmin, v;
int vcount;
#ifdef DEBUG
for (i = 0; i < nmonpoly; i++)
{
TRACE("\n\nPolygon %d: ", i);
vfirst = mchain[mon[i]].vnum;
p = mchain[mon[i]].next;
TRACE("%d ", mchain[mon[i]].vnum);
while (mchain[p].vnum != vfirst)
{
TRACE("%d ", mchain[p].vnum);
p = mchain[p].next;
}
}
TRACE("\n");
#endif
op_idx = 0;
for (i = 0; i < nmonpoly; i++)
{
vcount = 1;
vfirst = mchain[mon[i]].vnum;
ymax = ymin = vert[vfirst].pt;
posmax = posmin = mon[i];
p = mchain[mon[i]].next;
while ((v = mchain[p].vnum) != vfirst)
{
if (_greater_than(&vert[v].pt, &ymax))
{
ymax = vert[v].pt;
posmax = p;
}
if (_less_than(&vert[v].pt, &ymin))
{
ymin = vert[v].pt;
posmin = p;
}
p = mchain[p].next;
vcount++;
}
if (vcount == 3) /* already a triangle */
{
op[op_idx][0] = mchain[p].vnum;
op[op_idx][1] = mchain[mchain[p].next].vnum;
op[op_idx][2] = mchain[mchain[p].prev].vnum;
op_idx++;
}
else /* triangulate the polygon */
{
v = mchain[mchain[posmax].next].vnum;
if (_equal_to(&vert[v].pt, &ymin))
{ /* LHS is a single line */
triangulate_single_polygon(posmax, TRI_LHS, op);
}
else
triangulate_single_polygon(posmax, TRI_RHS, op);
}
}
#ifdef DEBUG
for (i = 0; i < (global.nseg - 2); i++)
TRACE("tri #%d: (%d, %d, %d)\n", i, op[i][0], op[i][1],
op[i][2]);
#endif
return 0;
}
/* A greedy corner-cutting algorithm to triangulate a y-monotone
* polygon in O(n) time.
* Joseph O-Rourke, Computational Geometry in C.
*/
int triangulate_single_polygon(int posmax, int side, int op[][3])
{
register int v;
int rc[SEGSIZE], ri = 0; /* reflex chain */
int endv, tmp, vpos;
if (side == TRI_RHS) /* RHS segment is a single segment */
{
rc[0] = mchain[posmax].vnum;
tmp = mchain[posmax].next;
rc[1] = mchain[tmp].vnum;
ri = 1;
vpos = mchain[tmp].next;
v = mchain[vpos].vnum;
if ((endv = mchain[mchain[posmax].prev].vnum) == 0)
endv = global.nseg;
}
else /* LHS is a single segment */
{
tmp = mchain[posmax].next;
rc[0] = mchain[tmp].vnum;
tmp = mchain[tmp].next;
rc[1] = mchain[tmp].vnum;
ri = 1;
vpos = mchain[tmp].next;
v = mchain[vpos].vnum;
endv = mchain[posmax].vnum;
}
while ((v != endv) || (ri > 1))
{
if (ri > 0) /* reflex chain is non-empty */
{
if (CROSS(vert[v].pt, vert[rc[ri - 1]].pt,
vert[rc[ri]].pt) > 0)
{ /* convex corner: cut if off */
op[op_idx][0] = rc[ri - 1];
op[op_idx][1] = rc[ri];
op[op_idx][2] = v;
op_idx++;
ri--;
}
else /* non-convex */
{ /* add v to the chain */
ri++;
rc[ri] = v;
vpos = mchain[vpos].next;
v = mchain[vpos].vnum;
}
}
else /* reflex-chain empty: add v to the */
{ /* reflex chain and advance it */
rc[++ri] = v;
vpos = mchain[vpos].next;
v = mchain[vpos].vnum;
}
} /* end-while */
/* reached the bottom vertex. Add in the triangle formed */
op[op_idx][0] = rc[ri - 1];
op[op_idx][1] = rc[ri];
op[op_idx][2] = v;
op_idx++;
ri--;
return 0;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -