You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
538 lines
13 KiB
538 lines
13 KiB
/***************************************************************************
|
|
* Copyright (C) 2003-2004 by David Saxton *
|
|
* david@bluehaze.org *
|
|
* *
|
|
* This program is free software; you can redistribute it and/or modify *
|
|
* it under the terms of the GNU General Public License as published by *
|
|
* the Free Software Foundation; either version 2 of the License, or *
|
|
* (at your option) any later version. *
|
|
***************************************************************************/
|
|
|
|
#include "conrouter.h"
|
|
#include "icndocument.h"
|
|
|
|
#include <kdebug.h>
|
|
|
|
#include <assert.h>
|
|
#include <cmath>
|
|
|
|
inline static int toCanvas( int pos )
|
|
{
|
|
return pos*8+4;
|
|
}
|
|
inline static int fromCanvas( int pos )
|
|
{
|
|
return (pos-4)/8;
|
|
}
|
|
|
|
inline static TQPoint toCanvas( const TQPoint * const pos )
|
|
{
|
|
return TQPoint( toCanvas(pos->x()), toCanvas(pos->y()) );
|
|
}
|
|
inline static TQPoint fromCanvas( const TQPoint * const pos )
|
|
{
|
|
return TQPoint( fromCanvas(pos->x()), fromCanvas(pos->y()) );
|
|
}
|
|
|
|
inline static TQPoint toCanvas( const TQPoint &pos )
|
|
{
|
|
return TQPoint( toCanvas(pos.x()), toCanvas(pos.y()) );
|
|
}
|
|
inline static TQPoint fromCanvas( const TQPoint &pos )
|
|
{
|
|
return TQPoint( fromCanvas(pos.x()), fromCanvas(pos.y()) );
|
|
}
|
|
|
|
static inline int roundDouble( const double x )
|
|
{
|
|
return int(std::floor(x+0.5));
|
|
}
|
|
|
|
ConRouter::ConRouter( ICNDocument *cv )
|
|
{
|
|
p_icnDocument = cv;
|
|
m_lcx = m_lcy = 0;
|
|
}
|
|
|
|
|
|
ConRouter::~ConRouter()
|
|
{
|
|
}
|
|
|
|
|
|
TQPointList ConRouter::pointList( bool reverse ) const
|
|
{
|
|
TQPointList pointList;
|
|
|
|
if (reverse)
|
|
{
|
|
bool notDone = m_cellPointList.size() > 0;
|
|
for ( TQPointList::const_iterator it = m_cellPointList.fromLast(); notDone; --it )
|
|
{
|
|
pointList.append( toCanvas(&*it) );
|
|
if ( it == m_cellPointList.begin() ) notDone = false;
|
|
}
|
|
}
|
|
else
|
|
{
|
|
const TQPointList::const_iterator end = m_cellPointList.end();
|
|
for ( TQPointList::const_iterator it = m_cellPointList.begin(); it != end; ++it )
|
|
{
|
|
pointList.append( toCanvas(&*it) );
|
|
}
|
|
}
|
|
|
|
return pointList;
|
|
}
|
|
|
|
|
|
static double qpoint_distance( const TQPoint & p1, const TQPoint & p2 )
|
|
{
|
|
double dx = p1.x() - p2.x();
|
|
double dy = p1.y() - p2.y();
|
|
|
|
return std::sqrt( dx*dx + dy*dy );
|
|
}
|
|
|
|
|
|
TQPointListList ConRouter::splitPoints( const TQPoint &pos ) const
|
|
{
|
|
const TQPoint split = fromCanvas(&pos);
|
|
|
|
TQValueList<TQPointList> list;
|
|
|
|
// Check that the point is in the connector points, and not at the start or end
|
|
bool found = false;
|
|
TQPointList::const_iterator end = m_cellPointList.end();
|
|
|
|
double dl[] = { 0.0, 1.1, 1.5 }; // sqrt(2) < 1.5 < sqrt(5)
|
|
for ( unsigned i = 0; (i < 3) && !found; ++i )
|
|
{
|
|
for ( TQPointList::const_iterator it = m_cellPointList.begin(); it != end && !found; ++it )
|
|
{
|
|
if ( qpoint_distance( *it, split ) <= dl[i] && it != m_cellPointList.begin() && it != m_cellPointList.fromLast() )
|
|
found = true;
|
|
}
|
|
}
|
|
|
|
TQPointList first;
|
|
TQPointList second;
|
|
|
|
if (!found)
|
|
{
|
|
kdWarning() << "ConRouter::splitConnectorPoints: Could not find point ("<<pos.x()<<", "<<pos.y()<<") in connector points"<<endl;
|
|
kdWarning() << "ConRouter::splitConnectorPoints: Returning generic list"<<endl;
|
|
|
|
first.append( toCanvas(m_cellPointList.first()) );
|
|
first.append(pos);
|
|
second.append(pos);
|
|
second.append( toCanvas(m_cellPointList.last()) );
|
|
|
|
list.append(first);
|
|
list.append(second);
|
|
|
|
return list;
|
|
}
|
|
|
|
// Now add the points to the two lists
|
|
bool gotToSplit = false;
|
|
for ( TQPointList::const_iterator it = m_cellPointList.begin(); it != end; ++it )
|
|
{
|
|
TQPoint canvasPoint = toCanvas(&*it);
|
|
if ( *it == split )
|
|
{
|
|
gotToSplit = true;
|
|
first.append(canvasPoint);
|
|
second.prepend(canvasPoint);
|
|
}
|
|
else if (!gotToSplit)
|
|
{
|
|
first.append(canvasPoint);
|
|
}
|
|
else /*if (gotToSplit)*/
|
|
{
|
|
second.append(canvasPoint);
|
|
}
|
|
}
|
|
|
|
list.append(first);
|
|
list.append(second);
|
|
|
|
return list;
|
|
}
|
|
|
|
|
|
TQPointListList ConRouter::dividePoints( uint n ) const
|
|
{
|
|
// Divide the points up into n pieces...
|
|
|
|
TQPointList points = m_cellPointList;
|
|
assert( n != 0 );
|
|
if ( points.size() == 0 ) {
|
|
points += TQPoint( toCanvas(m_lcx), toCanvas(m_lcy) );
|
|
}
|
|
|
|
const float avgLength = float(points.size()-1)/float(n);
|
|
|
|
TQPointListList pll;
|
|
for ( uint i=0; i<n; ++i )
|
|
{
|
|
TQPointList pl;
|
|
// Get the points between (pos) and (pos+avgLength)
|
|
const int endPos = roundDouble( avgLength*(i+1) );
|
|
const int startPos = roundDouble( avgLength*i );
|
|
const TQPointList::iterator end = ++points.at(endPos);
|
|
for ( TQPointList::iterator it = points.at(startPos); it != end; ++it )
|
|
{
|
|
pl += toCanvas(*it);
|
|
}
|
|
pll += pl;
|
|
}
|
|
return pll;
|
|
}
|
|
|
|
|
|
void ConRouter::checkACell( int x, int y, Cell *prev, int prevX, int prevY, int nextScore )
|
|
{
|
|
if ( !p_icnDocument->isValidCellReference(x,y) ) return;
|
|
Cell * const c = &(*cellsPtr)[x][y];
|
|
if ( c->permanent ) return;
|
|
int newScore = nextScore + c->CIpenalty + c->Cpenalty;
|
|
|
|
// Check for changing direction
|
|
if ( x != prevX && prev->prevX == prevX ) newScore += 5;
|
|
else if ( y != prevY && prev->prevY == prevY ) newScore += 5;
|
|
|
|
if ( c->bestScore < newScore ) return;
|
|
|
|
// We only want to change the previous cell if the score is different,
|
|
// or the score is the same but this cell allows the connector
|
|
// to travel in the same direction
|
|
|
|
if ( c->bestScore == newScore &&
|
|
x != prevX &&
|
|
y != prevY ) return;
|
|
|
|
c->bestScore = newScore;
|
|
c->prevX = prevX;
|
|
c->prevY = prevY;
|
|
|
|
if ( !c->addedToLabels )
|
|
{
|
|
c->addedToLabels = true;
|
|
Point point;
|
|
point.x = x;
|
|
point.y = y;
|
|
point.prevX = prevX;
|
|
point.prevY = prevY;
|
|
TempLabelMap::iterator it = tempLabels.insert( std::make_pair(newScore,point) );
|
|
c->point = &it->second;
|
|
}
|
|
else
|
|
{
|
|
c->point->prevX = prevX;
|
|
c->point->prevY = prevY;
|
|
}
|
|
}
|
|
|
|
void ConRouter::checkCell( int x, int y )
|
|
{
|
|
Cell * const c = &(*cellsPtr)[x][y];
|
|
|
|
c->permanent = true;
|
|
const int nextScore = c->bestScore+1;
|
|
|
|
// Check the surrounding cells (up, left, right, down)
|
|
if ( y > 0 ) checkACell( x, y-1, c, x, y, nextScore );
|
|
if ( x > 0 ) checkACell( x-1, y, c, x, y, nextScore );
|
|
if ( x+1 < xcells ) checkACell( x+1, y, c, x, y, nextScore );
|
|
if ( y+1 < ycells ) checkACell( x, y+1, c, x, y, nextScore );
|
|
}
|
|
|
|
|
|
bool ConRouter::needsRouting( int sx, int sy, int ex, int ey ) const
|
|
{
|
|
if ( m_cellPointList.size() < 2 )
|
|
{
|
|
// Better be on the safe side...
|
|
return true;
|
|
}
|
|
|
|
const int scx = fromCanvas(sx);
|
|
const int scy = fromCanvas(sy);
|
|
const int ecx = fromCanvas(ex);
|
|
const int ecy = fromCanvas(ey);
|
|
|
|
const int psx = m_cellPointList.first().x();
|
|
const int psy = m_cellPointList.first().y();
|
|
const int pex = m_cellPointList.last().x();
|
|
const int pey = m_cellPointList.last().y();
|
|
|
|
return (psx != scx || psy != scy || pex != ecx || pey != ecy ) &&
|
|
(pex != scx || pey != scy || psx != ecx || psy != ecy );
|
|
}
|
|
|
|
|
|
void ConRouter::setRoutePoints( const TQPointList &pointList )
|
|
{
|
|
m_cellPointList = pointList;
|
|
removeDuplicatePoints();
|
|
}
|
|
|
|
|
|
void ConRouter::setPoints( const TQPointList &pointList, bool reverse )
|
|
{
|
|
if ( pointList.size() == 0 )
|
|
return;
|
|
|
|
TQPointList cellPointList;
|
|
|
|
TQPoint prevCellPoint = fromCanvas(*pointList.begin());
|
|
cellPointList.append(prevCellPoint);
|
|
const TQPointList::const_iterator end = pointList.end();
|
|
for ( TQPointList::const_iterator it = pointList.begin(); it != end; ++it )
|
|
{
|
|
TQPoint cellPoint = fromCanvas(*it);
|
|
|
|
while ( prevCellPoint != cellPoint )
|
|
{
|
|
cellPointList.append(prevCellPoint);
|
|
|
|
if ( prevCellPoint.x() < cellPoint.x() ) prevCellPoint.setX( prevCellPoint.x()+1 );
|
|
else if ( prevCellPoint.x() > cellPoint.x() ) prevCellPoint.setX( prevCellPoint.x()-1 );
|
|
if ( prevCellPoint.y() < cellPoint.y() ) prevCellPoint.setY( prevCellPoint.y()+1 );
|
|
else if ( prevCellPoint.y() > cellPoint.y() ) prevCellPoint.setY( prevCellPoint.y()-1 );
|
|
};
|
|
|
|
prevCellPoint = cellPoint;
|
|
}
|
|
cellPointList.append(prevCellPoint);
|
|
|
|
if (reverse)
|
|
{
|
|
m_cellPointList.clear();
|
|
const TQPointList::iterator begin = cellPointList.begin();
|
|
for ( TQPointList::iterator it = cellPointList.fromLast(); it != begin; --it )
|
|
{
|
|
m_cellPointList += *it;
|
|
}
|
|
m_cellPointList += *begin;
|
|
}
|
|
else {
|
|
m_cellPointList = cellPointList;
|
|
}
|
|
|
|
removeDuplicatePoints();
|
|
}
|
|
|
|
|
|
void ConRouter::translateRoute( int dx, int dy )
|
|
{
|
|
if ( dx == 0 && dy == 0 ) {
|
|
return;
|
|
}
|
|
|
|
m_lcx += dx;
|
|
m_lcy += dy;
|
|
|
|
// const TQPoint ds = TQPoint( fromCanvas(dx), fromCanvas(dy) );
|
|
const TQPoint ds = TQPoint( dx/8, dy/8 );
|
|
|
|
TQPointList::iterator end = m_cellPointList.end();
|
|
for ( TQPointList::iterator it = m_cellPointList.begin(); it != end; ++it )
|
|
{
|
|
(*it) += ds;
|
|
}
|
|
|
|
removeDuplicatePoints();
|
|
}
|
|
|
|
|
|
void ConRouter::mapRoute( int sx, int sy, int ex, int ey )
|
|
{
|
|
const int scx = fromCanvas(sx);
|
|
const int scy = fromCanvas(sy);
|
|
const int ecx = fromCanvas(ex);
|
|
const int ecy = fromCanvas(ey);
|
|
|
|
if ( !p_icnDocument->isValidCellReference( scx, scy ) ||
|
|
!p_icnDocument->isValidCellReference( ecx, ecy ) )
|
|
{
|
|
return;
|
|
}
|
|
|
|
m_cellPointList.clear();
|
|
m_lcx = ecx;
|
|
m_lcy = ecy;
|
|
|
|
|
|
// First, lets try some common connector routes (which will not necesssarily
|
|
// be shortest, but they will be neat, and cut down on overall CPU usage)
|
|
// If that fails, we will resort to a shortest-route algorithm to find an
|
|
// appropriate route.
|
|
|
|
// Connector configuration: Line
|
|
{
|
|
bool ok = checkLineRoute( scx, scy, ecx, ecy, 4*ICNDocument::hs_connector, 0 );
|
|
if (ok) {
|
|
return;
|
|
} else {
|
|
m_cellPointList.clear();
|
|
}
|
|
}
|
|
|
|
// Corner 1
|
|
{
|
|
bool ok = checkLineRoute( scx, scy, ecx, ecy, 2*ICNDocument::hs_connector, 0 );
|
|
if (!ok) {
|
|
m_cellPointList.clear();
|
|
} else {
|
|
ok = checkLineRoute( scx, scy, ecx, ecy, ICNDocument::hs_connector-1, 0 );
|
|
if (ok) {
|
|
return;
|
|
} else {
|
|
m_cellPointList.clear();
|
|
}
|
|
}
|
|
}
|
|
|
|
// Corner 2
|
|
{
|
|
bool ok = checkLineRoute( scx, scy, ecx, ecy, 2*ICNDocument::hs_connector, 0 );
|
|
if (!ok) {
|
|
m_cellPointList.clear();
|
|
} else {
|
|
ok = checkLineRoute( scx, scy, ecx, ecy, ICNDocument::hs_connector-1, 0 );
|
|
if (ok) {
|
|
return;
|
|
} else {
|
|
m_cellPointList.clear();
|
|
}
|
|
}
|
|
}
|
|
|
|
// It seems we must resort to brute-force route-checking
|
|
{
|
|
cellsPtr = p_icnDocument->cells();
|
|
cellsPtr->reset();
|
|
|
|
xcells = p_icnDocument->canvas()->width()/8;
|
|
ycells = p_icnDocument->canvas()->height()/8;
|
|
|
|
// Now to map out the shortest routes to the cells
|
|
Cell * const startCell = &(*cellsPtr)[ecx][ecy];
|
|
startCell->permanent = true;
|
|
startCell->bestScore = 0;
|
|
startCell->prevX = -1;
|
|
startCell->prevY = -1;
|
|
|
|
tempLabels.clear();
|
|
checkCell( ecx, ecy );
|
|
|
|
// Daniel: I changed it from a do while to a while otherwise
|
|
// in rare cases the iterator can end up as end().
|
|
while ( tempLabels.size() > 0 && !(*cellsPtr)[scx][scy].permanent )
|
|
{
|
|
TempLabelMap::iterator it = tempLabels.begin();
|
|
checkCell( it->second.x, it->second.y );
|
|
tempLabels.erase(it);
|
|
}
|
|
|
|
// Now, retrace the shortest route from the endcell to get out points :)
|
|
int x = scx, y = scy;
|
|
bool ok = true;
|
|
do
|
|
{
|
|
m_cellPointList.append( TQPoint( x, y ) );
|
|
int newx = (*cellsPtr)[x][y].prevX;
|
|
int newy = (*cellsPtr)[x][y].prevY;
|
|
if ( newx == x && newy == y ) {
|
|
ok = false;
|
|
}
|
|
x = newx;
|
|
y = newy;
|
|
}
|
|
while ( p_icnDocument->isValidCellReference(x,y) && x != -1 && y != -1 && ok );
|
|
|
|
// And append the last point...
|
|
m_cellPointList.append( TQPoint( ecx, ecy ) );
|
|
}
|
|
|
|
removeDuplicatePoints();
|
|
}
|
|
|
|
|
|
bool ConRouter::checkLineRoute( int scx, int scy, int ecx, int ecy, int maxConScore, int maxCIScore )
|
|
{
|
|
if ( (scx != ecx) && (scy != ecy) ) {
|
|
return false;
|
|
}
|
|
|
|
const bool isHorizontal = scy == ecy;
|
|
|
|
int start=0, end=0, x=0, y=0, dd=0;
|
|
if (isHorizontal)
|
|
{
|
|
dd = (scx<ecx)?1:-1;
|
|
start = scx;
|
|
end = ecx+dd;
|
|
y = scy;
|
|
}
|
|
else
|
|
{
|
|
dd = (scy<ecy)?1:-1;
|
|
start = scy;
|
|
end = ecy+dd;
|
|
x = scx;
|
|
}
|
|
|
|
Cells *cells = p_icnDocument->cells();
|
|
|
|
if (isHorizontal)
|
|
{
|
|
for ( int x = start; x!=end; x+=dd )
|
|
{
|
|
if ( std::abs((double)(x-start))>1 && std::abs((double)(x-end))>1 && ((*cells)[x][y].CIpenalty > maxCIScore || (*cells)[x][y].Cpenalty > maxConScore) )
|
|
{
|
|
return false;
|
|
} else {
|
|
m_cellPointList.append( TQPoint( x, y ) );
|
|
}
|
|
}
|
|
}
|
|
else
|
|
{
|
|
for ( int y = start; y!=end; y+=dd )
|
|
{
|
|
if ( std::abs((double)(y-start))>1 && std::abs((double)(y-end))>1 && ((*cells)[x][y].CIpenalty > maxCIScore || (*cells)[x][y].Cpenalty > maxConScore) )
|
|
{
|
|
return false;
|
|
} else {
|
|
m_cellPointList.append( TQPoint( x, y ) );
|
|
}
|
|
}
|
|
}
|
|
|
|
m_cellPointList.prepend( TQPoint( scx, scy ) );
|
|
m_cellPointList.append( TQPoint( ecx, ecy ) );
|
|
removeDuplicatePoints();
|
|
return true;
|
|
}
|
|
|
|
|
|
void ConRouter::removeDuplicatePoints()
|
|
{
|
|
TQPoint prev(-1,-1);
|
|
|
|
const TQPointList::iterator end = m_cellPointList.end();
|
|
for ( TQPointList::iterator it = m_cellPointList.begin(); it != end; ++it )
|
|
{
|
|
if ( *it == prev ) {
|
|
*it = TQPoint(-1,-1);
|
|
} else {
|
|
prev = *it;
|
|
}
|
|
}
|
|
m_cellPointList.remove( TQPoint(-1,-1) );
|
|
}
|