39 int index = (int)_vertices.size();
40 _vertices.push_back(point);
64 _polygon.push_back(index);
72 _holes.push_back(vector_int());
84 nassertv(!_holes.empty());
85 _holes.back().push_back(index);
98 cleanup_polygon_indices(_polygon);
100 for (hi = _holes.begin(); hi != _holes.end(); ++hi) {
101 cleanup_polygon_indices(*hi);
104 if (_polygon.size() < 3) {
111 seg.push_back(segment_t());
112 make_segment(_polygon,
true);
114 for (hi = _holes.begin(); hi != _holes.end(); ++hi) {
115 if ((*hi).size() >= 3) {
116 make_segment(*hi,
false);
121 int num_segments = (int)seg.size() - 1;
122 permute.reserve(num_segments);
124 for (i = 0; i < num_segments; ++i) {
125 permute.push_back(i + 1);
153 while (construct_trapezoids(num_segments) != 0) {
156 for (i = 0; i < num_segments; ++i) {
158 nassertv(j >= 0 && j < num_segments);
160 permute[i] = permute[j];
186 int nmonpoly = monotonate_trapezoids(num_segments);
190 triangulate_monotone_polygons(num_segments, nmonpoly);
207 return _result.size();
219 nassertr(n >= 0 && n < (
int)_result.size(), -1);
220 return _result[n]._v0;
232 nassertr(n >= 0 && n < (
int)_result.size(), -1);
233 return _result[n]._v1;
245 nassertr(n >= 0 && n < (
int)_result.size(), -1);
246 return _result[n]._v2;
253 cleanup_polygon_indices(vector_int &polygon) {
256 while (pi < polygon.size()) {
257 if (polygon[pi] >= 0 && (
size_t)polygon[pi] < _vertices.size()) {
262 polygon.erase(polygon.begin() + pi);
268 while (pi < polygon.size()) {
269 if (_vertices[polygon[pi]] != _vertices[polygon[pi - 1]]) {
274 polygon.erase(polygon.begin() + pi);
278 if (polygon.size() > 1 && _vertices[polygon.back()] == _vertices[polygon.front()]) {
284 while (polygon.size() >= 3) {
285 bool removed_any =
false;
287 int prevprev = polygon[polygon.size() - 2];
288 int prev = polygon[polygon.size() - 1];
290 for (
size_t i = 0; i < polygon.size(); ++i) {
291 int cur = polygon[i];
292 if (_vertices[prevprev] == _vertices[cur]) {
295 polygon.erase(polygon.begin() + i);
299 polygon.erase(polygon.begin() + i - 1);
329 #define REALLY_BIG 1<<30
345 #define SP_SIMPLE_LRUP 1
346 #define SP_SIMPLE_LRDN 2
348 #define SP_2UP_LEFT 4
349 #define SP_2UP_RIGHT 5
350 #define SP_2DN_LEFT 6
351 #define SP_2DN_RIGHT 7
352 #define SP_NOSPLIT -1
361 #define CROSS(v0, v1, v2) (((v1).x - (v0).x)*((v2).y - (v0).y) - \
362 ((v1).y - (v0).y)*((v2).x - (v0).x))
364 #define DOT(v0, v1) ((v0).x * (v1).x + (v0).y * (v1).y)
366 #define FP_EQUAL(s, t) (fabs(s - t) <= C_EPS)
369 #define CROSS_SINE(v0, v1) ((v0).x * (v1).y - (v1).x * (v0).y)
370 #define LENGTH(v0) (sqrt((v0).x * (v0).x + (v0).y * (v0).y))
378 check_left_winding(
const vector_int &range)
const {
383 size_t j = range.size() - 1;
384 for (
size_t i = 0; i < range.size(); ++i) {
385 const LPoint2d &p0 = _vertices[range[j]];
386 const LPoint2d &p1 = _vertices[range[i]];
387 area += p0[0] * p1[1] - p0[1] * p1[0];
400 make_segment(
const vector_int &range,
bool want_left_winding) {
401 int num_points = (int)range.size();
402 nassertv(num_points >= 2);
404 int first = (int)seg.size();
405 int last = first + num_points - 1;
407 if (want_left_winding == check_left_winding(range)) {
409 int first = (int)seg.size();
410 int last = first + num_points - 1;
412 seg.push_back(segment_t(
this, range[0], range[1],
415 for (
int i = 1; i < num_points - 1; ++i) {
416 seg.push_back(segment_t(
this, range[i], range[i + 1],
417 first + i - 1, first + i + 1));
420 seg.push_back(segment_t(
this, range[num_points - 1], range[0],
425 seg.push_back(segment_t(
this, range[0], range[num_points - 1],
428 for (
int i = 1; i < num_points - 1; ++i) {
429 seg.push_back(segment_t(
this, range[num_points - i], range[num_points - i - 1],
430 first + i - 1, first + i + 1));
433 seg.push_back(segment_t(
this, range[1], range[0],
443 nassertr(choose_idx < (
int)permute.size(), 0);
447 return permute[choose_idx++];
450 double Triangulator::
451 math_log2(
double v) {
452 static const double log2 = log(2.0);
453 return log(v) / log2;
458 math_logstar_n(
int n) {
462 for (i = 0, v = (
double) n; v >= 1; i++)
470 math_N(
int n,
int h) {
474 for (i = 0, v = (
int) n; i < h; i++)
477 return (
int) ceil((
double) 1.0*n/v);
482 int Triangulator::newnode() {
483 int index = (int)qs.size();
484 qs.push_back(node_t());
490 int Triangulator::newtrap() {
491 int tr_idx = (int)tr.size();
492 tr.push_back(trap_t());
493 tr[tr_idx].lseg = -1;
494 tr[tr_idx].rseg = -1;
495 tr[tr_idx].state = ST_VALID;
502 int Triangulator::_max(point_t *yval, point_t *v0, point_t *v1) {
503 if (v0->y > v1->y + C_EPS)
505 else if (FP_EQUAL(v0->y, v1->y))
507 if (v0->x > v1->x + C_EPS)
520 int Triangulator::_min(point_t *yval, point_t *v0, point_t *v1) {
521 if (v0->y < v1->y - C_EPS)
523 else if (FP_EQUAL(v0->y, v1->y))
538 _greater_than(point_t *v0, point_t *v1) {
539 if (v0->y > v1->y + C_EPS)
541 else if (v0->y < v1->y - C_EPS)
544 return (v0->x > v1->x);
549 _equal_to(point_t *v0, point_t *v1) {
550 return (FP_EQUAL(v0->y, v1->y) && FP_EQUAL(v0->x, v1->x));
554 _greater_than_equal_to(point_t *v0, point_t *v1) {
555 if (v0->y > v1->y + C_EPS)
557 else if (v0->y < v1->y - C_EPS)
560 return (v0->x >= v1->x);
564 _less_than(point_t *v0, point_t *v1) {
565 if (v0->y < v1->y - C_EPS)
567 else if (v0->y > v1->y + C_EPS)
570 return (v0->x < v1->x);
588 init_query_structure(
int segnum) {
589 int i1, i2, i3, i4, i5, i6, i7, root;
591 segment_t *s = &seg[segnum];
597 tr.push_back(trap_t());
598 qs.push_back(node_t());
601 qs[i1].nodetype = T_Y;
602 _max(&qs[i1].yval, &s->v0, &s->v1);
607 qs[i2].nodetype = T_SINK;
613 qs[i3].nodetype = T_Y;
614 _min(&qs[i3].yval, &s->v0, &s->v1);
619 qs[i4].nodetype = T_SINK;
624 qs[i5].nodetype = T_X;
625 qs[i5].segnum = segnum;
630 qs[i6].nodetype = T_SINK;
635 qs[i7].nodetype = T_SINK;
643 tr[t4].lo = qs[i1].yval;
644 tr[t2].hi = qs[i1].yval;
645 tr[t1].hi = qs[i1].yval;
646 tr[t3].hi = qs[i3].yval;
647 tr[t2].lo = qs[i3].yval;
648 tr[t1].lo = qs[i3].yval;
649 tr[t4].hi.y = (double) (REALLY_BIG);
650 tr[t4].hi.x = (double) (REALLY_BIG);
651 tr[t3].lo.y = (double) -1* (REALLY_BIG);
652 tr[t3].lo.x = (double) -1* (REALLY_BIG);
653 tr[t2].lseg = segnum;
654 tr[t1].rseg = segnum;
669 tr[t2].state = ST_VALID;
670 tr[t1].state = ST_VALID;
671 tr[t4].state = ST_VALID;
672 tr[t3].state = ST_VALID;
679 s->is_inserted =
true;
690 is_left_of(
int segnum, point_t *v) {
691 segment_t *s = &seg[segnum];
694 if (_greater_than(&s->v1, &s->v0))
696 if (FP_EQUAL(s->v1.y, v->y))
703 else if (FP_EQUAL(s->v0.y, v->y))
711 area = CROSS(s->v0, s->v1, (*v));
715 if (FP_EQUAL(s->v1.y, v->y))
722 else if (FP_EQUAL(s->v0.y, v->y))
730 area = CROSS(s->v1, s->v0, (*v));
746 inserted(
int segnum,
int whichpt) {
747 if (whichpt == FIRSTPT)
748 return seg[seg[segnum].prev].is_inserted;
750 return seg[seg[segnum].next].is_inserted;
758 locate_endpoint(point_t *v, point_t *vo,
int r) {
761 node_t *rptr = &qs[r];
763 switch (rptr->nodetype)
769 if (_greater_than(v, &rptr->yval))
770 return locate_endpoint(v, vo, rptr->right);
771 else if (_equal_to(v, &rptr->yval))
773 if (_greater_than(vo, &rptr->yval))
774 return locate_endpoint(v, vo, rptr->right);
776 return locate_endpoint(v, vo, rptr->left);
779 return locate_endpoint(v, vo, rptr->left);
782 if (_equal_to(v, &seg[rptr->segnum].v0) ||
783 _equal_to(v, &seg[rptr->segnum].v1))
785 if (FP_EQUAL(v->y, vo->y))
788 return locate_endpoint(v, vo, rptr->left);
790 return locate_endpoint(v, vo, rptr->right);
793 else if (is_left_of(rptr->segnum, vo))
794 return locate_endpoint(v, vo, rptr->left);
796 return locate_endpoint(v, vo, rptr->right);
798 else if (is_left_of(rptr->segnum, v))
799 return locate_endpoint(v, vo, rptr->left);
801 return locate_endpoint(v, vo, rptr->right);
804 fprintf(stderr,
"Haggu !!!!!\n");
819 merge_trapezoids(
int segnum,
int tfirst,
int tlast,
int side) {
828 while ((t > 0) && _greater_than_equal_to(&tr[t].lo, &tr[tlast].lo))
831 cond = ((((tnext = tr[t].d0) > 0) && (tr[tnext].rseg == segnum)) ||
832 (((tnext = tr[t].d1) > 0) && (tr[tnext].rseg == segnum)));
834 cond = ((((tnext = tr[t].d0) > 0) && (tr[tnext].lseg == segnum)) ||
835 (((tnext = tr[t].d1) > 0) && (tr[tnext].lseg == segnum)));
839 if ((tr[t].lseg == tr[tnext].lseg) &&
840 (tr[t].rseg == tr[tnext].rseg))
844 ptnext = qs[tr[tnext].sink].parent;
846 if (qs[ptnext].left == tr[tnext].sink)
847 qs[ptnext].left = tr[t].sink;
849 qs[ptnext].right = tr[t].sink;
854 if ((tr[t].d0 = tr[tnext].d0) > 0) {
855 if (tr[tr[t].d0].u0 == tnext) {
857 }
else if (tr[tr[t].d0].u1 == tnext) {
862 if ((tr[t].d1 = tr[tnext].d1) > 0) {
863 if (tr[tr[t].d1].u0 == tnext) {
865 }
else if (tr[tr[t].d1].u1 == tnext) {
870 tr[t].lo = tr[tnext].lo;
871 tr[tnext].state = ST_INVALID;
893 add_segment(
int segnum) {
898 int tu, tl, sk, tfirst, tlast;
899 int tfirstr = 0, tlastr = 0, tfirstl = 0, tlastl = 0;
902 int tribot = 0, is_swapped = 0;
906 if (_greater_than(&s.v1, &s.v0))
918 if ((is_swapped) ? !inserted(segnum, LASTPT) :
919 !inserted(segnum, FIRSTPT))
923 tu = locate_endpoint(&s.v0, &s.v1, s.root0);
925 tr[tl].state = ST_VALID;
927 tr[tl].hi.y = s.v0.y;
928 tr[tu].lo.y = s.v0.y;
929 tr[tl].hi.x = s.v0.x;
930 tr[tu].lo.x = s.v0.x;
936 if (((tmp_d = tr[tl].d0) > 0) && (tr[tmp_d].u0 == tu))
938 if (((tmp_d = tr[tl].d0) > 0) && (tr[tmp_d].u1 == tu))
941 if (((tmp_d = tr[tl].d1) > 0) && (tr[tmp_d].u0 == tu))
943 if (((tmp_d = tr[tl].d1) > 0) && (tr[tmp_d].u1 == tu))
953 qs[sk].nodetype = T_Y;
955 qs[sk].segnum = segnum;
959 qs[i1].nodetype = T_SINK;
963 qs[i2].nodetype = T_SINK;
973 tfirst = locate_endpoint(&s.v0, &s.v1, s.root0);
977 if ((is_swapped) ? !inserted(segnum, FIRSTPT) :
978 !inserted(segnum, LASTPT))
982 tu = locate_endpoint(&s.v1, &s.v0, s.root1);
985 tr[tl].state = ST_VALID;
987 tr[tl].hi.y = s.v1.y;
988 tr[tu].lo.y = s.v1.y;
989 tr[tl].hi.x = s.v1.x;
990 tr[tu].lo.x = s.v1.x;
996 if (((tmp_d = tr[tl].d0) > 0) && (tr[tmp_d].u0 == tu))
998 if (((tmp_d = tr[tl].d0) > 0) && (tr[tmp_d].u1 == tu))
1001 if (((tmp_d = tr[tl].d1) > 0) && (tr[tmp_d].u0 == tu))
1003 if (((tmp_d = tr[tl].d1) > 0) && (tr[tmp_d].u1 == tu))
1013 qs[sk].nodetype = T_Y;
1015 qs[sk].segnum = segnum;
1019 qs[i1].nodetype = T_SINK;
1023 qs[i2].nodetype = T_SINK;
1033 tlast = locate_endpoint(&s.v1, &s.v0, s.root1);
1044 _greater_than_equal_to(&tr[t].lo, &tr[tlast].lo))
1052 qs[sk].nodetype = T_X;
1053 qs[sk].segnum = segnum;
1057 qs[i1].nodetype = T_SINK;
1061 qs[i2].nodetype = T_SINK;
1064 tr[tn].state = ST_VALID;
1069 if (_equal_to(&tr[t].lo, &tr[tlast].lo))
1080 if ((tr[t].d0 <= 0) && (tr[t].d1 <= 0))
1083 fprintf(stderr,
"add_segment: error\n");
1091 else if ((tr[t].d0 > 0) && (tr[t].d1 <= 0))
1093 if ((tr[t].u0 > 0) && (tr[t].u1 > 0))
1095 if (tr[t].usave > 0)
1097 if (tr[t].uside == S_LEFT)
1099 tr[tn].u0 = tr[t].u1;
1101 tr[tn].u1 = tr[t].usave;
1103 tr[tr[t].u0].d0 = t;
1104 tr[tr[tn].u0].d0 = tn;
1105 tr[tr[tn].u1].d0 = tn;
1110 tr[tn].u0 = tr[t].u1;
1111 tr[t].u1 = tr[t].u0;
1112 tr[t].u0 = tr[t].usave;
1114 tr[tr[t].u0].d0 = t;
1115 tr[tr[t].u1].d0 = t;
1116 tr[tr[tn].u0].d0 = tn;
1123 tr[tn].u0 = tr[t].u1;
1126 tr[tr[tn].u0].d0 = tn;
1131 int tmp_u = tr[t].u0;
1133 if (((td0 = tr[tmp_u].d0) > 0) &&
1134 ((td1 = tr[tmp_u].d1) > 0))
1136 if ((tr[td0].rseg > 0) &&
1137 !is_left_of(tr[td0].rseg, &s.v1))
1142 tr[tr[tn].u0].d1 = tn;
1149 tr[tr[t].u0].d0 = t;
1154 tr[tr[t].u0].d0 = t;
1155 tr[tr[t].u0].d1 = tn;
1159 if (FP_EQUAL(tr[t].lo.y, tr[tlast].lo.y) &&
1160 FP_EQUAL(tr[t].lo.x, tr[tlast].lo.x) && tribot)
1164 tmptriseg = seg[segnum].prev;
1166 tmptriseg = seg[segnum].next;
1168 if ((tmptriseg > 0) && is_left_of(tmptriseg, &s.v0))
1171 tr[tr[t].d0].u0 = t;
1178 tr[tr[tn].d0].u1 = tn;
1185 if ((tr[tr[t].d0].u0 > 0) && (tr[tr[t].d0].u1 > 0))
1187 if (tr[tr[t].d0].u0 == t)
1189 tr[tr[t].d0].usave = tr[tr[t].d0].u1;
1190 tr[tr[t].d0].uside = S_LEFT;
1194 tr[tr[t].d0].usave = tr[tr[t].d0].u0;
1195 tr[tr[t].d0].uside = S_RIGHT;
1198 tr[tr[t].d0].u0 = t;
1199 tr[tr[t].d0].u1 = tn;
1206 else if ((tr[t].d0 <= 0) && (tr[t].d1 > 0))
1208 if ((tr[t].u0 > 0) && (tr[t].u1 > 0))
1210 if (tr[t].usave > 0)
1212 if (tr[t].uside == S_LEFT)
1214 tr[tn].u0 = tr[t].u1;
1216 tr[tn].u1 = tr[t].usave;
1218 tr[tr[t].u0].d0 = t;
1219 tr[tr[tn].u0].d0 = tn;
1220 tr[tr[tn].u1].d0 = tn;
1225 tr[tn].u0 = tr[t].u1;
1226 tr[t].u1 = tr[t].u0;
1227 tr[t].u0 = tr[t].usave;
1229 tr[tr[t].u0].d0 = t;
1230 tr[tr[t].u1].d0 = t;
1231 tr[tr[tn].u0].d0 = tn;
1239 tr[tn].u0 = tr[t].u1;
1242 tr[tr[tn].u0].d0 = tn;
1247 int tmp_u = tr[t].u0;
1249 if (((td0 = tr[tmp_u].d0) > 0) &&
1250 ((td1 = tr[tmp_u].d1) > 0))
1252 if ((tr[td0].rseg > 0) &&
1253 !is_left_of(tr[td0].rseg, &s.v1))
1258 tr[tr[tn].u0].d1 = tn;
1265 tr[tr[t].u0].d0 = t;
1270 tr[tr[t].u0].d0 = t;
1271 tr[tr[t].u0].d1 = tn;
1275 if (FP_EQUAL(tr[t].lo.y, tr[tlast].lo.y) &&
1276 FP_EQUAL(tr[t].lo.x, tr[tlast].lo.x) && tribot)
1279 tmptriseg = seg[segnum].prev;
1281 tmptriseg = seg[segnum].next;
1283 if ((tmptriseg > 0) && is_left_of(tmptriseg, &s.v0))
1286 tr[tr[t].d1].u0 = t;
1293 tr[tr[tn].d1].u1 = tn;
1300 if ((tr[tr[t].d1].u0 > 0) && (tr[tr[t].d1].u1 > 0))
1302 if (tr[tr[t].d1].u0 == t)
1304 tr[tr[t].d1].usave = tr[tr[t].d1].u1;
1305 tr[tr[t].d1].uside = S_LEFT;
1309 tr[tr[t].d1].usave = tr[tr[t].d1].u0;
1310 tr[tr[t].d1].uside = S_RIGHT;
1313 tr[tr[t].d1].u0 = t;
1314 tr[tr[t].d1].u1 = tn;
1331 if (FP_EQUAL(tr[t].lo.y, s.v0.y))
1333 if (tr[t].lo.x > s.v0.x)
1340 yt = (y0 - s.v0.y)/(s.v1.y - s.v0.y);
1341 tmppt.x = s.v0.x + yt * (s.v1.x - s.v0.x);
1343 if (_less_than(&tmppt, &tr[t].lo))
1350 if ((tr[t].u0 > 0) && (tr[t].u1 > 0))
1352 if (tr[t].usave > 0)
1354 if (tr[t].uside == S_LEFT)
1356 tr[tn].u0 = tr[t].u1;
1358 tr[tn].u1 = tr[t].usave;
1360 tr[tr[t].u0].d0 = t;
1361 tr[tr[tn].u0].d0 = tn;
1362 tr[tr[tn].u1].d0 = tn;
1367 tr[tn].u0 = tr[t].u1;
1368 tr[t].u1 = tr[t].u0;
1369 tr[t].u0 = tr[t].usave;
1371 tr[tr[t].u0].d0 = t;
1372 tr[tr[t].u1].d0 = t;
1373 tr[tr[tn].u0].d0 = tn;
1381 tr[tn].u0 = tr[t].u1;
1384 tr[tr[tn].u0].d0 = tn;
1389 int tmp_u = tr[t].u0;
1391 if (((td0 = tr[tmp_u].d0) > 0) &&
1392 ((td1 = tr[tmp_u].d1) > 0))
1394 if ((tr[td0].rseg > 0) &&
1395 !is_left_of(tr[td0].rseg, &s.v1))
1400 tr[tr[tn].u0].d1 = tn;
1407 tr[tr[t].u0].d0 = t;
1412 tr[tr[t].u0].d0 = t;
1413 tr[tr[t].u0].d1 = tn;
1417 if (FP_EQUAL(tr[t].lo.y, tr[tlast].lo.y) &&
1418 FP_EQUAL(tr[t].lo.x, tr[tlast].lo.x) && tribot)
1424 tr[tr[t].d0].u0 = t;
1425 tr[tr[t].d0].u1 = -1;
1426 tr[tr[t].d1].u0 = tn;
1427 tr[tr[t].d1].u1 = -1;
1429 tr[tn].d0 = tr[t].d1;
1438 tr[tr[t].d0].u0 = t;
1439 tr[tr[t].d0].u1 = tn;
1440 tr[tr[t].d1].u0 = tn;
1441 tr[tr[t].d1].u1 = -1;
1452 tr[tr[t].d0].u0 = t;
1453 tr[tr[t].d0].u1 = -1;
1454 tr[tr[t].d1].u0 = t;
1455 tr[tr[t].d1].u1 = tn;
1460 tr[tn].d0 = tr[t].d1;
1469 tr[tn_sav].lseg = segnum;
1470 tr[t_sav].rseg = segnum;
1480 merge_trapezoids(segnum, tfirstl, tlastl, S_LEFT);
1481 merge_trapezoids(segnum, tfirstr, tlastr, S_RIGHT);
1483 seg[segnum].is_inserted =
true;
1493 find_new_roots(
int segnum) {
1495 segment_t *s = &seg[segnum];
1500 s->root0 = locate_endpoint(&s->v0, &s->v1, s->root0);
1501 s->root0 = tr[s->root0].sink;
1503 s->root1 = locate_endpoint(&s->v1, &s->v0, s->root1);
1504 s->root1 = tr[s->root1].sink;
1511 construct_trapezoids(
int nseg) {
1519 root = init_query_structure(choose_segment());
1521 for (i = 1; i <= nseg; i++) {
1522 seg[i].root1 = root;
1523 seg[i].root0 = root;
1526 for (h = 1; h <= math_logstar_n(nseg); h++)
1528 for (i = math_N(nseg, h -1) + 1; i <= math_N(nseg, h); i++) {
1529 if (add_segment(choose_segment()) != 0) {
1536 for (i = 1; i <= nseg; i++)
1540 for (i = math_N(nseg, math_logstar_n(nseg)) + 1; i <= nseg; i++)
1541 add_segment(choose_segment());
1550 inside_polygon(trap_t *t) {
1553 if (t->state == ST_INVALID)
1556 if ((t->lseg <= 0) || (t->rseg <= 0))
1559 if (((t->u0 <= 0) && (t->u1 <= 0)) ||
1560 ((t->d0 <= 0) && (t->d1 <= 0)))
1561 return (_greater_than(&seg[rseg].v1, &seg[rseg].v0));
1570 int index = (int)mon.size();
1579 new_chain_element() {
1580 int index = (int)mchain.size();
1581 mchain.push_back(monchain_t());
1587 double Triangulator::
1588 get_angle(point_t *vp0, point_t *vpnext, point_t *vp1) {
1591 v0.x = vpnext->x - vp0->x;
1592 v0.y = vpnext->y - vp0->y;
1594 v1.x = vp1->x - vp0->x;
1595 v1.y = vp1->y - vp0->y;
1597 if (CROSS_SINE(v0, v1) >= 0)
1598 return DOT(v0, v1)/LENGTH(v0)/LENGTH(v1);
1600 return (-1.0 * DOT(v0, v1)/LENGTH(v0)/LENGTH(v1) - 2);
1607 get_vertex_positions(
int v0,
int v1,
int *ip,
int *iq) {
1608 vertexchain_t *vp0, *vp1;
1621 for (i = 0; i < 4; i++)
1623 if (vp0->vnext[i] <= 0)
1625 if ((temp = get_angle(&vp0->pt, &(vert[vp0->vnext[i]].pt),
1638 for (i = 0; i < 4; i++)
1640 if (vp1->vnext[i] <= 0)
1642 if ((temp = get_angle(&vp1->pt, &(vert[vp1->vnext[i]].pt),
1661 make_new_monotone_poly(
int mcur,
int v0,
int v1) {
1663 int mnew = newmon();
1665 vertexchain_t *vp0, *vp1;
1667 if (v0 <= 0 || v1 <= 0) {
1674 get_vertex_positions(v0, v1, &ip, &iq);
1682 i = new_chain_element();
1683 j = new_chain_element();
1685 mchain[i].vnum = v0;
1686 mchain[j].vnum = v1;
1688 mchain[i].next = mchain[p].next;
1689 mchain[mchain[p].next].prev = i;
1692 mchain[j].prev = mchain[q].prev;
1693 mchain[mchain[q].prev].next = j;
1698 nf0 = vp0->nextfree;
1699 nf1 = vp1->nextfree;
1701 vp0->vnext[ip] = v1;
1704 vp0->vnext[nf0] = mchain[mchain[i].next].vnum;
1706 vp1->vnext[nf1] = v0;
1712 fprintf(stderr,
"make_poly: mcur = %d, (v0, v1) = (%d, %d)\n",
1714 fprintf(stderr,
"next posns = (p, q) = (%d, %d)\n", p, q);
1727 monotonate_trapezoids(
int n) {
1736 vert.insert(vert.begin(), n + 1, vertexchain_t());
1737 mchain.insert(mchain.begin(), n + 1, monchain_t());
1739 visited.insert(visited.begin(), tr.size(), 0);
1743 for (i = 1; i < (int)tr.size(); i++)
1744 if (inside_polygon(&tr[i]))
1746 if (i >= (
int)tr.size()) {
1757 for (i = 1; i <= n; i++)
1759 mchain[i].prev = i - 1;
1760 mchain[i].next = i + 1;
1762 vert[i].pt = seg[i].v0;
1763 vert[i].vnext[0] = i + 1;
1764 vert[i].vpos[0] = i;
1765 vert[i].nextfree = 1;
1766 vert[i].user_i = seg[i].v0_i;
1770 vert[n].vnext[0] = 1;
1771 vert[n].vpos[0] = n;
1777 for (i = 1; i <= n; i++)
1779 mchain[i].prev = seg[i].prev;
1780 mchain[i].next = seg[i].next;
1782 vert[i].pt = seg[i].v0;
1783 vert[i].vnext[0] = seg[i].next;
1784 vert[i].vpos[0] = i;
1785 vert[i].nextfree = 1;
1786 vert[i].user_i = seg[i].v0_i;
1795 if (tr[tr_start].u0 > 0)
1796 traverse_polygon(0, tr_start, tr[tr_start].u0, TR_FROM_UP);
1797 else if (tr[tr_start].d0 > 0)
1798 traverse_polygon(0, tr_start, tr[tr_start].d0, TR_FROM_DN);
1807 traverse_polygon(
int mcur,
int trnum,
int from,
int dir) {
1810 if (mcur < 0 || trnum <= 0)
1816 trap_t *t = &tr[trnum];
1825 visited[trnum] =
true;
1837 if ((t->u0 <= 0) && (t->u1 <= 0))
1839 if ((t->d0 > 0) && (t->d1 > 0))
1841 v0 = tr[t->d1].lseg;
1845 mnew = make_new_monotone_poly(mcur, v1, v0);
1846 traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
1847 traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
1851 mnew = make_new_monotone_poly(mcur, v0, v1);
1852 traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
1853 traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
1858 retval = SP_NOSPLIT;
1859 traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
1860 traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
1861 traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
1862 traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
1866 else if ((t->d0 <= 0) && (t->d1 <= 0))
1868 if ((t->u0 > 0) && (t->u1 > 0))
1871 v1 = tr[t->u0].rseg;
1874 mnew = make_new_monotone_poly(mcur, v1, v0);
1875 traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
1876 traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
1880 mnew = make_new_monotone_poly(mcur, v0, v1);
1881 traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
1882 traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
1887 retval = SP_NOSPLIT;
1888 traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
1889 traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
1890 traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
1891 traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
1895 else if ((t->u0 > 0) && (t->u1 > 0))
1897 if ((t->d0 > 0) && (t->d1 > 0))
1899 v0 = tr[t->d1].lseg;
1900 v1 = tr[t->u0].rseg;
1901 retval = SP_2UP_2DN;
1902 if (((dir == TR_FROM_DN) && (t->d1 == from)) ||
1903 ((dir == TR_FROM_UP) && (t->u1 == from)))
1905 mnew = make_new_monotone_poly(mcur, v1, v0);
1906 traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
1907 traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
1908 traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
1909 traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
1913 mnew = make_new_monotone_poly(mcur, v0, v1);
1914 traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
1915 traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
1916 traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
1917 traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
1922 if (_equal_to(&t->lo, &seg[t->lseg].v1))
1924 v0 = tr[t->u0].rseg;
1925 v1 = seg[t->lseg].next;
1927 retval = SP_2UP_LEFT;
1928 if ((dir == TR_FROM_UP) && (t->u0 == from))
1930 mnew = make_new_monotone_poly(mcur, v1, v0);
1931 traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
1932 traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
1933 traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
1934 traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
1938 mnew = make_new_monotone_poly(mcur, v0, v1);
1939 traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
1940 traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
1941 traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
1942 traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
1948 v1 = tr[t->u0].rseg;
1949 retval = SP_2UP_RIGHT;
1950 if ((dir == TR_FROM_UP) && (t->u1 == from))
1952 mnew = make_new_monotone_poly(mcur, v1, v0);
1953 traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
1954 traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
1955 traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
1956 traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
1960 mnew = make_new_monotone_poly(mcur, v0, v1);
1961 traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
1962 traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
1963 traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
1964 traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
1969 else if ((t->u0 > 0) || (t->u1 > 0))
1971 if ((t->d0 > 0) && (t->d1 > 0))
1973 if (_equal_to(&t->hi, &seg[t->lseg].v0))
1975 v0 = tr[t->d1].lseg;
1977 retval = SP_2DN_LEFT;
1978 if (!((dir == TR_FROM_DN) && (t->d0 == from)))
1980 mnew = make_new_monotone_poly(mcur, v1, v0);
1981 traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
1982 traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
1983 traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
1984 traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
1988 mnew = make_new_monotone_poly(mcur, v0, v1);
1989 traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
1990 traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
1991 traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
1992 traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
1997 v0 = tr[t->d1].lseg;
1998 v1 = seg[t->rseg].next;
2000 retval = SP_2DN_RIGHT;
2001 if ((dir == TR_FROM_DN) && (t->d1 == from))
2003 mnew = make_new_monotone_poly(mcur, v1, v0);
2004 traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
2005 traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
2006 traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
2007 traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
2011 mnew = make_new_monotone_poly(mcur, v0, v1);
2012 traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
2013 traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
2014 traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
2015 traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
2021 if (_equal_to(&t->hi, &seg[t->lseg].v0) &&
2022 _equal_to(&t->lo, &seg[t->rseg].v0))
2026 retval = SP_SIMPLE_LRDN;
2027 if (dir == TR_FROM_UP)
2029 mnew = make_new_monotone_poly(mcur, v1, v0);
2030 traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
2031 traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
2032 traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
2033 traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
2037 mnew = make_new_monotone_poly(mcur, v0, v1);
2038 traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
2039 traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
2040 traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
2041 traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
2044 else if (_equal_to(&t->hi, &seg[t->rseg].v1) &&
2045 _equal_to(&t->lo, &seg[t->lseg].v1))
2047 v0 = seg[t->rseg].next;
2048 v1 = seg[t->lseg].next;
2050 retval = SP_SIMPLE_LRUP;
2051 if (dir == TR_FROM_UP)
2053 mnew = make_new_monotone_poly(mcur, v1, v0);
2054 traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
2055 traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
2056 traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
2057 traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
2061 mnew = make_new_monotone_poly(mcur, v0, v1);
2062 traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
2063 traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
2064 traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
2065 traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
2070 retval = SP_NOSPLIT;
2071 traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
2072 traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
2073 traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
2074 traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
2089 triangulate_monotone_polygons(
int nvert,
int nmonpoly) {
2092 int p, vfirst, posmax, posmin, v;
2093 int vcount, processed;
2096 for (i = 0; i < nmonpoly; i++)
2098 fprintf(stderr,
"\n\nPolygon %d: ", i);
2099 vfirst = mchain[mon[i]].vnum;
2100 p = mchain[mon[i]].next;
2101 fprintf (stderr,
"%d ", mchain[mon[i]].vnum);
2102 while (mchain[p].vnum != vfirst)
2104 fprintf(stderr,
"%d ", mchain[p].vnum);
2105 if (mchain[p].vnum == -1) {
2106 fprintf(stderr,
" xx");
2112 fprintf(stderr,
"\n");
2115 for (i = 0; i < nmonpoly; i++)
2119 vfirst = mchain[mon[i]].vnum;
2123 ymin = vert[vfirst].pt;
2127 mchain[mon[i]].marked =
true;
2128 p = mchain[mon[i]].next;
2129 while ((v = mchain[p].vnum) != vfirst)
2134 if (mchain[p].marked)
2140 mchain[p].marked =
true;
2142 if (_greater_than(&vert[v].pt, &ymax))
2147 if (_less_than(&vert[v].pt, &ymin))
2161 _result.push_back(Triangle(
this, mchain[p].vnum,
2162 mchain[mchain[p].next].vnum,
2163 mchain[mchain[p].prev].vnum));
2167 v = mchain[mchain[posmax].next].vnum;
2168 if (_equal_to(&vert[v].pt, &ymin))
2170 triangulate_single_polygon(nvert, posmax, TRI_LHS);
2173 triangulate_single_polygon(nvert, posmax, TRI_RHS);
2184 triangulate_single_polygon(
int nvert,
int posmax,
int side) {
2188 int endv, tmp, vpos;
2193 if (side == TRI_RHS)
2195 rc.push_back(mchain[posmax].vnum);
2196 tmp = mchain[posmax].next;
2197 rc.push_back(mchain[tmp].vnum);
2200 vpos = mchain[tmp].next;
2201 v = mchain[vpos].vnum;
2203 if ((endv = mchain[mchain[posmax].prev].vnum) == 0)
2208 tmp = mchain[posmax].next;
2209 rc.push_back(mchain[tmp].vnum);
2210 tmp = mchain[tmp].next;
2211 rc.push_back(mchain[tmp].vnum);
2214 vpos = mchain[tmp].next;
2215 v = mchain[vpos].vnum;
2217 endv = mchain[posmax].vnum;
2220 int num_triangles = 0;
2222 while ((v != endv) || (ri > 1))
2232 PN_stdfloat crossResult = CROSS(vert[v].pt, vert[rc[ri - 1]].pt,
2234 if ( crossResult >= 0 )
2236 if (crossResult > 0) {
2237 _result.push_back(Triangle(
this, rc[ri - 1], rc[ri], v));
2238 if (++num_triangles >= nvert - 2) {
2246 nassertv(ri + 1 == (
int)rc.size());
2252 nassertv(ri + 1 == (
int)rc.size());
2253 vpos = mchain[vpos].next;
2254 v = mchain[vpos].vnum;
2261 nassertv(ri + 1 == (
int)rc.size());
2262 vpos = mchain[vpos].next;
2263 v = mchain[vpos].vnum;
2268 _result.push_back(Triangle(
this, rc[ri - 1], rc[ri], v));
A handy class to return random numbers.
int random_int(int range)
Returns a random integer in the range [0, range).
int get_triangle_v0(int n) const
Returns vertex 0 of the nth triangle generated by the previous call to triangulate().
void clear()
Removes all vertices and polygon specifications from the Triangulator, and prepares it to start over.
void add_polygon_vertex(int index)
Adds the next consecutive vertex of the polygon.
void clear_polygon()
Removes the current polygon definition (and its set of holes), but does not clear the vertex pool.
int get_triangle_v1(int n) const
Returns vertex 1 of the nth triangle generated by the previous call to triangulate().
int get_num_triangles() const
Returns the number of triangles generated by the previous call to triangulate().
int add_vertex(const LPoint2d &point)
Adds a new vertex to the vertex pool.
void add_hole_vertex(int index)
Adds the next consecutive vertex of the current hole.
void triangulate()
Does the work of triangulating the specified polygon.
void begin_hole()
Finishes the previous hole, if any, and prepares to add a new hole.
int get_triangle_v2(int n) const
Returns vertex 2 of the nth triangle generated by the previous call to triangulate().
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.