GISCup 2015
 All Classes Files Functions Variables Typedefs Enumerations Enumerator Macros
Classes | Macros | Typedefs | Enumerations | Functions | Variables
giscup.hpp File Reference
#include <iostream>
#include <iomanip>
#include <sstream>
#include <stdexcept>
#include <limits>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <boost/pending/queue.hpp>
#include <boost/graph/astar_search.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/random.hpp>
#include <boost/graph/reverse_graph.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/random.hpp>
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point.hpp>
#include <boost/geometry/geometries/box.hpp>
#include <boost/geometry/geometries/polygon.hpp>
#include <boost/geometry/index/rtree.hpp>
#include <boost/geometry/algorithms/distance.hpp>
#include <boost/foreach.hpp>
#include <boost/property_tree/ptree.hpp>
#include <boost/property_tree/json_parser.hpp>
#include <shapefil.h>
#include "codegen/NewRoadAttrib.hpp"
#include "codegen/NewNodeAttrib.hpp"
#include "algorithm/boostastar.hpp"
#include "algorithm/astar.hpp"
#include "algorithm/dijkstra.hpp"
#include "algorithm/boostdijkstra.hpp"
#include "algorithm/ALT.hpp"

Go to the source code of this file.

Classes

class  NewShapeCollection
struct  location
class  VariousSearchEngines
 VariousSearchEngines. More...
struct  VariousSearchEngines::queue_compare
 a comparation functional to sort with smallest priority first More...
class  VariousSearchEngines::distance_heuristic< Graph, CostType, LocMap >
 distance_heuristic provides distance heuristic for the A* search using WebMercatorDistance method More...
struct  VariousSearchEngines::found_goal
class  VariousSearchEngines::astar_goal_visitor< Vertex >
 astar_goal_visitor terminates the search on the goal and counts edge examinations More...
class  VariousSearchEngines::dijkstra_goal_visitor< Vertex >
 dijkstra_goal_visitor ends the search by throwing an expception at the goal vertex and counts edge examinations. More...
class  VariousSearchEngines::landmark_t
 landmark_t is a container for the data representing a landmark. More...

Macros

#define DEFAULT_STATS(x)   {cout << stats (x,g, colors, shortest_path, d, lastStart, lastGoal,getDistance(),stat_examines) << endl;}
 Outpus (cout) statistics with the most common global parameters.
#define STAT_EXAMINE()   {stat_examines ++;}
 STAT_EXAMINE()

Typedefs

typedef bg::model::point
< double, 2, bg::cs::cartesian > 
point
typedef bg::model::box< pointbox
typedef bg::model::polygon
< point, false, false > 
polygon
typedef bg::model::linestring
< point
linestring
typedef std::pair< box, unsigned > value
typedef std::vector
< std::vector< double > > 
polyline
typedef std::vector< polylinepolycollection
typedef std::vector
< std::vector< double > > 
pointcollection
typedef std::vector
< NewRoadAttrib
newroadattribcollection
typedef std::vector
< NewNodeAttrib
newnodeattribcollection
typedef double cost
typedef adjacency_list< vecS,
vecS, bidirectionalS, property
< vertex_color_t,
default_color_type >, property
< edge_weight_t, cost,
property< edge_index_t, size_t > > > 
mygraph_t
typedef adjacency_list< vecS,
vecS, undirectedS, property
< vertex_color_t,
default_color_type >, property
< edge_weight_t, cost,
property< edge_index_t, size_t > > > 
mygraph_t_undirected
typedef property_map
< mygraph_t, edge_weight_t >
::type 
WeightMap
typedef property_map
< mygraph_t, vertex_color_t >
::type 
ColorMap
typedef color_traits
< property_traits< ColorMap >
::value_type > 
Color
typedef property_map
< mygraph_t, edge_index_t >
::type 
IndexMap
typedef
mygraph_t::vertex_descriptor 
vertex
typedef mygraph_t::edge_descriptor edge_descriptor
typedef mygraph_t::vertex_iterator vertex_iterator

Enumerations

enum  SearchAlgorithms {
  SEARCH_ALGORITHM_REFERENCE_AStar, SEARCH_ALGORITHM_REFERENCE_Dijkstra, SEARCH_ALGORITHM_EXPLICIT_AStar, SEARCH_ALGORITHM_Dijkstra,
  SEARCH_ALGORITHM_ALT, SEARCH_ALGORITHM_MAX
}
 SearchAlgorithms. More...

Functions

double satof (std::string s)
 satof converts an std::string to a double irrespective of the current locale in "C"-locale
double _DBFReadDoubleAttribute (DBFHandle hDBF, int id, int iField)
 _DBFReadDoubleAttribute reads a double attribute from Shapefiles in "C"-locale
std::string removeExt (std::string const &filename)
 removeExt removes the extension from a filename.
bool less_second (const value &lhs, const value &rhs)
 compares pairs of value & on the second argument
std::pair< double, double > WebMercator2WGS84 (double mercatorY_lat, double mercatorX_lon)
 WebMercator2WGS84 transforms WebMercator to WGS84.
