libosmscout  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Groups
Geometric helper

Collection of classes and methods releated to low level geometric stuff. More...

Classes

class  osmscout::CLASS_FINAL
 Representation of an (complex/multipolygon) area. More...
 
struct  osmscout::PathIntersection
 Information about intersection of two paths. More...
 
class  osmscout::Projection
 The Projection class is an abstract base class for multiple projection implementations. More...
 

Functions

template<typename N >
bool osmscout::AreaIsCCW (const std::vector< N > &edges)
 Returns true, if the polygon is counter clock wise (CCW) More...
 
template<typename N >
bool osmscout::AreaIsClockwise (const std::vector< N > &edges)
 Returns true, if the closed polygon with the given nodes is oriented clockwise. More...
 
template<typename N >
bool osmscout::AreaIsSimple (std::vector< N > points)
 Returns true, if the handed polygon is simple (aka not complex). More...
 
template<typename N >
bool osmscout::AreaIsSimple (const std::vector< std::pair< N, N > > &edges, const std::vector< bool > &edgeStartsNewPoly)
 Returns true, if the handed polygons are simple (aka not complex). More...
 
template<typename N >
bool osmscout::AreaIsValid (std::vector< N > &outerPoints, std::vector< std::vector< N > > &innerPoints)
 
double osmscout::Det (double x1, double y1, double x2, double y2)
 Calculates the determinant of the line between the given points. More...
 
OSMSCOUT_API double osmscout::DistanceToSegment (double px, double py, double p1x, double p1y, double p2x, double p2y, double &r, double &qx, double &qy)
 Return de distance of the point (px,py) to the segment [(p1x,p1y),(p2x,p2y)], r the abscissa on the line of (qx,qy) the orthogonal projected point from (px,py). More...
 
template<typename N >
bool osmscout::FindIntersection (const std::vector< N > &way, size_t &i, size_t &j)
 Find next intersetion on way (with itself) from node index i. More...
 
template<typename N >
void osmscout::FindPathIntersections (const std::vector< N > &aPath, const std::vector< N > &bPath, bool aClosed, bool bClosed, std::vector< PathIntersection > &intersections, size_t aStartIndex=0, size_t bStartIndex=0)
 Find all intersections between aPath and bPath from node index aStartIndex and bStartIndex. More...
 
template<typename N >
void osmscout::GetBoundingBox (const std::vector< N > &nodes, double &minLon, double &maxLon, double &minLat, double &maxLat)
 Calculate the bounding box of the (non empty) vector of geo coords. More...
 
template<typename N >
void osmscout::GetBoundingBox (const std::vector< N > &nodes, GeoBox &boundingBox)
 Calculate the bounding box of the (non empty) vector of geo coords. More...
 
OSMSCOUT_API double osmscout::GetEllipsoidalDistance (double aLon, double aLat, double bLon, double bLat)
 Calculates the ellipsoidal (WGS-84) distance between the two given points on the ellipsoid [km]. More...
 
OSMSCOUT_API double osmscout::GetEllipsoidalDistance (const GeoCoord &a, const GeoCoord &b)
 Calculates the ellipsoidal (WGS-84) distance between the two given points on the ellipsoid [km]. More...
 
OSMSCOUT_API void osmscout::GetEllipsoidalDistance (double lat1, double lon1, double bearing, double distance, double &lat2, double &lon2)
 Given a starting point and a bearing and a distance calculates the coordinates of the resulting point in the (WGS-84) ellipsoid. More...
 
template<typename N , typename I >
bool osmscout::GetLineIntersection (const N &a1, const N &a2, const N &b1, const N &b2, I &intersection)
 Returns true, if the lines defined by the given coordinates intersect. More...
 
template<typename N >
bool osmscout::GetLineIntersectionPixel (const N &a1, const N &a2, const N &b1, const N &b2, N &intersection)
 Returns true, if the lines defined by the given coordinates intersect. More...
 
template<typename N , typename M >
int osmscout::GetRelationOfPointToArea (const N &point, const std::vector< M > &nodes)
 Gives information about the position of the point in relation to the area. More...
 
OSMSCOUT_API double osmscout::GetSphericalBearingFinal (const GeoCoord &a, const GeoCoord &b)
 Calculates the final bearing for a line from one coordinate two the other coordinate on a sphere. More...
 
