/*
* vim: ts=4 sw=4 et tw=0 wm=0
*
* libavoid - Fast, Incremental, Object-avoiding Line Router
*
* Copyright (C) 2004-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 <algorithm>
#include <vector>
#include <climits>
#define _USE_MATH_DEFINES
#include <cmath>
#include "libavoid/vertices.h"
#include "libavoid/makepath.h"
#include "libavoid/geometry.h"
#include "libavoid/connector.h"
#include "libavoid/assertions.h"
#ifdef ASTAR_DEBUG
#include <SDL_gfxPrimitives.h>
#endif
namespace Avoid {
class ANode
{
public:
double g; // Gone
double h; // Heuristic
double f; // Formula f = g + h
// seemingly equal paths during orthogonal routing.
g(0),
h(0),
f(0),
prevIndex(-1),
{
}
ANode()
g(0),
h(0),
f(0),
prevIndex(-1),
timeStamp(-1)
{
}
};
// This returns the opposite result (>) so that when used with stl::make_heap,
// the head node of the heap will be the smallest value, rather than the
// largest. This saves us from having to sort the heap (and then reorder
// it back into a heap) when getting the next node to examine. This way we
// get better complexity -- logarithmic pushs and pops to the heap.
//
{
if (a.f != b.f)
{
return a.f > b.f;
}
{
// Tiebreaker, if two paths have equal cost, then choose the one with
// the highest timeStamp. This corresponds to the furthest point
// explored along the straight-line path. When exploring we give the
// directions the following timeStamps; left:1, right:2 and forward:3,
// then we always try to explore forward first.
}
}
{
return (l.x * r.x) + (l.y * r.y);
}
{
return (l.x * r.y) - (l.y * r.x);
}
// Return the angle between the two line segments made by the
// points p1--p2 and p2--p3. Return value is in radians.
//
{
{
// If two of the points are the same, then we can't say anything
// about the angle between. Treat them as being collinear.
return M_PI;
}
}
// Construct a temporary Polygon path given several VertInf's for a connector.
//
{
{
routeSize += 1;
}
routeSize -= 3;
{
routeSize -= 1;
}
}
// Given the two points for a new segment of a path (inf2 & inf3)
// as well as the distance between these points (dist), as well as
// possibly the previous point (inf1) [from inf1--inf2], return a
// cost associated with this route.
//
{
{
// This is not the first segment, so there is a bend
// between it and the last one in the existing path.
if ((angle_penalty > 0) || (segmt_penalty > 0))
{
if (rad > 0)
{
// Make `xval' between 0--10 then take its log so small
// angles are not penalised as much as large ones.
//
//db_printf("deg from straight: %g\tpenalty: %g\n",
// rad * 180 / M_PI, (angle_penalty * yval));
}
{
// Needs to double back
}
else if (rad > 0)
{
// Only penalise as an extra segment if the two
// segments are not collinear.
result += segmt_penalty;
}
}
}
{
// Return here if we ar not in the postprocessing stage
return result;
}
const double cluster_crossing_penalty =
// XXX: Clustered routing doesn't yet work with orthogonal connectors.
(cluster_crossing_penalty > 0) &&
{
{
}
// There are clusters so do cluster routing.
{
{
// Cluster boundary points should correspond to shape
// vertices and hence already be in the list of vertices.
}
bool isConn = false;
}
}
const double shared_path_penalty =
if (shared_path_penalty > 0)
{
// Penalises shared paths, except if the connectors shared an endpoint.
{
}
{
{
continue;
}
bool isConn = true;
{
// Penalise unecessary shared paths in the middle of
// connectors.
}
}
}
{
{
}
{
{
continue;
}
bool isConn = true;
}
}
return result;
}
{
{
return euclideanDist(a, b);
}
else // Orthogonal
{
// XXX: This currently just takes into account the compulsory
// bend but will have to be updated when port direction
// information is available.
int num_penalties = 0;
double xmove = b.x - a.x;
double ymove = b.y - a.y;
if (!last)
{
// Just two points.
{
num_penalties += 1;
}
}
else
{
// We have three points, so we know the direction of the
// previous segment.
{
// Target point is back in the direction of the first point,
// so at least two bends are required.
num_penalties += 2;
}
else if (rad > 0)
{
// To the side, so at least one bend.
num_penalties += 1;
}
}
return manhattanDist(a, b) + penalty;
}
}
class CmpVisEdgeRotation
{
public:
{
}
{
return u->rotationLessThan(_lastPt, v);
}
private:
};
// Returns the best path from src to tar using the cost function.
//
// The path is worked out using the aStar algorithm, and is encoded via
// prevIndex values for each ANode which point back to the previous ANode's
// position in the DONE vector. At completion, this order is written into
// the pathNext links in each of the VerInfs along the path.
//
// The aStar STL code is based on public domain code available on the
// internet.
//
{
{
}
{
int rIndx = 0;
{
#ifdef PATHDEBUG
#endif
if (!last)
{
Node.g = 0;
}
else
{
// Calculate the Heuristic.
// The A* formula
// Point parent to last BestNode (pushed onto DONE)
}
{
}
else
{
}
rIndx++;
}
}
else
{
// Create the start node
Node.g = 0;
// Set a null parent, so cost function knows this is the first segment.
// Populate the PENDING container with the first location
}
// Create a heap from PENDING for sorting
{
// Set the Node with lowest f value to BESTNODE.
// Since the ANode operator< is reversed, the head of the
// heap is the node with the lowest f value.
// Pop off the heap. Actually this moves the
// far left value to the far right. The node
// is not actually removed since the pop is to
// the heap and not the container.
// Remove node from right (the value we pop_heap'd)
// Push the BestNode onto DONE
#if 0
db_printf("Considering... ");
if (prevInf)
{
//prevInf->id.db_print();
}
db_printf("\n");
#endif
#if defined(ASTAR_DEBUG)
if (router->avoid_screen)
{
{
}
//SDL_Delay(500);
{
}
}
#endif
// If at destination, break and create path below
{
#ifdef PATHDEBUG
#endif
//bPathFound = true; // arrived at destination...
// Correct all the pathNext pointers.
{
}
// Check that we've gone through the complete path.
// Fill in the final pathNext pointer.
break;
}
// Check adjacent points in graph
if (isOrthogonal)
{
// We would like to explore in a structured way,
// so sort the points in the visList...
}
{
// Set the index to the previous ANode that we reached
// this ANode through (the last BestNode pushed onto DONE).
// Only check shape verticies, or the tar endpoint.
{
continue;
}
// Don't bother looking at the segment we just arrived along.
{
continue;
}
if (edgeDist == 0)
{
continue;
}
if (!router->_orthogonalRouting &&
{
// The bendpoint is not valid, i.e., is a zigzag corner, so...
continue;
// For RubberBand routing we want to allow these routes and
// unwind them later, otherwise instead or unwinding, paths
// can go the *really* long way round.
}
// Calculate the Heuristic.
// The A* formula
#if 0
#endif
bNodeFound = false;
// Check to see if already on PENDING
{
{
// If already on PENDING
{
}
bNodeFound = true;
break;
}
}
if (!bNodeFound ) // If Node NOT found on PENDING
{
// Check to see if already on DONE
{
{
// If on DONE, Which has lower gone?
{
}
bNodeFound = true;
break;
}
}
}
if (!bNodeFound ) // If Node NOT found on PENDING or DONE
{
// Push NewNode onto PENDING
// Push NewNode onto heap
#if 0
// Display PENDING and DONE containers (For Debugging)
cout << "PENDING: ";
{
}
cout << "DONE: ";
{
}
#endif
}
}
}
}
// Returns the best path for the connector referred to by lineRef.
//
// The path encoded in the pathNext links in each of the VertInfs
// backwards along the path, from the tar back to the source.
//
{
// TODO: Could be more efficient here.
if (isOrthogonal)
{
}
else // if (!isOrthogonal)
{
// If the connector hates crossings or there are clusters present,
// then we want to examine direct paths:
{
}
else
{
}
}
#if 0
t = t->lstNext)
{
db_printf(" -> ");
db_printf("\n");
}
#endif
}
}