template<typename coord >
double WebMercatorDistance (coord p1, coord p2, coord p3, coord p4)
 WebMercatorDistance: Calculate Distance between WebMercator Points.
std::string shapename (size_t type)
 shapename returns a string name of the SHP type of geometry field
std::string dbftype (size_t type)
 dbftype returns a string representation of the data type of a DBF field
void handlePolyline (polycollection &coll, SHPObject *shape)
 handlePolyline adds a polyline to a collection from a SHP shape
void handlePoint (pointcollection &coll, SHPObject *shape)
 handlePoint adds a point to a collection from a SHP shape
template<typename polylinecollection , typename attribcollection , typename outstream , typename shapehandler >
void importSHP (std::string filename, polylinecollection &coll, attribcollection &attribs, shapehandler handler, outstream &out=std::cerr, bool verbose=true)
 importSHP reads a shapefile into collections
template<typename polylinecollection , typename outstream , typename shapehandler >
void importSHPOnlyGeometry (std::string filename, polylinecollection &coll, shapehandler handler, outstream &out=std::cerr, bool verbose=false)
 importSHPOnlyGeometry
template<typename polylinecollection , typename attribcollection , typename outstream >
void importSHPPolylines (std::string filename, polylinecollection &coll, attribcollection &attribs, outstream &out=std::cerr, bool verbose=false)
 Interface for importSHP for the case of polylines.
template<typename polylinecollection , typename outstream >
void importSHPPolylinesOnlyGeometry (std::string filename, polylinecollection &coll, outstream &out=std::cerr, bool verbose=false)
 Interface for importSHPOnlyGeometry for polylines.
template<typename collection , typename attribcollection , typename outstream >
void importSHPPoints (std::string filename, collection &coll, attribcollection &attribs, outstream &out=std::cerr, bool verbose=false)
 Interface for importSHP for the case of points.
template<class Graph , class Colors , class PathDescriptor , class Distance >
std::string stats (std::string name, Graph &g, Colors &colors, PathDescriptor &shortest_path, Distance &d, size_t lastStart, size_t lastGoal, double _d, size_t examines)
 stats(...) returns statistics from the last run of an algorithm

Variables

const std::vector< std::string > SearchAlgorithmNames
 Names of the search algorithms as strings.

Macro Definition Documentation

#define DEFAULT_STATS (   x)    {cout << stats (x,g, colors, shortest_path, d, lastStart, lastGoal,getDistance(),stat_examines) << endl;}

Outpus (cout) statistics with the most common global parameters.

This function define is called from search engines to output statistics after searching. This is usually conditional on a preprocessor configuration flag.

#define STAT_EXAMINE ( )    {stat_examines ++;}

STAT_EXAMINE()

Helper macro called on an examination of an edge. Updates class-global variable stat_examines accordingly. For speed, you can redefine this to do nothing...

Typedef Documentation

typedef bg::model::box<point> box
typedef color_traits<property_traits<ColorMap>::value_type> Color
typedef property_map<mygraph_t, vertex_color_t>::type ColorMap
typedef double cost
typedef mygraph_t::edge_descriptor edge_descriptor
typedef property_map<mygraph_t, edge_index_t>::type IndexMap
typedef bg::model::linestring<point> linestring
typedef adjacency_list<vecS, vecS, bidirectionalS, property<vertex_color_t,default_color_type>, property<edge_weight_t, cost, property<edge_index_t,size_t> > > mygraph_t
typedef adjacency_list<vecS, vecS, undirectedS, property<vertex_color_t,default_color_type>, property<edge_weight_t, cost, property<edge_index_t,size_t> > > mygraph_t_undirected
typedef std::vector<NewNodeAttrib> newnodeattribcollection
typedef std::vector<NewRoadAttrib> newroadattribcollection
typedef bg::model::point<double, 2, bg::cs::cartesian> point
typedef std::vector<std::vector<double> > pointcollection
typedef std::vector<polyline> polycollection
typedef bg::model::polygon<point, false, false> polygon
typedef std::vector<std::vector<double> > polyline
typedef std::pair<box, unsigned> value
typedef mygraph_t::vertex_descriptor vertex
typedef mygraph_t::vertex_iterator vertex_iterator
typedef property_map<mygraph_t, edge_weight_t>::type WeightMap

Enumeration Type Documentation

SearchAlgorithms.

Constants to give identifications to the various search algorithm implementations in this file.

Enumerator:
SEARCH_ALGORITHM_REFERENCE_AStar 
SEARCH_ALGORITHM_REFERENCE_Dijkstra 
SEARCH_ALGORITHM_EXPLICIT_AStar 
SEARCH_ALGORITHM_Dijkstra 
SEARCH_ALGORITHM_ALT 
SEARCH_ALGORITHM_MAX 

Function Documentation

double _DBFReadDoubleAttribute ( DBFHandle  hDBF,
int  id,
int  iField 
)

_DBFReadDoubleAttribute reads a double attribute from Shapefiles in "C"-locale

Reading the Double values fails in most locales. This function reads the value as a string and converts it using our safe implementation satof. This function is used in loading Shapefile attributes.