OSMSCOUT_API double osmscout::GetSphericalBearingInitial (const GeoCoord &a, const GeoCoord &b)
 Calculates the initial bearing for a line from one coordinate to the other coordinate on a sphere. More...
 
OSMSCOUT_API double osmscout::GetSphericalDistance (const GeoCoord &a, const GeoCoord &b)
 Calculates the spherical distance between the two given points on the sphere [km]. More...
 
template<typename N , typename M >
bool osmscout::IsAreaAtLeastPartlyInArea (const std::vector< N > &a, const std::vector< M > &b, const GeoBox &aBox, const GeoBox &bBox)
 Return true, if at least one point of area a in within area b. More...
 
template<typename N , typename M >
bool osmscout::IsAreaAtLeastPartlyInArea (const std::vector< N > &a, const std::vector< M > &b)
 Return true, if at least one point of area a in within area b. More...
 
template<typename N , typename M >
bool osmscout::IsAreaCompletelyInArea (const std::vector< N > &a, const std::vector< M > &b)
 Return true, if area a is completely in area b. More...
 
template<typename N , typename M >
bool osmscout::IsAreaSubOfArea (const std::vector< N > &a, const std::vector< M > &b)
 Assumes that the given areas do not intersect. More...
 
template<typename N , typename M >
bool osmscout::IsAreaSubOfAreaOrSame (const std::vector< N > &a, const std::vector< M > &b)
 Assumes that the given areas do not intersect. More...
 
template<typename N , typename M >
bool osmscout::IsAreaSubOfAreaQuorum (const std::vector< N > &a, const std::vector< M > &b)
 Assumes that the given areas do not intersect. More...
 
template<typename N , typename M >
bool osmscout::IsCoordInArea (const N &point, const std::vector< M > &nodes)
 Returns true, if point in area. More...
 
template<typename N >
bool osmscout::LinesIntersect (const N &a1, const N &a2, const N &b1, const N &b2)
 Returns true, if the lines defined by the given coordinates intersect. More...
 
void osmscout::Normalize (double x, double y, double &nx, double &ny)
 
OSMSCOUT_API double osmscout::NormalizeRelativeAngel (double angle)
 Normalizes the given bearing to be in the interval [-180.0 - 180.0]. More...
 
void OSMSCOUT_API osmscout::ScanConvertLine (int x1, int y1, int x2, int y2, std::vector< ScanCell > &cells)
 Does a scan conversion for a line between the given coordinates. More...
 

Detailed Description

Collection of classes and methods releated to low level geometric stuff.

Function Documentation

template<typename N >
bool osmscout::AreaIsCCW ( const std::vector< N > &  edges)

Returns true, if the polygon is counter clock wise (CCW)

Referenced by osmscout::AreaIsValid().

template<typename N >
bool osmscout::AreaIsClockwise ( const std::vector< N > &  edges)

Returns true, if the closed polygon with the given nodes is oriented clockwise.

It is assumed, that the polygon is valid. Validity is not checked.

See http://en.wikipedia.org/wiki/Curve_orientation.

Referenced by osmscout::PolygonMerger::AddPolygon().

template<typename N >
bool osmscout::AreaIsSimple ( std::vector< N >  points)

Returns true, if the handed polygon is simple (aka not complex).

Currently the following checks are done:

  • Polygon has at least 3 points
  • Assure that the line segments that make up the polygon only meet at their end points.

References osmscout::LinesIntersect().

Referenced by osmscout::AreaIsValid().

template<typename N >
bool osmscout::AreaIsSimple ( const std::vector< std::pair< N, N > > &  edges,
const std::vector< bool > &  edgeStartsNewPoly 
)

Returns true, if the handed polygons are simple (aka not complex).

This method supports passing multiple closed polygons and checks all of them.

Currently it is checked, that the line segments that make up the polygon, only meet at their end points.

References osmscout::LinesIntersect().

template<typename N >
bool osmscout::AreaIsValid ( std::vector< N > &  outerPoints,
std::vector< std::vector< N > > &  innerPoints 
)
Parameters
outerPoints
innerPoints
Returns

References osmscout::AreaIsCCW(), and osmscout::AreaIsSimple().

double osmscout::Det ( double  x1,
double  y1,
double  x2,
double  y2 
)
inline

Calculates the determinant of the line between the given points.

double osmscout::DistanceToSegment ( double  px,
double  py,
double  p1x,
double  p1y,
double  p2x,
double  p2y,
double &  r,
double &  qx,
double &  qy 
)

