/* * vim: ts=4 sw=4 et tw=0 wm=0 * * libavoid - Fast, Incremental, Object-avoiding Line Router * Copyright (C) 2004-2006 Michael Wybrow <mjwybrow@users.sourceforge.net> * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public * License as published by the Free Software Foundation; either * version 2.1 of the License, or (at your option) any later version. * * This library is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this library; if not, write to the Free Software * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA * */ #include "libavoid/debug.h" #include "libavoid/graph.h" #include "libavoid/connector.h" #include "libavoid/geometry.h" #include "libavoid/polyutil.h" #include "libavoid/timer.h" #include "libavoid/vertices.h" #include "libavoid/router.h" #include <math.h> using std::pair; namespace Avoid { EdgeInf::EdgeInf(VertInf *v1, VertInf *v2) : lstPrev(NULL) , lstNext(NULL) , _blocker(0) , _router(NULL) , _added(false) , _visible(false) , _v1(v1) , _v2(v2) , _dist(-1) { // Not passed NULL values. assert(v1 && v2); // We are in the same instance assert(_v1->_router == _v2->_router); _router = _v1->_router; _conns.clear(); } EdgeInf::~EdgeInf() { if (_added) { makeInactive(); } } void EdgeInf::makeActive(void) { assert(_added == false); if (_visible) { _router->visGraph.addEdge(this); _pos1 = _v1->visList.insert(_v1->visList.begin(), this); _v1->visListSize++; _pos2 = _v2->visList.insert(_v2->visList.begin(), this); _v2->visListSize++; } else // if (invisible) { _router->invisGraph.addEdge(this); _pos1 = _v1->invisList.insert(_v1->invisList.begin(), this); _v1->invisListSize++; _pos2 = _v2->invisList.insert(_v2->invisList.begin(), this); _v2->invisListSize++; } _added = true; } void EdgeInf::makeInactive(void) { assert(_added == true); if (_visible) { _router->visGraph.removeEdge(this); _v1->visList.erase(_pos1); _v1->visListSize--; _v2->visList.erase(_pos2); _v2->visListSize--; } else // if (invisible) { _router->invisGraph.removeEdge(this); _v1->invisList.erase(_pos1); _v1->invisListSize--; _v2->invisList.erase(_pos2); _v2->invisListSize--; } _blocker = 0; _conns.clear(); _added = false; } void EdgeInf::setDist(double dist) { //assert(dist != 0); if (_added && !_visible) { makeInactive(); } if (!_added) { _visible = true; makeActive(); } _dist = dist; _blocker = 0; } void EdgeInf::alertConns(void) { FlagList::iterator finish = _conns.end(); for (FlagList::iterator i = _conns.begin(); i != finish; ++i) { *(*i) = true; } _conns.clear(); } void EdgeInf::addConn(bool *flag) { _conns.push_back(flag); } void EdgeInf::addCycleBlocker(void) { // Needs to be in invisibility graph. addBlocker(-1); } void EdgeInf::addBlocker(int b) { assert(_router->InvisibilityGrph); if (_added && _visible) { makeInactive(); } if (!_added) { _visible = false; makeActive(); } _dist = 0; _blocker = b; } pair<VertID, VertID> EdgeInf::ids(void) { return std::make_pair(_v1->id, _v2->id); } pair<Point, Point> EdgeInf::points(void) { return std::make_pair(_v1->point, _v2->point); } void EdgeInf::db_print(void) { db_printf("Edge("); _v1->id.db_print(); db_printf(","); _v2->id.db_print(); db_printf(")\n"); } void EdgeInf::checkVis(void) { if (_added && !_visible) { db_printf("\tChecking visibility for existing invisibility edge..." "\n\t\t"); db_print(); } else if (_added && _visible) { db_printf("\tChecking visibility for existing visibility edge..." "\n\t\t"); db_print(); } int blocker = 0; bool cone1 = true; bool cone2 = true; VertInf *i = _v1; VertInf *j = _v2; const VertID& iID = i->id; const VertID& jID = j->id; const Point& iPoint = i->point; const Point& jPoint = j->point; _router->st_checked_edges++; if (iID.isShape) { cone1 = inValidRegion(_router->IgnoreRegions, i->shPrev->point, iPoint, i->shNext->point, jPoint); } else { ShapeSet& ss = _router->contains[iID]; if ((jID.isShape) && (ss.find(jID.objID) != ss.end())) { db_printf("1: Edge of bounding shape\n"); // Don't even check this edge, it should be zero, // since a point in a shape can't see it's corners cone1 = false; } } if (cone1) { // If outside the first cone, don't even bother checking. if (jID.isShape) { cone2 = inValidRegion(_router->IgnoreRegions, j->shPrev->point, jPoint, j->shNext->point, iPoint); } else { ShapeSet& ss = _router->contains[jID]; if ((iID.isShape) && (ss.find(iID.objID) != ss.end())) { db_printf("2: Edge of bounding shape\n"); // Don't even check this edge, it should be zero, // since a point in a shape can't see it's corners cone2 = false; } } } if (cone1 && cone2 && ((blocker = firstBlocker()) == 0)) { // if i and j see each other, add edge db_printf("\tSetting visibility edge... \n\t\t"); db_print(); double d = dist(iPoint, jPoint); setDist(d); } else if (_router->InvisibilityGrph) { #if 0 db_printf("%d, %d, %d\n", cone1, cone2, blocker); db_printf("\t(%d, %d)--(%d, %d)\n", (int) iInfo.point.x, (int) iInfo.point.y, (int) jInfo.point.x, (int) jInfo.point.y); #endif // if i and j can't see each other, add blank edge db_printf("\tSetting invisibility edge... \n\t\t"); db_print(); addBlocker(blocker); } } int EdgeInf::firstBlocker(void) { ShapeSet ss = ShapeSet(); Point& pti = _v1->point; Point& ptj = _v2->point; VertID& iID = _v1->id; VertID& jID = _v2->id; ContainsMap &contains = _router->contains; if (!(iID.isShape)) { ss.insert(contains[iID].begin(), contains[iID].end()); } if (!(jID.isShape)) { ss.insert(contains[jID].begin(), contains[jID].end()); } VertInf *last = _router->vertices.end(); for (VertInf *k = _router->vertices.shapesBegin(); k != last; ) { VertID kID = k->id; if ((ss.find(kID.objID) != ss.end())) { unsigned int shapeID = kID.objID; db_printf("Endpoint is inside shape %u so ignore shape edges.\n", kID.objID); // One of the endpoints is inside this shape so ignore it. while ((k != last) && (k->id.objID == shapeID)) { // And skip the other vertices from this shape. k = k->lstNext; } continue; } Point& kPoint = k->point; Point& kPrevPoint = k->shPrev->point; if (segmentIntersect(pti, ptj, kPrevPoint, kPoint)) { ss.clear(); return kID.objID; } k = k->lstNext; } ss.clear(); return 0; } bool EdgeInf::isBetween(VertInf *i, VertInf *j) { if ( ((i == _v1) && (j == _v2)) || ((i == _v2) && (j == _v1)) ) { return true; } return false; } VertInf *EdgeInf::otherVert(VertInf *vert) { assert((vert == _v1) || (vert == _v2)); if (vert == _v1) { return _v2; } return _v1; } EdgeInf *EdgeInf::checkEdgeVisibility(VertInf *i, VertInf *j, bool knownNew) { Router *router = i->_router; EdgeInf *edge = NULL; if (knownNew) { assert(existingEdge(i, j) == NULL); edge = new EdgeInf(i, j); } else { edge = existingEdge(i, j); if (edge == NULL) { edge = new EdgeInf(i, j); } } edge->checkVis(); if (!(edge->_added) && !(router->InvisibilityGrph)) { delete edge; edge = NULL; } return edge; } EdgeInf *EdgeInf::existingEdge(VertInf *i, VertInf *j) { VertInf *selected = NULL; if (i->visListSize <= j->visListSize) { selected = i; } else { selected = j; } EdgeInfList& visList = selected->visList; EdgeInfList::iterator finish = visList.end(); for (EdgeInfList::iterator edge = visList.begin(); edge != finish; ++edge) { if ((*edge)->isBetween(i, j)) { return (*edge); } } if (i->invisListSize <= j->invisListSize) { selected = i; } else { selected = j; } EdgeInfList& invisList = selected->invisList; finish = invisList.end(); for (EdgeInfList::iterator edge = invisList.begin(); edge != finish; ++edge) { if ((*edge)->isBetween(i, j)) { return (*edge); } } return NULL; } //=========================================================================== EdgeList::EdgeList() : _firstEdge(NULL) , _lastEdge(NULL) , _count(0) { } void EdgeList::addEdge(EdgeInf *edge) { if (_firstEdge == NULL) { assert(_lastEdge == NULL); _lastEdge = edge; _firstEdge = edge; edge->lstPrev = NULL; edge->lstNext = NULL; } else { assert(_lastEdge != NULL); _lastEdge->lstNext = edge; edge->lstPrev = _lastEdge; _lastEdge = edge; edge->lstNext = NULL; } _count++; } void EdgeList::removeEdge(EdgeInf *edge) { if (edge->lstPrev) { edge->lstPrev->lstNext = edge->lstNext; } if (edge->lstNext) { edge->lstNext->lstPrev = edge->lstPrev; } if (edge == _lastEdge) { _lastEdge = edge->lstPrev; if (edge == _firstEdge) { _firstEdge = NULL; } } else if (edge == _firstEdge) { _firstEdge = edge->lstNext; } edge->lstPrev = NULL; edge->lstNext = NULL; _count--; } EdgeInf *EdgeList::begin(void) { return _firstEdge; } EdgeInf *EdgeList::end(void) { return NULL; } }