shady.common.pathfinder
Class Pathfinder

java.lang.Object
  extended by shady.common.pathfinder.Pathfinder

public class Pathfinder
extends java.lang.Object

A Shady pathfinder implementation.

TBD more doc

Target: 1.4 JRE.

Copyright (C) 2006 Marsette A. Vona, III

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.

This program 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 General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.

Author:
Peter Osagie

Field Summary
private  boolean annotateGripperPoints
          Flag that determins if we want to draw the possible gripper points.
private  boolean annotatePath
          Flag that determins if we want to annotate the path only.
private  double CENTER_TO_CENTER_DISTANCE
          Shady center-to-center dictance used as a radius when finding the intersection points.
static double CIRCLE_ANNOTATION_WIDTH
          Width of the circles that are drawn to represent the possible shady barrel connection points.
private  ClickPointListener clickPointListener
          Used when adding a listener.
private  Point.OnSegment connectedBarrelLocation
          The current connected barrel location for shady.
private static java.lang.String cvsid
          CVS id.
static double DEFAULT_SEARCH_RADIUS_COEFFICIENT
          A default searchRadiusCoefficient value.
private  double DEFAULT_SEGMENT_END_DEADBAND
          Default extra dead region at ends of segments where gripping is prohibited, as a multiple of the mechanism gripper width.
private  Environment environment
          The environment.
static double EPSILON
          A default epsilon.
private  java.util.LinkedList graph
          The graph representation of the possible connection points.
private  GraphicsDisplay graphicsDisplay
          The asynchronous graphics rendering system.
private  double searchRadius
          Together with the searchRadiusCoefficient and the CENTER_TO_CENTER_DISTANCE defines a radius used when adding new intersecting points to the possible barrel connection points.
private  double searchRadiusCoefficient
          Used to define the searchRadius.
private  double segmentEndDeadbandM
          Extra dead region at ends of segments where gripping is prohibited in meters.
private  Segment[] segments
          The segments in the environment.
private  ShadyCommonAPI shady
          The mechanism.
 java.util.LinkedList shortestPath
          The shortest path of nodes that is found by getShortestPath(shady.common.Point.OnSegment) See Node.
private  boolean usePathfinder
          Flag that determins if the path planer should be invoked.
 
Constructor Summary
Pathfinder(ShadyCommonAPI shady, Environment environment, GraphicsDisplay graphicsDisplay)
          Create a new Pathfinder.
 
Method Summary
 void addAnnotation(Point.OnSegment point, java.awt.Color color)
          Draws a 2D circle corresponding to a point in the path.
 void addPathfinderAnnotations()
          Draws all intersection points, i.e all possible shady connection points.
 void createGraph()
          Finds all the possible shady barrel connection points and creates the graph representation of those.
private  void dijkstras()
          A Dijkstras shortest path implementation.
private  Node findNode(Point.OnSegment point)
          Finds the node containing the given point.
 int findPath()
          TBD more doc
private  Node getCheepestNode(java.util.LinkedList Q)
          Finds the node with the shortest distance from the start node in the given queue.
 Point.OnSegment getClosestGripperPoint(Point.Cartesian point)
          Finds the closest possible gripper connection point to any 2D point.
private  java.util.LinkedList getIntersections(Point circleCenter)
          Finds all intrsecting points for a circle with radius searchRadius, center point circleCenter and all segments in the environment.
 java.util.LinkedList getShortestPath(Point.OnSegment goalPoint)
          Finds the shortest path from the current connection point to goal point with use of Dijkstras shortest path algorithm.
 boolean getUsePathfinder()
          Check if the path planner should be invoked or not.
 boolean isTherePointCloseBy(Point.OnSegment point)
          Checks if there is already a closer gripper point within the searchRadius on the same segment.
private  void relax(Node u, Node v, double w)
          Checks whether the current best estimate of the shortest distance to v can be improved by going through u.
 void removeAnnotation(Point.OnSegment point)
          Removes a previously drawn pathfinder annotation.
 void removePathfinderAnnotations()
          Removes all previous drawn intersection points, i.e all possible shady connection points.
 void setAnnotateAll(boolean state)
          Set the level of annotation.
 void setAnnotateGripperPoints(boolean state)
          Set the level of annotation.
 void setAnnotatePath(boolean state)
          Set the level of annotation.
 void setSearchRadiusCoefficient(double coeff)
          Sets the searchRadiusCoefficient.
 void setSegmentEndDeadband(double segmentEndDeadband)
          Set the extra dead region at ends of segments where gripping is prohibited, as a multiple of the mechanism gripper width.
 void setSegmentEndDeadbandMeters(double segmentEndDeadbandM)
          Set the extra dead region at ends of segments where gripping is prohibited, in meters.
 void setUsePathfinder(boolean state)
          Used to set if the path planner should be invoked or not.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

