/*
* vim: ts=4 sw=4 et tw=0 wm=0
*
* libavoid - Fast, Incremental, Object-avoiding Line Router
*
* Copyright (C) 2009 Monash University
*
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
* 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
* 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.
*
* Author(s): Michael Wybrow <mjwybrow@users.sourceforge.net>
*/
#include <cstdlib>
#include <cfloat>
#include <cmath>
#include <set>
#include <list>
#include <algorithm>
#include "libavoid/geomtypes.h"
#include "libavoid/orthogonal.h"
#include "libavoid/connector.h"
#include "libavoid/assertions.h"
#ifdef LIBAVOID_SDL
#include <SDL_gfxPrimitives.h>
#endif
namespace Avoid {
class ShiftSegment
{
public:
// For shiftable segments.
fixed(false),
{
}
// For fixed segments.
sBend(false),
fixed(true),
{
// This has no space to shift.
}
{
}
{
}
{
}
{
}
{
if (fixed)
{
isFixed = true;
return 0;
}
if (lowC())
{
return 1;
}
else if (highC())
{
return -1;
}
return 0;
}
int order(void) const
{
if (lowC())
{
return -1;
}
else if (highC())
{
return 1;
}
return 0;
}
bool operator<(const ShiftSegment& rhs) const
{
{
}
return this < &rhs;
}
// This counts segments that are colliear and share an endpoint as
// overlapping. This allows them to be nudged apart where possible.
{
{
{
return true;
}
}
return false;
}
bool sBend;
bool fixed;
double minSpaceLimit;
double maxSpaceLimit;
private:
bool lowC(void) const
{
// This is true if this is a cBend and its adjoining points
// are at lower positions.
{
return true;
}
return false;
}
bool highC(void) const
{
// This is true if this is a cBend and its adjoining points
// are at higher positions.
{
return true;
}
return false;
}
};
struct Node;
struct Node
{
ShapeRef *v;
VertInf *c;
double pos;
: v(v),
c(NULL),
pos(p),
{
//COLA_ASSERT(r->width()<1e40);
}
: v(NULL),
c(c),
pos(p),
{
}
: v(NULL),
c(NULL),
pos(p),
{
// These values shouldn't ever be used, so they don't matter.
}
~Node()
{
}
// Find the first Node above in the scanline that is a shape edge,
// and does not have an open or close event at this position (meaning
// it is just about to be removed).
{
{
}
if (curr)
{
}
return -DBL_MAX;
}
// Find the first Node below in the scanline that is a shape edge,
// and does not have an open or close event at this position (meaning
// it is just about to be removed).
{
{
}
if (curr)
{
}
return DBL_MAX;
}
// Mark all connector segments above in the scanline as being able
// to see to this shape edge.
{
{
{
}
}
}
// Mark all connector segments below in the scanline as being able
// to see to this shape edge.
{
{
{
}
}
}
{
bool clearVisibility = true;
firstAbovePos = -DBL_MAX;
// We start looking left from the right side of the shape,
// and vice versa.
// Find the first blocking edge above this point. Don't count the
// edges as we are travelling out of shapes we are inside, but then
// mark clearVisibility as false.
{
{
}
clearVisibility = false;
}
if (curr)
{
}
while (curr)
{
// There might be a larger shape after this one in the ordering.
{
}
}
// 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.
curr = firstBelow;
{
{
}
clearVisibility = false;
}
if (curr)
{
}
while (curr)
{
// There might be a larger shape after this one in the ordering.
{
}
}
return clearVisibility;
}
{
{
}
if (curr)
{
}
return -DBL_MAX;
}
{
{
}
if (curr)
{
}
return DBL_MAX;
}
// This is a bit inefficient, but we won't need to do it once we have
// connection points.
{
{
{
return true;
}
}
{
{
return true;
}
}
return false;
}
};
{
{
}
// Use the pointers to the base objects to differentiate them.
void *up = (u->v) ? (void *) u->v :
((u->c) ? (void *) u->c : (void *) u->ss);
void *vp = (v->v) ? (void *) v->v :
((v->c) ? (void *) v->c : (void *) v->ss);
}
// Note: Open must come first.
typedef enum {
} EventType;
struct Event
{
: type(t),
v(v),
pos(p)
{};
Node *v;
double pos;
};
// Used for quicksort. Must return <0, 0, or >0.
static int compare_events(const void *a, const void *b)
{
{
}
{
}
}
// Returns a bitfield of the direction of visibility (in this dimension)
// made up of ConnDirDown (for visibility towards lower position values)
// and ConnDirUp (for visibility towards higher position values).
//
{
{
{
return (ConnDirDown | ConnDirUp);
}
else if (dirs == ConnDirLeft)
{
return ConnDirDown;
}
else if (dirs == ConnDirRight)
{
return ConnDirUp;
}
}
{
{
return (ConnDirDown | ConnDirUp);
}
else if (dirs == ConnDirDown)
{
// For libavoid the Y-axis points downwards, so in terms of
// smaller or larger position values, Down is Up and vice versa.
return ConnDirUp;
}
{
// For libavoid the Y-axis points downwards, so in terms of
// smaller or larger position values, Down is Up and vice versa.
return ConnDirDown;
}
}
// Can occur for ConnDirNone visibility.
return ConnDirNone;
}
struct PosVertInf
{
: pos(p),
dir(d)
{
}
bool operator<(const PosVertInf& rhs) const
{
{
}
}
double pos;
// A bitfield marking the direction of visibility (in this dimension)
// made up of ConnDirDown (for visibility towards lower position values)
// and ConnDirUp (for visibility towards higher position values).
//
};
struct CmpVertInf
{
{
// Comparator for VertSet, an ordered set of VertInf pointers.
// It is assumed vertical sets of points will all have the same
// x position and horizontal sets all share a y position, so this
// method can be used to sort both these sets.
{
}
{
}
return u < v;
}
};
// A set of points to break the line segment,
// along with vertices for these points.
// Temporary structure used to store the possible horizontal visibility
// lines arising from the vertical sweep.
class LineSegment
{
public:
LineSegment(const double& b, const double& f, const double& p,
: begin(b),
finish(f),
pos(p),
shapeSide(false)
{
if (bvi)
{
}
if (fvi)
{
}
}
pos(p),
shapeSide(false)
{
if (bfvi)
{
}
}
// Order by begin, pos, finish.
bool operator<(const LineSegment& rhs) const
{
{
}
{
}
{
}
return false;
}
{
{
// Lines are exactly equal.
return true;
}
{
{
// They are colinear and overlap by some amount.
return true;
}
}
return false;
}
{
}
VertInf *beginVertInf(void) const
{
{
return NULL;
}
}
VertInf *finishVertInf(void) const
{
{
return NULL;
}
}
{
{
{
found = *v;
break;
}
}
if (!found)
{
}
return found;
}
// Set begin endpoint vertex if none has been assigned.
{
if (vert)
{
}
{
}
}
// Set begin endpoint vertex if none has been assigned.
{
if (vert)
{
}
{
}
}
// Converts a section of the points list to a set of breakPoints.
// Returns the first of the intersection points occuring at finishPos.
{
{
{
// We're done.
break;
}
{
}
}
// Returns the first of the intersection points at finishPos.
return firstIntersectionPt;
}
// Add visibility edge(s) for this segment. There may be multiple if
// one of the endpoints is shared by multiple connector endpoints.
{
}
// 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
// endpoint of the segment is shared by multiple connector endpoints.
{
// Does a vertex already exist for this point.
// Generate segments and set end iterator to the first point
// at the intersection position.
// Add the intersections points to intersectionSet.
{
++restEnd;
}
// Adjust segment to remove processed portion.
return intersectionSet;
}
// Insert vertical breakpoints.
{
{
}
{
}
{
{
getPosVertInfDirection(*v, YDIM)));
}
}
}
// Insert vertical breakpoints.
{
{
}
{
}
{
{
getPosVertInfDirection(*v, YDIM)));
}
}
}
{
{
if (!beginVertInf())
{
// Add begin point if it didn't intersect another line.
}
}
{
if (!finishVertInf())
{
// Add finish point if it didn't intersect another line.
}
}
const bool orthogonal = true;
{
{
// Assert points are not at the same position.
{
// 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).
{
{
break;
}
--side;
}
{
}
// Give last visibility back to the first non-connector
// endpoint vertex (i.e., the side of the shape).
{
++side;
}
{
}
}
// The normal case.
//
// 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.
//
bool generateEdge = true;
{
generateEdge = false;
}
{
generateEdge = false;
}
if (generateEdge)
{
}
++last;
}
++vert;
{
// Still looking at same pair, just reset prev number pointer.
}
else
{
// vert has moved to the beginning of a number number group.
// Last is now in the right place, so do nothing.
}
}
}
double begin;
double finish;
double pos;
bool shapeSide;
private:
// 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();
};
class SegmentListWrapper
{
public:
{
{
{
{
// This is not the first segment that overlaps,
// so we need to merge and then delete an existing
// segment.
}
else
{
// This is the first overlapping segment, so just
// merge the new segment with this one.
}
}
}
{
// Add this line.
}
return &(*found);
}
{
return _list;
}
private:
};
// 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.
{
{
{
// Add horizontal visibility segment.
// We've now swept past this horizontal segment, so delete.
continue;
}
{
// We've yet to reach this segment in the sweep, so ignore.
++it;
continue;
}
{
if (inVertSegRegion)
{
}
}
{
if (inVertSegRegion)
{
// Add horizontal visibility segment.
// And we've now finished with the segment, so delete.
continue;
}
}
else
{
if (inVertSegRegion)
{
// Add horizontal visibility segment.
v != intersectionVerts.end(); ++v)
{
getPosVertInfDirection(*v, YDIM)));
}
}
}
++it;
}
// Split breakPoints set into visibility segments.
}
// 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.
{
Node *v = e->v;
{
// Work out neighbours
{
v->firstAbove = u;
u->firstBelow = v;
}
{
v->firstBelow = u;
u->firstAbove = v;
}
}
if (pass == 2)
{
{
// Shape edge positions.
// As far as we can see.
// Only difference between Open and Close is whether the line
// segments are at the top or bottom of the shape. Decide here.
if (minLimitMax >= maxLimitMin)
{
// Insert possible visibility segments.
// There are no overlapping shapes, so give full visibility.
{
}
{
}
}
else
{
{
}
{
}
}
}
{
// Connection point.
// As far as we can see.
{
true, NULL, centreVert));
}
{
true, centreVert, NULL));
}
{
// Add a point segment for the centre point.
}
if (!inShape)
{
// This is not contained within a shape so add a normal
// visibility graph point here too (since paths won't route
// *through* connector endpoint vertices).
{
if (line1)
{
}
if (line2)
{
}
}
}
}
}
{
// Clean up neighbour pointers.
if (l != NULL)
{
l->firstBelow = v->firstBelow;
}
if (r != NULL)
{
r->firstAbove = v->firstAbove;
}
{
delete v;
}
else // if (e->type == Close)
{
delete v;
}
}
}
// 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.
{
Node *v = e->v;
{
// Work out neighbours
{
v->firstAbove = u;
u->firstBelow = v;
}
{
v->firstBelow = u;
u->firstAbove = v;
}
}
if (pass == 2)
{
{
// Shape edge positions.
// As far as we can see.
// Only difference between Open and Close is whether the line
// segments are at the left or right of the shape. Decide here.
if (minLimitMax >= maxLimitMin)
{
}
else
{
{
}
{
}
}
}
{
// Connection point.
// As far as we can see.
{
}
{
}
}
}
{
// Clean up neighbour pointers.
if (l != NULL)
{
l->firstBelow = v->firstBelow;
}
if (r != NULL)
{
r->firstAbove = v->firstAbove;
}
{
delete v;
}
else // if (e->type == Close)
{
delete v;
}
}
}
{
// Set up the events for the vertical sweep.
unsigned ctr = 0;
for (unsigned i = 0; i < n; i++)
{
++shRefIt;
}
{
}
// Process the vertical sweep.
// We do multiple passes over sections of the list so we can add relevant
// entries to the scanline that might follow, before process them.
unsigned int posStartIndex = 0;
unsigned int posFinishIndex = 0;
for (unsigned i = 0; i <= totalEvents; ++i)
{
// If we have finished the current scanline or all events, then we
// process the events on the current scanline in a couple of passes.
{
posFinishIndex = i;
{
for (unsigned j = posStartIndex; j < posFinishIndex; ++j)
{
}
}
if (i == totalEvents)
{
// We have cleaned up, so we can now break out of loop.
break;
}
posStartIndex = i;
}
// Do the first sweep event handling -- building the correct
// structure of the scanline.
}
for (unsigned i = 0; i < totalEvents; ++i)
{
delete events[i];
}
// Set up the events for the horizontal sweep.
ctr = 0;
for (unsigned i = 0; i < n; i++)
{
++shRefIt;
}
{
}
// Process the horizontal sweep
posStartIndex = 0;
for (unsigned i = 0; i <= totalEvents; ++i)
{
// If we have finished the current scanline or all events, then we
// process the events on the current scanline in a couple of passes.
{
posFinishIndex = i;
{
for (unsigned j = posStartIndex; j < posFinishIndex; ++j)
{
}
}
// Process the merged line segments.
{
}
if (i == totalEvents)
{
// We have cleaned up, so we can now break out of loop.
break;
}
posStartIndex = i;
}
// Do the first sweep event handling -- building the correct
// structure of the scanline.
}
for (unsigned i = 0; i < totalEvents; ++i)
{
delete events[i];
}
delete [] events;
// Add portions of the horizontal line that are after the final vertical
// position we considered.
{
}
}
//============================================================================
// Path Adjustment code
//============================================================================
// 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.
//
unsigned int pass)
{
Node *v = e->v;
{
// Work out neighbours
{
v->firstAbove = u;
u->firstBelow = v;
}
{
v->firstBelow = u;
u->firstAbove = v;
}
}
{
if (v->ss)
{
// As far as we can see.
v->ss->minSpaceLimit =
v->ss->maxSpaceLimit =
}
else
{
}
}
{
// Clean up neighbour pointers.
if (l != NULL)
{
l->firstBelow = v->firstBelow;
}
if (r != NULL)
{
r->firstAbove = v->firstAbove;
}
delete v;
}
}
{
{
// This code assumes the routes are pretty optimal, so we don't
// do this adjustment if the routes have no segment penalty.
return;
}
// For each connector.
{
{
continue;
}
// Determine all line segments that we are interested in shifting.
// We don't consider the first or last segment of a path.
{
{
// It's a segment in the dimension we are processing,
{
indexLow = i;
indexHigh = i - 1;
}
{
// 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.
continue;
}
// The segment probably has space to be shifted.
bool isSBend = false;
||
{
isSBend = true;
// 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.
{
}
else
{
}
}
else
{
// isCBend: Both adjoining segments are in the same
// direction. We indicate this for later by setting
// the maxLim or minLim to the segment position.
{
}
else
{
}
}
}
}
}
if (segmentList.empty())
{
// There are no segments, so we can just return now.
return;
}
// Do a sweep and shift these segments.
// Set up the events for the sweep.
unsigned ctr = 0;
for (unsigned i = 0; i < n; i++)
{
++shRefIt;
}
{
}
// Process the sweep.
// We do multiple passes over sections of the list so we can add relevant
// entries to the scanline that might follow, before process them.
unsigned int posStartIndex = 0;
unsigned int posFinishIndex = 0;
for (unsigned i = 0; i <= totalEvents; ++i)
{
// If we have finished the current scanline or all events, then we
// process the events on the current scanline in a couple of passes.
{
posFinishIndex = i;
{
for (unsigned j = posStartIndex; j < posFinishIndex; ++j)
{
}
}
if (i == totalEvents)
{
// We have cleaned up, so we can now break out of loop.
break;
}
posStartIndex = i;
}
// Do the first sweep event handling -- building the correct
// structure of the scanline.
}
for (unsigned i = 0; i < totalEvents; ++i)
{
delete events[i];
}
delete [] events;
}
{
// Simplify routes.
{
{
continue;
}
}
}
{
// Simplify routes.
int crossingsN = 0;
// Do segment splitting.
{
{
continue;
}
{
{
continue;
}
{
continue;
}
}
}
{
{
continue;
}
{
{
continue;
}
{
continue;
}
bool checkForBranchingSegments = false;
int crossings = 0;
{
}
if (crossings > 0)
{
crossingsN += crossings;
}
}
}
// Sort the point orders.
{
//const VertID& ptID = it->first;
{
}
}
}
class CmpLineOrder
{
public:
{
}
bool *comparable = NULL) const
{
if (comparable)
{
*comparable = true;
}
#ifndef NDEBUG
#endif
{
}
// 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;
{
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
// terms of C-bend direction and S-bends and use that if it
// differs for the two segments.
{
}
// Need to index using the original point into the map, so find it.
{
// 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
// these segments is not important since we do not constrain
// them against each other.
//COLA_ASSERT(lhs.overlapsWith(rhs, dimension) == false);
// We do need to be consistent though.
if (comparable)
{
*comparable = 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
// up any constraints between such segments when doing the nudging.
//
{
{
// Get and remove the first element from the origList.
// Find the insertion point in the resultList.
{
bool comparable = false;
if (comparable && lessThan)
{
// If it is comparable and lessThan, then we have found the
// insertion point.
break;
}
}
// Insert the element into the reultList at the required point.
}
return resultList;
}
{
// Do the actual nudging.
while (!segmentList.empty())
{
// Take a reference segment
// Then, find the segments that overlap this one.
{
bool overlaps = false;
{
{
overlaps = true;
break;
}
}
if (overlaps)
{
// Consider segments from the beginning, since we mave have
// since passed segments that overlap with the new set.
}
else
{
++curr;
}
}
{
// Save creating the solver instance if there is just one
// immovable segment.
{
continue;
}
}
// Process these segments.
// IDs:
const int freeID = 0;
// Weights:
//printf("-------------------------------------------------------\n");
//printf("Nudge -- size: %d\n", (int) currentRegion.size());
{
// Create a solver variable for the position of this segment.
if (currSegment->sBend)
{
// For s-bends, take the middle as ideal.
((currSegment->maxSpaceLimit -
}
else if (currSegment->fixed)
{
// Fixed segments shouldn't get moved.
}
else
{
// 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.
}
//printf("line %.15f pos: %g min: %g max: %g\n",
// lowPt[dimension], idealPos, currSegment->minSpaceLimit,
// currSegment->maxSpaceLimit);
// Constrain position in relation to previously seen segments,
// if necessary (i.e. when they could overlap).
{
{
// 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
// segments are fixed in place.
}
else
{
++prevVarIt;
}
}
if (!currSegment->fixed)
{
// If this segment sees a channel boundary to its left,
// then constrain its placement as such.
{
0.0));
}
// If this segment sees a channel boundary to its right,
// then constrain its placement as such.
{
0.0));
}
}
}
#if 0
}
#endif
f.solve();
bool satisfied = true;
{
{
{
satisfied = false;
break;
}
}
}
if (satisfied)
{
{
//printf("Pos: %X, %g\n", (int) currSegment->connRef, newPos);
}
}
#if 0
}
#endif
}
}
{
{
// Build nudging info.
// XXX: We need to build the point orders separately in each
// dimension since things move. There is probably a more
// efficient way to do this.
// Simplify routes.
// Do the centring and nudging.
}
}
}