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