Skip to content

Commit

Permalink
Added QgsTracer to support tracing in map tools
Browse files Browse the repository at this point in the history
The tracer builds a graph from input layers and uses Dijkstra's
algorithm for the shortest path in the graph.

There is already QgsGraph class and friends in QGIS code including
Dijkstra's algorithm, however that implementation does not fit our
needs well for a number of reasons (some of them would be easy
to fix, but others would require a significant rewrite):
- limited to single input layer
- no monitoring of changes in the input layers
- no support for polygons
- not in core library
- shortest path alg does only stops when all distances are calculated
- every point of input layer represented as a vertex in graph
  (resulting graph is much denser than necessary and path finding slower)
- edges have always one direction, requiring two edges between each
  pair of vertices (resulting graph has twice as many edges)
- graph is always built with start/finish points
  (does not allow temporary addition of start/finish points and their
   removal without complete rebuild of the graph)
  • Loading branch information
wonder-sk committed Jan 8, 2016
1 parent e0a557a commit 9a6ffc4
Show file tree
Hide file tree
Showing 5 changed files with 782 additions and 0 deletions.
3 changes: 3 additions & 0 deletions src/core/CMakeLists.txt
Expand Up @@ -184,6 +184,7 @@ SET(QGIS_CORE_SRCS
qgssqlexpressioncompiler.cpp
qgsstatisticalsummary.cpp
qgsstringutils.cpp
qgstracer.cpp
qgstransaction.cpp
qgstextlabelfeature.cpp
qgstolerance.cpp
Expand Down Expand Up @@ -454,6 +455,7 @@ SET(QGIS_CORE_MOC_HDRS
qgsrelationmanager.h
qgsrunprocess.h
qgssnappingutils.h
qgstracer.h
qgstransaction.h
qgsvectordataprovider.h
qgsvectorlayercache.h
Expand Down Expand Up @@ -659,6 +661,7 @@ SET(QGIS_CORE_HDRS
qgsstringutils.h
qgstextlabelfeature.h
qgstolerance.h
qgstracer.h

qgsvectordataprovider.h
qgsvectorlayercache.h
Expand Down

0 comments on commit 9a6ffc4

Please sign in to comment.