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