Root/
| 1 | /* |
| 2 | Copyright 2010 Christian Vetter veaac.fdirct@gmail.com |
| 3 | |
| 4 | This file is part of MoNav. |
| 5 | |
| 6 | MoNav is free software: you can redistribute it and/or modify |
| 7 | it under the terms of the GNU General Public License as published by |
| 8 | the Free Software Foundation, either version 3 of the License, or |
| 9 | (at your option) any later version. |
| 10 | |
| 11 | MoNav is distributed in the hope that it will be useful, |
| 12 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 13 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 14 | GNU General Public License for more details. |
| 15 | |
| 16 | You should have received a copy of the GNU General Public License |
| 17 | along with MoNav. If not, see <http://www.gnu.org/licenses/>. |
| 18 | */ |
| 19 | |
| 20 | #ifndef EDGECONNECTOR_H |
| 21 | #define EDGECONNECTOR_H |
| 22 | |
| 23 | #include "utils/coordinates.h" |
| 24 | #include <vector> |
| 25 | #include <QMultiHash> |
| 26 | #include <algorithm> |
| 27 | |
| 28 | static uint qHash( const UnsignedCoordinate& key ) |
| 29 | { |
| 30 | return qHash( key.x ) ^ qHash( key.y ); |
| 31 | } |
| 32 | |
| 33 | template< class Node > |
| 34 | class EdgeConnector |
| 35 | { |
| 36 | |
| 37 | public: |
| 38 | |
| 39 | struct Edge { |
| 40 | Node source; |
| 41 | Node target; |
| 42 | bool reverseable; |
| 43 | }; |
| 44 | |
| 45 | static void run( std::vector< unsigned >* segments, std::vector< unsigned >* segmentDescriptions, std::vector< bool >* reversed, const std::vector< Edge >& edges ) |
| 46 | { |
| 47 | // build node index |
| 48 | QMultiHash< Node, unsigned > nodes; |
| 49 | QMultiHash< Node, unsigned > backwardNodes; |
| 50 | for ( unsigned i = 0; i < edges.size(); i++ ) { |
| 51 | nodes.insert( edges[i].source, i ); |
| 52 | backwardNodes.insert( edges[i].target, i ); |
| 53 | if ( edges[i].reverseable ) { |
| 54 | nodes.insert( edges[i].target, i ); |
| 55 | backwardNodes.insert( edges[i].source, i ); |
| 56 | } |
| 57 | } |
| 58 | |
| 59 | std::vector< bool > used( edges.size(), false ); |
| 60 | reversed->resize( edges.size(), false ); |
| 61 | for ( unsigned i = 0; i < edges.size(); i++ ) { |
| 62 | if ( used[i] ) |
| 63 | continue; |
| 64 | |
| 65 | unsigned lastSize = segmentDescriptions->size(); |
| 66 | |
| 67 | segmentDescriptions->push_back( i ); |
| 68 | |
| 69 | used[i] = true; |
| 70 | removeEdge( &nodes, &backwardNodes, edges[i], i ); |
| 71 | |
| 72 | // chain edges forward |
| 73 | Node lastNode = edges[i].target; |
| 74 | while ( nodes.contains( lastNode ) ) { |
| 75 | unsigned nextEdge = nodes.value( lastNode ); |
| 76 | assert( !used[nextEdge] ); |
| 77 | |
| 78 | if ( lastNode != edges[nextEdge].source ) { |
| 79 | assert( lastNode == edges[nextEdge].target ); |
| 80 | assert( edges[nextEdge].reverseable ); |
| 81 | ( *reversed )[nextEdge] = true; |
| 82 | lastNode = edges[nextEdge].source; |
| 83 | } else { |
| 84 | lastNode = edges[nextEdge].target; |
| 85 | } |
| 86 | |
| 87 | segmentDescriptions->push_back( nextEdge ); |
| 88 | |
| 89 | used[nextEdge] = true; |
| 90 | removeEdge( &nodes, &backwardNodes, edges[nextEdge], nextEdge ); |
| 91 | } |
| 92 | |
| 93 | // chain edges backward |
| 94 | std::vector< unsigned > backwardsPath; |
| 95 | lastNode = edges[i].source; |
| 96 | while ( backwardNodes.contains( lastNode ) ) { |
| 97 | unsigned nextEdge = backwardNodes.value( lastNode ); |
| 98 | assert( !used[nextEdge] ); |
| 99 | |
| 100 | if ( lastNode != edges[nextEdge].target ) { |
| 101 | assert( lastNode == edges[nextEdge].source ); |
| 102 | assert( edges[nextEdge].reverseable ); |
| 103 | ( *reversed )[nextEdge] = true; |
| 104 | lastNode = edges[nextEdge].target; |
| 105 | } else { |
| 106 | lastNode = edges[nextEdge].source; |
| 107 | } |
| 108 | |
| 109 | backwardsPath.push_back( nextEdge ); |
| 110 | |
| 111 | used[nextEdge] = true; |
| 112 | removeEdge( &nodes, &backwardNodes, edges[nextEdge], nextEdge ); |
| 113 | } |
| 114 | |
| 115 | segmentDescriptions->insert( segmentDescriptions->begin() + lastSize, backwardsPath.rbegin(), backwardsPath.rend() ); |
| 116 | |
| 117 | segments->push_back( segmentDescriptions->size() - lastSize ); |
| 118 | } |
| 119 | |
| 120 | assert( segmentDescriptions->size() == edges.size() ); |
| 121 | } |
| 122 | |
| 123 | protected: |
| 124 | |
| 125 | static void removeEdge( QMultiHash< Node, unsigned >* nodes, QMultiHash< Node, unsigned >* backwardsNodes, const Edge& edge, unsigned value ) |
| 126 | { |
| 127 | nodes->remove( edge.source, value ); |
| 128 | nodes->remove( edge.target, value ); |
| 129 | backwardsNodes->remove( edge.target, value ); |
| 130 | backwardsNodes->remove( edge.source, value ); |
| 131 | } |
| 132 | |
| 133 | }; |
| 134 | |
| 135 | #endif // EDGECONNECTOR_H |
| 136 |
Branches:
master
