← Back to branch summary

~ubuntu-branches/ubuntu/utopic/qgis/utopic

« back to all changes in this revision

Viewing changes to src/plugins/roadgraph/utils.h

  • Committer: Package Import Robot
  • Author(s): Francesco Paolo Lovergine
  • Date: 2012-04-24 15:12:20 UTC
  • mfrom: (3.1.9 sid)
  • Revision ID: package-import@ubuntu.com-20120424151220-r88g00af5fpn5fc3
Tags: 1.7.4+1.7.5~20120320-1
http://bugs.debian.org/661491
http://bugs.debian.org/606304
http://bugs.debian.org/615683
http://bugs.debian.org/616182
http://bugs.debian.org/600308
http://bugs.debian.org/617048
The "Sometimes they come back" release.

* Branching from Qgis tree and adapting to current Debian Policy and
  standards. The target tree is currently set to release-1.7.
  (closes: #661491, #606304, #615683, #616182, #600308)
* Policy bumped to 3.9.3.
* Moving to debhelper compatibility level 9.
* Source format is now 3.0 with quilt support.
* Merged with 2bf42287 upstream git snapshot.
* Migrated to dh_python2 instead of python-central.
  (closes: #617048)
* Snapshot in qgis.org release-1.7: c936d031
* Added an automagic creation of a lintian override for sqlite embedding.
  This is required for uploading currently.
* Added missing ${misc:Depends} to make lintian happy.
* Copyright notes updated and debian/copyright moved to format 1.0.
* More licenses notices now reported in debian/copyright. Thanks ftpmasters.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/plugins/roadgraph/utils.h
 
1
/***************************************************************************
 
2
 *   Copyright (C) 2009 by Sergey Yakushev                                 *
 
3
 *   yakushevs <at> list.ru                                                *
 
4
 *                                                                         *
 
5
 *   This is file define road-graph plugins utils                          *
 
6
 *                                                                         *
 
7
 *   This program is free software; you can redistribute it and/or modify  *
 
8
 *   it under the terms of the GNU General Public License as published by  *
 
9
 *   the Free Software Foundation; either version 2 of the License, or     *
 
10
 *   (at your option) any later version.                                   *
 
11
 ***************************************************************************/
 
12
#ifndef ROADGRAPHPLUGIN_UTILS_H
 
13
#define ROADGRAPHPLUGIN_UTILS_H
 
14
 
 
15
//  QT includes
 
16
#include <qlist.h>
 
17
 
 
18
// Qgis includes
 
19
#include "qgspoint.h"
 
20
 
 
21
// standard includes
 
22
#include <map>
 
23
#include <set>
 
24
 
 
25
// forward declaration Qgis-classes
 
26
 
 
27
/**
 
28
@author Sergey Yakushev
 
29
*/
 
30
 
 
31
/**
 
32
 * \brief return big const double value
 
33
 */
 
34
double infinity();
 
35
 
 
36
/**
 
37
 * return distance from length <x1,y1><x2,y2> to point <x,y> or infinity() value
 
38
 * in union point
 
39
 */
 
40
double distance( const QgsPoint& p1, const QgsPoint& p2, const QgsPoint& p, QgsPoint& center );
 
41
 
 
42
/**
 
43
 * \class QgsPointCompare
 
44
 * \brief This class implement operation "<", ">", "==" and etc. for use QgsPoint type in STL containers
 
45
 *
 
46
 */
 
47
class QgsPointCompare
 
48
{
 
49
  public:
 
50
    bool operator()( const QgsPoint& a, const QgsPoint& b ) const;
 
51
};
 
52
 
 
53
/**
 
54
 * \class ArcAttributes
 
55
 * \brief This class contained arcs attributes.
 
56
 */
 
57
class ArcAttributes
 
58
{
 
59
  public:
 
60
    ArcAttributes();
 
61
    ArcAttributes( double cost, double time, int mFeatureId );
 
62
  public:
 
63
    double mCost;
 
64
    double mTime;
 
65
    int mFeatureId;
 
66
};
 
67
 
 
68
typedef std::map< QgsPoint, ArcAttributes, QgsPointCompare > AdjacencyMatrixString;
 
69
typedef std::map< QgsPoint, AdjacencyMatrixString,  QgsPointCompare > AdjacencyMatrix;
 
70
 
 
71
 
 
72
/**
 
73
 * \class DijkstraFinder
 
74
 * \brief This class find shortest path via two points using Dijkstra's algorithm
 
75
 */
 
76
class DijkstraFinder
 
77
{
 
78
  public:
 
79
    enum OptimizationCriterion { byTime = 1, byCost = 2 };
 
80
  private:
 
81
    class DijkstraIterator
 
82
    {
 
83
      public:
 
84
        DijkstraIterator()
 
85
        {
 
86
          mCost = infinity();
 
87
          mTime = infinity();
 
88
        }
 
89
        double mCost;
 
90
        double mTime;
 
91
        QgsPoint mBackPoint;
 
92
        QgsPoint mFrontPoint;
 
93
    };
 
94
    class CompareDijkstraIterator
 
95
    {
 
96
      public:
 
97
        CompareDijkstraIterator( OptimizationCriterion criterion = byCost ) :
 
98
            mCriterion( criterion )
 
99
        { }
 
100
        bool operator()( const DijkstraIterator& a, const DijkstraIterator& b ) const
 
101
        {
 
102
          if ( mCriterion == byCost )
 
103
          {
 
104
            return a.mCost < b.mCost;
 
105
          }
 
106
          return a.mTime < b.mTime;
 
107
        }
 
108
        bool operator==( const CompareDijkstraIterator& a ) const
 
109
        {
 
110
          return mCriterion == a.mCriterion;
 
111
        }
 
112
      private:
 
113
        OptimizationCriterion mCriterion;
 
114
    };
 
115
  public:
 
116
    /**
 
117
     * constructor.
 
118
     * m is adjacency matrix of graph, criterion is a citerion of shortest path
 
119
     */
 
120
    DijkstraFinder( const AdjacencyMatrix &m, OptimizationCriterion criterion );
 
121
 
 
122
    /**
 
123
     * find all shortest path from point frontPoint to all points of graph.
 
124
     * return tree.
 
125
     */
 
126
    std::map< QgsPoint , DijkstraIterator, QgsPointCompare > find( const QgsPoint& p );
 
127
 
 
128
    /**
 
129
     * return shortest path form point frontPoint to endPoint
 
130
     */
 
131
    AdjacencyMatrix find( const QgsPoint& frontPoint, const QgsPoint& endPoint );
 
132
 
 
133
  private:
 
134
    const AdjacencyMatrix& mAdjacencyMatrix;
 
135
    OptimizationCriterion mCriterion;
 
136
};
 
137
#endif