cvsid

private static final java.lang.String cvsid

CVS id.

See Also:
Constant Field Values

shady

private final ShadyCommonAPI shady

The mechanism.


environment

private final Environment environment

The environment.


graphicsDisplay

private final GraphicsDisplay graphicsDisplay

The asynchronous graphics rendering system.


segments

private final Segment[] segments

The segments in the environment.


CENTER_TO_CENTER_DISTANCE

private final double CENTER_TO_CENTER_DISTANCE

Shady center-to-center dictance used as a radius when finding the intersection points.


DEFAULT_SEGMENT_END_DEADBAND

private final double DEFAULT_SEGMENT_END_DEADBAND

Default extra dead region at ends of segments where gripping is prohibited, as a multiple of the mechanism gripper width.

See Also:
Constant Field Values

EPSILON

public static final double EPSILON

A default epsilon.

See Also:
Constant Field Values

DEFAULT_SEARCH_RADIUS_COEFFICIENT

public static final double DEFAULT_SEARCH_RADIUS_COEFFICIENT

A default searchRadiusCoefficient value.

See Also:
Constant Field Values

CIRCLE_ANNOTATION_WIDTH

public static final double CIRCLE_ANNOTATION_WIDTH

Width of the circles that are drawn to represent the possible shady barrel connection points.

See Also:
Constant Field Values

clickPointListener

private final ClickPointListener clickPointListener

Used when adding a listener.

Whenever GraphicsDisplay.clickPointCartesian is changed, that is when the user clicks somewhere in the draphics display, a new path may be computed


searchRadiusCoefficient

private double searchRadiusCoefficient

Used to define the searchRadius.

