src/libavoid/graph.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-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 */
  22
  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"
  28
  29 #include <math.h>
  30
  31 namespace Avoid {
  32
  33
  34 static int st_checked_edges = 0;
  35
  36 EdgeList visGraph;
  37 EdgeList invisGraph;
  38
  39
  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 }
  52
  53
  54 EdgeInf::~EdgeInf()
  55 {
  56     if (_added)
  57     {
  58         makeInactive();
  59     }
  60 }
  61
  62
  63 void EdgeInf::makeActive(void)
  64 {
  65     assert(_added == false);
  66
  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 }
  85
  86
  87 void EdgeInf::makeInactive(void)
  88 {
  89     assert(_added == true);
  90
  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 }
 111
 112
 113 double EdgeInf::getDist(void)
 114 {
 115     return _dist;
 116 }
 117
 118
 119 void EdgeInf::setDist(double dist)
 120 {
 121     //assert(dist != 0);
 122
 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 }
 135
 136
 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 }
 145
 146
 147 void EdgeInf::addConn(bool *flag)
 148 {
 149     _conns.push_back(flag);
 150 }
 151
 152
 153 void EdgeInf::addCycleBlocker(void)
 154 {
 155     // Needs to be in invisibility graph.
 156     addBlocker(-1);
 157 }
 158
 159
 160 void EdgeInf::addBlocker(int b)
 161 {
 162     assert(InvisibilityGrph);
 163
 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 }
 177
 178
 179 bool EdgeInf::hasBlocker(int b)
 180 {
 181     assert(InvisibilityGrph);
 182
 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 }
 198
 199
 200 pair<VertID, VertID> EdgeInf::ids(void)
 201 {
 202     return std::make_pair(_v1->id, _v2->id);
 203 }
 204
 205
 206 pair<Point, Point> EdgeInf::points(void)
 207 {
 208     return std::make_pair(_v1->point, _v2->point);
 209 }
 210
 211
 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 }
 220
 221
 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     }
 236
 237     int blocker = 0;
 238     bool cone1 = true;
 239     bool cone2 = true;
 240
 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;
 247
 248     st_checked_edges++;
 249
 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];
 258
 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     }
 267
 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];
 279
 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     }
 289
 290     if (cone1 && cone2 && ((blocker = firstBlocker()) == 0))
 291     {
 292
 293         // if i and j see each other, add edge
 294         db_printf("\tSetting visibility edge... \n\t\t");
 295         db_print();
 296
 297         double d = dist(iPoint, jPoint);
 298
 299         setDist(d);
 300
 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
 310
 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 }
 317
 318
 319 int EdgeInf::firstBlocker(void)
 320 {
 321     ShapeSet ss = ShapeSet();
 322
 323     Point& pti = _v1->point;
 324     Point& ptj = _v2->point;
 325     VertID& iID = _v1->id;
 326     VertID& jID = _v2->id;
 327
 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     }
 336
 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;
 356
 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 }
 367
 368
 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 }
 378
 379
 380 VertInf *EdgeInf::otherVert(VertInf *vert)
 381 {
 382     assert((vert == _v1) || (vert == _v2));
 383
 384     if (vert == _v1)
 385     {
 386         return _v2;
 387     }
 388     return _v1;
 389 }
 390
 391
 392 EdgeInf *EdgeInf::checkEdgeVisibility(VertInf *i, VertInf *j, bool knownNew)
 393 {
 394     EdgeInf *edge = NULL;
 395
 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     }
 415
 416     return edge;
 417 }
 418
 419
 420 EdgeInf *EdgeInf::existingEdge(VertInf *i, VertInf *j)
 421 {
 422     VertInf *selected = NULL;
 423
 424     if (i->visListSize <= j->visListSize)
 425     {
 426         selected = i;
 427     }
 428     else
 429     {
 430         selected = j;
 431     }
 432
 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     }
 443
 444     if (i->invisListSize <= j->invisListSize)
 445     {
 446         selected = i;
 447     }
 448     else
 449     {
 450         selected = j;
 451     }
 452
 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     }
 463
 464     return NULL;
 465 }
 466
 467
 468 //===========================================================================
 469
 470
 471 EdgeList::EdgeList()
 472     : _firstEdge(NULL)
 473     , _lastEdge(NULL)
 474     , _count(0)
 475 {
 476 }
 477
 478
 479 void EdgeList::addEdge(EdgeInf *edge)
 480 {
 481     if (_firstEdge == NULL)
 482     {
 483         assert(_lastEdge == NULL);
 484
 485         _lastEdge = edge;
 486         _firstEdge = edge;
 487
 488         edge->lstPrev = NULL;
 489         edge->lstNext = NULL;
 490     }
 491     else
 492     {
 493         assert(_lastEdge != NULL);
 494
 495         _lastEdge->lstNext = edge;
 496         edge->lstPrev = _lastEdge;
 497
 498         _lastEdge = edge;
 499
 500         edge->lstNext = NULL;
 501     }
 502     _count++;
 503 }
 504
 505
 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     }
 528
 529
 530     edge->lstPrev = NULL;
 531     edge->lstNext = NULL;
 532
 533     _count--;
 534 }
 535
 536
 537 EdgeInf *EdgeList::begin(void)
 538 {
 539     return _firstEdge;
 540 }
 541
 542
 543 EdgeInf *EdgeList::end(void)
 544 {
 545     return NULL;
 546 }
 547
 548
 549 // General visibility graph utility functions
 550
 551
 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;
 561
 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;
 571
 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             }
 580
 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 }
 608
 609
 610 void checkAllBlockedEdges(int pid)
 611 {
 612     assert(InvisibilityGrph);
 613
 614     for (EdgeInf *iter = invisGraph.begin(); iter != invisGraph.end() ; )
 615     {
 616         EdgeInf *tmp = iter;
 617         iter = iter->lstNext;
 618
 619         if (tmp->hasBlocker(pid))
 620         {
 621             tmp->checkVis();
 622         }
 623     }
 624 }
 625
 626
 627 void checkAllMissingEdges(void)
 628 {
 629     assert(!InvisibilityGrph);
 630
 631     VertInf *first = NULL;
 632
 633     if (IncludeEndpoints)
 634     {
 635         first = vertices.connsBegin();
 636     }
 637     else
 638     {
 639         first = vertices.shapesBegin();
 640     }
 641
 642     VertInf *pend = vertices.end();
 643     for (VertInf *i = first; i != pend; i = i->lstNext)
 644     {
 645         VertID iID = i->id;
 646
 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             }
 656
 657             // See if the edge is already there?
 658             bool found = (EdgeInf::existingEdge(i, j) != NULL);
 659
 660             if (!found)
 661             {
 662                 // Didn't already exist, check.
 663                 bool knownNew = true;
 664                 EdgeInf::checkEdgeVisibility(i, j, knownNew);
 665             }
 666         }
 667     }
 668 }
 669
 670
 671 void generateContains(VertInf *pt)
 672 {
 673     contains[pt->id].clear();
 674
 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 }
 686
 687
 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 }
 699
 700
 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 }
 709
 710
 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))
 717
 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
 726
 727 void markConnectors(ShapeRef *shape)
 728 {
 729     assert(SelectiveReroute);
 730
 731     ConnRefList::iterator end = connRefs.end();
 732     for (ConnRefList::iterator it = connRefs.begin(); it != end; ++it)
 733     {
 734         ConnRef *conn = (*it);
 735
 736         if (conn->_route.pn == 0)
 737         {
 738             // Ignore uninitialised connectors.
 739             continue;
 740         }
 741
 742         Point start = conn->_route.ps[0];
 743         Point end = conn->_route.ps[conn->_route.pn - 1];
 744
 745         double conndist = conn->_route_dist;
 746
 747         double estdist;
 748         double e1, e2;
 749
 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;
 756
 757             double offy;
 758             double a;
 759             double b;
 760             double c;
 761             double d;
 762
 763             double min;
 764             double max;
 765
 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;
 774
 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;
 786
 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);
 799
 800                 double theta = 0 - atan2(n_p2.y, n_p2.x);
 801                 //printf("theta = %.2f\n", theta * (180 / PI));
 802
 803                 Point r_p1 = {0, 0};
 804                 Point r_p2 = n_p2;
 805                 start = n_start;
 806                 end = n_end;
 807
 808                 double cosv = cos(theta);
 809                 double sinv = sin(theta);
 810
 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);
 820
 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;
 828
 829                 offy = r_p1.y;
 830                 a = start.x;
 831                 b = start.y - offy;
 832                 c = end.x;
 833                 d = end.y - offy;
 834
 835                 min = MIN(r_p1.x, r_p2.x);
 836                 max = MAX(r_p1.x, r_p2.x);
 837
 838             }
 839
 840             double x;
 841             if ((b + d) == 0)
 842             {
 843                 db_printf("WARNING: (b + d) == 0\n");
 844                 d = d * -1;
 845             }
 846
 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             }
 865
 866             //printf("%.1f, %.1f, %.1f, %.1f\n", a, b, c, d);
 867             //printf("x = %.1f\n", x);
 868
 869             // XXX: Use MAX and MIN
 870             x = (x < min) ? min : x;
 871             x = (x > max) ? max : x;
 872
 873             //printf("x = %.1f\n", x);
 874
 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);
 887
 888             e1 = dist(start, xp);
 889             e2 = dist(xp, end);
 890             estdist = e1 + e2;
 891
 892
 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             }
 905
 906         }
 907     }
 908 }
 909
 910
 911 void printInfo(void)
 912 {
 913     FILE *fp = stdout;
 914     fprintf(fp, "\nVisibility Graph info:\n");
 915     fprintf(fp, "----------------------\n");
 916
 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;
 928
 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();
 948
 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");
 974
 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 }
 982
 983
 984 }
 985
 986