makepath.cpp revision e8325ddfe05ac8dd00fbf1e25a583ee33887c031
/*
* vim: ts=4 sw=4 et tw=0 wm=0
*
* libavoid - Fast, Incremental, Object-avoiding Line Router
* Copyright (C) 2004-2006 Michael Wybrow <mjwybrow@users.sourceforge.net>
*
* --------------------------------------------------------------------
* The dijkstraPath function is based on code published and described
* in "Algorithms in C" (Second Edition), 1990, by Robert Sedgewick.
* --------------------------------------------------------------------
*
* 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.
*
* 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. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*
*/
#include "libavoid/vertices.h"
#include "libavoid/makepath.h"
#include "libavoid/geometry.h"
#include "libavoid/connector.h"
#include <vector>
#include <math.h>
namespace Avoid {
double segmt_penalty = 0;
double angle_penalty = 0;
{
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.
//
{
}
// 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))
{
// Make `rad' between 0--10 then take its log so small
// angles are not penalised as much as large ones.
// Don't penalise as an extra segment if there is no turn.
if (rad > 0.0005)
{
result += segmt_penalty;
}
}
}
return result;
}
// Returns the best path from src to tar using the cost function.
//
// The path is worked out via Dijkstra's algorithm, and is encoded via
// pathNext links in each of the VerInfs along the path.
//
// Based on the code of 'matrixpfs'.
//
{
// initialize arrays
{
}
{
k->pathDist *= -1;
{
k->pathDist = 0;
}
++edge)
{
// Only check shape verticies, or endpoints.
if ((t->pathDist < 0) &&
{
{
t->pathNext = k;
}
{
min = t;
}
}
}
++edge)
{
// Only check shape verticies, or endpoints.
if ((t->pathDist < 0) &&
{
{
min = t;
}
}
}
}
}
class ANode
{
public:
double g; // Gone
double h; // Heuristic
double f; // Formula f = g + h
, g(0)
, h(0)
, f(0)
{
}
ANode()
, g(0)
, h(0)
, f(0)
{
}
};
{
return a.f < b.f;
}
{
return a.f > b.f;
}
// 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
// pathNext links in each of the VerInfs along the path.
//
// The aStar STL code is based on public domain code available on the
// internet.
//
{
bool bNodeFound = false; // Flag if node is found in container
// 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
{
// Ascending sort based on overloaded operators below
// Set the Node with lowest f value to BESTNODE
// 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
printf("Considering... ");
BestNode.f);
printf("\n");
#endif
// If at destination, break and create path below
{
//bPathFound = true; // arrived at destination...
break;
}
// Check adjacent points in graph
++edge)
{
// Only check shape verticies, or the tar endpoint.
{
continue;
}
if (edgeDist == 0)
{
continue;
}
// Calculate the Heuristic.
// The A* formula
// Point parent to last BestNode (pushed onto DONE)
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
// Re-Assert heap, or will be short by one
#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 VerInfs
// backwards along the path, from the tar back to the source.
//
{
// TODO: Could be more efficient here.
{
return;
}
(directEdge->getDist() > 0))
{
}
else
{
// Mark the path endpoints as not being able to see
// each other. This is true if we are here.
{
if (!directEdge)
{
}
directEdge->addBlocker(0);
}
if (router->UseAStarSearch)
{
}
else
{
}
#if 0
t = t->lstNext)
{
printf(" -> ");
printf("\n");
}
#endif
}
}
}