1 #ifndef OSMIUM_AREA_DETAIL_SEGMENT_LIST_HPP 2 #define OSMIUM_AREA_DETAIL_SEGMENT_LIST_HPP 3 4 /* 5 6 This file is part of Osmium (https://osmcode.org/libosmium). 7 8 Copyright 2013-2021 Jochen Topf <jochen@topf.org> and others (see README). 9 10 Boost Software License - Version 1.0 - August 17th, 2003 11 12 Permission is hereby granted, free of charge, to any person or organization 13 obtaining a copy of the software and accompanying documentation covered by 14 this license (the "Software") to use, reproduce, display, distribute, 15 execute, and transmit the Software, and to prepare derivative works of the 16 Software, and to permit third-parties to whom the Software is furnished to 17 do so, all subject to the following: 18 19 The copyright notices in the Software and this entire statement, including 20 the above license grant, this restriction and the following disclaimer, 21 must be included in all copies of the Software, in whole or in part, and 22 all derivative works of the Software, unless such copies or derivative 23 works are solely in the form of machine-executable object code generated by 24 a source language processor. 25 26 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 27 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 28 FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT 29 SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE 30 FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE, 31 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 32 DEALINGS IN THE SOFTWARE. 33 34 */ 35 36 #include <osmium/area/detail/node_ref_segment.hpp> 37 #include <osmium/area/problem_reporter.hpp> 38 #include <osmium/osm/item_type.hpp> 39 #include <osmium/osm/location.hpp> 40 #include <osmium/osm/node_ref.hpp> 41 #include <osmium/osm/relation.hpp> 42 #include <osmium/osm/types.hpp> 43 #include <osmium/osm/way.hpp> 44 45 #include <algorithm> 46 #include <cassert> 47 #include <cstdint> 48 #include <cstring> 49 #include <iostream> 50 #include <iterator> 51 #include <numeric> 52 #include <unordered_set> 53 #include <vector> 54 55 namespace osmium { 56 57 namespace area { 58 59 namespace detail { 60 61 /** 62 * Iterate over all relation members and the vector of ways at the 63 * same time and call given function with the relation member and 64 * way as parameter. This takes into account that there might be 65 * non-way members in the relation. 66 */ 67 template <typename F> for_each_member(const osmium::Relation & relation,const std::vector<const osmium::Way * > & ways,F && func)68 inline void for_each_member(const osmium::Relation& relation, const std::vector<const osmium::Way*>& ways, F&& func) { 69 auto way_it = ways.cbegin(); 70 for (const osmium::RelationMember& member : relation.members()) { 71 if (member.type() == osmium::item_type::way) { 72 assert(way_it != ways.cend()); 73 func(member, **way_it); 74 ++way_it; 75 } 76 } 77 } 78 79 /** 80 * This is a helper class for the area assembler. It models 81 * a list of segments. 82 */ 83 class SegmentList { 84 85 using slist_type = std::vector<NodeRefSegment>; 86 87 slist_type m_segments{}; 88 89 bool m_debug; 90 parse_role(const char * role)91 static role_type parse_role(const char* role) noexcept { 92 if (role[0] == '\0') { 93 return role_type::empty; 94 } 95 if (!std::strcmp(role, "outer")) { 96 return role_type::outer; 97 } 98 if (!std::strcmp(role, "inner")) { 99 return role_type::inner; 100 } 101 return role_type::unknown; 102 } 103 104 /** 105 * Calculate the number of segments in all the ways together. 106 */ get_num_segments(const std::vector<const osmium::Way * > & members)107 static std::size_t get_num_segments(const std::vector<const osmium::Way*>& members) noexcept { 108 return std::accumulate(members.cbegin(), members.cend(), static_cast<std::size_t>(0), [](std::size_t sum, const osmium::Way* way) { 109 if (way->nodes().empty()) { 110 return sum; 111 } 112 return sum + way->nodes().size() - 1; 113 }); 114 } 115 extract_segments_from_way_impl(ProblemReporter * problem_reporter,uint64_t & duplicate_nodes,const osmium::Way & way,role_type role)116 uint32_t extract_segments_from_way_impl(ProblemReporter* problem_reporter, uint64_t& duplicate_nodes, const osmium::Way& way, role_type role) { 117 uint32_t invalid_locations = 0; 118 119 osmium::NodeRef previous_nr; 120 for (const osmium::NodeRef& nr : way.nodes()) { 121 if (!nr.location().valid()) { 122 ++invalid_locations; 123 if (problem_reporter) { 124 problem_reporter->report_invalid_location(way.id(), nr.ref()); 125 } 126 continue; 127 } 128 if (previous_nr.location()) { 129 if (previous_nr.location() != nr.location()) { 130 m_segments.emplace_back(previous_nr, nr, role, &way); 131 } else { 132 ++duplicate_nodes; 133 if (problem_reporter) { 134 problem_reporter->report_duplicate_node(previous_nr.ref(), nr.ref(), nr.location()); 135 } 136 } 137 } 138 previous_nr = nr; 139 } 140 141 return invalid_locations; 142 } 143 144 public: 145 SegmentList(bool debug)146 explicit SegmentList(bool debug) noexcept : 147 m_debug(debug) { 148 } 149 150 SegmentList(const SegmentList&) = delete; 151 SegmentList(SegmentList&&) = delete; 152 153 SegmentList& operator=(const SegmentList&) = delete; 154 SegmentList& operator=(SegmentList&&) = delete; 155 156 ~SegmentList() noexcept = default; 157 158 /// The number of segments in the list. size() const159 std::size_t size() const noexcept { 160 return m_segments.size(); 161 } 162 163 /// Is the segment list empty? empty() const164 bool empty() const noexcept { 165 return m_segments.empty(); 166 } 167 168 using const_iterator = slist_type::const_iterator; 169 using iterator = slist_type::iterator; 170 front()171 NodeRefSegment& front() { 172 return m_segments.front(); 173 } 174 back()175 NodeRefSegment& back() { 176 return m_segments.back(); 177 } 178 operator [](std::size_t n) const179 const NodeRefSegment& operator[](std::size_t n) const noexcept { 180 assert(n < m_segments.size()); 181 return m_segments[n]; 182 } 183 operator [](const std::size_t n)184 NodeRefSegment& operator[](const std::size_t n) noexcept { 185 assert(n < m_segments.size()); 186 return m_segments[n]; 187 } 188 begin()189 iterator begin() noexcept { 190 return m_segments.begin(); 191 } 192 end()193 iterator end() noexcept { 194 return m_segments.end(); 195 } 196 begin() const197 const_iterator begin() const noexcept { 198 return m_segments.begin(); 199 } 200 end() const201 const_iterator end() const noexcept { 202 return m_segments.end(); 203 } 204 205 /** 206 * Enable or disable debug output to stderr. This is used 207 * for debugging libosmium itself. 208 */ enable_debug_output(const bool debug=true)209 void enable_debug_output(const bool debug = true) noexcept { 210 m_debug = debug; 211 } 212 213 /// Sort the list of segments. sort()214 void sort() { 215 std::sort(m_segments.begin(), m_segments.end()); 216 } 217 218 /** 219 * Extract segments from given way and add them to the list. 220 * 221 * Segments connecting two nodes with the same location (ie 222 * same node or different nodes with same location) are 223 * removed after reporting the duplicate node. 224 */ extract_segments_from_way(ProblemReporter * problem_reporter,uint64_t & duplicate_nodes,const osmium::Way & way)225 uint32_t extract_segments_from_way(ProblemReporter* problem_reporter, uint64_t& duplicate_nodes, const osmium::Way& way) { 226 if (way.nodes().empty()) { 227 return 0; 228 } 229 m_segments.reserve(way.nodes().size() - 1); 230 return extract_segments_from_way_impl(problem_reporter, duplicate_nodes, way, role_type::outer); 231 } 232 233 /** 234 * Extract all segments from all ways that make up this 235 * multipolygon relation and add them to the list. 236 */ extract_segments_from_ways(ProblemReporter * problem_reporter,uint64_t & duplicate_nodes,uint64_t & duplicate_ways,const osmium::Relation & relation,const std::vector<const osmium::Way * > & members)237 uint32_t extract_segments_from_ways(ProblemReporter* problem_reporter, 238 uint64_t& duplicate_nodes, 239 uint64_t& duplicate_ways, 240 const osmium::Relation& relation, 241 const std::vector<const osmium::Way*>& members) { 242 assert(relation.cmembers().size() >= members.size()); 243 244 const std::size_t num_segments = get_num_segments(members); 245 if (problem_reporter) { 246 problem_reporter->set_nodes(num_segments); 247 } 248 m_segments.reserve(num_segments); 249 250 std::unordered_set<osmium::object_id_type> ids; 251 ids.reserve(members.size()); 252 uint32_t invalid_locations = 0; 253 for_each_member(relation, members, [&](const osmium::RelationMember& member, const osmium::Way& way) { 254 if (ids.count(way.id()) == 0) { 255 ids.insert(way.id()); 256 const auto role = parse_role(member.role()); 257 invalid_locations += extract_segments_from_way_impl(problem_reporter, duplicate_nodes, way, role); 258 } else { 259 ++duplicate_ways; 260 if (problem_reporter) { 261 problem_reporter->report_duplicate_way(way); 262 } 263 } 264 }); 265 266 return invalid_locations; 267 } 268 269 /** 270 * Find duplicate segments (ie same start and end point) in the 271 * list and remove them. This will always remove pairs of the 272 * same segment. So if there are three, for instance, two will 273 * be removed and one will be left. 274 */ erase_duplicate_segments(ProblemReporter * problem_reporter,uint64_t & duplicate_segments,uint64_t & overlapping_segments)275 void erase_duplicate_segments(ProblemReporter* problem_reporter, uint64_t& duplicate_segments, uint64_t& overlapping_segments) { 276 while (true) { 277 auto it = std::adjacent_find(m_segments.begin(), m_segments.end()); 278 if (it == m_segments.end()) { 279 break; 280 } 281 if (m_debug) { 282 std::cerr << " erase duplicate segment: " << *it << "\n"; 283 } 284 285 // Only count and report duplicate segments if they 286 // belong to the same way or if they don't both have 287 // the role "inner". Those cases are definitely wrong. 288 // If the duplicate segments belong to different 289 // "inner" ways, they could be touching inner rings 290 // which are perfectly okay. Note that for this check 291 // the role has to be correct in the member data. 292 if (it->way() == std::next(it)->way() || !it->role_inner() || !std::next(it)->role_inner()) { 293 ++duplicate_segments; 294 if (problem_reporter) { 295 problem_reporter->report_duplicate_segment(it->first(), it->second()); 296 } 297 } 298 299 if (it+2 != m_segments.end() && *it == *(it+2)) { 300 ++overlapping_segments; 301 if (problem_reporter) { 302 problem_reporter->report_overlapping_segment(it->first(), it->second()); 303 } 304 } 305 306 m_segments.erase(it, it+2); 307 } 308 } 309 310 /** 311 * Find intersection between segments. 312 * 313 * @param problem_reporter Any intersections found are 314 * reported to this object. 315 * @returns true if there are intersections. 316 */ find_intersections(ProblemReporter * problem_reporter) const317 uint32_t find_intersections(ProblemReporter* problem_reporter) const { 318 if (m_segments.empty()) { 319 return 0; 320 } 321 322 uint32_t found_intersections = 0; 323 324 for (auto it1 = m_segments.cbegin(); it1 != m_segments.cend() - 1; ++it1) { 325 const NodeRefSegment& s1 = *it1; 326 for (auto it2 = it1+1; it2 != m_segments.end(); ++it2) { 327 const NodeRefSegment& s2 = *it2; 328 329 assert(s1 != s2); // erase_duplicate_segments() should have made sure of that 330 331 if (outside_x_range(s2, s1)) { 332 break; 333 } 334 335 if (y_range_overlap(s1, s2)) { 336 osmium::Location intersection{calculate_intersection(s1, s2)}; 337 if (intersection) { 338 ++found_intersections; 339 if (m_debug) { 340 std::cerr << " segments " << s1 << " and " << s2 << " intersecting at " << intersection << "\n"; 341 } 342 if (problem_reporter) { 343 problem_reporter->report_intersection(s1.way()->id(), s1.first().location(), s1.second().location(), 344 s2.way()->id(), s2.first().location(), s2.second().location(), intersection); 345 } 346 } 347 } 348 } 349 } 350 351 return found_intersections; 352 } 353 354 }; // class SegmentList 355 356 } // namespace detail 357 358 } // namespace area 359 360 } // namespace osmium 361 362 #endif // OSMIUM_AREA_DETAIL_SEGMENT_LIST_HPP 363