Module org.jgrapht.osm
Package org.jgrapht.osm

Class HaversineHeuristic<V>

java.lang.Object
org.jgrapht.osm.HaversineHeuristic<V>
Type Parameters:
V - the vertex type
All Implemented Interfaces:
AStarAdmissibleHeuristic<V>
public final class HaversineHeuristic<V> extends Object implements AStarAdmissibleHeuristic<V>
Great-circle (Haversine) admissible heuristic for A* over geographic graphs. Given a coordinate lookup that returns {lat, lon} in decimal degrees for a vertex, this heuristic returns the great-circle distance in metres between two vertices. The heuristic is admissible whenever edge weights represent ground distance in metres along a path no shorter than the great-circle line.

The default sphere radius is the IUGG mean Earth radius (6,371,008.8 m); supply a custom radius to model bodies other than Earth or to match a preprocessing routine that used a different constant.

Author:
Shai Eilat

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    static final double
    EARTH_RADIUS_M
    IUGG mean Earth radius in metres.

  • Constructor Summary

    Constructors
    Constructor
    Description
    HaversineHeuristic(Function<V,double[]> coordinates)
    Constructs a heuristic backed by the given coordinate lookup, using the default Earth radius.
    HaversineHeuristic(Function<V,double[]> coordinates, double radiusMeters)
    Constructs a heuristic with a custom sphere radius.

  • Method Summary

    Modifier and Type
    Method
    Description
    static double
    distanceMeters(double lat1, double lon1, double lat2, double lon2)
    Computes the great-circle distance in metres between two (lat, lon) points (in decimal degrees) on Earth, using the default radius.
    static double
    distanceMeters(double lat1, double lon1, double lat2, double lon2, double radiusMeters)
    Computes the great-circle distance in metres between two (lat, lon) points (in decimal degrees) on a sphere of the given radius.
    double
    getCostEstimate(V source, V target)
    An admissible "heuristic estimate" of the distance from $x$, the sourceVertex, to the goal (usually denoted $h(x)$).
    static <V> HaversineHeuristic<V>
    ofMap(Map<V,double[]> coords)
    Convenience factory for the common case where coordinates are stored in a Map.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    Methods inherited from interface org.jgrapht.alg.interfaces.AStarAdmissibleHeuristic

    isConsistent

  • Field Details

    • EARTH_RADIUS_M

      public static final double EARTH_RADIUS_M
      IUGG mean Earth radius in metres.
      See Also:

  • Constructor Details

    • HaversineHeuristic

      public HaversineHeuristic(Function<V,double[]> coordinates)
      Constructs a heuristic backed by the given coordinate lookup, using the default Earth radius.
      Parameters:
      coordinates - maps a vertex to {lat, lon} in decimal degrees

    • HaversineHeuristic

      public HaversineHeuristic(Function<V,double[]> coordinates, double radiusMeters)
      Constructs a heuristic with a custom sphere radius.
      Parameters:
      coordinates - maps a vertex to {lat, lon} in decimal degrees
      radiusMeters - the sphere radius in metres

  • Method Details

    • ofMap

      public static <V> HaversineHeuristic<V> ofMap(Map<V,double[]> coords)
      Convenience factory for the common case where coordinates are stored in a Map.
      Type Parameters:
      V - the vertex type
      Parameters:
      coords - the coordinate map
      Returns:
      a heuristic backed by coords::get

    • getCostEstimate

      public double getCostEstimate(V source, V target)
      Description copied from interface: AStarAdmissibleHeuristic
      An admissible "heuristic estimate" of the distance from $x$, the sourceVertex, to the goal (usually denoted $h(x)$). This is the good guess function which must never overestimate the distance.
      Specified by:
      getCostEstimate in interface AStarAdmissibleHeuristic<V>
      Parameters:
      source - the source vertex
      target - the target vertex
      Returns:
      an estimate of the distance from the source to the target vertex

    • distanceMeters

      public static double distanceMeters(double lat1, double lon1, double lat2, double lon2)
      Computes the great-circle distance in metres between two (lat, lon) points (in decimal degrees) on Earth, using the default radius.
      Parameters:
      lat1 - latitude of the first point in decimal degrees
      lon1 - longitude of the first point in decimal degrees
      lat2 - latitude of the second point in decimal degrees
      lon2 - longitude of the second point in decimal degrees
      Returns:
      the great-circle distance in metres

    • distanceMeters

      public static double distanceMeters(double lat1, double lon1, double lat2, double lon2, double radiusMeters)
      Computes the great-circle distance in metres between two (lat, lon) points (in decimal degrees) on a sphere of the given radius.
      Parameters:
      lat1 - latitude of the first point in decimal degrees
      lon1 - longitude of the first point in decimal degrees
      lat2 - latitude of the second point in decimal degrees
      lon2 - longitude of the second point in decimal degrees
      radiusMeters - the sphere radius in metres
      Returns:
      the great-circle distance in metres