Return de distance of the point (px,py) to the segment [(p1x,p1y),(p2x,p2y)], r the abscissa on the line of (qx,qy) the orthogonal projected point from (px,py).

return the minimum distance from the point p to the line segment [p1,p2] this could be the distance from p to p1 or to p2 if q the orthogonal projection of p on the line supporting the segment is outside [p1,p2] r is the abscissa of q on the line, 0 <= r <= 1 if q is between p1 and p2.

0 <= r <= 1 if q is between p1 and p2.

Referenced by osmscout::LocationService::DescribeLocationByWay(), and osmscout::SimpleRoutingService::GetClosestRoutableNode().

template<typename N >
bool osmscout::FindIntersection ( const std::vector< N > &  way,
size_t &  i,
size_t &  j 
)

Find next intersetion on way (with itself) from node index i.

Return true if some intersection was found (way is not simple), i and j indexes are setup to start possition of intesections lines.

References osmscout::ComputeSegmentBoxes(), Intersects, and osmscout::LinesIntersect().

template<typename N >
void osmscout::FindPathIntersections ( const std::vector< N > &  aPath,
const std::vector< N > &  bPath,
bool  aClosed,
bool  bClosed,
std::vector< PathIntersection > &  intersections,
size_t  aStartIndex = 0,
size_t  bStartIndex = 0 
)
template<typename N >
void osmscout::GetBoundingBox ( const std::vector< N > &  nodes,
double &  minLon,
double &  maxLon,
double &  minLat,
double &  maxLat 
)

Calculate the bounding box of the (non empty) vector of geo coords.

Parameters
nodesThe geo coordinates
minLon
maxLon
minLat
maxLat

Referenced by OverlayWay::boundingBox(), osmscout::CLASS_FINAL::GetBoundingBox(), osmscout::CLASS_FINAL::Intersects(), osmscout::IsAreaAtLeastPartlyInArea(), and osmscout::MapPainter::IsVisibleWay().

template<typename N >
void osmscout::GetBoundingBox ( const std::vector< N > &  nodes,
GeoBox &  boundingBox 
)

Calculate the bounding box of the (non empty) vector of geo coords.

Parameters
nodesThe geo coordinates
minLon
maxLon
minLat
maxLat
double osmscout::GetEllipsoidalDistance ( double  aLon,
double  aLat,
double  bLon,
double  bLat 
)
double osmscout::GetEllipsoidalDistance ( const GeoCoord &  a,
const GeoCoord &  b 
)

Calculates the ellipsoidal (WGS-84) distance between the two given points on the ellipsoid [km].

References osmscout::GetEllipsoidalDistance().

void osmscout::GetEllipsoidalDistance ( double  lat1,
double  lon1,
double  bearing,
double  distance,
double &  lat2,
double &  lon2 
)

Given a starting point and a bearing and a distance calculates the coordinates of the resulting point in the (WGS-84) ellipsoid.

References M_PI.

template<typename N , typename I >
bool osmscout::GetLineIntersection ( const N &  a1,
const N &  a2,
const N &  b1,
const N &  b2,
I &  intersection 
)

Returns true, if the lines defined by the given coordinates intersect.

Returns the intersection.

Referenced by osmscout::FindPathIntersections(), and osmscout::GetGridPoints().

template<typename N >
bool osmscout::GetLineIntersectionPixel ( const N &  a1,
const N &  a2,
const N &  b1,
const N &  b2,
N &  intersection 
)

Returns true, if the lines defined by the given coordinates intersect.

Returns the intersection.

template<typename N , typename M >
int osmscout::GetRelationOfPointToArea ( const N &  point,
const std::vector< M > &  nodes 
)
inline

Gives information about the position of the point in relation to the area.

If -1 returned, the point is outside the area, if 0, the point is on the area boundary, 1 the point is within the area.

Referenced by osmscout::IsAreaAtLeastPartlyInArea(), osmscout::IsAreaCompletelyInArea(), osmscout::IsAreaSubOfArea(), osmscout::IsAreaSubOfAreaOrSame(), and osmscout::IsAreaSubOfAreaQuorum().

double osmscout::GetSphericalBearingFinal ( const GeoCoord &  a,
const GeoCoord &  b 
)

Calculates the final bearing for a line from one coordinate two the other coordinate on a sphere.

Taken the path from A to B over a sphere return the bearing (0..2PI) at the destination point B.

References M_PI, and osmscout::sincos().

