📄 chtrconstr.cpp
字号:
i1 = newnode(); /* Upper trapezoid sink */
i2 = newnode(); /* Lower trapezoid sink */
sk = tr[tu].sink;
qs[sk].nodetype = T_Y;
qs[sk].yval = s.v1;
qs[sk].segnum = segnum; /* not really reqd ... maybe later */
qs[sk].left = i2;
qs[sk].right = i1;
qs[i1].nodetype = T_SINK;
qs[i1].trnum = tu;
qs[i1].parent = sk;
qs[i2].nodetype = T_SINK;
qs[i2].trnum = tl;
qs[i2].parent = sk;
tr[tu].sink = i1;
tr[tl].sink = i2;
tlast = tu;
}
else /* v1 already present */
{ /* Get the lowermost intersecting trapezoid */
vper.x = s.v1.x + EPS * (s.v0.x - s.v1.x);
vper.y = s.v1.y + EPS * (s.v0.y - s.v1.y);
tlast = locate_endpoint(&s.v1, &s.v0, s.root1);
tribot = 1;
}
/* Thread the segment into the query tree creating a new X-node */
/* First, split all the trapezoids which are intersected by s into */
/* two */
t = tfirst; /* topmost trapezoid */
while ((t > 0) &&
_greater_than_equal_to(&tr[t].lo, &tr[tlast].lo))
/* traverse from top to bot */
{
int t_sav, tn_sav;
sk = tr[t].sink;
i1 = newnode(); /* left trapezoid sink */
i2 = newnode(); /* right trapezoid sink */
qs[sk].nodetype = T_X;
qs[sk].segnum = segnum;
qs[sk].left = i1;
qs[sk].right = i2;
qs[i1].nodetype = T_SINK; /* left trapezoid (use existing one) */
qs[i1].trnum = t;
qs[i1].parent = sk;
qs[i2].nodetype = T_SINK; /* right trapezoid (allocate new) */
qs[i2].trnum = tn = newtrap();
tr[tn].state = ST_VALID;
qs[i2].parent = sk;
if (t == tfirst)
tfirstr = tn;
if (_equal_to(&tr[t].lo, &tr[tlast].lo))
tlastr = tn;
tr[tn] = tr[t];
tr[t].sink = i1;
tr[tn].sink = i2;
t_sav = t;
tn_sav = tn;
/* error */
if ((tr[t].d0 <= 0) && (tr[t].d1 <= 0)) /* case cannot arise */
{
TRACE( "add_segment: error\n");
throw CH_EX_TRIANGULATION;
break;
}
/* only one trapezoid below. partition t into two and make the */
/* two resulting trapezoids t and tn as the upper neighbours of */
/* the sole lower trapezoid */
else if ((tr[t].d0 > 0) && (tr[t].d1 <= 0))
{ /* Only one trapezoid below */
if ((tr[t].u0 > 0) && (tr[t].u1 > 0))
{ /* continuation of a chain from abv. */
if (tr[t].usave > 0) /* three upper neighbours */
{
if (tr[t].uside == S_LEFT)
{
tr[tn].u0 = tr[t].u1;
tr[t].u1 = -1;
tr[tn].u1 = tr[t].usave;
tr[tr[t].u0].d0 = t;
tr[tr[tn].u0].d0 = tn;
tr[tr[tn].u1].d0 = tn;
}
else /* intersects in the right */
{
tr[tn].u1 = -1;
tr[tn].u0 = tr[t].u1;
tr[t].u1 = tr[t].u0;
tr[t].u0 = tr[t].usave;
tr[tr[t].u0].d0 = t;
tr[tr[t].u1].d0 = t;
tr[tr[tn].u0].d0 = tn;
}
tr[t].usave = tr[tn].usave = 0;
}
else /* No usave.... simple case */
{
tr[tn].u0 = tr[t].u1;
tr[t].u1 = tr[tn].u1 = -1;
tr[tr[tn].u0].d0 = tn;
}
}
else
{ /* fresh seg. or upward cusp */
int tmp_u = tr[t].u0;
int td0, td1;
if (((td0 = tr[tmp_u].d0) > 0) &&
((td1 = tr[tmp_u].d1) > 0))
{ /* upward cusp */
if ((tr[td0].rseg > 0) &&
!is_left_of(tr[td0].rseg, &s.v1))
{
tr[t].u0 = tr[t].u1 = tr[tn].u1 = -1;
tr[tr[tn].u0].d1 = tn;
}
else /* cusp going leftwards */
{
tr[tn].u0 = tr[tn].u1 = tr[t].u1 = -1;
tr[tr[t].u0].d0 = t;
}
}
else /* fresh segment */
{
tr[tr[t].u0].d0 = t;
tr[tr[t].u0].d1 = tn;
}
}
if (FP_EQUAL(tr[t].lo.y, tr[tlast].lo.y) &&
FP_EQUAL(tr[t].lo.x, tr[tlast].lo.x) && tribot)
{ /* bottom forms a triangle */
if (is_swapped)
{
tmptriseg = segnum - 1;
if (tmptriseg == 0)
tmptriseg = global.nseg;
}
else
tmptriseg = MODULO_NEXT(segnum + 1, global.nseg);
if ((tmptriseg > 0) && is_left_of(tmptriseg, &s.v0))
{
/* L-R downward cusp */
tr[tr[t].d0].u0 = t;
tr[tn].d0 = tr[tn].d1 = -1;
}
else
{
/* R-L downward cusp */
tr[tr[tn].d0].u1 = tn;
tr[t].d0 = tr[t].d1 = -1;
}
}
else
{
if ((tr[tr[t].d0].u0 > 0) && (tr[tr[t].d0].u1 > 0))
{
if (tr[tr[t].d0].u0 == t) /* passes thru LHS */
{
tr[tr[t].d0].usave = tr[tr[t].d0].u1;
tr[tr[t].d0].uside = S_LEFT;
}
else
{
tr[tr[t].d0].usave = tr[tr[t].d0].u0;
tr[tr[t].d0].uside = S_RIGHT;
}
}
tr[tr[t].d0].u0 = t;
tr[tr[t].d0].u1 = tn;
}
t = tr[t].d0;
}
else if ((tr[t].d0 <= 0) && (tr[t].d1 > 0))
{ /* Only one trapezoid below */
if ((tr[t].u0 > 0) && (tr[t].u1 > 0))
{ /* continuation of a chain from abv. */
if (tr[t].usave > 0) /* three upper neighbours */
{
if (tr[t].uside == S_LEFT)
{
tr[tn].u0 = tr[t].u1;
tr[t].u1 = -1;
tr[tn].u1 = tr[t].usave;
tr[tr[t].u0].d0 = t;
tr[tr[tn].u0].d0 = tn;
tr[tr[tn].u1].d0 = tn;
}
else /* intersects in the right */
{
tr[tn].u1 = -1;
tr[tn].u0 = tr[t].u1;
tr[t].u1 = tr[t].u0;
tr[t].u0 = tr[t].usave;
tr[tr[t].u0].d0 = t;
tr[tr[t].u1].d0 = t;
tr[tr[tn].u0].d0 = tn;
}
tr[t].usave = tr[tn].usave = 0;
}
else /* No usave.... simple case */
{
tr[tn].u0 = tr[t].u1;
tr[t].u1 = tr[tn].u1 = -1;
tr[tr[tn].u0].d0 = tn;
}
}
else
{ /* fresh seg. or upward cusp */
int tmp_u = tr[t].u0;
int td0, td1;
if (((td0 = tr[tmp_u].d0) > 0) &&
((td1 = tr[tmp_u].d1) > 0))
{ /* upward cusp */
if ((tr[td0].rseg > 0) &&
!is_left_of(tr[td0].rseg, &s.v1))
{
tr[t].u0 = tr[t].u1 = tr[tn].u1 = -1;
tr[tr[tn].u0].d1 = tn;
}
else
{
tr[tn].u0 = tr[tn].u1 = tr[t].u1 = -1;
tr[tr[t].u0].d0 = t;
}
}
else /* fresh segment */
{
tr[tr[t].u0].d0 = t;
tr[tr[t].u0].d1 = tn;
}
}
if (FP_EQUAL(tr[t].lo.y, tr[tlast].lo.y) &&
FP_EQUAL(tr[t].lo.x, tr[tlast].lo.x) && tribot)
{ /* bottom forms a triangle */
int tmpseg;
if (is_swapped)
{
tmpseg = segnum - 1;
if (tmpseg == 0)
tmpseg = global.nseg;
}
else
tmpseg = MODULO_NEXT(segnum + 1, global.nseg);
if ((tmpseg > 0) && is_left_of(tmpseg, &s.v0))
{
/* L-R downward cusp */
tr[tr[t].d1].u0 = t;
tr[tn].d0 = tr[tn].d1 = -1;
}
else
{
/* R-L downward cusp */
tr[tr[tn].d1].u1 = tn;
tr[t].d0 = tr[t].d1 = -1;
}
}
else
{
if ((tr[tr[t].d1].u0 > 0) && (tr[tr[t].d1].u1 > 0))
{
if (tr[tr[t].d1].u0 == t) /* passes thru LHS */
{
tr[tr[t].d1].usave = tr[tr[t].d1].u1;
tr[tr[t].d1].uside = S_LEFT;
}
else
{
tr[tr[t].d1].usave = tr[tr[t].d1].u0;
tr[tr[t].d1].uside = S_RIGHT;
}
}
tr[tr[t].d1].u0 = t;
tr[tr[t].d1].u1 = tn;
}
t = tr[t].d1;
}
/* two trapezoids below. Find out which one is intersected by */
/* this segment and proceed down that one */
else
{
int tmpseg = tr[tr[t].d0].rseg;
double y0, yt;
point_t tmppt;
int i_d0, i_d1;
//int tnext;
i_d0 = i_d1 = FALSE;
if (FP_EQUAL(tr[t].lo.y, s.v0.y))
{
if (tr[t].lo.x > s.v0.x)
i_d0 = TRUE;
else
i_d1 = TRUE;
}
else
{
tmppt.y = y0 = tr[t].lo.y;
yt = (y0 - s.v0.y)/(s.v1.y - s.v0.y);
tmppt.x = s.v0.x + yt * (s.v1.x - s.v0.x);
if (_less_than(&tmppt, &tr[t].lo))
i_d0 = TRUE;
else
i_d1 = TRUE;
}
/* check continuity from the top so that the lower-neighbour */
/* values are properly filled for the upper trapezoid */
if ((tr[t].u0 > 0) && (tr[t].u1 > 0))
{ /* continuation of a chain from abv. */
if (tr[t].usave > 0) /* three upper neighbours */
{
if (tr[t].uside == S_LEFT)
{
tr[tn].u0 = tr[t].u1;
tr[t].u1 = -1;
tr[tn].u1 = tr[t].usave;
tr[tr[t].u0].d0 = t;
tr[tr[tn].u0].d0 = tn;
tr[tr[tn].u1].d0 = tn;
}
else /* intersects in the right */
{
tr[tn].u1 = -1;
tr[tn].u0 = tr[t].u1;
tr[t].u1 = tr[t].u0;
tr[t].u0 = tr[t].usave;
tr[tr[t].u0].d0 = t;
tr[tr[t].u1].d0 = t;
tr[tr[tn].u0].d0 = tn;
}
tr[t].usave = tr[tn].usave = 0;
}
else /* No usave.... simple case */
{
tr[tn].u0 = tr[t].u1;
tr[tn].u1 = -1;
tr[t].u1 = -1;
tr[tr[tn].u0].d0 = tn;
}
}
else
{ /* fresh seg. or upward cusp */
int tmp_u = tr[t].u0;
int td0, td1;
if (((td0 = tr[tmp_u].d0) > 0) &&
((td1 = tr[tmp_u].d1) > 0))
{ /* upward cusp */
if ((tr[td0].rseg > 0) &&
!is_left_of(tr[td0].rseg, &s.v1))
{
tr[t].u0 = tr[t].u1 = tr[tn].u1 = -1;
tr[tr[tn].u0].d1 = tn;
}
else
{
tr[tn].u0 = tr[tn].u1 = tr[t].u1 = -1;
tr[tr[t].u0].d0 = t;
}
}
else /* fresh segment */
{
tr[tr[t].u0].d0 = t;
tr[tr[t].u0].d1 = tn;
}
}
if (FP_EQUAL(tr[t].lo.y, tr[tlast].lo.y) &&
FP_EQUAL(tr[t].lo.x, tr[tlast].lo.x) && tribot)
{
/* this case arises only at the lowest trapezoid.. i.e.
tlast, if the lower endpoint of the segment is
already inserted in the structure */
tr[tr[t].d0].u0 = t;
tr[tr[t].d0].u1 = -1;
tr[tr[t].d1].u0 = tn;
tr[tr[t].d1].u1 = -1;
tr[tn].d0 = tr[t].d1;
tr[t].d1 = tr[tn].d1 = -1;
tnext = tr[t].d1;
}
else if (i_d0)
/* intersecting d0 */
{
tr[tr[t].d0].u0 = t;
tr[tr[t].d0].u1 = tn;
tr[tr[t].d1].u0 = tn;
tr[tr[t].d1].u1 = -1;
/* new code to determine the bottom neighbours of the */
/* newly partitioned trapezoid */
tr[t].d1 = -1;
tnext = tr[t].d0;
}
else /* intersecting d1 */
{
tr[tr[t].d0].u0 = t;
tr[tr[t].d0].u1 = -1;
tr[tr[t].d1].u0 = t;
tr[tr[t].d1].u1 = tn;
/* new code to determine the bottom neighbours of the */
/* newly partitioned trapezoid */
tr[tn].d0 = tr[t].d1;
tr[tn].d1 = -1;
tnext = tr[t].d1;
}
t = tnext;
}
tr[t_sav].rseg = tr[tn_sav].lseg = segnum;
} /* end-while */
/* Now combine those trapezoids which share common segments. We can */
/* use the pointers to the parent to connect these together. This */
/* works only because all these new trapezoids have been formed */
/* due to splitting by the segment, and hence have only one parent */
tfirstl = tfirst;
tlastl = tlast;
merge_trapezoids(segnum, tfirstl, tlastl, S_LEFT);
if(tfirstr == -1) throw CH_EX_TRIANGULATION;
merge_trapezoids(segnum, tfirstr, tlastr, S_RIGHT);
seg[segnum].is_inserted = TRUE;
return 0;
}
/* Update the roots stored for each of the endpoints of the segment.
* This is done to speed up the location-query for the endpoint when
* the segment is inserted into the trapezoidation subsequently
*/
int ChTriangulator::find_new_roots(int segnum)
{
segment_t *s = &seg[segnum];
point_t vper;
if (s->is_inserted)
return 0;
vper.x = s->v0.x + EPS * (s->v1.x - s->v0.x);
vper.y = s->v0.y + EPS * (s->v1.y - s->v0.y);
s->root0 = locate_endpoint(&s->v0, &s->v1, s->root0);
s->root0 = tr[s->root0].sink;
vper.x = s->v1.x + EPS * (s->v0.x - s->v1.x);
vper.y = s->v1.y + EPS * (s->v0.y - s->v1.y);
s->root1 = locate_endpoint(&s->v1, &s->v0, s->root1);
s->root1 = tr[s->root1].sink;
return 0;
}
/* Main routine to perform trapezoidation */
int ChTriangulator::construct_trapezoids(int nseg, segment_t *seg)
{
register int i;
int root, h;
q_idx = tr_idx = 1;
/* Add the first segment and get the query structure and trapezoid */
/* list initialised */
root = init_query_structure(choose_segment());
#ifdef SIMPLE /* no randomization */
for (i = 1; i <= nseg; i++)
seg[i].root0 = seg[i].root1 = root;
for (i = 2; i <= nseg; i++)
add_segment(choose_segment());
#else
for (i = 1; i <= nseg; i++)
seg[i].root0 = seg[i].root1 = root;
for (h = 1; h <= math_logstar_n(nseg); h++)
{
for (i = math_N(nseg, h -1) + 1; i <= math_N(nseg, h); i++)
add_segment(choose_segment());
/* Find a new root for each of the segment endpoints */
for (i = 1; i <= nseg; i++)
find_new_roots(i);
}
for (i = math_N(nseg, math_logstar_n(nseg)) + 1; i <= nseg; i++)
add_segment(choose_segment());
#endif
return 0;
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -