1 /* 2 3 Copyright (c) 2017, Project OSRM contributors 4 All rights reserved. 5 6 Redistribution and use in source and binary forms, with or without modification, 7 are permitted provided that the following conditions are met: 8 9 Redistributions of source code must retain the above copyright notice, this list 10 of conditions and the following disclaimer. 11 Redistributions in binary form must reproduce the above copyright notice, this 12 list of conditions and the following disclaimer in the documentation and/or 13 other materials provided with the distribution. 14 15 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND 16 ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 17 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 18 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR 19 ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 20 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 21 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON 22 ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 23 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 24 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 25 26 */ 27 28 #ifndef OSRM_ENGINE_PHANTOM_NODES_H 29 #define OSRM_ENGINE_PHANTOM_NODES_H 30 31 #include "extractor/travel_mode.hpp" 32 33 #include "util/bearing.hpp" 34 #include "util/coordinate.hpp" 35 #include "util/typedefs.hpp" 36 37 #include <boost/assert.hpp> 38 39 namespace osrm 40 { 41 namespace engine 42 { 43 44 struct PhantomNode 45 { PhantomNodeosrm::engine::PhantomNode46 PhantomNode() 47 : forward_segment_id{SPECIAL_SEGMENTID, false}, reverse_segment_id{SPECIAL_SEGMENTID, 48 false}, 49 forward_weight(INVALID_EDGE_WEIGHT), reverse_weight(INVALID_EDGE_WEIGHT), 50 forward_weight_offset(0), reverse_weight_offset(0), 51 forward_distance(INVALID_EDGE_DISTANCE), reverse_distance(INVALID_EDGE_DISTANCE), 52 forward_distance_offset(0), reverse_distance_offset(0), 53 forward_duration(MAXIMAL_EDGE_DURATION), reverse_duration(MAXIMAL_EDGE_DURATION), 54 forward_duration_offset(0), reverse_duration_offset(0), 55 fwd_segment_position(0), is_valid_forward_source{false}, is_valid_forward_target{false}, 56 is_valid_reverse_source{false}, is_valid_reverse_target{false}, bearing(0) 57 58 { 59 } 60 GetForwardWeightPlusOffsetosrm::engine::PhantomNode61 EdgeWeight GetForwardWeightPlusOffset() const 62 { 63 BOOST_ASSERT(forward_segment_id.enabled); 64 return forward_weight_offset + forward_weight; 65 } 66 GetReverseWeightPlusOffsetosrm::engine::PhantomNode67 EdgeWeight GetReverseWeightPlusOffset() const 68 { 69 BOOST_ASSERT(reverse_segment_id.enabled); 70 return reverse_weight_offset + reverse_weight; 71 } 72 GetForwardDurationosrm::engine::PhantomNode73 EdgeWeight GetForwardDuration() const 74 { 75 BOOST_ASSERT(forward_segment_id.enabled); 76 return forward_duration + forward_duration_offset; 77 } 78 GetReverseDurationosrm::engine::PhantomNode79 EdgeWeight GetReverseDuration() const 80 { 81 BOOST_ASSERT(reverse_segment_id.enabled); 82 return reverse_duration + reverse_duration_offset; 83 } 84 85 // DO THIS FOR DISTANCE 86 GetForwardDistanceosrm::engine::PhantomNode87 EdgeDistance GetForwardDistance() const 88 { 89 // ..... <-- forward_distance 90 // .... <-- offset 91 // ......... <-- desired distance 92 // x <-- this is PhantomNode.location 93 // 0----1----2----3----4 <-- EdgeBasedGraph Node segments 94 BOOST_ASSERT(forward_segment_id.enabled); 95 return forward_distance + forward_distance_offset; 96 } 97 GetReverseDistanceosrm::engine::PhantomNode98 EdgeDistance GetReverseDistance() const 99 { 100 // .......... <-- reverse_distance 101 // ... <-- offset 102 // ............. <-- desired distance 103 // x <-- this is PhantomNode.location 104 // 0----1----2----3----4 <-- EdgeBasedGraph Node segments 105 BOOST_ASSERT(reverse_segment_id.enabled); 106 return reverse_distance + reverse_distance_offset; 107 } 108 IsBidirectedosrm::engine::PhantomNode109 bool IsBidirected() const { return forward_segment_id.enabled && reverse_segment_id.enabled; } 110 IsValidosrm::engine::PhantomNode111 bool IsValid(const unsigned number_of_nodes) const 112 { 113 return location.IsValid() && 114 ((forward_segment_id.id < number_of_nodes) || 115 (reverse_segment_id.id < number_of_nodes)) && 116 ((forward_weight != INVALID_EDGE_WEIGHT) || 117 (reverse_weight != INVALID_EDGE_WEIGHT)) && 118 ((forward_duration != MAXIMAL_EDGE_DURATION) || 119 (reverse_duration != MAXIMAL_EDGE_DURATION)) && 120 ((forward_distance != INVALID_EDGE_DISTANCE) || 121 (reverse_distance != INVALID_EDGE_DISTANCE)) && 122 (component.id != INVALID_COMPONENTID); 123 } 124 IsValidosrm::engine::PhantomNode125 bool IsValid(const unsigned number_of_nodes, const util::Coordinate queried_coordinate) const 126 { 127 return queried_coordinate == input_location && IsValid(number_of_nodes); 128 } 129 IsValidosrm::engine::PhantomNode130 bool IsValid() const { return location.IsValid(); } 131 IsValidForwardSourceosrm::engine::PhantomNode132 bool IsValidForwardSource() const 133 { 134 return forward_segment_id.enabled && is_valid_forward_source; 135 } IsValidForwardTargetosrm::engine::PhantomNode136 bool IsValidForwardTarget() const 137 { 138 return forward_segment_id.enabled && is_valid_forward_target; 139 } IsValidReverseSourceosrm::engine::PhantomNode140 bool IsValidReverseSource() const 141 { 142 return reverse_segment_id.enabled && is_valid_reverse_source; 143 } IsValidReverseTargetosrm::engine::PhantomNode144 bool IsValidReverseTarget() const 145 { 146 return reverse_segment_id.enabled && is_valid_reverse_target; 147 } GetBearingosrm::engine::PhantomNode148 short GetBearing(const bool traversed_in_reverse) const 149 { 150 if (traversed_in_reverse) 151 return std::round(util::bearing::reverse(bearing)); 152 return std::round(bearing); 153 } 154 operator ==osrm::engine::PhantomNode155 bool operator==(const PhantomNode &other) const { return location == other.location; } 156 157 template <class OtherT> PhantomNodeosrm::engine::PhantomNode158 explicit PhantomNode(const OtherT &other, 159 ComponentID component, 160 EdgeWeight forward_weight, 161 EdgeWeight reverse_weight, 162 EdgeWeight forward_weight_offset, 163 EdgeWeight reverse_weight_offset, 164 EdgeDistance forward_distance, 165 EdgeDistance reverse_distance, 166 EdgeDistance forward_distance_offset, 167 EdgeDistance reverse_distance_offset, 168 EdgeWeight forward_duration, 169 EdgeWeight reverse_duration, 170 EdgeWeight forward_duration_offset, 171 EdgeWeight reverse_duration_offset, 172 bool is_valid_forward_source, 173 bool is_valid_forward_target, 174 bool is_valid_reverse_source, 175 bool is_valid_reverse_target, 176 const util::Coordinate location, 177 const util::Coordinate input_location, 178 const unsigned short bearing) 179 : forward_segment_id{other.forward_segment_id}, 180 reverse_segment_id{other.reverse_segment_id}, forward_weight{forward_weight}, 181 reverse_weight{reverse_weight}, forward_weight_offset{forward_weight_offset}, 182 reverse_weight_offset{reverse_weight_offset}, forward_distance{forward_distance}, 183 reverse_distance{reverse_distance}, forward_distance_offset{forward_distance_offset}, 184 reverse_distance_offset{reverse_distance_offset}, forward_duration{forward_duration}, 185 reverse_duration{reverse_duration}, forward_duration_offset{forward_duration_offset}, 186 reverse_duration_offset{reverse_duration_offset}, 187 component{component.id, component.is_tiny}, location{location}, 188 input_location{input_location}, fwd_segment_position{other.fwd_segment_position}, 189 is_valid_forward_source{is_valid_forward_source}, 190 is_valid_forward_target{is_valid_forward_target}, 191 is_valid_reverse_source{is_valid_reverse_source}, 192 is_valid_reverse_target{is_valid_reverse_target}, bearing{bearing} 193 { 194 } 195 196 SegmentID forward_segment_id; 197 SegmentID reverse_segment_id; 198 EdgeWeight forward_weight; 199 EdgeWeight reverse_weight; 200 EdgeWeight forward_weight_offset; // TODO: try to remove -> requires path unpacking changes 201 EdgeWeight reverse_weight_offset; // TODO: try to remove -> requires path unpacking changes 202 EdgeDistance forward_distance; 203 EdgeDistance reverse_distance; 204 EdgeDistance forward_distance_offset; // TODO: try to remove -> requires path unpacking changes 205 EdgeDistance reverse_distance_offset; // TODO: try to remove -> requires path unpacking changes 206 EdgeWeight forward_duration; 207 EdgeWeight reverse_duration; 208 EdgeWeight forward_duration_offset; // TODO: try to remove -> requires path unpacking changes 209 EdgeWeight reverse_duration_offset; // TODO: try to remove -> requires path unpacking changes 210 ComponentID component; 211 212 util::Coordinate location; // this is the coordinate of x 213 util::Coordinate input_location; 214 unsigned short fwd_segment_position; 215 // is phantom node valid to be used as source or target 216 private: 217 unsigned short is_valid_forward_source : 1; 218 unsigned short is_valid_forward_target : 1; 219 unsigned short is_valid_reverse_source : 1; 220 unsigned short is_valid_reverse_target : 1; 221 unsigned short bearing : 12; 222 }; 223 224 static_assert(sizeof(PhantomNode) == 80, "PhantomNode has more padding then expected"); 225 226 using PhantomNodePair = std::pair<PhantomNode, PhantomNode>; 227 228 struct PhantomNodeWithDistance 229 { 230 PhantomNode phantom_node; 231 double distance; 232 }; 233 234 struct PhantomNodes 235 { 236 PhantomNode source_phantom; 237 PhantomNode target_phantom; 238 }; 239 } // namespace engine 240 } // namespace osrm 241 242 #endif // PHANTOM_NODES_H 243