The coefficient is in the range of [0.0 1.0], where 0.0 searches for all possible points within EPSILON (you probably don't want to do that) and 1.0 uses the shady center-to-center distance.

Default value is 1.0.


searchRadius

private double searchRadius

Together with the searchRadiusCoefficient and the CENTER_TO_CENTER_DISTANCE defines a radius used when adding new intersecting points to the possible barrel connection points. If there already exists a point within the search radius it will not be added to the possible set of points. This to limit the amount of points.


connectedBarrelLocation

private Point.OnSegment connectedBarrelLocation

The current connected barrel location for shady.


graph

private java.util.LinkedList graph

The graph representation of the possible connection points.

N.B the graph only contains a set of nodes. The edges are stored in each node. See Node


shortestPath

public java.util.LinkedList shortestPath

The shortest path of nodes that is found by getShortestPath(shady.common.Point.OnSegment) See Node.

The nodes are storded with the next (i.e following) point in the path first and the desired goal node last. That is, the current connection point is not in the path.


usePathfinder

private boolean usePathfinder

Flag that determins if the path planer should be invoked.


annotateGripperPoints

private boolean annotateGripperPoints

Flag that determins if we want to draw the possible gripper points.


annotatePath

private boolean annotatePath

Flag that determins if we want to annotate the path only.


segmentEndDeadbandM

private double segmentEndDeadbandM

Extra dead region at ends of segments where gripping is prohibited in meters.

Constructor Detail

Pathfinder

public Pathfinder(ShadyCommonAPI shady,
                  Environment environment,
                  GraphicsDisplay graphicsDisplay)

Create a new Pathfinder.

Parameters:
shady - the shady instance
environment - the current environment
Method Detail

setSegmentEndDeadband

public void setSegmentEndDeadband(double segmentEndDeadband)

Set the extra dead region at ends of segments where gripping is prohibited, as a multiple of the mechanism gripper width.

See also setSegmentEndDeadbandMeters(double).

Parameters:
segmentEndDeadband - the extra dead region at ends of segments where gripping is prohibited, as a multiple of the mechanism gripper width

setSegmentEndDeadbandMeters

public void setSegmentEndDeadbandMeters(double segmentEndDeadbandM)

Set the extra dead region at ends of segments where gripping is prohibited, in meters.

See also setSegmentEndDeadband(double).

Parameters:
segmentEndDeadbandM - the extra dead region at ends of segments where gripping is prohibited, in meters

findPath

public int findPath()

TBD more doc

Returns:
pathfinder fault

createGraph

public void createGraph()

Finds all the possible shady barrel connection points and creates the graph representation of those.

The algorithm applys a breath first search from the current connection point to the given end point.


getIntersections

private java.util.LinkedList getIntersections(Point circleCenter)

Finds all intrsecting points for a circle with radius searchRadius, center point circleCenter and all segments in the environment.

N.B! This method is bound by 2D.

Parameters:
circleCenter - the circle center with radius CENTER_TO_CENTER_DISTANCE
Returns:
the intersections

isTherePointCloseBy

public boolean isTherePointCloseBy(Point.OnSegment point)

Checks if there is already a closer gripper point within the searchRadius on the same segment.

Uses the default EPSILON value in order to make up for any matimatical imprecision.

Parameters:
point - the point to compare to
Returns:
true if so, false if not

getClosestGripperPoint

public Point.OnSegment getClosestGripperPoint(Point.Cartesian point)

Finds the closest possible gripper connection point to any 2D point.

If no point is found null is returned.

Parameters:
point - target point
Returns:
closes possible gripper connection point in 2D or null

getShortestPath

public java.util.LinkedList getShortestPath(Point.OnSegment goalPoint)

Finds the shortest path from the current connection point to goal point with use of Dijkstras shortest path algorithm.

Parameters:
goalPoint - the desired end point in the graph
Returns:
the path of nodes, see Node. The nodes are storded with the next (i.e following) point in the path first and the desired goal node last. The current connection point is not stored in the path

dijkstras

private void dijkstras()

A Dijkstras shortest path implementation.

Calculates the shortest path for each node in the graph.


relax

private void relax(Node u,
                   Node v,
                   double w)

Checks whether the current best estimate of the shortest distance to v can be improved by going through u.

Parameters:
u - source node
v - end node
w - weight or cost between node u and v

getCheepestNode

private Node getCheepestNode(java.util.LinkedList Q)

Finds the node with the shortest distance from the start node in the given queue. Used by Dijkstras' algorithm.

Parameters:
Q - set of nodes
Returns:
the node with shortest distance from the start node

findNode

private Node findNode(Point.OnSegment point)

Finds the node containing the given point. If none is found null is returned.

Parameters:
point - the point to look for
Returns:
the node in the graph that corresponds to the goal point or null

setUsePathfinder

public void setUsePathfinder(boolean state)

Used to set if the path planner should be invoked or not.

Parameters:
state - if true the path planner is enabled. If false no computations are done.

getUsePathfinder

public boolean getUsePathfinder()

Check if the path planner should be invoked or not.

Returns:
true if the path planner is enabled

setAnnotateGripperPoints

public void setAnnotateGripperPoints(boolean state)

Set the level of annotation.

Parameters:
state - if true draws the gripper points. Otherwise not.

setAnnotatePath

public void setAnnotatePath(boolean state)

Set the level of annotation.

Parameters:
state - if true the path annotations will be drawn. Otherwise not.

setAnnotateAll

public void setAnnotateAll(boolean state)

Set the level of annotation.

Parameters:
state - if true annotates everything. Otherwise not.

addAnnotation

public void addAnnotation(Point.OnSegment point,
                          java.awt.Color color)

Draws a 2D circle corresponding to a point in the path.

N.B! This method is bound by 2D.

Parameters:
point - the circle center point
color - the color

removeAnnotation

public void removeAnnotation(Point.OnSegment point)

Removes a previously drawn pathfinder annotation.

Parameters:
point - the circle center point

addPathfinderAnnotations

public void addPathfinderAnnotations()

Draws all intersection points, i.e all possible shady connection points.


removePathfinderAnnotations

public void removePathfinderAnnotations()

Removes all previous drawn intersection points, i.e all possible shady connection points.


setSearchRadiusCoefficient

public void setSearchRadiusCoefficient(double coeff)

Sets the searchRadiusCoefficient.

Parameters:
coeff - is the search radius coefficient. It is in the range of [0.0 1.0], where 0.0 searches for all possible points down to EPSILON (you probably don't want to do that) and 1.0 uses the shady center-to-center distance. If outside range searchRadiusCoefficient is set to 1.0