src/libavoid/router.cpp

   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-2006  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 */
  22
  23 #include <cstdlib>
  24 #include "libavoid/shape.h"
  25 #include "libavoid/router.h"
  26 #include "libavoid/visibility.h"
  27 #include "libavoid/connector.h"
  28 #include "libavoid/polyutil.h"
  29 #include "libavoid/debug.h"
  30 #include "libavoid/region.h"
  31 #include "math.h"
  32
  33 //#define ORTHOGONAL_ROUTING
  34
  35 namespace Avoid {
  36
  37
  38 static const unsigned int infoAdd = 1;
  39 static const unsigned int infoDel = 2;
  40 static const unsigned int infoMov = 3;
  41
  42
  43 class MoveInfo {
  44     public:
  45         MoveInfo(ShapeRef *s, Polygn *p, bool fM)
  46             : shape(s)
  47             , newPoly(copyPoly(*p))
  48             , firstMove(fM)
  49         { }
  50         ~MoveInfo()
  51         {
  52             freePoly(newPoly);
  53         }
  54         ShapeRef *shape;
  55         Polygn newPoly;
  56         bool firstMove;
  57 };
  58
  59
  60
  61 Router::Router()
  62     : PartialTime(false)
  63     , SimpleRouting(false)
  64     , segmt_penalty(0)
  65     , angle_penalty(0)
  66     , crossing_penalty(200)
  67     // Algorithm options:
  68     , UseAStarSearch(true)
  69     , IgnoreRegions(true)
  70     , SelectiveReroute(true)
  71     , IncludeEndpoints(true)
  72     , UseLeesAlgorithm(false)
  73     , InvisibilityGrph(true)
  74     , ConsolidateMoves(true)
  75     , PartialFeedback(false)
  76     // Instrumentation:
  77     , st_checked_edges(0)
  78 #ifdef LINEDEBUG
  79     , avoid_screen(NULL)
  80 #endif
  81 { }
  82
  83
  84
  85
  86 void Router::addShape(ShapeRef *shape)
  87 {
  88     unsigned int pid = shape->id();
  89     Polygn poly = shape->poly();
  90
  91     adjustContainsWithAdd(poly, pid);
  92
  93     // o  Check all visibility edges to see if this one shape
  94     //    blocks them.
  95     newBlockingShape(&poly, pid);
  96
  97 #ifdef ORTHOGONAL_ROUTING
  98     Region::addShape(shape);
  99 #endif
 100
 101     // o  Calculate visibility for the new vertices.
 102     if (UseLeesAlgorithm)
 103     {
 104         shapeVisSweep(shape);
 105     }
 106     else
 107     {
 108         shapeVis(shape);
 109     }
 110     callbackAllInvalidConnectors();
 111 }
 112
 113
 114 void Router::delShape(ShapeRef *shape)
 115 {
 116     unsigned int pid = shape->id();
 117
 118     // Delete items that are queued in the movList.
 119     for (MoveInfoList::iterator it = moveList.begin(); it != moveList.end(); )
 120     {
 121         if ((*it)->shape->id() == pid)
 122         {
 123             MoveInfoList::iterator doomed = it;
 124             ++it;
 125             moveList.erase(doomed);
 126         }
 127         else
 128         {
 129             ++it;
 130         }
 131     }
 132
 133     // o  Remove entries related to this shape's vertices
 134     shape->removeFromGraph();
 135
 136     if (SelectiveReroute)
 137     {
 138         markConnectors(shape);
 139     }
 140
 141     adjustContainsWithDel(pid);
 142
 143 #ifdef ORTHOGONAL_ROUTING
 144     Region::removeShape(shape);
 145 #endif
 146
 147     delete shape;
 148
 149     // o  Check all edges that were blocked by this shape.
 150     if (InvisibilityGrph)
 151     {
 152         checkAllBlockedEdges(pid);
 153     }
 154     else
 155     {
 156         // check all edges not in graph
 157         checkAllMissingEdges();
 158     }
 159     callbackAllInvalidConnectors();
 160 }
 161
 162
 163 void Router::moveShape(ShapeRef *shape, Polygn *newPoly, const bool first_move)
 164 {
 165     // Sanely cope with the case where the user requests moving the same
 166     // shape multiple times before rerouting connectors.
 167     bool alreadyThere = false;
 168     unsigned int id = shape->id();
 169     MoveInfoList::iterator finish = moveList.end();
 170     for (MoveInfoList::iterator it = moveList.begin(); it != finish; ++it)
 171     {
 172         if ((*it)->shape->id() == id)
 173         {
 174             if (!SimpleRouting)
 175             {
 176                 fprintf(stderr,
 177                         "warning: multiple moves requested for shape %d.\n",
 178                         (int) id);
 179             }
 180             // Just update the MoveInfo with the second polygon, but
 181             // leave the firstMove setting alone.
 182             (*it)->newPoly = copyPoly(*newPoly);
 183             alreadyThere = true;
 184         }
 185     }
 186
 187     if (!alreadyThere)
 188     {
 189         MoveInfo *moveInfo = new MoveInfo(shape, newPoly, first_move);
 190         moveList.push_back(moveInfo);
 191     }
 192
 193     if (!ConsolidateMoves)
 194     {
 195         processMoves();
 196     }
 197 }
 198
 199
 200 void Router::processMoves(void)
 201 {
 202     // If SimpleRouting, then don't update yet.
 203     if (moveList.empty() || SimpleRouting)
 204     {
 205         return;
 206     }
 207
 208     MoveInfoList::iterator curr;
 209     MoveInfoList::iterator finish = moveList.end();
 210     for (curr = moveList.begin(); curr != finish; ++curr)
 211     {
 212         MoveInfo *moveInf = *curr;
 213         ShapeRef *shape = moveInf->shape;
 214         Polygn *newPoly = &(moveInf->newPoly);
 215         bool first_move = moveInf->firstMove;
 216
 217         unsigned int pid = shape->id();
 218         bool notPartialTime = !(PartialFeedback && PartialTime);
 219
 220         // o  Remove entries related to this shape's vertices
 221         shape->removeFromGraph();
 222
 223         if (SelectiveReroute && (notPartialTime || first_move))
 224         {
 225             markConnectors(shape);
 226         }
 227
 228         adjustContainsWithDel(pid);
 229
 230 #ifdef ORTHOGONAL_ROUTING
 231         Region::removeShape(shape);
 232 #endif
 233
 234         shape->setNewPoly(*newPoly);
 235
 236         adjustContainsWithAdd(*newPoly, pid);
 237
 238         // Ignore this shape for visibility.
 239         // XXX: We don't really need to do this if we're not using Partial
 240         //      Feedback.  Without this the blocked edges still route
 241         //      around the shape until it leaves the connector.
 242         shape->makeInactive();
 243
 244     }
 245
 246     if (InvisibilityGrph)
 247     {
 248         for (curr = moveList.begin(); curr != finish; ++curr)
 249         {
 250             MoveInfo *moveInf = *curr;
 251             ShapeRef *shape = moveInf->shape;
 252             unsigned int pid = shape->id();
 253
 254             // o  Check all edges that were blocked by this shape.
 255             checkAllBlockedEdges(pid);
 256         }
 257     }
 258     else
 259     {
 260         // check all edges not in graph
 261         checkAllMissingEdges();
 262     }
 263
 264     while ( ! moveList.empty() )
 265     {
 266         MoveInfo *moveInf = moveList.front();
 267         ShapeRef *shape = moveInf->shape;
 268         Polygn *newPoly = &(moveInf->newPoly);
 269
 270         unsigned int pid = shape->id();
 271         bool notPartialTime = !(PartialFeedback && PartialTime);
 272
 273         // Restore this shape for visibility.
 274         shape->makeActive();
 275
 276 #ifdef ORTHOGONAL_ROUTING
 277         Region::addShape(shape);
 278 #endif
 279
 280         // o  Check all visibility edges to see if this one shape
 281         //    blocks them.
 282         if (notPartialTime)
 283         {
 284             newBlockingShape(newPoly, pid);
 285         }
 286
 287         // o  Calculate visibility for the new vertices.
 288         if (UseLeesAlgorithm)
 289         {
 290             shapeVisSweep(shape);
 291         }
 292         else
 293         {
 294             shapeVis(shape);
 295         }
 296
 297         moveList.pop_front();
 298         delete moveInf;
 299     }
 300     callbackAllInvalidConnectors();
 301 }
 302
 303
 304 //----------------------------------------------------------------------------
 305
 306 // XXX: attachedShapes and attachedConns both need to be rewritten
 307 //      for constant time lookup of attached objects once this info
 308 //      is stored better within libavoid.  Also they shouldn't need to
 309 //      be friends of ConnRef.
 310
 311     // Returns a list of connector Ids of all the connectors of type
 312     // 'type' attached to the shape with the ID 'shapeId'.
 313 void Router::attachedConns(IntList &conns, const unsigned int shapeId,
 314         const unsigned int type)
 315 {
 316     ConnRefList::iterator fin = connRefs.end();
 317     for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) {
 318
 319         if ((type & runningTo) && ((*i)->_dstId == shapeId)) {
 320             conns.push_back((*i)->_id);
 321         }
 322         else if ((type & runningFrom) && ((*i)->_srcId == shapeId)) {
 323             conns.push_back((*i)->_id);
 324         }
 325     }
 326 }
 327
 328
 329     // Returns a list of shape Ids of all the shapes attached to the
 330     // shape with the ID 'shapeId' with connection type 'type'.
 331 void Router::attachedShapes(IntList &shapes, const unsigned int shapeId,
 332         const unsigned int type)
 333 {
 334     ConnRefList::iterator fin = connRefs.end();
 335     for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) {
 336         if ((type & runningTo) && ((*i)->_dstId == shapeId)) {
 337             if ((*i)->_srcId != 0)
 338             {
 339                 // Only if there is a shape attached to the other end.
 340                 shapes.push_back((*i)->_srcId);
 341             }
 342         }
 343         else if ((type & runningFrom) && ((*i)->_srcId == shapeId)) {
 344             if ((*i)->_dstId != 0)
 345             {
 346                 // Only if there is a shape attached to the other end.
 347                 shapes.push_back((*i)->_dstId);
 348             }
 349         }
 350     }
 351 }
 352
 353
 354     // It's intended this function is called after shape movement has
 355     // happened to alert connectors that they need to be rerouted.
 356 void Router::callbackAllInvalidConnectors(void)
 357 {
 358     ConnRefList::iterator fin = connRefs.end();
 359     for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) {
 360         (*i)->handleInvalid();
 361     }
 362 }
 363
 364
 365 void Router::newBlockingShape(Polygn *poly, int pid)
 366 {
 367     // o  Check all visibility edges to see if this one shape
 368     //    blocks them.
 369     EdgeInf *finish = visGraph.end();
 370     for (EdgeInf *iter = visGraph.begin(); iter != finish ; )
 371     {
 372         EdgeInf *tmp = iter;
 373         iter = iter->lstNext;
 374
 375         if (tmp->getDist() != 0)
 376         {
 377             std::pair<VertID, VertID> ids(tmp->ids());
 378             VertID eID1 = ids.first;
 379             VertID eID2 = ids.second;
 380             std::pair<Point, Point> points(tmp->points());
 381             Point e1 = points.first;
 382             Point e2 = points.second;
 383             bool blocked = false;
 384
 385             bool ep_in_poly1 = !(eID1.isShape) ? inPoly(*poly, e1) : false;
 386             bool ep_in_poly2 = !(eID2.isShape) ? inPoly(*poly, e2) : false;
 387             if (ep_in_poly1 || ep_in_poly2)
 388             {
 389                 // Don't check edges that have a connector endpoint
 390                 // and are inside the shape being added.
 391                 continue;
 392             }
 393
 394             for (int pt_i = 0; pt_i < poly->pn; pt_i++)
 395             {
 396                 int pt_n = (pt_i == (poly->pn - 1)) ? 0 : pt_i + 1;
 397                 if (segmentIntersect(e1, e2, poly->ps[pt_i], poly->ps[pt_n]))
 398                 {
 399                     blocked = true;
 400                     break;
 401                 }
 402             }
 403             if (blocked)
 404             {
 405                 db_printf("\tRemoving newly blocked edge (by shape %3d)"
 406                         "... \n\t\t", pid);
 407                 tmp->alertConns();
 408                 tmp->db_print();
 409                 if (InvisibilityGrph)
 410                 {
 411                     tmp->addBlocker(pid);
 412                 }
 413                 else
 414                 {
 415                     delete tmp;
 416                 }
 417             }
 418         }
 419     }
 420 }
 421
 422
 423 void Router::checkAllBlockedEdges(int pid)
 424 {
 425     assert(InvisibilityGrph);
 426
 427     for (EdgeInf *iter = invisGraph.begin(); iter != invisGraph.end() ; )
 428     {
 429         EdgeInf *tmp = iter;
 430         iter = iter->lstNext;
 431
 432         if (tmp->_blocker == -1)
 433         {
 434             tmp->alertConns();
 435             tmp->checkVis();
 436         }
 437         else if (tmp->_blocker == pid)
 438         {
 439             tmp->checkVis();
 440         }
 441     }
 442 }
 443
 444
 445 void Router::checkAllMissingEdges(void)
 446 {
 447     assert(!InvisibilityGrph);
 448
 449     VertInf *first = NULL;
 450
 451     if (IncludeEndpoints)
 452     {
 453         first = vertices.connsBegin();
 454     }
 455     else
 456     {
 457         first = vertices.shapesBegin();
 458     }
 459
 460     VertInf *pend = vertices.end();
 461     for (VertInf *i = first; i != pend; i = i->lstNext)
 462     {
 463         VertID iID = i->id;
 464
 465         // Check remaining, earlier vertices
 466         for (VertInf *j = first ; j != i; j = j->lstNext)
 467         {
 468             VertID jID = j->id;
 469             if (!(iID.isShape) && (iID.objID != jID.objID))
 470             {
 471                 // Don't keep visibility between edges of different conns
 472                 continue;
 473             }
 474
 475             // See if the edge is already there?
 476             bool found = (EdgeInf::existingEdge(i, j) != NULL);
 477
 478             if (!found)
 479             {
 480                 // Didn't already exist, check.
 481                 bool knownNew = true;
 482                 EdgeInf::checkEdgeVisibility(i, j, knownNew);
 483             }
 484         }
 485     }
 486 }
 487
 488
 489 void Router::generateContains(VertInf *pt)
 490 {
 491     contains[pt->id].clear();
 492
 493     ShapeRefList::iterator finish = shapeRefs.end();
 494     for (ShapeRefList::iterator i = shapeRefs.begin(); i != finish; ++i)
 495     {
 496         Polygn poly = copyPoly(*i);
 497         if (inPoly(poly, pt->point))
 498         {
 499             contains[pt->id].insert((*i)->id());
 500         }
 501         freePoly(poly);
 502     }
 503 }
 504
 505
 506 void Router::adjustContainsWithAdd(const Polygn& poly, const int p_shape)
 507 {
 508     for (VertInf *k = vertices.connsBegin(); k != vertices.shapesBegin();
 509             k = k->lstNext)
 510     {
 511         if (inPoly(poly, k->point))
 512         {
 513             contains[k->id].insert(p_shape);
 514         }
 515     }
 516 }
 517
 518
 519 void Router::adjustContainsWithDel(const int p_shape)
 520 {
 521     for (VertInf *k = vertices.connsBegin(); k != vertices.shapesBegin();
 522             k = k->lstNext)
 523     {
 524         contains[k->id].erase(p_shape);
 525     }
 526 }
 527
 528
 529 #ifdef SELECTIVE_DEBUG
 530 static double AngleAFromThreeSides(const double a, const double b,
 531         const double c)
 532 {
 533     // returns angle A, the angle opposite from side a, in radians
 534     return acos((pow(b, 2) + pow(c, 2) - pow(a, 2)) / (2 * b * c));
 535 }
 536 #endif
 537
 538 void Router::markConnectors(ShapeRef *shape)
 539 {
 540     assert(SelectiveReroute);
 541
 542     ConnRefList::iterator end = connRefs.end();
 543     for (ConnRefList::iterator it = connRefs.begin(); it != end; ++it)
 544     {
 545         ConnRef *conn = (*it);
 546
 547         if (conn->_route.pn == 0)
 548         {
 549             // Ignore uninitialised connectors.
 550             continue;
 551         }
 552         else if (conn->_needs_reroute_flag)
 553         {
 554             // Already marked, so skip.
 555             continue;
 556         }
 557
 558         Point start = conn->_route.ps[0];
 559         Point end = conn->_route.ps[conn->_route.pn - 1];
 560
 561         double conndist = conn->_route_dist;
 562
 563         double estdist;
 564         double e1, e2;
 565
 566         VertInf *beginV = shape->firstVert();
 567         VertInf *endV = shape->lastVert()->lstNext;
 568         for (VertInf *i = beginV; i != endV; i = i->lstNext)
 569         {
 570             const Point& p1 = i->point;
 571             const Point& p2 = i->shNext->point;
 572
 573             double offy;
 574             double a;
 575             double b;
 576             double c;
 577             double d;
 578
 579             double min;
 580             double max;
 581
 582             if (p1.y == p2.y)
 583             {
 584                 // Standard case
 585                 offy = p1.y;
 586                 a = start.x;
 587                 b = start.y - offy;
 588                 c = end.x;
 589                 d = end.y - offy;
 590
 591                 min = std::min(p1.x, p2.x);
 592                 max = std::max(p1.x, p2.x);
 593             }
 594             else if (p1.x == p2.x)
 595             {
 596                 // Other Standard case
 597                 offy = p1.x;
 598                 a = start.y;
 599                 b = start.x - offy;
 600                 c = end.y;
 601                 d = end.x - offy;
 602
 603                 min = std::min(p1.y, p2.y);
 604                 max = std::max(p1.y, p2.y);
 605             }
 606             else
 607             {
 608                 // Need to do rotation
 609                 Point n_p2(p2.x - p1.x, p2.y - p1.y);
 610                 Point n_start(start.x - p1.x, start.y - p1.y);
 611                 Point n_end(end.x - p1.x, end.y - p1.y);
 612                 //printf("n_p2:    (%.1f, %.1f)\n", n_p2.x, n_p2.y);
 613                 //printf("n_start: (%.1f, %.1f)\n", n_start.x, n_start.y);
 614                 //printf("n_end:   (%.1f, %.1f)\n", n_end.x, n_end.y);
 615
 616                 double theta = 0 - atan2(n_p2.y, n_p2.x);
 617                 //printf("theta = %.2f\n", theta * (180 / PI));
 618
 619                 Point r_p1(0, 0);
 620                 Point r_p2 = n_p2;
 621                 start = n_start;
 622                 end = n_end;
 623
 624                 double cosv = cos(theta);
 625                 double sinv = sin(theta);
 626
 627                 r_p2.x = cosv * n_p2.x - sinv * n_p2.y;
 628                 r_p2.y = cosv * n_p2.y + sinv * n_p2.x;
 629                 start.x = cosv * n_start.x - sinv * n_start.y;
 630                 start.y = cosv * n_start.y + sinv * n_start.x;
 631                 end.x = cosv * n_end.x - sinv * n_end.y;
 632                 end.y = cosv * n_end.y + sinv * n_end.x;
 633                 //printf("r_p2:    (%.1f, %.1f)\n", r_p2.x, r_p2.y);
 634                 //printf("r_start: (%.1f, %.1f)\n", start.x, start.y);
 635                 //printf("r_end:   (%.1f, %.1f)\n", end.x, end.y);
 636
 637                 if (((int) r_p2.y) != 0)
 638                 {
 639                     printf("r_p2.y: %f != 0\n", r_p2.y);
 640                     std::abort();
 641                 }
 642                 // This might be slightly off.
 643                 r_p2.y = 0;
 644
 645                 offy = r_p1.y;
 646                 a = start.x;
 647                 b = start.y - offy;
 648                 c = end.x;
 649                 d = end.y - offy;
 650
 651                 min = std::min(r_p1.x, r_p2.x);
 652                 max = std::max(r_p1.x, r_p2.x);
 653
 654             }
 655
 656             double x;
 657             if ((b + d) == 0)
 658             {
 659                 db_printf("WARNING: (b + d) == 0\n");
 660                 d = d * -1;
 661             }
 662
 663             if ((b == 0) && (d == 0))
 664             {
 665                 db_printf("WARNING: b == d == 0\n");
 666                 if (((a < min) && (c < min)) ||
 667                         ((a > max) && (c > max)))
 668                 {
 669                     // It's going to get adjusted.
 670                     x = a;
 671                 }
 672                 else
 673                 {
 674                     continue;
 675                 }
 676             }
 677             else
 678             {
 679                 x = ((b*c) + (a*d)) / (b + d);
 680             }
 681
 682             //printf("%.1f, %.1f, %.1f, %.1f\n", a, b, c, d);
 683             //printf("x = %.1f\n", x);
 684
 685             x = std::max(min, x);
 686             x = std::min(max, x);
 687
 688             //printf("x = %.1f\n", x);
 689
 690             Point xp;
 691             if (p1.x == p2.x)
 692             {
 693                 xp.x = offy;
 694                 xp.y = x;
 695             }
 696             else
 697             {
 698                 xp.x = x;
 699                 xp.y = offy;
 700             }
 701             //printf("(%.1f, %.1f)\n", xp.x, xp.y);
 702
 703             e1 = dist(start, xp);
 704             e2 = dist(xp, end);
 705             estdist = e1 + e2;
 706
 707
 708             //printf("is %.1f < %.1f\n", estdist, conndist);
 709             if (estdist < conndist)
 710             {
 711 #ifdef SELECTIVE_DEBUG
 712                 //double angle = AngleAFromThreeSides(dist(start, end),
 713                 //        e1, e2);
 714                 printf("[%3d] - Possible better path found (%.1f < %.1f)\n",
 715                         conn->_id, estdist, conndist);
 716 #endif
 717                 conn->_needs_reroute_flag = true;
 718                 break;
 719             }
 720
 721         }
 722     }
 723 }
 724
 725
 726 void Router::printInfo(void)
 727 {
 728     FILE *fp = stdout;
 729     fprintf(fp, "\nVisibility Graph info:\n");
 730     fprintf(fp, "----------------------\n");
 731
 732     unsigned int currshape = 0;
 733     int st_shapes = 0;
 734     int st_vertices = 0;
 735     int st_endpoints = 0;
 736     int st_valid_shape_visedges = 0;
 737     int st_valid_endpt_visedges = 0;
 738     int st_invalid_visedges = 0;
 739     VertInf *finish = vertices.end();
 740     for (VertInf *t = vertices.connsBegin(); t != finish; t = t->lstNext)
 741     {
 742         VertID pID = t->id;
 743
 744         if ((pID.isShape) && (pID.objID != currshape))
 745         {
 746             currshape = pID.objID;
 747             st_shapes++;
 748         }
 749         if (pID.isShape)
 750         {
 751             st_vertices++;
 752         }
 753         else
 754         {
 755             // The shape 0 ones are temporary and not considered.
 756             st_endpoints++;
 757         }
 758     }
 759     for (EdgeInf *t = visGraph.begin(); t != visGraph.end();
 760             t = t->lstNext)
 761     {
 762         std::pair<VertID, VertID> idpair = t->ids();
 763
 764         if (!(idpair.first.isShape) || !(idpair.second.isShape))
 765         {
 766             st_valid_endpt_visedges++;
 767         }
 768         else
 769         {
 770             st_valid_shape_visedges++;
 771         }
 772     }
 773     for (EdgeInf *t = invisGraph.begin(); t != invisGraph.end();
 774             t = t->lstNext)
 775     {
 776         st_invalid_visedges++;
 777     }
 778     fprintf(fp, "Number of shapes: %d\n", st_shapes);
 779     fprintf(fp, "Number of vertices: %d (%d real, %d endpoints)\n",
 780             st_vertices + st_endpoints, st_vertices, st_endpoints);
 781     fprintf(fp, "Number of vis_edges: %d (%d valid [%d normal, %d endpt], "
 782             "%d invalid)\n", st_valid_shape_visedges + st_invalid_visedges +
 783             st_valid_endpt_visedges, st_valid_shape_visedges +
 784             st_valid_endpt_visedges, st_valid_shape_visedges,
 785             st_valid_endpt_visedges, st_invalid_visedges);
 786     fprintf(fp, "----------------------\n");
 787     fprintf(fp, "checkVisEdge tally: %d\n", st_checked_edges);
 788     fprintf(fp, "----------------------\n");
 789
 790     fprintf(fp, "ADDS:  "); timers.Print(tmAdd);
 791     fprintf(fp, "DELS:  "); timers.Print(tmDel);
 792     fprintf(fp, "MOVS:  "); timers.Print(tmMov);
 793     fprintf(fp, "***S:  "); timers.Print(tmSev);
 794     fprintf(fp, "PTHS:  "); timers.Print(tmPth);
 795     fprintf(fp, "\n");
 796 }
 797
 798
 799 }
 800