Referenced by osmscout::RoutePostprocessor::DirectionPostprocessor::Process().

double osmscout::GetSphericalBearingInitial ( const GeoCoord &  a,
const GeoCoord &  b 
)
double osmscout::GetSphericalDistance ( const GeoCoord &  a,
const GeoCoord &  b 
)

Calculates the spherical distance between the two given points on the sphere [km].

Calculating basic cost for the A* algorithm based on the spherical distance of two points on earth [km].

References osmscout::DegToRad().

Referenced by osmscout::AbstractRoutingService< RoutingState >::CalculateRoute(), LocationListModel::data(), LocationEntry::distanceTo(), osmscout::AbstractRoutingService< RoutingState >::GetRNode(), and osmscout::AbstractRoutingService< RoutingState >::WalkPaths().

template<typename N , typename M >
bool osmscout::IsAreaAtLeastPartlyInArea ( const std::vector< N > &  a,
const std::vector< M > &  b,
const GeoBox &  aBox,
const GeoBox &  bBox 
)
inline

Return true, if at least one point of area a in within area b.

References osmscout::GetRelationOfPointToArea().

Referenced by osmscout::IsAreaAtLeastPartlyInArea().

template<typename N , typename M >
bool osmscout::IsAreaAtLeastPartlyInArea ( const std::vector< N > &  a,
const std::vector< M > &  b 
)
inline

Return true, if at least one point of area a in within area b.

References osmscout::GetBoundingBox(), and osmscout::IsAreaAtLeastPartlyInArea().

template<typename N , typename M >
bool osmscout::IsAreaCompletelyInArea ( const std::vector< N > &  a,
const std::vector< M > &  b 
)
inline

Return true, if area a is completely in area b.

References osmscout::GetRelationOfPointToArea().

template<typename N , typename M >
bool osmscout::IsAreaSubOfArea ( const std::vector< N > &  a,
const std::vector< M > &  b 
)
inline

Assumes that the given areas do not intersect.

Returns true, of area a is within b (because at least one point of area a is in b), else (at least one point of area a is outside area b) false

References osmscout::GetRelationOfPointToArea().

template<typename N , typename M >
bool osmscout::IsAreaSubOfAreaOrSame ( const std::vector< N > &  a,
const std::vector< M > &  b 
)
inline

Assumes that the given areas do not intersect.

Returns true, of area a is within b or the same as b. This version uses some heuristic based on the assumption that areas are either in another area or not - but there may be some smaller errors due to areas slightly overlapping.

References osmscout::GetRelationOfPointToArea().

template<typename N , typename M >
bool osmscout::IsAreaSubOfAreaQuorum ( const std::vector< N > &  a,
const std::vector< M > &  b 
)
inline

Assumes that the given areas do not intersect.

Returns true, of area a is within b. This version uses some heuristic based on the assumption that areas are either in another area or not - but there may be some smaller errors due to areas slightly overlapping.

References osmscout::GetRelationOfPointToArea().

template<typename N , typename M >
bool osmscout::IsCoordInArea ( const N &  point,
const std::vector< M > &  nodes 
)
inline

Returns true, if point in area.

http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm

Returns true, if point in on the area border or within the area.

See http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html

Referenced by osmscout::LocationService::LoadNearAreas().

template<typename N >
bool osmscout::LinesIntersect ( const N &  a1,
const N &  a2,
const N &  b1,
const N &  b2 
)

Returns true, if the lines defined by the given coordinates intersect.

Referenced by osmscout::AreaIsSimple(), and osmscout::FindIntersection().

void osmscout::Normalize ( double  x,
double  y,
double &  nx,
double &  ny 
)
inline
double osmscout::NormalizeRelativeAngel ( double  angle)

Normalizes the given bearing to be in the interval [-180.0 - 180.0].

Referenced by osmscout::RoutePostprocessor::DirectionPostprocessor::Process().

void osmscout::ScanConvertLine ( int  x1,
int  y1,
int  x2,
int  y2,
std::vector< ScanCell > &  cells 
)

Does a scan conversion for a line between the given coordinates.

This functions does a scan conversion of a line with the given start and end points.

This problem is equal to the following problem: Assuming an index that works by referencing lines by linking them to all cells in a cell grid that contain or are crossed by the line. Which cells does the line cross?

The given vector for the result data is not cleared on start, to allow multiple calls to this method with different line segments.

The algorithm of Bresenham is used together with some checks for special cases.