std::string dbftype ( size_t  type)

dbftype returns a string representation of the data type of a DBF field

Given a DBF database, the type of the field is returned as a string from the type of a field's integer description.

void handlePoint ( pointcollection coll,
SHPObject *  shape 
)
inline

handlePoint adds a point to a collection from a SHP shape

This function reads point data from SHP file objects given by the shape parameter. The resulting point is pushed to a collection in 3D (x,y,z)

void handlePolyline ( polycollection coll,
SHPObject *  shape 
)
inline

handlePolyline adds a polyline to a collection from a SHP shape

Whenever a shape of is read, this function can be used to create a polyline from the geometry in the SHPObject parameter and push it onto the collection given as a parameter

template<typename polylinecollection , typename attribcollection , typename outstream , typename shapehandler >
void importSHP ( std::string  filename,
polylinecollection &  coll,
attribcollection &  attribs,
shapehandler  handler,
outstream &  out = std::cerr,
bool  verbose = true 
)

importSHP reads a shapefile into collections

This function imports a shapefile. The filename is given without the SHP suffix, the collections must support push_back and brace expressions, attributecollections must provide the interface as generated in codegen (checking file format), shapehandler should be either handlePoint for point geometry or handlePolyline for other geometry.

if VERY_VERBOSE is defined to one, all shapes are output to the given stream

template<typename polylinecollection , typename outstream , typename shapehandler >
void importSHPOnlyGeometry ( std::string  filename,
polylinecollection &  coll,
shapehandler  handler,
outstream &  out = std::cerr,
bool  verbose = false 
)

importSHPOnlyGeometry

Reads an SHP file similar to importSHP, but does not read or parse the associated DBF file. Currently used for polygonal avoidances, as their attributes are actually never used.

template<typename collection , typename attribcollection , typename outstream >
void importSHPPoints ( std::string  filename,
collection &  coll,
attribcollection &  attribs,
outstream &  out = std::cerr,
bool  verbose = false 
)

Interface for importSHP for the case of points.

simplifies calling importSHP.

template<typename polylinecollection , typename attribcollection , typename outstream >
void importSHPPolylines ( std::string  filename,
polylinecollection &  coll,
attribcollection &  attribs,
outstream &  out = std::cerr,
bool  verbose = false 
)

Interface for importSHP for the case of polylines.

simplifies calling importSHP.

template<typename polylinecollection , typename outstream >
void importSHPPolylinesOnlyGeometry ( std::string  filename,
polylinecollection &  coll,
outstream &  out = std::cerr,
bool  verbose = false 
)

Interface for importSHPOnlyGeometry for polylines.

simplifies calling importSHP.

bool less_second ( const value lhs,
const value rhs 
)

compares pairs of value & on the second argument

Implements the less relation for pairs depending only on the second part of a pair. The pairs are fixed types value

std::string removeExt ( std::string const &  filename)

removeExt removes the extension from a filename.

The shapefile library expects shapefiles given without extension and refuses to load files given the SHP extension.

double satof ( std::string  s)

satof converts an std::string to a double irrespective of the current locale in "C"-locale

Converting string to double is non-trivial as several languages (especially german) use a "," instead of a "." and vice versa. If this source is pulled from a system that actually uses german locale (or system locale) classical atof will fail with respect to shapefiles. This satof is a replacement explicitly setting C-locale in which "." and "," have the meaning of the English language

std::string shapename ( size_t  type)

shapename returns a string name of the SHP type of geometry field

Given a SHP type, returns a string representation of the geometry type of the a specific entity.

template<class Graph , class Colors , class PathDescriptor , class Distance >
std::string stats ( std::string  name,
Graph &  g,
Colors &  colors,
PathDescriptor &  shortest_path,
Distance &  d,
size_t  lastStart,
size_t  lastGoal,
double  _d,
size_t  examines 
)

stats(...) returns statistics from the last run of an algorithm

It uses the search variables given as arguments to create a json string containing graph search performance relevant data. Note that this might be wrong / uncallable on twosided variants of searches, as it only supports one colormap. Some statistics will, however, be vaild (such as examines, distance, ...)

std::pair<double,double> WebMercator2WGS84 ( double  mercatorY_lat,
double  mercatorX_lon 
)

WebMercator2WGS84 transforms WebMercator to WGS84.

Returns a std::pair(lat,lon) out of two distinct parammeters in mercator.

template<typename coord >
double WebMercatorDistance ( coord  p1,
coord  p2,
coord  p3,
coord  p4 
)

WebMercatorDistance: Calculate Distance between WebMercator Points.

Return the distance between two WebMercatorCoordinate pairs by first transforming to WGS84 and using well-known Haversine formula.

Variable Documentation

const std::vector<std::string> SearchAlgorithmNames
Initial value:
{
"Boost A* ",
"Boost Dijkstra",
"Basic A* ",
"Basic Dijkstra ",
"ALT "
}

Names of the search algorithms as strings.

These names have been modified to be flushleft into equal-length strings in order to have more readable output.