package geography;
import graph.*;
/** A route in a Streetmap. This is just a wrapper around a Path in the
* Streetmap's graph, whose vertices hold Points and whose edges hold street
* names. The toString() method gives nice route descriptions.
*/
public class Route {
/** The path, or null if no path exists. */
protected Path path;
/** See {@link #Route(Path,int)}. */
protected int verbosity;
// ---------- PROTECTED CONSTANTS USED BY OUR PROTECTED METHODS ----------
/** Two segments of the same street need not be separately reported
* unless their direction changes by more than plus or minus this many degrees.
*/
protected static final double MERGE_ANGLE_TOLERANCE = 30.0;
/** Cutoffs for the different descriptions in TURN_NAMES.
* Last value should be 180 (or more). */
protected static final double[] TURN_CUTOFFS = {-130, -100, -60, -20, -10, 10, 20, 60, 100, 130, 180};
/** To describe a turn of d degrees, we use the first description
* in TURN_NAMES whose corresponding cutoff in TURN_CUTOFFS is >= d. */
protected static final String[] TURN_NAMES = {"Turn sharply right, doubling back",
"Turn sharply right",
"Turn right",
"Bear right",
"Bear slightly right",
"Continue straight",
"Bear slightly left",
"Bear left",
"Turn left",
"Turn sharply left",
"Turn sharply left, doubling back"};
/** Direction names for evenly spaced points around the compass. We
* divide the compass into this many equal pie slices. The first name
* DIR_NAMES[0] refers to the slice centered at 0 degrees, and the remaining
* names proceed counterclockwise.
*/
protected static final String[] DIR_NAMES = {"east", "northeast", "north", "northwest",
"west", "southwest", "south", "southeast"};
// ---------- CONSTRUCTOR ----------
/** Turns a Path into a Route. */
public Route(Path path) {
this(path, 0);
}
/** Turns a Path into a Route.
*
* Verbosity level can be 0, 1, 2, or 3. It controls how much
* detail is included in the directions produced by toString()
*/
public Route(Path path, int verbosity) {
this.path = path;
this.verbosity = verbosity;
}
// ---------- PUBLIC METHODS ----------
/** Describes the route as a long string of several \n-terminated lines.
* Example line: "Bear left onto Main St going northeast and continue 2.3 miles.\n"
* The 2.3 miles here may be made of several edges, and perhaps only
* the first of these goes northeast, although any abrupt changes in direction
* or street name (as detected by {@link #hasTurn}) would have caused us to break
* this line into multiple lines.
*/
public String toString() {
// Special cases.
if (path==null)
return "Sorry, you can't get there from here.";
else if (path.isEmpty())
return "Stay where you are! You're already there.";
// Not a special case.
Point origin = (Point)getEdge(0).origin().element();
Point destination = (Point)getEdge(path.size()-1).destination().element();
double totalDistance = 0;
String result = "";
// Each time we go through this loop, we print one line.
for (int i=0; i < path.size(); i++) { // warning: we may increase i during the loop if segments merge
if (verbosity >= 1) // include actual coordinates along route
result += getEdge(i).origin().element() + "\t";
if (i==0)
result += "Start on ";
else
result += turnName(getEdge(i-1), getEdge(i))+" onto ";
DirectedEdge e = getEdge(i);
result += streetName(e) + " going " + dirName(e);
double distance = Streetmap.edgeLength(e);
// Maybe we will go through some subsequent edges as well if they're
// part of the same street.
while (i+1 < path.size() && !hasTurn(getEdge(i), getEdge(i+1))) {
// add next segment, as it is a continuation of this one
distance += Streetmap.edgeLength(getEdge(++i));
}
// Ok, we've finished accumulating edeges for this line.
result += " and continue " + distanceString(distance) + ".\n";
totalDistance += distance;
}
// Now print a final line summarizing the route.
if (verbosity >= 1) // include actual final coordinate
result += destination + "\t";
result += "Total driving distance: "+distanceString(totalDistance);
result += " (Straight-line distance: "+distanceString(origin.distanceTo(destination))+".)\n";
return result;
}
// ---------- METHODS THAT FIGURE OUT HOW TO PRINT ----------
// These methods are not static because some of them depend on
// verbosity, which is an instance variable.
//
// A subclass might override some of these methods to get a
// different style or language of printing. For example, it
// might report "0.3520562 kilometres" in place of "0.21 miles".
/** Given an edge, returns a printable street name for
* the street segment it represents.
*/
protected String streetName(DirectedEdge e) {
String s = (String) e.element();
if (s.equals(""))
s = "unnamed street";
return s;
}
/** Turns a direction into its printable name.
* See documentation for {@link #DIR_NAMES}.
*/
protected String dirName(DirectedEdge e) {
// The compass is divided up into several equal-width "slices"
// with names. Which slice are we in?
double dir = Streetmap.edgeDirection(e);
double sliceWidth = 360.0 / DIR_NAMES.length; // number of degrees per direction
int sliceNum = (int) Math.round(dir/sliceWidth);
if (sliceNum < 0) // now deal with negative directions by wrapping around
sliceNum += DIR_NAMES.length;
return DIR_NAMES[sliceNum]+angleString(dir);
}
/** Turns a change in direction into its printable name:
* describes a turn from ss1 onto ss2.
* See documentation for {@link #TURN_NAMES}.
*/
protected String turnName(DirectedEdge e1, DirectedEdge e2) {
double ddir = dirChange(e1, e2);
int i=0;
// TURN_CUTOFFS is designed so that this loop will finish before
// we fall off the end of the array.
while (TURN_CUTOFFS[i] < ddir)
i++;
return TURN_NAMES[i]+angleString(ddir);
}
/** Turns a distance into printable form. */
protected String distanceString(double meters) {
double miles = meters*0.00062137119;
miles = Math.round(miles*100)/100.0; // round it to 2 digits
return miles+" miles";
}
/** Way to print angles for the user. */
protected String angleString(double degrees) {
if (verbosity >= 2)
return " ("+Math.round(degrees)+" degrees)";
else
return "";
}
/** Do we have to report a turn from e1 onto e2, or are we just
* continuing pretty much straight on the same street?
*
* An unnamed street is fair game to be the same as this one.
*
* See documentation for {@link #MERGE_ANGLE_TOLERANCE}. If
* verbosity is >= 3, we report all turns.
*/
private boolean hasTurn(DirectedEdge e1, DirectedEdge e2) {
if (verbosity >= 3)
return true;
else
return streetChange(e1,e2) // new street or sharp turn
|| (Math.abs(dirChange(e1, e2)) > MERGE_ANGLE_TOLERANCE);
}
/** Does the transition from e1 to e2 represent a change
* of street?
*
* If either edge is unnamed, assume there's no change of street.
* This reduces the number of unnamed edges that are unnecessarily
* printed -- it is common for one segment of a long street to be
* missing its name.
*/
private boolean streetChange(DirectedEdge e1, DirectedEdge e2) {
return !(e1.element().equals("")
|| e2.element().equals("")
|| e1.element().equals(e2.element()));
}
// ---------- UTILITY METHODS ----------
/** Get a particular edge of the path. */
protected DirectedEdge getEdge(int index) {
return (DirectedEdge) path.get(index); // vector method
}
/** Change in direction of a turn from e1 onto e2.
*
* Return value is from -180 to 180 degrees.
* Positive values are counterclockwise.
*
* This method is final because it doesn't make sense to override it;
* it's just true.
*/
protected static final double dirChange(DirectedEdge e1, DirectedEdge e2) {
double result = Streetmap.edgeDirection(e2) - Streetmap.edgeDirection(e1);
// Result could be anywhere from -360 to 360.
// Put it into the range [-180,180].
if (result < -180)
return result + 360;
else if (result > 180)
return result - 360;
else
return result;
}
}