ext/OGDF/src/energybased/UniformGrid.cpp

   1 /*
   2  * $Revision: 2616 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-16 15:34:43 +0200 (Mo, 16. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Implementation of class UniformGrid
  11  *
  12  * \author Rene Weiskircher
  13  *
  14  * \par License:
  15  * This file is part of the Open Graph Drawing Framework (OGDF).
  16  *
  17  * \par
  18  * Copyright (C)<br>
  19  * See README.txt in the root directory of the OGDF installation for details.
  20  *
  21  * \par
  22  * This program is free software; you can redistribute it and/or
  23  * modify it under the terms of the GNU General Public License
  24  * Version 2 or 3 as published by the Free Software Foundation;
  25  * see the file LICENSE.txt included in the packaging of this file
  26  * for details.
  27  *
  28  * \par
  29  * This program is distributed in the hope that it will be useful,
  30  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  31  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  32  * GNU General Public License for more details.
  33  *
  34  * \par
  35  * You should have received a copy of the GNU General Public
  36  * License along with this program; if not, write to the Free
  37  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  38  * Boston, MA 02110-1301, USA.
  39  *
  40  * \see  http://www.gnu.org/copyleft/gpl.html
  41  ***************************************************************/
  42
  43 #include<ogdf/internal/energybased/UniformGrid.h>
  44 #include<float.h>
  45
  46 namespace ogdf {
  47         const double UniformGrid::m_epsilon = 0.000001;
  48         const double UniformGrid::m_edgeMultiplier = 1.0;
  49
  50 //      int UniformGrid::constructorcounter = 0;
  51
  52         void UniformGrid::ModifiedBresenham(
  53                 const IPoint &p1,
  54                 const IPoint &p2,
  55                 SList<IPoint> &crossedCells) const{
  56                 crossedCells.clear();
  57
  58                 int Ax = p1.m_x;
  59                 int Ay = p1.m_y;
  60                 int Bx = p2.m_x;
  61                 int By = p2.m_y;
  62                 //------------------------------------------------------------------------
  63                 // INITIALIZE THE COMPONENTS OF THE ALGORITHM THAT ARE NOT AFFECTED BY THE
  64                 // SLOPE OR DIRECTION OF THE LINE
  65                 //------------------------------------------------------------------------
  66                 int dX = abs(Bx-Ax);    // store the change in X and Y of the line endpoints
  67                 int dY = abs(By-Ay);
  68
  69                 //------------------------------------------------------------------------
  70                 // DETERMINE "DIRECTIONS" TO INCREMENT X AND Y (REGARDLESS OF DECISION)
  71                 //------------------------------------------------------------------------
  72                 int Xincr, Yincr,Xoffset,Yoffset;
  73                 if (Ax > Bx) { Xincr=-1; Xoffset = -1;} else { Xincr=1; Xoffset = 0;}   // which direction in X?
  74                 if (Ay > By) { Yincr=-1; Yoffset = -1;} else { Yincr=1; Yoffset = 0;}   // which direction in Y?
  75                 // the offsets are necessary because we always want the cell left and below
  76                 // the point were bresenham wants to draw it
  77
  78                 //------------------------------------------------------------------------
  79                 // DETERMINE INDEPENDENT VARIABLE (ONE THAT ALWAYS INCREMENTS BY 1 (OR -1) )
  80                 // AND INITIATE APPROPRIATE LINE DRAWING ROUTINE (BASED ON FIRST OCTANT
  81                 // ALWAYS). THE X AND Y'S MAY BE FLIPPED IF Y IS THE INDEPENDENT VARIABLE.
  82                 //------------------------------------------------------------------------
  83                 if (dX >= dY)   // if X is the independent variable
  84                 {
  85                         int dPr         = dY<<1;  // amount to increment decision if right is chosen (always)
  86                         int dPru        = dPr - (dX<<1);   // amount to increment decision if up is chosen
  87                         int P           = dPr - dX;  // decision variable start value
  88                         int secondY = Ay+Yincr; //Y-coordinate of secondary point
  89                         int testval = P;        //if P is equal to testval, the the next point is drawn exactly
  90                                                                 // on the segment. If P is smaller than testval, it is below the
  91                                                                 //segment
  92
  93
  94                         for (; dX>=0; dX--)  // process each point in the line one at a time (just use dX)
  95                         {
  96                                 crossedCells.pushBack(IPoint(Ax+Xoffset,Ay+Yoffset));//add the primary cell
  97                                 crossedCells.pushBack(IPoint(Ax+Xoffset,secondY+Yoffset));//add the secondary cell
  98                                 if (P > 0)          // is the pixel going right AND up?
  99                                 {
 100                                         Ax+=Xincr;             // increment independent variable
 101                                         Ay+=Yincr;         // increment dependent variable
 102                                         P+=dPru;           // increment decision (for up)
 103                                 }
 104                                 else                     // is the pixel just going right?
 105                                 {
 106                                         Ax+=Xincr;         // increment independent variable
 107                                         P+=dPr;            // increment decision (for right)
 108                                 }
 109                                 if(P - testval < 0) //primary cell above the line
 110                                         secondY = Ay-Yincr;
 111                                 else secondY = Ay+Yincr;//primary cell below the line
 112                         }
 113                 }
 114                 else              // if Y is the independent variable
 115                 {
 116                         int dPr         = dX<<1;    // amount to increment decision if right is chosen (always)
 117                         int dPru        = dPr - (dY<<1);   // amount to increment decision if up is chosen
 118                         int P           = dPr - dY;  // decision variable start value
 119                         int testval = P; // substracting this from P tells us if the cell is drawn left or
 120                                                         // right from the actual segment
 121                         int secondX = Ax+Xincr; //X-Coordinate of secondary cell
 122
 123                         for (; dY>=0; dY--)            // process each point in the line one at a time (just use dY)
 124                         {
 125                                 crossedCells.pushBack(IPoint(Ax+Xoffset,Ay+Yoffset));// add the primary cell
 126                                 crossedCells.pushBack(IPoint(secondX+Xoffset,Ay+Yoffset));// add the secondary cell
 127                                 if (P > 0)               // is the pixel going up AND right?
 128                                 {
 129                                         Ax+=Xincr;         // increment dependent variable
 130                                         Ay+=Yincr;         // increment independent variable
 131                                         P+=dPru;           // increment decision (for up)
 132                                 }
 133                                 else                     // is the pixel just going up?
 134                                 {
 135                                         Ay+=Yincr;         // increment independent variable
 136                                         P+=dPr;            // increment decision (for right)
 137                                 }
 138                                 if(P - testval < 0) //primary cell left of the line
 139                                         secondX = Ax-Xincr;
 140                                 else secondX = Ax+Xincr;//primary cell right of the line
 141                         }
 142                 }
 143
 144         }
 145
 146         void UniformGrid::DoubleModifiedBresenham(
 147                 const DPoint &p1,
 148                 const DPoint &p2,
 149                 SList<IPoint> &crossedCells) const{
 150                 crossedCells.clear();
 151                 //------------------------------------------------------------------------
 152                 // INITIALIZE THE COMPONENTS OF THE ALGORITHM THAT ARE NOT AFFECTED BY THE
 153                 // SLOPE OR DIRECTION OF THE LINE
 154                 //------------------------------------------------------------------------
 155                 double dX = fabs(p2.m_x-p1.m_x);        // store the change in X and Y of the line endpoints
 156                 double dY = fabs(p1.m_y-p2.m_y);
 157
 158
 159                 //------------------------------------------------------------------------
 160                 // DETERMINE INDEPENDENT VARIABLE (ONE THAT ALWAYS INCREMENTS BY 1 (OR -1) )
 161                 // AND INITIATE APPROPRIATE LINE DRAWING ROUTINE (BASED ON FIRST OCTANT
 162                 // ALWAYS). THE X AND Y'S MAY BE FLIPPED IF Y IS THE INDEPENDENT VARIABLE.
 163                 //------------------------------------------------------------------------
 164                 if (dX >= dY)   // if X is the independent variable
 165                 {
 166                         DPoint left,right;
 167                         if(p1.m_x > p2.m_x) {
 168                                 left = p2;
 169                                 right = p1;
 170                         }
 171                         else {
 172                                 left = p1;
 173                                 right= p2;
 174                         }
 175                         //Now we determine the coordinates of the start cell
 176                         //and the end cell
 177                         IPoint start(computeGridPoint(left));
 178                         if(p1 == p2) {
 179                                 crossedCells.pushBack(start);
 180                                 return;
 181                         }
 182                         IPoint end(computeGridPoint(right));
 183                         //Since computeGridPoint rounds down, this gives us the point p1 and
 184                         //below each of the points. This is the address of the cell that contains
 185                         //the point
 186                         //int Yincr = 1;
 187                         //if(left.m_y > right.m_y) Yincr = -1;
 188                         double slope = (right.m_y-left.m_y)/(right.m_x-left.m_x);
 189                         double c = left.m_y-slope*left.m_x;
 190                         OGDF_ASSERT(fabs(slope*right.m_x+c - right.m_y) < m_epsilon);
 191                         int endX = end.m_x+1;
 192                         double dYincr = slope * m_CellSize;
 193                         double OldYPos = slope*start.m_x*m_CellSize+c;
 194                         int oldY = (int)floor(OldYPos/m_CellSize);
 195                         for(int i = start.m_x; i <= endX; i++) {
 196                                 crossedCells.pushBack(IPoint(i,oldY));
 197                                 double newY = OldYPos + dYincr;
 198                                 OGDF_ASSERT(newY - ((i+1)*m_CellSize*slope+c) < m_epsilon)
 199                                 int newCellY = (int)floor(newY/m_CellSize);
 200                                 if(newCellY != oldY) {
 201                                         oldY = newCellY;
 202                                         crossedCells.pushBack(IPoint(i,oldY));
 203                                 }
 204                                 OldYPos = newY;
 205                         }
 206                 }
 207                 else              // if Y is the independent variable
 208                 {
 209                         DPoint bottom,top;
 210                         if(p1.m_y > p2.m_y) {
 211                                 bottom = p2;
 212                                 top = p1;
 213                         }
 214                         else {
 215                                 bottom = p1;
 216                                 top = p2;
 217                         }
 218                         IPoint start(computeGridPoint(bottom));
 219                         IPoint end(computeGridPoint(top));
 220                         //int Xincr = 1;
 221                         //if(bottom.m_x > top.m_x) Xincr = -1;
 222                         double slope = (top.m_x-bottom.m_x)/(top.m_y-bottom.m_y);
 223                         double c = bottom.m_x-slope*bottom.m_y;
 224                         OGDF_ASSERT(fabs(slope*top.m_y+c - top.m_x) < m_epsilon);
 225                         int endY = end.m_y+1;
 226                         double dXincr = slope * m_CellSize;
 227                         double OldXPos = slope*start.m_y*m_CellSize+c;
 228                         int oldX = (int)floor(OldXPos/m_CellSize);
 229                         for(int i = start.m_y; i <= endY; i++) {
 230                                 crossedCells.pushBack(IPoint(oldX,i));
 231                                 double newX = OldXPos + dXincr;
 232                                 OGDF_ASSERT(newX - ((i+1)*m_CellSize*slope+c) < m_epsilon)
 233                                 int newCellX = (int)floor(newX/m_CellSize);
 234                                 if(newCellX != oldX) {
 235                                         oldX = newCellX;
 236                                         crossedCells.pushBack(IPoint(oldX,i));
 237                                 }
 238                                 OldXPos = newX;
 239                         }
 240                 }
 241
 242         }
 243 //constructor for computing the grid and the crossings from scratch for the
 244 //layout given by AG
 245 UniformGrid::UniformGrid(const GraphAttributes &AG) :
 246         m_layout(AG),
 247         m_graph(AG.constGraph()),
 248         m_crossings(m_graph),
 249         m_cells(m_graph),
 250         m_CellSize(0.0),
 251         m_crossNum(0)
 252 {
 253         //cout<<"New grid \n";
 254         node v = m_graph.firstNode();
 255         DPoint pos(m_layout.x(v),m_layout.y(v));
 256 #ifdef OGDF_DEBUG
 257         m_crossingTests = 0;
 258         m_maxEdgesPerCell = 0;
 259         usedTime(m_time);
 260 #endif
 261         IntersectionRectangle ir;
 262         computeGridGeometry(v,pos,ir);
 263         double maxLength = max(ir.height(),ir.width());
 264         m_CellSize = maxLength/(m_edgeMultiplier*(m_graph).numberOfEdges());
 265         List<edge> L;
 266         m_graph.allEdges(L);
 267         computeCrossings(L,v,pos);
 268 #ifdef OGDF_DEBUG
 269         m_time = usedTime(m_time);
 270 #endif
 271 }
 272
 273 //constructor for computing the grid and the crossings from scratch for
 274 //the given layout where node v is moved to newPos
 275 UniformGrid::UniformGrid(
 276         const GraphAttributes &AG,
 277         const node v,
 278         const DPoint& newPos)
 279 :
 280         m_layout(AG),
 281         m_graph(AG.constGraph()),
 282         m_crossings(m_graph),
 283         m_cells(m_graph),
 284         m_CellSize(0.0),
 285         m_crossNum(0)
 286 {
 287 #ifdef OGDF_DEBUG
 288         m_crossingTests = 0;
 289         m_maxEdgesPerCell = 0;
 290         usedTime(m_time);
 291 #endif
 292         IntersectionRectangle ir;
 293         computeGridGeometry(v,newPos,ir);
 294         double maxLength = max(ir.height(),ir.width());
 295         m_CellSize = maxLength/(m_edgeMultiplier*(m_graph).numberOfEdges());
 296         List<edge> L;
 297         m_graph.allEdges(L);
 298         computeCrossings(L,v,newPos);
 299 #ifdef OGDF_DEBUG
 300         m_time = usedTime(m_time);
 301 #endif
 302 }
 303
 304 //constructor for computing an updated grid for a given grid where one
 305 //vertex is moved to a new position
 306 UniformGrid::UniformGrid(
 307         const UniformGrid &ug,
 308         const node v,
 309         const DPoint& newPos) :
 310         m_layout(ug.m_layout),
 311         m_graph(ug.m_graph),
 312         m_grid(ug.m_grid),
 313         m_crossings(ug.m_crossings),
 314         m_cells(ug.m_cells),
 315         m_CellSize(ug.m_CellSize),
 316         m_crossNum(ug.m_crossNum)
 317 {
 318         //constructorcounter++;
 319 #ifdef OGDF_DEBUG
 320         m_crossingTests = 0;
 321         m_maxEdgesPerCell = 0;
 322         usedTime(m_time);
 323         IntersectionRectangle ir;
 324         computeGridGeometry(v,newPos,ir);
 325         double l = max(ir.width(),ir.height());
 326         l/=(m_graph.numberOfEdges()*m_edgeMultiplier);
 327         OGDF_ASSERT(l > 0.5*m_CellSize && l < 2.0*m_CellSize);
 328 #endif
 329         //compute the list of edge incident to v
 330         List<edge> incident;
 331         m_graph.adjEdges(v,incident);
 332         //set the crossings of all these edges to zero, update the global crossing
 333         //number, remove them from their cells. Note that we cannot insert the edge
 334         //with its new position into the grid in the same loop because we may get
 335         //crossings with other edges incident to v
 336         ListIterator<edge> it1;
 337         for(it1 = incident.begin(); it1.valid(); ++it1) {
 338                 edge& e = *it1;
 339                 //we clear the list of crossings of e and delete e from the
 340                 //crossings lists of all the edges it crosses
 341                 List<edge>& c = m_crossings[e];
 342                 while(!c.empty()) {
 343                         edge crossed = c.popFrontRet();
 344                         List<edge>& cl = m_crossings[crossed];
 345                         ListIterator<edge> it2 = cl.begin();
 346                         while(*it2 != e) ++it2;
 347                         cl.del(it2);
 348                         m_crossNum--;
 349                 }
 350                 List<IPoint>& cells = m_cells[e];
 351                 //delete e from all its cells
 352                 while(!cells.empty()) {
 353                         IPoint p = cells.popFrontRet();
 354                         List<edge>& eList = m_grid(p.m_x,p.m_y);
 355                         ListIterator<edge> it2 = eList.begin();
 356                         while(*it2 != e) ++it2;
 357                         eList.del(it2);
 358                 }
 359         }// at this point, all the data structures look as if the edges in the
 360         //list incident where not present. Now we reinsert the edges into the
 361         //grid with their new positions and update the crossings
 362         computeCrossings(incident,v,newPos);
 363 #ifdef OGDF_DEBUG
 364         m_time = usedTime(m_time);
 365 #endif
 366 }
 367
 368
 369 void UniformGrid::computeGridGeometry(
 370         const node moved,
 371         const DPoint& newPos,
 372         IntersectionRectangle& ir) const
 373 {
 374         //first we compute the resolution and size of the grid
 375         double MinX = DBL_MAX, MinY = DBL_MAX, MaxX =DBL_MIN, MaxY = DBL_MIN;
 376         //find lower left and upper right vertex
 377         node v;
 378         forall_nodes(v,m_graph) {
 379                 double x = 0.0, y = 0.0;
 380                 if(v != moved) {// v is the node that was moved
 381                         x = m_layout.x(v);
 382                         y = m_layout.y(v);
 383                 }
 384                 else {// v is not the moved node
 385                         x = newPos.m_x;
 386                         y = newPos.m_y;
 387                 }
 388                 if(x < MinX) MinX = x;
 389                 if(x > MaxX) MaxX = x;
 390                 if(y < MinY) MinY = y;
 391                 if(y > MaxY) MaxY = y;
 392         }
 393         ir = IntersectionRectangle(MinX,MinY,MaxX,MaxY);
 394 }
 395
 396
 397 void UniformGrid::computeCrossings(
 398         const List<edge>& toInsert,
 399         const node moved,
 400         const DPoint& newPos)
 401 {
 402         //now we compute all the remaining data of the class in one loop
 403         //going through all edges and storing them in the grid.
 404         ListConstIterator<edge> it;
 405         for(it = toInsert.begin(); it.valid(); ++it) {
 406                 const edge& e = *it;
 407                 SList<IPoint> crossedCells;
 408                 DPoint sPos,tPos;
 409                 const node& s = e->source();
 410                 if(s != moved) sPos = DPoint(m_layout.x(s),m_layout.y(s));
 411                 else sPos = newPos;
 412                 const node& t = e->target();
 413                 if(t != moved) tPos = DPoint(m_layout.x(t),m_layout.y(t));
 414                 else tPos = newPos;
 415                 DoubleModifiedBresenham(sPos,tPos,crossedCells);
 416                 SListConstIterator<IPoint> it1;
 417                 for(it1 = crossedCells.begin(); it1.valid(); ++it1) {
 418                         const IPoint& p = *it1;
 419                         (m_cells[e]).pushBack(p);
 420                         List<edge>& edgeList = m_grid(p.m_x,p.m_y);
 421                         if(!edgeList.empty()) { //there are already edges in that list
 422                                 ListConstIterator<edge> it2;
 423                                 OGDF_ASSERT(!edgeList.empty());
 424                                 for(it2 = edgeList.begin(); it2.valid(); ++it2) {
 425                                         if(crossingTest(e,*it2,moved,newPos,p)) { //two edges cross in p
 426                                                 ++m_crossNum;
 427                                                 m_crossings[e].pushBack(*it2);
 428                                                 m_crossings[*it2].pushBack(e);
 429                                         }
 430                                 }
 431                         }
 432                         //now we insert the new edge into the list and store the position
 433                         //returned by pushBack in the corresponding list of m_storedIn
 434                         edgeList.pushBack(e);
 435 #ifdef OGDF_DEBUG
 436                         if(m_maxEdgesPerCell < edgeList.size())
 437                                 m_maxEdgesPerCell = edgeList.size();
 438 #endif
 439                 }
 440         }
 441 #ifdef OGDF_DEBUG
 442         int SumCros = 0;
 443         edge e;
 444         forall_edges(e,m_graph) SumCros += m_crossings[e].size();
 445         OGDF_ASSERT((SumCros >> 1) == m_crossNum);
 446 #endif
 447 }
 448
 449
 450 //returns true if both edges are not adjacent and cross inside the given cell
 451 bool UniformGrid::crossingTest(
 452         const edge e1,
 453         const edge e2,
 454         const node moved,
 455         const DPoint& newPos,
 456         const IPoint& cell)
 457 {
 458         bool crosses = false;
 459         node s1 = e1->source(), t1 = e1->target();
 460         node s2 = e2->source(), t2 = e2->target();
 461         if(s1 != s2 && s1 != t2 && t1 != s2 && t1 != t2) {//not adjacent
 462                 double xLeft = cell.m_x*m_CellSize;
 463                 double xRight = (cell.m_x+1)*m_CellSize;
 464                 double xBottom = cell.m_y*m_CellSize;
 465                 double xTop = (cell.m_y+1)*m_CellSize;
 466                 DPoint ps1,pt1,ps2,pt2;
 467                 if(s1 != moved) ps1 = DPoint(m_layout.x(s1),m_layout.y(s1));
 468                 else ps1 = newPos;
 469                 if(t1 != moved) pt1 = DPoint(m_layout.x(t1),m_layout.y(t1));
 470                 else pt1 = newPos;
 471                 if(s2 != moved) ps2 = DPoint(m_layout.x(s2),m_layout.y(s2));
 472                 else ps2 = newPos;
 473                 if(t2 != moved) pt2 = DPoint(m_layout.x(t2),m_layout.y(t2));
 474                 else pt2 = newPos;
 475                 DLine l1(ps1,pt1),l2(ps2,pt2);
 476                 DPoint crossPoint;
 477 #ifdef OGDF_DEBUG
 478                 m_crossingTests++;
 479 #endif
 480                 if(l1.intersection(l2,crossPoint)) {
 481                         if(crossPoint.m_x >= xLeft && crossPoint.m_x < xRight &&
 482                                 crossPoint.m_y >= xBottom && crossPoint.m_y < xTop) {
 483                                 crosses = true;
 484                         }
 485                 }
 486         }
 487         return crosses;
 488 }
 489
 490 #ifdef OGDF_DEBUG
 491
 492 void UniformGrid::markCells(SList<IPoint> &result, Array2D<bool> &cells) const {
 493                 while(!result.empty()) {
 494                         IPoint p = result.popFrontRet();
 495                         if(cells.low1() <= p.m_x && cells.high1() >= p.m_x
 496                                 && cells.low2() <= p.m_y && cells.high2() >= p.m_y)
 497                                 cells(p.m_x,p.m_y) = true;
 498                 }
 499 }
 500
 501
 502 void UniformGrid::checkBresenham(DPoint p1, DPoint p2) const
 503 {
 504         int crossed = 0;
 505         DPoint bottomleft(min(p1.m_x,p2.m_x),min(p1.m_y,p2.m_y));
 506         DPoint topright(max(max(p1.m_x,p2.m_x),bottomleft.m_x+1.0),
 507                 max(max(p1.m_y,p2.m_y),bottomleft.m_y+1.0));
 508         IPoint ibl(computeGridPoint(bottomleft));
 509         IPoint itr(computeGridPoint(topright));
 510         Array2D<bool> cells(ibl.m_x,itr.m_x+1,ibl.m_y,itr.m_y+1,false);
 511         SList<IPoint> result;
 512         DoubleModifiedBresenham(p1,p2,result);
 513         cout << "\nList computed by Bresenham:\n";
 514
 515         for(SListIterator<IPoint> it = result.begin(); it.valid(); ++it) {
 516                 cout << computeRealPoint(*it) << " ";
 517         }
 518
 519         markCells(result,cells);
 520         cout << "\nCrossed cells:\n";
 521         if(p1.m_x == p2.m_x) { //vertical segment
 522                 int cellXcoord = (int)floor(p1.m_x/m_CellSize);
 523                 double b = floor(min(p1.m_y,p2.m_y)/m_CellSize);
 524                 double t = ceil(max(p1.m_y,p2.m_y)/m_CellSize);
 525                 OGDF_ASSERT(isInt(b) && isInt(t));
 526                 int intT = (int)t;
 527                 for(int i = int(b); i < intT; i++) {
 528                         crossed++;
 529                         IPoint p(cellXcoord,i);
 530                         cout << computeRealPoint(p) << " ";
 531                         if(!cells(p.m_x,p.m_y)) {
 532                                 cout << "\nCell " << computeRealPoint(p) << " is not marked!";
 533                                 exit(1);
 534                         }
 535                 }
 536         }
 537         else {
 538                 if(p1.m_y == p2.m_y) { //horizontal segment
 539                         double tmp = floor(p1.m_y/m_CellSize);
 540                         assert(isInt(tmp));
 541                         int cellYcoord = (int)tmp;
 542                         double l = floor(min(p1.m_x,p2.m_x)/m_CellSize);
 543                         double r = ceil(max(p1.m_x,p2.m_x)/m_CellSize);
 544                         assert(isInt(l) && isInt(r));
 545                         int intR = (int)r;
 546                         for(int i = int(l); i < intR; i++) {
 547                                 crossed++;
 548                                 IPoint p(i,cellYcoord);
 549                                 cout << computeRealPoint(p) << " ";
 550                                 if(!cells(p.m_x,p.m_y)) {
 551                                         cout << "\nCell " << computeRealPoint(p) << " is not marked!";
 552                                         exit(1);
 553                                 }
 554                         }
 555                 }
 556                 else {
 557                         for(int i = cells.low1(); i <= cells.high1(); i++) {
 558                                 for(int j = cells.low2(); j <= cells.high2(); j++) {
 559                                         IPoint p(i,j);
 560                                         if(crossesCell(p1,p2,p)) {
 561                                                 crossed++;
 562                                                 cout << computeRealPoint(p) << " ";
 563                                                 if(!cells(p.m_x,p.m_y)) {
 564                                                         cout << "\n Cell " << computeRealPoint(p) << " is not marked!";
 565                                                         exit(1);
 566                                                 }
 567                                         }
 568                                 }
 569                         }
 570
 571                 }
 572         }
 573         if(crossed < max(fabs(p1.m_x-p2.m_x)/m_CellSize,fabs(p1.m_y-p2.m_y)/m_CellSize)) {
 574                 cout << "\nNot enough crossed cells for " << p1 << " " << p2 << "\n";
 575                 exit(1);
 576         }
 577         cout << "\n";
 578
 579 }
 580
 581
 582 void UniformGrid::checkBresenham(IPoint p1, IPoint p2) const
 583 {
 584         int crossed = 0;
 585         int left = min(p1.m_x,p2.m_x)-1;
 586         int right = max(max(p1.m_x,p2.m_x),left+1);
 587         int bottom = min(p1.m_y,p2.m_y)-1;
 588         int top = max(max(p1.m_y,p2.m_y),bottom+1);
 589         Array2D<bool> cells(left,right,bottom,top,false);
 590         SList<IPoint> result;
 591         ModifiedBresenham(p1,p2,result);
 592         cout << "\nList computed by Bresenham:\n" << result;
 593         markCells(result,cells);
 594         cout << "\nCrossed cells:\n";
 595         if(p1.m_x == p2.m_x) { //vertical segment
 596                 for(int i = min(p1.m_y,p2.m_y); i < max(p1.m_y,p2.m_y); i++) {
 597                         crossed++;
 598                         IPoint p(p1.m_x,i);
 599                         cout << p << " ";
 600                         if(!cells(p.m_x,p.m_y)) {
 601                                 cout << "\nCell " << p << " is not marked!";
 602                                 exit(1);
 603                         }
 604                 }
 605         }
 606         else {
 607                 if(p1.m_y == p2.m_y) { //horizontal segment
 608                         for(int i = min(p1.m_x,p2.m_x); i < max(p1.m_x,p2.m_x); i++) {
 609                                 crossed++;
 610                                 IPoint p(i,p1.m_y);
 611                                 cout << p << " ";
 612                                 if(!cells(i,p1.m_y)) {
 613                                         cout << "\nCell " << p <<" is not marked!";
 614                                         exit(1);
 615                                 }
 616                         }
 617                 }
 618                 else {
 619                         for(int i = cells.low1(); i <= cells.high1(); i++) {
 620                                 for(int j = cells.low2(); j <= cells.high2(); j++) {
 621                                         IPoint p(i,j);
 622                                         if(crossesCell(p1,p2,p)) {
 623                                                 crossed++;
 624                                                 cout << p << " ";
 625                                                 if(!cells(p.m_x,p.m_y)) {
 626                                                         cout << "\n Cell " << p << " is not marked!";
 627                                                         exit(1);
 628                                                 }
 629                                         }
 630                                 }
 631                         }
 632
 633                 }
 634         }
 635         if(crossed < max(abs(p1.m_x-p2.m_x),abs(p1.m_y-p2.m_y))) {
 636                 cout << "\nNot enough crossed cells for " << p1 << " " << p2 << "\n";
 637                 exit(1);
 638         }
 639         cout << "\n";
 640
 641 }
 642
 643
 644 //the upper and left boundary does not belong to a cell
 645 bool UniformGrid::crossesCell(
 646         IPoint A,
 647         IPoint B,
 648         const IPoint &CellAdr) const
 649 {
 650         bool crosses = false;
 651         if(A.m_x == B.m_x) {//line segment is vertical
 652                 if(A.m_x >= CellAdr.m_x && A.m_x < CellAdr.m_x+1) {
 653                         if(intervalIntersect(A.m_y,B.m_y,CellAdr.m_y,CellAdr.m_y+1))
 654                                 crosses = true;
 655                 }
 656         }
 657         else {//line segment not vertical
 658                 if(A.m_x > B.m_x) swap(A,B);
 659                 double m = double(B.m_y-A.m_y)/double(B.m_x-A.m_x);
 660                 double c = A.m_y-A.m_x*m;
 661                 double y1 = m*CellAdr.m_x + c;
 662                 double y2 = m*(CellAdr.m_x+1)+c;
 663                 crosses = intervalIntersect(A.m_x,B.m_x,CellAdr.m_x,CellAdr.m_x+1);
 664                 crosses = crosses && intervalIntersect(y1,y2,CellAdr.m_y,CellAdr.m_y+1);
 665         }
 666         return crosses;
 667 }
 668
 669
 670 //the upper and left boundary does not belong to a cell
 671 bool UniformGrid::crossesCell(
 672         DPoint A,
 673         DPoint B,
 674         const IPoint &CellAdr) const
 675 {
 676         bool crosses = false;
 677         double xLowCell = CellAdr.m_x * m_CellSize;
 678         double xHighCell = xLowCell + m_CellSize;
 679         double yLowCell = CellAdr.m_y * m_CellSize;
 680         double yHighCell = yLowCell + m_CellSize;
 681         if(A.m_x == B.m_x) {//line segment is vertical
 682                 if(A.m_x >= xLowCell && A.m_x < xHighCell) {
 683                         if(intervalIntersect(A.m_y,B.m_y,yLowCell,yHighCell))
 684                                 crosses = true;
 685                 }
 686         }
 687         else {//line segment not vertical
 688                 if(A.m_x > B.m_x) swap(A,B);
 689                 double m = (B.m_y-A.m_y)/(B.m_x-A.m_x);
 690                 double c = A.m_y-A.m_x*m;
 691                 double y1 = m * xLowCell + c;
 692                 double y2 = m * xHighCell + c;
 693                 crosses = intervalIntersect(A.m_x,B.m_x,xLowCell,xHighCell);
 694                 crosses = crosses && intervalIntersect(min(A.m_y,B.m_y),max(A.m_y,B.m_y),
 695                         yLowCell,yHighCell);
 696                 crosses = crosses && intervalIntersect(y1,y2,yLowCell,yHighCell);
 697         }
 698         return crosses;
 699 }
 700
 701
 702 bool UniformGrid::intervalIntersect(
 703         double a1,
 704         double a2,
 705         double cell1,
 706         double cell2) const
 707 {
 708         double epsilon = 0.000001;
 709         bool intersect = true;
 710         if(min(a1,a2)+epsilon >= max(cell1,cell2) || min(cell1,cell2)+epsilon >= max(a1,a2)) intersect = false;
 711         return intersect;
 712 }
 713
 714
 715 ostream &operator<<(ostream &out, const UniformGrid &ug)
 716 {
 717         out << "\nGrid Size: " << ug.m_CellSize;
 718         out << "\nEpsilon: " << ug.m_epsilon;
 719         out << "\nEdge Multiplier: " << ug.m_edgeMultiplier;
 720         out << "\nCrossing number: " << ug.m_crossNum;
 721 #ifdef OGDF_DEBUG
 722         out << "\nCrossing tests: " << ug.m_crossingTests;
 723         out << "\nMax edges per cell: " << ug.m_maxEdgesPerCell;
 724         out << "\nConstruction time: " << ug.m_time;
 725         IntersectionRectangle ir;
 726         node v = ug.m_graph.firstNode();
 727         ug.computeGridGeometry(v,DPoint(ug.m_layout.x(v),ug.m_layout.y(v)),ir);
 728         double l = max(ir.width(),ir.height());
 729         cout << "\nPreferred Cell Size: " << l/(ug.m_graph.numberOfEdges()*ug.m_edgeMultiplier);
 730 #endif
 731         return out;
 732 }
 733
 734
 735 #endif
 736 }//namespace