![[tokkee]](http://tokkee.org/images/avatar.png){kind=avatar}
index 747fd1f86f137e5909431b385b3ba1c54458a187..4a7b0af2d39309c521deca07140334e5aaceef36 100644 (file)
* See the file LICENSE.LGPL distributed with the library.
*
* Licensees holding a valid commercial license may use this file in
- * accordance with the commercial license agreement provided with the
+ * accordance with the commercial license agreement provided with the
* library.
*
* 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.
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
*
* Author(s): Michael Wybrow <mjwybrow@users.sourceforge.net>
*/
static const size_t YDIM = 1;
-class ShiftSegment
+class ShiftSegment
{
public:
// For shiftable segments.
- ShiftSegment(ConnRef *conn, const size_t low, const size_t high,
+ ShiftSegment(ConnRef *conn, const size_t low, const size_t high,
bool isSBend, const size_t dim, double minLim, double maxLim)
: connRef(conn),
indexLow(low),
maxSpaceLimit(maxLim)
{
}
+
// For fixed segments.
- ShiftSegment(ConnRef *conn, const size_t low, const size_t high,
+ ShiftSegment(ConnRef *conn, const size_t low, const size_t high,
const size_t dim)
: connRef(conn),
indexLow(low),
minSpaceLimit = lowPoint()[dim];
maxSpaceLimit = lowPoint()[dim];
}
+
Point& lowPoint(void)
{
return connRef->displayRoute().ps[indexLow];
}
+
Point& highPoint(void)
{
return connRef->displayRoute().ps[indexHigh];
}
+
const Point& lowPoint(void) const
{
return connRef->displayRoute().ps[indexLow];
}
- const Point& highPoint(void) const
+
+ const Point& highPoint(void) const
{
return connRef->displayRoute().ps[indexHigh];
}
- const int fixedOrder(bool& isFixed) const
+
+ int fixedOrder(bool& isFixed) const
{
if (fixed)
{
}
return 0;
}
- const int order(void) const
+
+ int order(void) const
{
if (lowC())
{
}
return 0;
}
+
bool operator<(const ShiftSegment& rhs) const
{
const Point& lowPt = lowPoint();
const Point& rhsLowPt = rhs.lowPoint();
-
+
if (lowPt[dimension] != rhsLowPt[dimension])
{
return lowPt[dimension] < rhsLowPt[dimension];
}
return this < &rhs;
}
+
// This counts segments that are colliear and share an endpoint as
// overlapping. This allows them to be nudged apart where possible.
bool overlapsWith(const ShiftSegment& rhs, const size_t dim) const
double minSpaceLimit;
double maxSpaceLimit;
private:
- const bool lowC(void) const
+ bool lowC(void) const
{
// This is true if this is a cBend and its adjoining points
// are at lower positions.
}
return false;
}
- const bool highC(void) const
+
+ bool highC(void) const
{
// This is true if this is a cBend and its adjoining points
// are at higher positions.
struct CmpNodePos { bool operator()(const Node* u, const Node* v) const; };
typedef std::set<Node*,CmpNodePos> NodeSet;
-struct Node
+struct Node
{
ShapeRef *v;
VertInf *c;
pos(p),
firstAbove(NULL),
firstBelow(NULL)
- {
+ {
//COLA_ASSERT(r->width()<1e40);
v->polygon().getBoundingRect(&min[0], &min[1], &max[0], &max[1]);
- }
+ }
Node(VertInf *c, const double p)
: v(NULL),
c(c),
{
min[0] = max[0] = c->point.x;
min[1] = max[1] = c->point.y;
- }
+ }
Node(ShiftSegment *ss, const double p)
: v(NULL),
c(NULL),
{
// These values shouldn't ever be used, so they don't matter.
min[0] = max[0] = min[1] = max[1] = 0;
- }
- ~Node()
+ }
+ ~Node()
{
}
// Find the first Node above in the scanline that is a shape edge,
{
curr = curr->firstAbove;
}
-
+
if (curr)
{
return curr->max[dim];
{
curr = curr->firstBelow;
}
-
+
if (curr)
{
return curr->min[dim];
}
return DBL_MAX;
}
- // Mark all connector segments above in the scanline as being able
+ // Mark all connector segments above in the scanline as being able
// to see to this shape edge.
void markShiftSegmentsAbove(size_t dim)
{
{
if (curr->ss && (curr->pos <= min[dim]))
{
- curr->ss->maxSpaceLimit =
+ curr->ss->maxSpaceLimit =
std::min(min[dim], curr->ss->maxSpaceLimit);
}
curr = curr->firstAbove;
}
}
- // Mark all connector segments below in the scanline as being able
+ // Mark all connector segments below in the scanline as being able
// to see to this shape edge.
void markShiftSegmentsBelow(size_t dim)
{
{
if (curr->ss && (curr->pos >= max[dim]))
{
- curr->ss->minSpaceLimit =
+ curr->ss->minSpaceLimit =
std::max(max[dim], curr->ss->minSpaceLimit);
}
curr = curr->firstBelow;
bool clearVisibility = true;
firstAbovePos = -DBL_MAX;
firstBelowPos = DBL_MAX;
- // We start looking left from the right side of the shape,
- // and vice versa.
+ // We start looking left from the right side of the shape,
+ // and vice versa.
lastAbovePos = max[dim];
lastBelowPos = min[dim];
}
curr = curr->firstAbove;
}
-
+
// Find the first blocking edge below this point. Don't count the
// edges as we are travelling out of shapes we are inside, but then
// mark clearVisibility as false.
return clearVisibility;
}
- double firstPointAbove(size_t dim)
- {
- Node *curr = firstAbove;
- while (curr && (curr->max[dim] >= pos))
- {
- curr = curr->firstAbove;
- }
-
- if (curr)
- {
- return curr->max[dim];
- }
- return -DBL_MAX;
- }
- double firstPointBelow(size_t dim)
- {
- Node *curr = firstBelow;
- while (curr && (curr->min[dim] <= pos))
- {
- curr = curr->firstBelow;
- }
-
- if (curr)
- {
- return curr->min[dim];
- }
- return DBL_MAX;
- }
- // This is a bit inefficient, but we won't need to do it once we have
+ double firstPointAbove(size_t dim)
+ {
+ Node *curr = firstAbove;
+ while (curr && (curr->max[dim] >= pos))
+ {
+ curr = curr->firstAbove;
+ }
+
+ if (curr)
+ {
+ return curr->max[dim];
+ }
+ return -DBL_MAX;
+ }
+ double firstPointBelow(size_t dim)
+ {
+ Node *curr = firstBelow;
+ while (curr && (curr->min[dim] <= pos))
+ {
+ curr = curr->firstBelow;
+ }
+
+ if (curr)
+ {
+ return curr->min[dim];
+ }
+ return DBL_MAX;
+ }
+ // This is a bit inefficient, but we won't need to do it once we have
// connection points.
bool isInsideShape(size_t dimension)
{
};
-bool CmpNodePos::operator() (const Node* u, const Node* v) const
+bool CmpNodePos::operator() (const Node* u, const Node* v) const
{
- if (u->pos != v->pos)
+ if (u->pos != v->pos)
{
return u->pos < v->pos;
}
-
+
// Use the pointers to the base objects to differentiate them.
- void *up = (u->v) ? (void *) u->v :
+ void *up = (u->v) ? (void *) u->v :
((u->c) ? (void *) u->c : (void *) u->ss);
- void *vp = (v->v) ? (void *) v->v :
+ void *vp = (v->v) ? (void *) v->v :
((v->c) ? (void *) v->c : (void *) v->ss);
return up < vp;
}
typedef enum {
Open = 1,
SegOpen = 2,
- ConnPoint = 3,
+ ConnPoint = 3,
SegClose = 4,
Close = 5
} EventType;
struct Event
{
- Event(EventType t, Node *v, double p)
+ Event(EventType t, Node *v, double p)
: type(t),
v(v),
pos(p)
// Returns a bitfield of the direction of visibility (in this dimension)
-// made up of ConnDirDown (for visibility towards lower position values)
+// made up of ConnDirDown (for visibility towards lower position values)
// and ConnDirUp (for visibility towards higher position values).
//
static ConnDirFlags getPosVertInfDirection(VertInf *v, size_t dim)
}
else if (dirs == ConnDirDown)
{
- // For libavoid the Y-axis points downwards, so in terms of
+ // For libavoid the Y-axis points downwards, so in terms of
// smaller or larger position values, Down is Up and vice versa.
return ConnDirUp;
}
else if (dirs == ConnDirUp)
{
- // For libavoid the Y-axis points downwards, so in terms of
+ // For libavoid the Y-axis points downwards, so in terms of
// smaller or larger position values, Down is Up and vice versa.
return ConnDirDown;
}
dir(d)
{
}
-
- bool operator<(const PosVertInf& rhs) const
+
+ bool operator<(const PosVertInf& rhs) const
{
if (pos != rhs.pos)
{
VertInf *vert;
// A bitfield marking the direction of visibility (in this dimension)
- // made up of ConnDirDown (for visibility towards lower position values)
+ // made up of ConnDirDown (for visibility towards lower position values)
// and ConnDirUp (for visibility towards higher position values).
//
ConnDirFlags dir;
struct CmpVertInf
-{
+{
bool operator()(const VertInf* u, const VertInf* v) const
{
// Comparator for VertSet, an ordered set of VertInf pointers.
typedef std::set<VertInf *, CmpVertInf> VertSet;
-// A set of points to break the line segment,
+// A set of points to break the line segment,
// along with vertices for these points.
typedef std::set<PosVertInf> BreakpointSet;
-// Temporary structure used to store the possible horizontal visibility
+// Temporary structure used to store the possible horizontal visibility
// lines arising from the vertical sweep.
-class LineSegment
+class LineSegment
{
public:
- LineSegment(const double& b, const double& f, const double& p,
- bool ss = false, VertInf *bvi = NULL, VertInf *fvi = NULL)
+ LineSegment(const double& b, const double& f, const double& p,
+ bool /*ss*/ = false, VertInf *bvi = NULL, VertInf *fvi = NULL)
: begin(b),
finish(f),
pos(p),
vertInfs.insert(fvi);
}
}
+
LineSegment(const double& bf, const double& p, VertInf *bfvi = NULL)
: begin(bf),
finish(bf),
vertInfs.insert(bfvi);
}
}
-
+
// Order by begin, pos, finish.
- bool operator<(const LineSegment& rhs) const
+ bool operator<(const LineSegment& rhs) const
{
if (begin != rhs.begin)
{
// Lines are exactly equal.
return true;
}
-
+
if (pos == rhs.pos)
{
if (((begin >= rhs.begin) && (begin <= rhs.finish)) ||
finish = std::max(finish, segment.finish);
vertInfs.insert(segment.vertInfs.begin(), segment.vertInfs.end());
}
-
+
VertInf *beginVertInf(void) const
{
if (vertInfs.empty())
}
}
- // Converts a section of the points list to a set of breakPoints.
+ // Converts a section of the points list to a set of breakPoints.
// Returns the first of the intersection points occuring at finishPos.
- VertSet::iterator addSegmentsUpTo(Router *router, double finishPos)
+ VertSet::iterator addSegmentsUpTo(Router */*router*/, double finishPos)
{
VertSet::iterator firstIntersectionPt = vertInfs.end();
- for (VertSet::iterator vert = vertInfs.begin();
+ for (VertSet::iterator vert = vertInfs.begin();
vert != vertInfs.end(); ++vert)
{
if ((*vert)->point.x > finishPos)
// We're done.
break;
}
-
+
breakPoints.insert(PosVertInf((*vert)->point.x, (*vert),
getPosVertInfDirection(*vert, XDIM)));
- if ((firstIntersectionPt == vertInfs.end()) &&
+ if ((firstIntersectionPt == vertInfs.end()) &&
((*vert)->point.x == finishPos))
{
firstIntersectionPt = vert;
return firstIntersectionPt;
}
- // Add visibility edge(s) for this segment. There may be multiple if
+ // Add visibility edge(s) for this segment. There may be multiple if
// one of the endpoints is shared by multiple connector endpoints.
void addEdgeHorizontal(Router *router)
{
commitBegin(router);
commitFinish(router);
-
+
addSegmentsUpTo(router, finish);
}
// Add visibility edge(s) for this segment up until an intersection.
// Then, move the segment beginning to the intersection point, so we
// later only consider the remainder of the segment.
- // There may be multiple segments added to the graph if the beginning
+ // There may be multiple segments added to the graph if the beginning
// endpoint of the segment is shared by multiple connector endpoints.
- VertSet addEdgeHorizontalTillIntersection(Router *router,
+ VertSet addEdgeHorizontalTillIntersection(Router *router,
LineSegment& vertLine)
{
VertSet intersectionSet;
// Does a vertex already exist for this point.
commitPositionX(router, vertLine.pos);
-
- // Generate segments and set end iterator to the first point
+
+ // Generate segments and set end iterator to the first point
// at the intersection position.
VertSet::iterator restBegin = addSegmentsUpTo(router, vertLine.pos);
// Add the intersections points to intersectionSet.
VertSet::iterator restEnd = restBegin;
- while ((restEnd != vertInfs.end()) &&
+ while ((restEnd != vertInfs.end()) &&
(*restEnd)->point.x == vertLine.pos)
{
++restEnd;
return intersectionSet;
}
-
+
// Insert vertical breakpoints.
void insertBreakpointsBegin(Router *router, LineSegment& vertLine)
{
{
if ((*v)->point.x == begin)
{
- vertLine.breakPoints.insert(PosVertInf(pos, *v,
+ vertLine.breakPoints.insert(PosVertInf(pos, *v,
getPosVertInfDirection(*v, YDIM)));
}
}
{
// Here we have a pair of two endpoints that are both
// connector endpoints and both are inside a shape.
-
+
// Give vert visibility back to the first non-connector
// endpoint vertex (i.e., the side of the shape).
BreakpointSet::iterator side = last;
bool canSeeDown = (vert->dir & ConnDirDown);
if (canSeeDown && side->vert->id.isShape)
{
- EdgeInf *edge = new
+ EdgeInf *edge = new
EdgeInf(side->vert, vert->vert, orthogonal);
- edge->setDist(vert->vert->point[dim] -
+ edge->setDist(vert->vert->point[dim] -
side->vert->point[dim]);
}
// Give last visibility back to the first non-connector
// endpoint vertex (i.e., the side of the shape).
side = vert;
- while ((side != breakPoints.end()) &&
+ while ((side != breakPoints.end()) &&
!side->vert->id.isShape)
{
++side;
bool canSeeUp = (last->dir & ConnDirUp);
if (canSeeUp && (side != breakPoints.end()))
{
- EdgeInf *edge = new
+ EdgeInf *edge = new
EdgeInf(last->vert, side->vert, orthogonal);
- edge->setDist(side->vert->point[dim] -
+ edge->setDist(side->vert->point[dim] -
last->vert->point[dim]);
}
}
-
+
// The normal case.
//
- // Note: It's okay to give two connector endpoints visbility
- // here since we only consider the partner endpoint as a
+ // Note: It's okay to give two connector endpoints visbility
+ // here since we only consider the partner endpoint as a
// candidate while searching if it is the other endpoint of
// the connector in question.
//
}
if (generateEdge)
{
- EdgeInf *edge =
+ EdgeInf *edge =
new EdgeInf(last->vert, vert->vert, orthogonal);
- edge->setDist(vert->vert->point[dim] -
+ edge->setDist(vert->vert->point[dim] -
last->vert->point[dim]);
}
double finish;
double pos;
bool shapeSide;
-
+
VertSet vertInfs;
BreakpointSet breakPoints;
private:
- // MSVC wants to generate the assignment operator and the default
- // constructor, but fails. Therefore we declare them private and
+ // MSVC wants to generate the assignment operator and the default
+ // constructor, but fails. Therefore we declare them private and
// don't implement them.
LineSegment & operator=(LineSegment const &);
LineSegment();
}
else
{
- // This is the first overlapping segment, so just
+ // This is the first overlapping segment, so just
// merge the new segment with this one.
curr->mergeVertInfs(segment);
found = curr;
// Given a router instance and a set of possible horizontal segments, and a
// possible vertical visibility segment, compute and add edges to the
// orthogonal visibility graph for all the visibility edges.
-static void intersectSegments(Router *router, SegmentList& segments,
+static void intersectSegments(Router *router, SegmentList& segments,
LineSegment& vertLine)
{
COLA_ASSERT(vertLine.beginVertInf() == NULL);
{
// Add horizontal visibility segment.
horiLine.addEdgeHorizontal(router);
-
+
horiLine.insertBreakpointsFinish(router, vertLine);
-
+
size_t dim = XDIM; // x-dimension
horiLine.generateVisibilityEdgesFromBreakpointSet(router, dim);
if (inVertSegRegion)
{
// Add horizontal visibility segment.
- VertSet intersectionVerts =
+ VertSet intersectionVerts =
horiLine.addEdgeHorizontalTillIntersection(
router, vertLine);
}
-// Processes an event for the vertical sweep used for computing the static
-// orthogonal visibility graph. This adds possible visibility sgments to
+// Processes an event for the vertical sweep used for computing the static
+// orthogonal visibility graph. This adds possible visibility sgments to
// the segments list.
// The first pass is adding the event to the scanline, the second is for
// processing the event and the third for removing it from the scanline.
-static void processEventVert(Router *router, NodeSet& scanline,
+static void processEventVert(Router *router, NodeSet& scanline,
SegmentListWrapper& segments, Event *e, unsigned int pass)
{
Node *v = e->v;
-
+
if ( ((pass == 1) && (e->type == Open)) ||
((pass == 2) && (e->type == ConnPoint)) )
{
NodeSet::iterator it = v->iter;
// Work out neighbours
- if (it != scanline.begin())
+ if (it != scanline.begin())
{
Node *u = *(--it);
v->firstAbove = u;
u->firstBelow = v;
}
it = v->iter;
- if (++it != scanline.end())
+ if (++it != scanline.end())
{
Node *u = *it;
v->firstBelow = u;
u->firstAbove = v;
}
}
-
+
if (pass == 2)
{
if ((e->type == Open) || (e->type == Close))
if (minLimitMax >= maxLimitMin)
{
// Insert possible visibility segments.
- VertInf *vI1 = new VertInf(router, dummyOrthogID,
+ VertInf *vI1 = new VertInf(router, dummyOrthogID,
Point(minShape, lineY));
- VertInf *vI2 = new VertInf(router, dummyOrthogID,
+ VertInf *vI2 = new VertInf(router, dummyOrthogID,
Point(maxShape, lineY));
-
+
// There are no overlapping shapes, so give full visibility.
if (minLimit < minShape)
{
segments.insert(LineSegment(minLimit, minShape, lineY,
true, NULL, vI1));
}
- segments.insert(LineSegment(minShape, maxShape, lineY,
+ segments.insert(LineSegment(minShape, maxShape, lineY,
true, vI1, vI2));
if (maxShape < maxLimit)
{
LineSegment *line1 = NULL, *line2 = NULL;
if (!inShape || (centreVert->visDirections & ConnDirLeft))
{
- line1 = segments.insert(LineSegment(minLimit, cp.x, e->pos,
+ line1 = segments.insert(LineSegment(minLimit, cp.x, e->pos,
true, NULL, centreVert));
}
if (!inShape || (centreVert->visDirections & ConnDirRight))
{
- line2 = segments.insert(LineSegment(cp.x, maxLimit, e->pos,
+ line2 = segments.insert(LineSegment(cp.x, maxLimit, e->pos,
true, centreVert, NULL));
}
if (!line1 && !line2)
// Add a point segment for the centre point.
segments.insert(LineSegment(cp.x, e->pos, centreVert));
}
-
+
if (!inShape)
{
// This is not contained within a shape so add a normal
}
}
}
-
+
if ( ((pass == 3) && (e->type == Close)) ||
((pass == 2) && (e->type == ConnPoint)) )
{
// Clean up neighbour pointers.
Node *l = v->firstAbove, *r = v->firstBelow;
- if (l != NULL)
+ if (l != NULL)
{
l->firstBelow = v->firstBelow;
}
}
-// Processes an event for the vertical sweep used for computing the static
-// orthogonal visibility graph. This adds possible visibility sgments to
+// Processes an event for the vertical sweep used for computing the static
+// orthogonal visibility graph. This adds possible visibility sgments to
// the segments list.
// The first pass is adding the event to the scanline, the second is for
// processing the event and the third for removing it from the scanline.
-static void processEventHori(Router *router, NodeSet& scanline,
+static void processEventHori(Router */*router*/, NodeSet& scanline,
SegmentListWrapper& segments, Event *e, unsigned int pass)
{
Node *v = e->v;
-
+
if ( ((pass == 1) && (e->type == Open)) ||
((pass == 2) && (e->type == ConnPoint)) )
{
NodeSet::iterator it = v->iter;
// Work out neighbours
- if (it != scanline.begin())
+ if (it != scanline.begin())
{
Node *u = *(--it);
v->firstAbove = u;
u->firstBelow = v;
}
it = v->iter;
- if (++it != scanline.end())
+ if (++it != scanline.end())
{
Node *u = *it;
v->firstBelow = u;
u->firstAbove = v;
}
}
-
+
if (pass == 2)
{
if ((e->type == Open) || (e->type == Close))
{
if ((minLimitMax > minLimit) && (minLimitMax >= minShape))
{
- LineSegment vertSeg =
+ LineSegment vertSeg =
LineSegment(minLimit, minLimitMax, lineX);
segments.insert(vertSeg);
}
if ((maxLimitMin < maxLimit) && (maxLimitMin <= maxShape))
{
- LineSegment vertSeg =
+ LineSegment vertSeg =
LineSegment(maxLimitMin, maxLimit, lineX);
segments.insert(vertSeg);
}
double minLimit = v->firstPointAbove(1);
double maxLimit = v->firstPointBelow(1);
bool inShape = v->isInsideShape(1);
-
+
if (!inShape || (centreVert->visDirections & ConnDirUp))
{
segments.insert(LineSegment(minLimit, cp.y, e->pos));
}
}
}
-
+
if ( ((pass == 3) && (e->type == Close)) ||
((pass == 2) && (e->type == ConnPoint)) )
{
// Clean up neighbour pointers.
Node *l = v->firstAbove, *r = v->firstBelow;
- if (l != NULL)
+ if (l != NULL)
{
l->firstBelow = v->firstBelow;
}
++shRefIt;
}
- for (VertInf *curr = router->vertices.connsBegin();
- curr && (curr != router->vertices.shapesBegin());
+ for (VertInf *curr = router->vertices.connsBegin();
+ curr && (curr != router->vertices.shapesBegin());
curr = curr->lstNext)
{
Point& point = curr->point;
{
for (unsigned j = posStartIndex; j < posFinishIndex; ++j)
{
- processEventVert(router, scanline, segments,
+ processEventVert(router, scanline, segments,
events[j], pass);
}
}
posStartIndex = i;
}
- // Do the first sweep event handling -- building the correct
+ // Do the first sweep event handling -- building the correct
// structure of the scanline.
const int pass = 1;
processEventVert(router, scanline, segments, events[i], pass);
++shRefIt;
}
- for (VertInf *curr = router->vertices.connsBegin();
- curr && (curr != router->vertices.shapesBegin());
+ for (VertInf *curr = router->vertices.connsBegin();
+ curr && (curr != router->vertices.shapesBegin());
curr = curr->lstNext)
{
Point& point = curr->point;
{
for (unsigned j = posStartIndex; j < posFinishIndex; ++j)
{
- processEventHori(router, scanline, vertSegments,
+ processEventHori(router, scanline, vertSegments,
events[j], pass);
}
}
-
+
// Process the merged line segments.
vertSegments.list().sort();
for (SegmentList::iterator curr = vertSegments.list().begin();
posStartIndex = i;
}
- // Do the first sweep event handling -- building the correct
+ // Do the first sweep event handling -- building the correct
// structure of the scanline.
const int pass = 1;
processEventHori(router, scanline, vertSegments, events[i], pass);
// Add portions of the horizontal line that are after the final vertical
// position we considered.
- for (SegmentList::iterator it = segments.list().begin();
+ for (SegmentList::iterator it = segments.list().begin();
it != segments.list().end(); )
{
LineSegment& horiLine = *it;
horiLine.addEdgeHorizontal(router);
-
+
size_t dim = XDIM; // x-dimension
horiLine.generateVisibilityEdgesFromBreakpointSet(router, dim);
-// Processes sweep events used to determine each horizontal and vertical
-// line segment in a connector's channel of visibility.
+// Processes sweep events used to determine each horizontal and vertical
+// line segment in a connector's channel of visibility.
// Four calls to this function are made at each position by the scanline:
// 1) Handle all Close event processing.
// 2) Remove Close event objects from the scanline.
// 3) Add Open event objects to the scanline.
// 4) Handle all Open event processing.
//
-static void processShiftEvent(Router *router, NodeSet& scanline,
- ShiftSegmentList& segments, Event *e, size_t dim,
- unsigned int pass)
+static void processShiftEvent(Router */*router*/, NodeSet& scanline,
+ ShiftSegmentList& /*segments*/, Event *e, size_t dim,
+ unsigned int pass)
{
Node *v = e->v;
-
+
if ( ((pass == 3) && (e->type == Open)) ||
((pass == 3) && (e->type == SegOpen)) )
{
NodeSet::iterator it = v->iter;
// Work out neighbours
- if (it != scanline.begin())
+ if (it != scanline.begin())
{
Node *u = *(--it);
v->firstAbove = u;
u->firstBelow = v;
}
it = v->iter;
- if (++it != scanline.end())
+ if (++it != scanline.end())
{
Node *u = *it;
v->firstBelow = u;
u->firstAbove = v;
}
}
-
+
if ( ((pass == 4) && (e->type == Open)) ||
((pass == 4) && (e->type == SegOpen)) ||
((pass == 1) && (e->type == SegClose)) ||
double minLimit = v->firstObstacleAbove(dim);
double maxLimit = v->firstObstacleBelow(dim);
- v->ss->minSpaceLimit =
+ v->ss->minSpaceLimit =
std::max(minLimit, v->ss->minSpaceLimit);
- v->ss->maxSpaceLimit =
+ v->ss->maxSpaceLimit =
std::min(maxLimit, v->ss->maxSpaceLimit);
}
else
v->markShiftSegmentsBelow(dim);
}
}
-
+
if ( ((pass == 2) && (e->type == SegClose)) ||
((pass == 2) && (e->type == Close)) )
{
// Clean up neighbour pointers.
Node *l = v->firstAbove, *r = v->firstBelow;
- if (l != NULL)
+ if (l != NULL)
{
l->firstBelow = v->firstBelow;
}
}
-static void buildOrthogonalChannelInfo(Router *router,
+static void buildOrthogonalChannelInfo(Router *router,
const size_t dim, ShiftSegmentList& segmentList)
{
if (router->routingPenalty(segmentPenalty) == 0)
size_t altDim = (dim + 1) % 2;
// For each connector.
- for (ConnRefList::const_iterator curr = router->connRefs.begin();
- curr != router->connRefs.end(); ++curr)
+ for (ConnRefList::const_iterator curr = router->connRefs.begin();
+ curr != router->connRefs.end(); ++curr)
{
if ((*curr)->routingType() != ConnType_Orthogonal)
{
continue;
}
Polygon& displayRoute = (*curr)->displayRoute();
- // Determine all line segments that we are interested in shifting.
+ // Determine all line segments that we are interested in shifting.
// We don't consider the first or last segment of a path.
for (size_t i = 1; i < displayRoute.size(); ++i)
{
indexLow = i;
indexHigh = i - 1;
}
- COLA_ASSERT(displayRoute.at(indexLow)[altDim] <
+ COLA_ASSERT(displayRoute.at(indexLow)[altDim] <
displayRoute.at(indexHigh)[altDim]);
if ((i == 1) || ((i + 1) == displayRoute.size()))
{
- // The first and last segment of a connector can't be
+ // The first and last segment of a connector can't be
// shifted. We call them fixed segments. Note: this
// will change if we later allow connection channels.
segmentList.push_back(
double prevPos = displayRoute.ps[i - 2][dim];
double nextPos = displayRoute.ps[i + 1][dim];
if (((prevPos < displayRoute.ps[i][dim]) &&
- (nextPos > displayRoute.ps[i][dim]))
+ (nextPos > displayRoute.ps[i][dim]))
||
((prevPos > displayRoute.ps[i][dim]) &&
(nextPos < displayRoute.ps[i][dim])) )
{
isSBend = true;
- // Determine limits if the s-bend is not due to an
- // obstacle. In this case we need to limit the channel
+ // Determine limits if the s-bend is not due to an
+ // obstacle. In this case we need to limit the channel
// to the span of the adjoining segments to this one.
if ((prevPos < displayRoute.ps[i][dim]) &&
(nextPos > displayRoute.ps[i][dim]))
else
{
// isCBend: Both adjoining segments are in the same
- // direction. We indicate this for later by setting
+ // direction. We indicate this for later by setting
// the maxLim or minLim to the segment position.
if (prevPos < displayRoute.ps[i][dim])
{
}
}
- segmentList.push_back(ShiftSegment(*curr, indexLow,
+ segmentList.push_back(ShiftSegment(*curr, indexLow,
indexHigh, isSBend, dim, minLim, maxLim));
}
}
// There are no segments, so we can just return now.
return;
}
-
+
// Do a sweep and shift these segments.
const size_t n = router->shapeRefs.size();
const size_t cpn = segmentList.size();
++shRefIt;
}
- for (ShiftSegmentList::iterator curr = segmentList.begin();
+ for (ShiftSegmentList::iterator curr = segmentList.begin();
curr != segmentList.end(); ++curr)
{
const Point& lowPt = curr->lowPoint();
{
for (unsigned j = posStartIndex; j < posFinishIndex; ++j)
{
- processShiftEvent(router, scanline, segmentList, events[j],
+ processShiftEvent(router, scanline, segmentList, events[j],
dim, pass);
}
}
posStartIndex = i;
}
- // Do the first sweep event handling -- building the correct
+ // Do the first sweep event handling -- building the correct
// structure of the scanline.
const int pass = 1;
processShiftEvent(router, scanline, segmentList, events[i],
static void simplifyOrthogonalRoutes(Router *router)
{
// Simplify routes.
- for (ConnRefList::const_iterator curr = router->connRefs.begin();
- curr != router->connRefs.end(); ++curr)
+ for (ConnRefList::const_iterator curr = router->connRefs.begin();
+ curr != router->connRefs.end(); ++curr)
{
if ((*curr)->routingType() != ConnType_Orthogonal)
{
}
-static void buildOrthogonalNudgingOrderInfo(Router *router,
+static void buildOrthogonalNudgingOrderInfo(Router *router,
PtOrderMap& pointOrders)
{
// Simplify routes.
int crossingsN = 0;
// Do segment splitting.
- for (ConnRefList::const_iterator curr = router->connRefs.begin();
- curr != router->connRefs.end(); ++curr)
+ for (ConnRefList::const_iterator curr = router->connRefs.begin();
+ curr != router->connRefs.end(); ++curr)
{
if ((*curr)->routingType() != ConnType_Orthogonal)
{
continue;
}
ConnRef *conn = *curr;
-
- for (ConnRefList::const_iterator curr2 = router->connRefs.begin();
- curr2 != router->connRefs.end(); ++curr2)
+
+ for (ConnRefList::const_iterator curr2 = router->connRefs.begin();
+ curr2 != router->connRefs.end(); ++curr2)
{
if ((*curr2)->routingType() != ConnType_Orthogonal)
{
continue;
}
ConnRef *conn2 = *curr2;
-
+
if (conn == conn2)
{
continue;
}
-
+
Avoid::Polygon& route = conn->displayRoute();
Avoid::Polygon& route2 = conn2->displayRoute();
splitBranchingSegments(route2, true, route);
}
}
- for (ConnRefList::const_iterator curr = router->connRefs.begin();
- curr != router->connRefs.end(); ++curr)
+ for (ConnRefList::const_iterator curr = router->connRefs.begin();
+ curr != router->connRefs.end(); ++curr)
{
if ((*curr)->routingType() != ConnType_Orthogonal)
{
continue;
}
ConnRef *conn = *curr;
-
- for (ConnRefList::const_iterator curr2 = curr;
- curr2 != router->connRefs.end(); ++curr2)
+
+ for (ConnRefList::const_iterator curr2 = curr;
+ curr2 != router->connRefs.end(); ++curr2)
{
if ((*curr2)->routingType() != ConnType_Orthogonal)
{
{
continue;
}
-
+
Avoid::Polygon& route = conn->displayRoute();
Avoid::Polygon& route2 = conn2->displayRoute();
bool checkForBranchingSegments = false;
for (size_t i = 1; i < route.size(); ++i)
{
const bool finalSegment = ((i + 1) == route.size());
- crossings += countRealCrossings(route2, true, route, i,
- checkForBranchingSegments, finalSegment, NULL,
+ crossings += countRealCrossings(route2, true, route, i,
+ checkForBranchingSegments, finalSegment, NULL,
&pointOrders, conn2, conn).first;
}
if (crossings > 0)
}
}
}
-
+
// Sort the point orders.
PtOrderMap::iterator finish = pointOrders.end();
for (PtOrderMap::iterator it = pointOrders.begin(); it != finish; ++it)
}
-class CmpLineOrder
+class CmpLineOrder
{
public:
CmpLineOrder(PtOrderMap& ord, const size_t dim)
{
*comparable = true;
}
- Point lhsLow = lhs.lowPoint();
- Point rhsLow = rhs.lowPoint();
+ Point lhsLow = lhs.lowPoint();
+ Point rhsLow = rhs.lowPoint();
#ifndef NDEBUG
- const Point& lhsHigh = lhs.highPoint();
- const Point& rhsHigh = rhs.highPoint();
+ const Point& lhsHigh = lhs.highPoint();
+ const Point& rhsHigh = rhs.highPoint();
#endif
size_t altDim = (dimension + 1) % 2;
{
return lhsLow[dimension] < rhsLow[dimension];
}
-
- // If one of these is fixed, then determine order based on
- // fixed segment, that is, order so the fixed segment doesn't
+
+ // If one of these is fixed, then determine order based on
+ // fixed segment, that is, order so the fixed segment doesn't
// block movement.
bool oneIsFixed = false;
const int lhsFixedOrder = lhs.fixedOrder(oneIsFixed);
return lhsFixedOrder < rhsFixedOrder;
}
- // C-bends that did not have a clear order with s-bends might
- // not have a good ordering here, so compare their order in
+ // C-bends that did not have a clear order with s-bends might
+ // not have a good ordering here, so compare their order in
// terms of C-bend direction and S-bends and use that if it
// differs for the two segments.
const int lhsOrder = lhs.order();
{
// A value for rhsPos or lhsPos mean the points are not directly
// comparable, meaning they are at the same position but cannot
- // overlap (they are just collinear. The relative order for
+ // overlap (they are just collinear. The relative order for
// these segments is not important since we do not constrain
// them against each other.
//COLA_ASSERT(lhs.overlapsWith(rhs, dimension) == false);
};
-// We can use the normaal sort algorithm for lists since it is not possible
-// to comapre all elements, but there will be an ordering defined between
-// most of the elements. Hence we order these, using insertion sort, and
-// the case of them not being able to be compared is handled by not setting
+// We can use the normaal sort algorithm for lists since it is not possible
+// to comapre all elements, but there will be an ordering defined between
+// most of the elements. Hence we order these, using insertion sort, and
+// the case of them not being able to be compared is handled by not setting
// up any constraints between such segments when doing the nudging.
//
-static ShiftSegmentList linesort(ShiftSegmentList origList,
+static ShiftSegmentList linesort(ShiftSegmentList origList,
CmpLineOrder& comparison)
{
ShiftSegmentList resultList;
typedef std::list<ShiftSegment *> ShiftSegmentPtrList;
-static void nudgeOrthogonalRoutes(Router *router, size_t dimension,
+static void nudgeOrthogonalRoutes(Router *router, size_t dimension,
PtOrderMap& pointOrders, ShiftSegmentList& segmentList)
{
// Do the actual nudging.
}
CmpLineOrder lineSortComp(pointOrders, dimension);
currentRegion = linesort(currentRegion, lineSortComp);
-
+
if (currentRegion.size() == 1)
{
// Save creating the solver instance if there is just one
currSegment != currentRegion.end(); ++currSegment)
{
Point& lowPt = currSegment->lowPoint();
-
+
// Create a solver variable for the position of this segment.
int varID = freeID;
double idealPos = lowPt[dimension];
{
COLA_ASSERT(currSegment->minSpaceLimit > -CHANNEL_MAX);
COLA_ASSERT(currSegment->maxSpaceLimit < CHANNEL_MAX);
-
+
// For s-bends, take the middle as ideal.
idealPos = currSegment->minSpaceLimit +
((currSegment->maxSpaceLimit -
}
else
{
- // Set a higher weight for c-bends to stop them sometimes
+ // Set a higher weight for c-bends to stop them sometimes
// getting pushed out into channels by more-free connectors
// to the "inner" side of them.
weight = strongWeight;
if (currSegment->overlapsWith(*prevSeg, dimension) &&
(!(currSegment->fixed) || !(prevSeg->fixed)))
{
- // If there is a previous segment to the left that
- // could overlap this in the shift direction, then
+ // If there is a previous segment to the left that
+ // could overlap this in the shift direction, then
// constrain the two segments to be separated.
- // Though don't add the constraint if both the
+ // Though don't add the constraint if both the
// segments are fixed in place.
cs.push_back(new Constraint(prevVar, vs[index],
router->orthogonalNudgeDistance()));
if (!currSegment->fixed)
{
- // If this segment sees a channel boundary to its left,
+ // If this segment sees a channel boundary to its left,
// then constrain its placement as such.
if (currSegment->minSpaceLimit > -CHANNEL_MAX)
{
- vs.push_back(new Variable(fixedID,
+ vs.push_back(new Variable(fixedID,
currSegment->minSpaceLimit, fixedWeight));
- cs.push_back(new Constraint(vs[vs.size() - 1], vs[index],
+ cs.push_back(new Constraint(vs[vs.size() - 1], vs[index],
0.0));
}
-
- // If this segment sees a channel boundary to its right,
+
+ // If this segment sees a channel boundary to its right,
// then constrain its placement as such.
if (currSegment->maxSpaceLimit < CHANNEL_MAX)
{
- vs.push_back(new Variable(fixedID,
+ vs.push_back(new Variable(fixedID,
currSegment->maxSpaceLimit, fixedWeight));
cs.push_back(new Constraint(vs[index], vs[vs.size() - 1],
0.0));
IncSolver f(vs,cs);
f.solve();
bool satisfied = true;
- for (size_t i = 0; i < vs.size(); ++i)
+ for (size_t i = 0; i < vs.size(); ++i)
{
if (vs[i]->id == fixedID)
{
{
// Build nudging info.
// XXX: We need to build the point orders separately in each
- // dimension since things move. There is probably a more
+ // dimension since things move. There is probably a more
// efficient way to do this.
PtOrderMap pointOrders;
buildOrthogonalNudgingOrderInfo(router, pointOrders);