1 /*
2 * vim: ts=4 sw=4 et tw=0 wm=0
3 *
4 * libavoid - Fast, Incremental, Object-avoiding Line Router
5 * Copyright (C) 2004-2005 Michael Wybrow <mjwybrow@users.sourceforge.net>
6 *
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public
9 * License as published by the Free Software Foundation; either
10 * version 2.1 of the License, or (at your option) any later version.
11 *
12 * This library is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details.
16 *
17 * You should have received a copy of the GNU Lesser General Public
18 * License along with this library; if not, write to the Free Software
19 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20 *
21 */
23 #include "libavoid/debug.h"
24 #include "libavoid/graph.h"
25 #include "libavoid/connector.h"
26 #include "libavoid/polyutil.h"
27 #include "libavoid/timer.h"
29 #include <math.h>
31 namespace Avoid {
34 static int st_checked_edges = 0;
36 EdgeList visGraph;
37 EdgeList invisGraph;
40 EdgeInf::EdgeInf(VertInf *v1, VertInf *v2)
41 : lstPrev(NULL)
42 , lstNext(NULL)
43 , _added(false)
44 , _visible(false)
45 , _v1(v1)
46 , _v2(v2)
47 , _dist(-1)
48 {
49 _blockers.clear();
50 _conns.clear();
51 }
54 EdgeInf::~EdgeInf()
55 {
56 if (_added)
57 {
58 makeInactive();
59 }
60 }
63 void EdgeInf::makeActive(void)
64 {
65 assert(_added == false);
67 if (_visible)
68 {
69 visGraph.addEdge(this);
70 _pos1 = _v1->visList.insert(_v1->visList.begin(), this);
71 _v1->visListSize++;
72 _pos2 = _v2->visList.insert(_v2->visList.begin(), this);
73 _v2->visListSize++;
74 }
75 else // if (invisible)
76 {
77 invisGraph.addEdge(this);
78 _pos1 = _v1->invisList.insert(_v1->invisList.begin(), this);
79 _v1->invisListSize++;
80 _pos2 = _v2->invisList.insert(_v2->invisList.begin(), this);
81 _v2->invisListSize++;
82 }
83 _added = true;
84 }
87 void EdgeInf::makeInactive(void)
88 {
89 assert(_added == true);
91 if (_visible)
92 {
93 visGraph.removeEdge(this);
94 _v1->visList.erase(_pos1);
95 _v1->visListSize--;
96 _v2->visList.erase(_pos2);
97 _v2->visListSize--;
98 }
99 else // if (invisible)
100 {
101 invisGraph.removeEdge(this);
102 _v1->invisList.erase(_pos1);
103 _v1->invisListSize--;
104 _v2->invisList.erase(_pos2);
105 _v2->invisListSize--;
106 }
107 _blockers.clear();
108 _conns.clear();
109 _added = false;
110 }
113 double EdgeInf::getDist(void)
114 {
115 return _dist;
116 }
119 void EdgeInf::setDist(double dist)
120 {
121 //assert(dist != 0);
123 if (_added && !_visible)
124 {
125 makeInactive();
126 }
127 if (!_added)
128 {
129 _visible = true;
130 makeActive();
131 }
132 _dist = dist;
133 _blockers.clear();
134 }
137 void EdgeInf::alertConns(void)
138 {
139 for (FlagList::iterator i = _conns.begin(); i != _conns.end(); ++i)
140 {
141 *(*i) = true;
142 }
143 _conns.clear();
144 }
147 void EdgeInf::addConn(bool *flag)
148 {
149 _conns.push_back(flag);
150 }
153 void EdgeInf::addCycleBlocker(void)
154 {
155 // Needs to be in invisibility graph.
156 addBlocker(-1);
157 }
160 void EdgeInf::addBlocker(int b)
161 {
162 assert(InvisibilityGrph);
164 if (_added && _visible)
165 {
166 makeInactive();
167 }
168 if (!_added)
169 {
170 _visible = false;
171 makeActive();
172 }
173 _dist = 0;
174 _blockers.clear();
175 _blockers.push_back(b);
176 }
179 bool EdgeInf::hasBlocker(int b)
180 {
181 assert(InvisibilityGrph);
183 ShapeList::iterator finish = _blockers.end();
184 for (ShapeList::iterator it = _blockers.begin(); it != finish; ++it)
185 {
186 if ((*it) == -1)
187 {
188 alertConns();
189 return true;
190 }
191 else if ((*it) == b)
192 {
193 return true;
194 }
195 }
196 return false;
197 }
200 pair<VertID, VertID> EdgeInf::ids(void)
201 {
202 return std::make_pair(_v1->id, _v2->id);
203 }
206 pair<Point, Point> EdgeInf::points(void)
207 {
208 return std::make_pair(_v1->point, _v2->point);
209 }
212 void EdgeInf::db_print(void)
213 {
214 db_printf("Edge(");
215 _v1->id.db_print();
216 db_printf(",");
217 _v2->id.db_print();
218 db_printf(")\n");
219 }
222 void EdgeInf::checkVis(void)
223 {
224 if (_added && !_visible)
225 {
226 db_printf("\tChecking visibility for existing invisibility edge..."
227 "\n\t\t");
228 db_print();
229 }
230 else if (_added && _visible)
231 {
232 db_printf("\tChecking visibility for existing visibility edge..."
233 "\n\t\t");
234 db_print();
235 }
237 int blocker = 0;
238 bool cone1 = true;
239 bool cone2 = true;
241 VertInf *i = _v1;
242 VertInf *j = _v2;
243 const VertID& iID = i->id;
244 const VertID& jID = j->id;
245 const Point& iPoint = i->point;
246 const Point& jPoint = j->point;
248 st_checked_edges++;
250 if (iID.isShape)
251 {
252 cone1 = inValidRegion(i->shPrev->point, iPoint, i->shNext->point,
253 jPoint);
254 }
255 else
256 {
257 ShapeSet& ss = contains[iID];
259 if ((jID.isShape) && (ss.find(jID.objID) != ss.end()))
260 {
261 db_printf("1: Edge of bounding shape\n");
262 // Don't even check this edge, it should be zero,
263 // since a point in a shape can't see it's corners
264 cone1 = false;
265 }
266 }
268 if (cone1)
269 {
270 // If outside the first cone, don't even bother checking.
271 if (jID.isShape)
272 {
273 cone2 = inValidRegion(j->shPrev->point, jPoint, j->shNext->point,
274 iPoint);
275 }
276 else
277 {
278 ShapeSet& ss = contains[jID];
280 if ((iID.isShape) && (ss.find(iID.objID) != ss.end()))
281 {
282 db_printf("2: Edge of bounding shape\n");
283 // Don't even check this edge, it should be zero,
284 // since a point in a shape can't see it's corners
285 cone2 = false;
286 }
287 }
288 }
290 if (cone1 && cone2 && ((blocker = firstBlocker()) == 0))
291 {
293 // if i and j see each other, add edge
294 db_printf("\tSetting visibility edge... \n\t\t");
295 db_print();
297 double d = dist(iPoint, jPoint);
299 setDist(d);
301 }
302 else if (InvisibilityGrph)
303 {
304 #if 0
305 db_printf("%d, %d, %d\n", cone1, cone2, blocker);
306 db_printf("\t(%d, %d)--(%d, %d)\n", (int) iInfo.point.x,
307 (int) iInfo.point.y, (int) jInfo.point.x,
308 (int) jInfo.point.y);
309 #endif
311 // if i and j can't see each other, add blank edge
312 db_printf("\tSetting invisibility edge... \n\t\t");
313 db_print();
314 addBlocker(blocker);
315 }
316 }
319 int EdgeInf::firstBlocker(void)
320 {
321 ShapeSet ss = ShapeSet();
323 Point& pti = _v1->point;
324 Point& ptj = _v2->point;
325 VertID& iID = _v1->id;
326 VertID& jID = _v2->id;
328 if (!(iID.isShape))
329 {
330 ss.insert(contains[iID].begin(), contains[iID].end());
331 }
332 if (!(jID.isShape))
333 {
334 ss.insert(contains[jID].begin(), contains[jID].end());
335 }
337 VertInf *last = vertices.end();
338 for (VertInf *k = vertices.shapesBegin(); k != last; )
339 {
340 VertID kID = k->id;
341 if ((ss.find(kID.objID) != ss.end()))
342 {
343 unsigned int shapeID = kID.objID;
344 db_printf("Endpoint is inside shape %u so ignore shape edges.\n",
345 kID.objID);
346 // One of the endpoints is inside this shape so ignore it.
347 while ((k != last) && (k->id.objID == shapeID))
348 {
349 // And skip the other vertices from this shape.
350 k = k->lstNext;
351 }
352 continue;
353 }
354 Point& kPoint = k->point;
355 Point& kPrevPoint = k->shPrev->point;
357 if (segmentIntersect(pti, ptj, kPrevPoint, kPoint))
358 {
359 ss.clear();
360 return kID.objID;
361 }
362 k = k->lstNext;
363 }
364 ss.clear();
365 return 0;
366 }
369 bool EdgeInf::isBetween(VertInf *i, VertInf *j)
370 {
371 if ( ((i == _v1) && (j == _v2)) ||
372 ((i == _v2) && (j == _v1)) )
373 {
374 return true;
375 }
376 return false;
377 }
380 VertInf *EdgeInf::otherVert(VertInf *vert)
381 {
382 assert((vert == _v1) || (vert == _v2));
384 if (vert == _v1)
385 {
386 return _v2;
387 }
388 return _v1;
389 }
392 EdgeInf *EdgeInf::checkEdgeVisibility(VertInf *i, VertInf *j, bool knownNew)
393 {
394 EdgeInf *edge = NULL;
396 if (knownNew)
397 {
398 assert(existingEdge(i, j) == NULL);
399 edge = new EdgeInf(i, j);
400 }
401 else
402 {
403 edge = existingEdge(i, j);
404 if (edge == NULL)
405 {
406 edge = new EdgeInf(i, j);
407 }
408 }
409 edge->checkVis();
410 if (!(edge->_added) && !InvisibilityGrph)
411 {
412 delete edge;
413 edge = NULL;
414 }
416 return edge;
417 }
420 EdgeInf *EdgeInf::existingEdge(VertInf *i, VertInf *j)
421 {
422 VertInf *selected = NULL;
424 if (i->visListSize <= j->visListSize)
425 {
426 selected = i;
427 }
428 else
429 {
430 selected = j;
431 }
433 EdgeInfList& visList = selected->visList;
434 EdgeInfList::iterator finish = visList.end();
435 for (EdgeInfList::iterator edge = visList.begin(); edge != finish;
436 ++edge)
437 {
438 if ((*edge)->isBetween(i, j))
439 {
440 return (*edge);
441 }
442 }
444 if (i->invisListSize <= j->invisListSize)
445 {
446 selected = i;
447 }
448 else
449 {
450 selected = j;
451 }
453 EdgeInfList& invisList = selected->invisList;
454 finish = invisList.end();
455 for (EdgeInfList::iterator edge = invisList.begin(); edge != finish;
456 ++edge)
457 {
458 if ((*edge)->isBetween(i, j))
459 {
460 return (*edge);
461 }
462 }
464 return NULL;
465 }
468 //===========================================================================
471 EdgeList::EdgeList()
472 : _firstEdge(NULL)
473 , _lastEdge(NULL)
474 , _count(0)
475 {
476 }
479 void EdgeList::addEdge(EdgeInf *edge)
480 {
481 if (_firstEdge == NULL)
482 {
483 assert(_lastEdge == NULL);
485 _lastEdge = edge;
486 _firstEdge = edge;
488 edge->lstPrev = NULL;
489 edge->lstNext = NULL;
490 }
491 else
492 {
493 assert(_lastEdge != NULL);
495 _lastEdge->lstNext = edge;
496 edge->lstPrev = _lastEdge;
498 _lastEdge = edge;
500 edge->lstNext = NULL;
501 }
502 _count++;
503 }
506 void EdgeList::removeEdge(EdgeInf *edge)
507 {
508 if (edge->lstPrev)
509 {
510 edge->lstPrev->lstNext = edge->lstNext;
511 }
512 if (edge->lstNext)
513 {
514 edge->lstNext->lstPrev = edge->lstPrev;
515 }
516 if (edge == _lastEdge)
517 {
518 _lastEdge = edge->lstPrev;
519 if (edge == _firstEdge)
520 {
521 _firstEdge = NULL;
522 }
523 }
524 else if (edge == _firstEdge)
525 {
526 _firstEdge = edge->lstNext;
527 }
530 edge->lstPrev = NULL;
531 edge->lstNext = NULL;
533 _count--;
534 }
537 EdgeInf *EdgeList::begin(void)
538 {
539 return _firstEdge;
540 }
543 EdgeInf *EdgeList::end(void)
544 {
545 return NULL;
546 }
549 // General visibility graph utility functions
552 void newBlockingShape(Polygn *poly, int pid)
553 {
554 // o Check all visibility edges to see if this one shape
555 // blocks them.
556 EdgeInf *finish = visGraph.end();
557 for (EdgeInf *iter = visGraph.begin(); iter != finish ; )
558 {
559 EdgeInf *tmp = iter;
560 iter = iter->lstNext;
562 if (tmp->getDist() != 0)
563 {
564 pair<VertID, VertID> ids(tmp->ids());
565 VertID eID1 = ids.first;
566 VertID eID2 = ids.second;
567 pair<Point, Point> points(tmp->points());
568 Point e1 = points.first;
569 Point e2 = points.second;
570 bool blocked = false;
572 bool ep_in_poly1 = !(eID1.isShape) ? inPoly(*poly, e1) : false;
573 bool ep_in_poly2 = !(eID2.isShape) ? inPoly(*poly, e2) : false;
574 if (ep_in_poly1 || ep_in_poly2)
575 {
576 // Don't check edges that have a connector endpoint
577 // and are inside the shape being added.
578 continue;
579 }
581 for (int pt_i = 0; pt_i < poly->pn; pt_i++)
582 {
583 int pt_n = (pt_i == (poly->pn - 1)) ? 0 : pt_i + 1;
584 if (segmentIntersect(e1, e2, poly->ps[pt_i], poly->ps[pt_n]))
585 {
586 blocked = true;
587 break;
588 }
589 }
590 if (blocked)
591 {
592 db_printf("\tRemoving newly blocked edge (by shape %3d)"
593 "... \n\t\t", pid);
594 tmp->alertConns();
595 tmp->db_print();
596 if (InvisibilityGrph)
597 {
598 tmp->addBlocker(pid);
599 }
600 else
601 {
602 delete tmp;
603 }
604 }
605 }
606 }
607 }
610 void checkAllBlockedEdges(int pid)
611 {
612 assert(InvisibilityGrph);
614 for (EdgeInf *iter = invisGraph.begin(); iter != invisGraph.end() ; )
615 {
616 EdgeInf *tmp = iter;
617 iter = iter->lstNext;
619 if (tmp->hasBlocker(pid))
620 {
621 tmp->checkVis();
622 }
623 }
624 }
627 void checkAllMissingEdges(void)
628 {
629 assert(!InvisibilityGrph);
631 VertInf *first = NULL;
633 if (IncludeEndpoints)
634 {
635 first = vertices.connsBegin();
636 }
637 else
638 {
639 first = vertices.shapesBegin();
640 }
642 VertInf *pend = vertices.end();
643 for (VertInf *i = first; i != pend; i = i->lstNext)
644 {
645 VertID iID = i->id;
647 // Check remaining, earlier vertices
648 for (VertInf *j = first ; j != i; j = j->lstNext)
649 {
650 VertID jID = j->id;
651 if (!(iID.isShape) && (iID.objID != jID.objID))
652 {
653 // Don't keep visibility between edges of different conns
654 continue;
655 }
657 // See if the edge is already there?
658 bool found = (EdgeInf::existingEdge(i, j) != NULL);
660 if (!found)
661 {
662 // Didn't already exist, check.
663 bool knownNew = true;
664 EdgeInf::checkEdgeVisibility(i, j, knownNew);
665 }
666 }
667 }
668 }
671 void generateContains(VertInf *pt)
672 {
673 contains[pt->id].clear();
675 ShapeRefList::iterator finish = shapeRefs.end();
676 for (ShapeRefList::iterator i = shapeRefs.begin(); i != finish; ++i)
677 {
678 Polygn poly = copyPoly(*i);
679 if (inPoly(poly, pt->point))
680 {
681 contains[pt->id].insert((*i)->id());
682 }
683 freePoly(poly);
684 }
685 }
688 void adjustContainsWithAdd(const Polygn& poly, const int p_shape)
689 {
690 for (VertInf *k = vertices.connsBegin(); k != vertices.shapesBegin();
691 k = k->lstNext)
692 {
693 if (inPoly(poly, k->point))
694 {
695 contains[k->id].insert(p_shape);
696 }
697 }
698 }
701 void adjustContainsWithDel(const int p_shape)
702 {
703 for (VertInf *k = vertices.connsBegin(); k != vertices.shapesBegin();
704 k = k->lstNext)
705 {
706 contains[k->id].erase(p_shape);
707 }
708 }
711 // Maybe this one should be in with the connector stuff, but it may later
712 // need to operate on a particular section of the visibility graph so it
713 // may have to stay here.
714 //
715 #define MIN(a, b) (((a) <= (b)) ? (a) : (b))
716 #define MAX(a, b) (((a) >= (b)) ? (a) : (b))
718 #ifdef SELECTIVE_DEBUG
719 static double AngleAFromThreeSides(const double a, const double b,
720 const double c)
721 {
722 // returns angle A, the angle opposite from side a, in radians
723 return acos((pow(b, 2) + pow(c, 2) - pow(a, 2)) / (2 * b * c));
724 }
725 #endif
727 void markConnectors(ShapeRef *shape)
728 {
729 assert(SelectiveReroute);
731 ConnRefList::iterator end = connRefs.end();
732 for (ConnRefList::iterator it = connRefs.begin(); it != end; ++it)
733 {
734 ConnRef *conn = (*it);
736 if (conn->_route.pn == 0)
737 {
738 // Ignore uninitialised connectors.
739 continue;
740 }
742 Point start = conn->_route.ps[0];
743 Point end = conn->_route.ps[conn->_route.pn - 1];
745 double conndist = conn->_route_dist;
747 double estdist;
748 double e1, e2;
750 VertInf *beginV = shape->firstVert();
751 VertInf *endV = shape->lastVert()->lstNext;
752 for (VertInf *i = beginV; i != endV; i = i->lstNext)
753 {
754 const Point& p1 = i->point;
755 const Point& p2 = i->shNext->point;
757 double offy;
758 double a;
759 double b;
760 double c;
761 double d;
763 double min;
764 double max;
766 if (p1.y == p2.y)
767 {
768 // Standard case
769 offy = p1.y;
770 a = start.x;
771 b = start.y - offy;
772 c = end.x;
773 d = end.y - offy;
775 min = MIN(p1.x, p2.x);
776 max = MAX(p1.x, p2.x);
777 }
778 else if (p1.x == p2.x)
779 {
780 // Other Standard case
781 offy = p1.x;
782 a = start.y;
783 b = start.x - offy;
784 c = end.y;
785 d = end.x - offy;
787 min = MIN(p1.y, p2.y);
788 max = MAX(p1.y, p2.y);
789 }
790 else
791 {
792 // Need to do rotation
793 Point n_p2 = { p2.x - p1.x, p2.y - p1.y };
794 Point n_start = { start.x - p1.x, start.y - p1.y };
795 Point n_end = { end.x - p1.x, end.y - p1.y };
796 //printf("n_p2: (%.1f, %.1f)\n", n_p2.x, n_p2.y);
797 //printf("n_start: (%.1f, %.1f)\n", n_start.x, n_start.y);
798 //printf("n_end: (%.1f, %.1f)\n", n_end.x, n_end.y);
800 double theta = 0 - atan2(n_p2.y, n_p2.x);
801 //printf("theta = %.2f\n", theta * (180 / PI));
803 Point r_p1 = {0, 0};
804 Point r_p2 = n_p2;
805 start = n_start;
806 end = n_end;
808 double cosv = cos(theta);
809 double sinv = sin(theta);
811 r_p2.x = cosv * n_p2.x - sinv * n_p2.y;
812 r_p2.y = cosv * n_p2.y + sinv * n_p2.x;
813 start.x = cosv * n_start.x - sinv * n_start.y;
814 start.y = cosv * n_start.y + sinv * n_start.x;
815 end.x = cosv * n_end.x - sinv * n_end.y;
816 end.y = cosv * n_end.y + sinv * n_end.x;
817 //printf("r_p2: (%.1f, %.1f)\n", r_p2.x, r_p2.y);
818 //printf("r_start: (%.1f, %.1f)\n", start.x, start.y);
819 //printf("r_end: (%.1f, %.1f)\n", end.x, end.y);
821 if (((int) r_p2.y) != 0)
822 {
823 printf("r_p2.y: %f != 0\n", r_p2.y);
824 abort();
825 }
826 // This might be slightly off.
827 r_p2.y = 0;
829 offy = r_p1.y;
830 a = start.x;
831 b = start.y - offy;
832 c = end.x;
833 d = end.y - offy;
835 min = MIN(r_p1.x, r_p2.x);
836 max = MAX(r_p1.x, r_p2.x);
838 }
840 double x;
841 if ((b + d) == 0)
842 {
843 db_printf("WARNING: (b + d) == 0\n");
844 d = d * -1;
845 }
847 if ((b == 0) && (d == 0))
848 {
849 db_printf("WARNING: b == d == 0\n");
850 if (((a < min) && (c < min)) ||
851 ((a > max) && (c > max)))
852 {
853 // It's going to get adjusted.
854 x = a;
855 }
856 else
857 {
858 continue;
859 }
860 }
861 else
862 {
863 x = ((b*c) + (a*d)) / (b + d);
864 }
866 //printf("%.1f, %.1f, %.1f, %.1f\n", a, b, c, d);
867 //printf("x = %.1f\n", x);
869 // XXX: Use MAX and MIN
870 x = (x < min) ? min : x;
871 x = (x > max) ? max : x;
873 //printf("x = %.1f\n", x);
875 Point xp;
876 if (p1.x == p2.x)
877 {
878 xp.x = offy;
879 xp.y = x;
880 }
881 else
882 {
883 xp.x = x;
884 xp.y = offy;
885 }
886 //printf("(%.1f, %.1f)\n", xp.x, xp.y);
888 e1 = dist(start, xp);
889 e2 = dist(xp, end);
890 estdist = e1 + e2;
893 //printf("is %.1f < %.1f\n", estdist, conndist);
894 if (estdist < conndist)
895 {
896 #ifdef SELECTIVE_DEBUG
897 //double angle = AngleAFromThreeSides(dist(start, end),
898 // e1, e2);
899 printf("[%3d] - Possible better path found (%.1f < %.1f)\n",
900 conn->_id, estdist, conndist);
901 #endif
902 conn->_needs_reroute_flag = true;
903 break;
904 }
906 }
907 }
908 }
911 void printInfo(void)
912 {
913 FILE *fp = stdout;
914 fprintf(fp, "\nVisibility Graph info:\n");
915 fprintf(fp, "----------------------\n");
917 unsigned int currshape = 0;
918 int st_shapes = 0;
919 int st_vertices = 0;
920 int st_endpoints = 0;
921 int st_valid_shape_visedges = 0;
922 int st_valid_endpt_visedges = 0;
923 int st_invalid_visedges = 0;
924 VertInf *finish = vertices.end();
925 for (VertInf *t = vertices.connsBegin(); t != finish; t = t->lstNext)
926 {
927 VertID pID = t->id;
929 if ((pID.isShape) && (pID.objID != currshape))
930 {
931 currshape = pID.objID;
932 st_shapes++;
933 }
934 if (pID.isShape)
935 {
936 st_vertices++;
937 }
938 else
939 {
940 // The shape 0 ones are temporary and not considered.
941 st_endpoints++;
942 }
943 }
944 for (EdgeInf *t = visGraph.begin(); t != visGraph.end();
945 t = t->lstNext)
946 {
947 std::pair<VertID, VertID> idpair = t->ids();
949 if (!(idpair.first.isShape) || !(idpair.second.isShape))
950 {
951 st_valid_endpt_visedges++;
952 }
953 else
954 {
955 st_valid_shape_visedges++;
956 }
957 }
958 for (EdgeInf *t = invisGraph.begin(); t != invisGraph.end();
959 t = t->lstNext)
960 {
961 st_invalid_visedges++;
962 }
963 fprintf(fp, "Number of shapes: %d\n", st_shapes);
964 fprintf(fp, "Number of vertices: %d (%d real, %d endpoints)\n",
965 st_vertices + st_endpoints, st_vertices, st_endpoints);
966 fprintf(fp, "Number of vis_edges: %d (%d valid [%d normal, %d endpt], "
967 "%d invalid)\n", st_valid_shape_visedges + st_invalid_visedges +
968 st_valid_endpt_visedges, st_valid_shape_visedges +
969 st_valid_endpt_visedges, st_valid_shape_visedges,
970 st_valid_endpt_visedges, st_invalid_visedges);
971 fprintf(fp, "----------------------\n");
972 fprintf(fp, "checkVisEdge tally: %d\n", st_checked_edges);
973 fprintf(fp, "----------------------\n");
975 fprintf(fp, "ADDS: "); timers.Print(tmAdd);
976 fprintf(fp, "DELS: "); timers.Print(tmDel);
977 fprintf(fp, "MOVS: "); timers.Print(tmMov);
978 fprintf(fp, "***S: "); timers.Print(tmSev);
979 fprintf(fp, "PTHS: "); timers.Print(tmPth);
980 fprintf(fp, "\n");
981 }
984 }