File indexing completed on 2023-10-03 05:09:10

0001 /***************************************************************************
0002  *   Copyright (C) 2003-2004 by David Saxton                               *
0003  *   david@bluehaze.org                                                    *
0004  *                                                                         *
0005  *   This program is free software; you can redistribute it and/or modify  *
0006  *   it under the terms of the GNU General Public License as published by  *
0007  *   the Free Software Foundation; either version 2 of the License, or     *
0008  *   (at your option) any later version.                                   *
0009  ***************************************************************************/
0010 
0011 #include "conrouter.h"
0012 #include "icndocument.h"
0013 #include "utils.h"
0014 
0015 #include <cassert>
0016 #include <cmath>
0017 #include <cstdlib>
0018 
0019 #include <ktechlab_debug.h>
0020 
0021 ConRouter::ConRouter(ICNDocument *cv)
0022 {
0023     p_icnDocument = cv;
0024     m_lcx = m_lcy = 0;
0025 }
0026 
0027 ConRouter::~ConRouter()
0028 {
0029 }
0030 
0031 QPointList ConRouter::pointList(bool reverse) const
0032 {
0033     QPointList pointList;
0034 
0035     if (reverse) {
0036         bool notDone = m_cellPointList.size() > 0;
0037         for (QPointList::const_iterator it = (--m_cellPointList.constEnd()); notDone; --it) {
0038             pointList.append(toCanvas(&*it));
0039             if (it == m_cellPointList.begin())
0040                 notDone = false;
0041         }
0042     } else {
0043         const QPointList::const_iterator end = m_cellPointList.end();
0044         for (QPointList::const_iterator it = m_cellPointList.begin(); it != end; ++it) {
0045             pointList.append(toCanvas(&*it));
0046         }
0047     }
0048 
0049     return pointList;
0050 }
0051 
0052 QPointListList ConRouter::splitPoints(const QPoint &pos) const
0053 {
0054     const QPoint split = fromCanvas(&pos);
0055 
0056     QList<QPointList> list;
0057 
0058     // Check that the point is in the connector points, and not at the start or end
0059     bool found = false;
0060     QPointList::const_iterator end = m_cellPointList.end();
0061 
0062     double dl[] = {0.0, 1.1, 1.5}; // sqrt(2) < 1.5 < sqrt(5)
0063     for (unsigned i = 0; (i < 3) && !found; ++i) {
0064         for (QPointList::const_iterator it = m_cellPointList.begin(); it != end && !found; ++it) {
0065             QPointList::const_iterator fromLast = --m_cellPointList.constEnd();
0066             if (qpoint_distance(*it, split) <= dl[i] && it != m_cellPointList.begin() && it != fromLast) // m_cellPointList.fromLast() )
0067                 found = true;
0068         }
0069     }
0070 
0071     QPointList first;
0072     QPointList second;
0073 
0074     if (!found) {
0075         qCWarning(KTL_LOG) << "ConRouter::splitConnectorPoints: Could not find point (" << pos.x() << ", " << pos.y() << ") in connector points";
0076         qCWarning(KTL_LOG) << "ConRouter::splitConnectorPoints: Returning generic list";
0077 
0078         first.append(toCanvas(m_cellPointList.first()));
0079         first.append(pos);
0080         second.append(pos);
0081         second.append(toCanvas(m_cellPointList.last()));
0082 
0083         list.append(first);
0084         list.append(second);
0085 
0086         return list;
0087     }
0088 
0089     // Now add the points to the two lists
0090     bool gotToSplit = false;
0091     for (QPointList::const_iterator it = m_cellPointList.begin(); it != end; ++it) {
0092         QPoint canvasPoint = toCanvas(&*it);
0093         if (*it == split) {
0094             gotToSplit = true;
0095             first.append(canvasPoint);
0096             second.prepend(canvasPoint);
0097         } else if (!gotToSplit) {
0098             first.append(canvasPoint);
0099         } else /*if (gotToSplit)*/
0100         {
0101             second.append(canvasPoint);
0102         }
0103     }
0104 
0105     list.append(first);
0106     list.append(second);
0107 
0108     return list;
0109 }
0110 
0111 QPointListList ConRouter::dividePoints(uint n) const
0112 {
0113     // Divide the points up into n pieces...
0114 
0115     QPointList points = m_cellPointList;
0116     assert(n != 0);
0117     if (points.size() == 0) {
0118         points += QPoint(toCanvas(m_lcx), toCanvas(m_lcy));
0119     }
0120 
0121     const float avgLength = float(points.size() - 1) / float(n);
0122 
0123     QPointListList pll;
0124     for (uint i = 0; i < n; ++i) {
0125         QPointList pl;
0126         // Get the points between (pos) and (pos+avgLength)
0127         const int endPos = roundDouble(avgLength * (i + 1));
0128         const int startPos = roundDouble(avgLength * i);
0129         // const QPointList::iterator end = ++points.at(endPos);
0130         // for ( QPointList::iterator it = points.at(startPos); it != end; ++it )
0131         for (int pos = startPos; pos < endPos; ++pos) {
0132             // pl += toCanvas(*it);
0133             pl += toCanvas(points.at(pos));
0134         }
0135         pll += pl;
0136     }
0137     return pll;
0138 }
0139 
0140 void ConRouter::checkACell(int x, int y, Cell *prev, int prevX, int prevY, int nextScore)
0141 {
0142     //  if ( !p_icnDocument->isValidCellReference(x,y) ) return;
0143     if (!cellsPtr->haveCell(x, y))
0144         return;
0145 
0146     Cell *c = &cellsPtr->cell(x, y);
0147     if (c->permanent)
0148         return;
0149 
0150     int newScore = nextScore + c->CIpenalty + c->Cpenalty;
0151 
0152     // Check for changing direction
0153     if (x != prevX && prev->prevX == prevX)
0154         newScore += 5;
0155     else if (y != prevY && prev->prevY == prevY)
0156         newScore += 5;
0157 
0158     if (c->bestScore < newScore)
0159         return;
0160 
0161     // We only want to change the previous cell if the score is different,
0162     // or the score is the same but this cell allows the connector
0163     // to travel in the same direction
0164 
0165     if (c->bestScore == newScore && x != prevX && y != prevY)
0166         return;
0167 
0168     c->bestScore = newScore;
0169     c->prevX = prevX;
0170     c->prevY = prevY;
0171 
0172     if (!c->addedToLabels) {
0173         c->addedToLabels = true;
0174         Point point;
0175         point.x = x;
0176         point.y = y;
0177         point.prevX = prevX;
0178         point.prevY = prevY;
0179         TempLabelMap::iterator it = tempLabels.insert(std::make_pair(newScore, point));
0180         c->point = &it->second;
0181     } else {
0182         c->point->prevX = prevX;
0183         c->point->prevY = prevY;
0184     }
0185 }
0186 
0187 void ConRouter::checkCell(int x, int y)
0188 {
0189     Cell *c = &cellsPtr->cell(x, y);
0190 
0191     c->permanent = true;
0192     int nextScore = c->bestScore + 1;
0193 
0194     // Check the surrounding cells (up, left, right, down)
0195     checkACell(x, y - 1, c, x, y, nextScore);
0196     checkACell(x - 1, y, c, x, y, nextScore);
0197     checkACell(x + 1, y, c, x, y, nextScore);
0198     checkACell(x, y + 1, c, x, y, nextScore);
0199 }
0200 
0201 bool ConRouter::needsRouting(int sx, int sy, int ex, int ey) const
0202 {
0203     if (m_cellPointList.size() < 2) {
0204         // Better be on the safe side...
0205         return true;
0206     }
0207 
0208     const int scx = fromCanvas(sx);
0209     const int scy = fromCanvas(sy);
0210     const int ecx = fromCanvas(ex);
0211     const int ecy = fromCanvas(ey);
0212 
0213     const int psx = m_cellPointList.first().x();
0214     const int psy = m_cellPointList.first().y();
0215     const int pex = m_cellPointList.last().x();
0216     const int pey = m_cellPointList.last().y();
0217 
0218     return (psx != scx || psy != scy || pex != ecx || pey != ecy) && (pex != scx || pey != scy || psx != ecx || psy != ecy);
0219 }
0220 
0221 void ConRouter::setRoutePoints(const QPointList &pointList)
0222 {
0223     m_cellPointList = pointList;
0224     removeDuplicatePoints();
0225 }
0226 
0227 void ConRouter::setPoints(const QPointList &pointList, bool reverse)
0228 {
0229     if (pointList.size() == 0)
0230         return;
0231 
0232     QPointList cellPointList;
0233 
0234     QPoint prevCellPoint = fromCanvas(*pointList.begin());
0235     cellPointList.append(prevCellPoint);
0236     const QPointList::const_iterator end = pointList.end();
0237     for (QPointList::const_iterator it = pointList.begin(); it != end; ++it) {
0238         QPoint cellPoint = fromCanvas(*it);
0239 
0240         while (prevCellPoint != cellPoint) {
0241             cellPointList.append(prevCellPoint);
0242 
0243             if (prevCellPoint.x() < cellPoint.x())
0244                 prevCellPoint.setX(prevCellPoint.x() + 1);
0245             else if (prevCellPoint.x() > cellPoint.x())
0246                 prevCellPoint.setX(prevCellPoint.x() - 1);
0247             if (prevCellPoint.y() < cellPoint.y())
0248                 prevCellPoint.setY(prevCellPoint.y() + 1);
0249             else if (prevCellPoint.y() > cellPoint.y())
0250                 prevCellPoint.setY(prevCellPoint.y() - 1);
0251         };
0252 
0253         prevCellPoint = cellPoint;
0254     }
0255     cellPointList.append(prevCellPoint);
0256 
0257     if (reverse) {
0258         m_cellPointList.clear();
0259         const QPointList::iterator begin = cellPointList.begin();
0260         for (QPointList::iterator it = --cellPointList.end(); it != begin; --it) {
0261             m_cellPointList += *it;
0262         }
0263         m_cellPointList += *begin;
0264     } else {
0265         m_cellPointList = cellPointList;
0266     }
0267 
0268     removeDuplicatePoints();
0269 }
0270 
0271 void ConRouter::translateRoute(int dx, int dy)
0272 {
0273     if (dx == 0 && dy == 0)
0274         return;
0275 
0276     m_lcx += dx;
0277     m_lcy += dy;
0278 
0279     //  const QPoint ds = QPoint( fromCanvas(dx), fromCanvas(dy) );
0280     const QPoint ds = QPoint(dx / 8, dy / 8);
0281 
0282     QPointList::iterator end = m_cellPointList.end();
0283     for (QPointList::iterator it = m_cellPointList.begin(); it != end; ++it) {
0284         (*it) += ds;
0285     }
0286 
0287     removeDuplicatePoints();
0288 }
0289 
0290 void ConRouter::mapRoute(int sx, int sy, int ex, int ey)
0291 {
0292     const int scx = fromCanvas(sx);
0293     const int scy = fromCanvas(sy);
0294     const int ecx = fromCanvas(ex);
0295     const int ecy = fromCanvas(ey);
0296 
0297     cellsPtr = p_icnDocument->cells();
0298 
0299     if (!cellsPtr->haveCell(scx, scy) || !cellsPtr->haveCell(ecx, ecy)) {
0300         qCDebug(KTL_LOG) << "cellPtr doesn't have cells, giving up";
0301         return;
0302     }
0303 
0304     m_cellPointList.clear();
0305     m_lcx = ecx;
0306     m_lcy = ecy;
0307 
0308     // First, lets try some common connector routes (which will not necesssarily
0309     // be shortest, but they will be neat, and cut down on overall CPU usage)
0310     // If that fails, we will resort to a shortest-route algorithm to find an
0311     // appropriate route.
0312 
0313     // Connector configuration: Line
0314     {
0315         bool ok = checkLineRoute(scx, scy, ecx, ecy, 4 * ICNDocument::hs_connector, 0);
0316         if (ok) {
0317             return;
0318         } else {
0319             m_cellPointList.clear();
0320         }
0321     }
0322 
0323     // Corner 1
0324     {
0325         bool ok = checkLineRoute(scx, scy, ecx, ecy, 2 * ICNDocument::hs_connector, 0);
0326         if (!ok) {
0327             m_cellPointList.clear();
0328         } else {
0329             ok = checkLineRoute(scx, scy, ecx, ecy, ICNDocument::hs_connector - 1, 0);
0330             if (ok) {
0331                 return;
0332             } else {
0333                 m_cellPointList.clear();
0334             }
0335         }
0336     }
0337 
0338     // Corner 2
0339     {
0340         bool ok = checkLineRoute(scx, scy, ecx, ecy, 2 * ICNDocument::hs_connector, 0);
0341         if (!ok) {
0342             m_cellPointList.clear();
0343         } else {
0344             ok = checkLineRoute(scx, scy, ecx, ecy, ICNDocument::hs_connector - 1, 0);
0345             if (ok) {
0346                 return;
0347             } else {
0348                 m_cellPointList.clear();
0349             }
0350         }
0351     }
0352 
0353     // It seems we must resort to brute-force route-checking
0354     {
0355         cellsPtr->reset();
0356 
0357         xcells = p_icnDocument->canvas()->width() / 8;
0358         ycells = p_icnDocument->canvas()->height() / 8;
0359 
0360         // Now to map out the shortest routes to the cells
0361         Cell *const startCell = &cellsPtr->cell(ecx, ecy);
0362         startCell->permanent = true;
0363         startCell->bestScore = 0;
0364         startCell->prevX = startCellPos;
0365         startCell->prevY = startCellPos;
0366 
0367         tempLabels.clear();
0368         checkCell(ecx, ecy);
0369 
0370         // Daniel: I changed it from a do while to a while otherwise
0371         // in rare cases the iterator can end up as end().
0372         while (tempLabels.size() > 0 && !cellsPtr->cell(scx, scy).permanent) {
0373             TempLabelMap::iterator it = tempLabels.begin();
0374             checkCell(it->second.x, it->second.y);
0375             tempLabels.erase(it);
0376         }
0377 
0378         // Now, retrace the shortest route from the endcell to get out points :)
0379         int x = scx, y = scy;
0380         bool ok = true;
0381 
0382         do {
0383             m_cellPointList.append(QPoint(x, y));
0384             int newx = cellsPtr->cell(x, y).prevX;
0385             int newy = cellsPtr->cell(x, y).prevY;
0386             if (newx == x && newy == y) {
0387                 ok = false;
0388             }
0389             x = newx;
0390             y = newy;
0391         } while (cellsPtr->haveCell(x, y) && (x != startCellPos) && (y != startCellPos) && ok);
0392 
0393         // And append the last point...
0394         m_cellPointList.append(QPoint(ecx, ecy));
0395     }
0396 
0397     removeDuplicatePoints();
0398 }
0399 
0400 bool ConRouter::checkLineRoute(int scx, int scy, int ecx, int ecy, int maxConScore, int maxCIScore)
0401 {
0402     if ((scx != ecx) && (scy != ecy))
0403         return false;
0404 
0405     const bool isHorizontal = scy == ecy;
0406 
0407     int start = 0, end = 0, x = 0, y = 0, dd = 0;
0408     if (isHorizontal) {
0409         dd = (scx < ecx) ? 1 : -1;
0410         start = scx;
0411         end = ecx + dd;
0412         y = scy;
0413     } else {
0414         dd = (scy < ecy) ? 1 : -1;
0415         start = scy;
0416         end = ecy + dd;
0417         x = scx;
0418     }
0419 
0420     Cells *cells = p_icnDocument->cells();
0421 
0422     if (isHorizontal) {
0423         for (int x = start; x != end; x += dd) {
0424             if (std::abs(x - start) > 1 && std::abs(x - end) > 1 && (cells->cell(x, y).CIpenalty > maxCIScore || cells->cell(x, y).Cpenalty > maxConScore)) {
0425                 return false;
0426             } else
0427                 m_cellPointList.append(QPoint(x, y));
0428         }
0429     } else {
0430         for (int y = start; y != end; y += dd) {
0431             if (std::abs(y - start) > 1 && std::abs(y - end) > 1 && (cells->cell(x, y).CIpenalty > maxCIScore || cells->cell(x, y).Cpenalty > maxConScore)) {
0432                 return false;
0433             } else {
0434                 m_cellPointList.append(QPoint(x, y));
0435             }
0436         }
0437     }
0438 
0439     m_cellPointList.prepend(QPoint(scx, scy));
0440     m_cellPointList.append(QPoint(ecx, ecy));
0441     removeDuplicatePoints();
0442     return true;
0443 }
0444 
0445 void ConRouter::removeDuplicatePoints()
0446 {
0447     QPoint invalid(-(1 << 30), -(1 << 30));
0448     QPoint prev = invalid;
0449 
0450     const QPointList::iterator end = m_cellPointList.end();
0451     for (QPointList::iterator it = m_cellPointList.begin(); it != end; ++it) {
0452         if (*it == prev) {
0453             *it = invalid;
0454         } else {
0455             prev = *it;
0456         }
0457     }
0458     m_cellPointList.removeAll(invalid);
0459 }