1 #ifndef OSMIUM_AREA_DETAIL_BASIC_ASSEMBLER_HPP 2 #define OSMIUM_AREA_DETAIL_BASIC_ASSEMBLER_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/assembler_config.hpp> 37 #include <osmium/area/detail/node_ref_segment.hpp> 38 #include <osmium/area/detail/proto_ring.hpp> 39 #include <osmium/area/detail/segment_list.hpp> 40 #include <osmium/area/problem_reporter.hpp> 41 #include <osmium/area/stats.hpp> 42 #include <osmium/builder/osm_object_builder.hpp> 43 #include <osmium/osm/location.hpp> 44 #include <osmium/osm/node_ref.hpp> 45 #include <osmium/osm/types.hpp> 46 #include <osmium/osm/way.hpp> 47 #include <osmium/util/iterator.hpp> 48 #include <osmium/util/timer.hpp> 49 50 #include <algorithm> 51 #include <cassert> 52 #include <cstdint> 53 #include <cstdlib> 54 #include <exception> 55 #include <iostream> 56 #include <iterator> 57 #include <list> 58 #include <unordered_map> 59 #include <unordered_set> 60 #include <utility> 61 #include <vector> 62 63 namespace osmium { 64 65 namespace area { 66 67 namespace detail { 68 69 using open_ring_its_type = std::list<std::list<ProtoRing>::iterator>; 70 71 struct location_to_ring_map { 72 osmium::Location location; 73 open_ring_its_type::iterator ring_it{}; 74 bool start{false}; 75 location_to_ring_maposmium::area::detail::location_to_ring_map76 location_to_ring_map(osmium::Location l, open_ring_its_type::iterator r, const bool s) noexcept : 77 location(l), 78 ring_it(r), 79 start(s) { 80 } 81 location_to_ring_maposmium::area::detail::location_to_ring_map82 explicit location_to_ring_map(osmium::Location l) noexcept : 83 location(l) { 84 } 85 ringosmium::area::detail::location_to_ring_map86 const ProtoRing& ring() const noexcept { 87 return **ring_it; 88 } 89 90 }; // struct location_to_ring_map 91 operator ==(const location_to_ring_map & lhs,const location_to_ring_map & rhs)92 inline bool operator==(const location_to_ring_map& lhs, const location_to_ring_map& rhs) noexcept { 93 return lhs.location == rhs.location; 94 } 95 operator <(const location_to_ring_map & lhs,const location_to_ring_map & rhs)96 inline bool operator<(const location_to_ring_map& lhs, const location_to_ring_map& rhs) noexcept { 97 return lhs.location < rhs.location; 98 } 99 100 /** 101 * Class for assembling ways and relations into multipolygons 102 * (areas). Contains the basic functionality needed but is not 103 * used directly. Use the osmium::area::Assembler class instead. 104 */ 105 class BasicAssembler { 106 107 static constexpr const std::size_t max_split_locations = 100ULL; 108 109 // Maximum recursion depth, stops complex multipolygons from 110 // breaking everything. 111 enum : unsigned { 112 max_depth = 20U 113 }; 114 115 struct slocation { 116 117 enum { 118 invalid_item = 1U << 30U 119 }; 120 121 uint32_t item : 31; 122 uint32_t reverse : 1; 123 slocationosmium::area::detail::BasicAssembler::slocation124 slocation() noexcept : 125 item(invalid_item), 126 reverse(false) { 127 } 128 slocationosmium::area::detail::BasicAssembler::slocation129 explicit slocation(uint32_t n, bool r = false) noexcept : 130 item(n), 131 reverse(r) { 132 } 133 locationosmium::area::detail::BasicAssembler::slocation134 osmium::Location location(const SegmentList& segment_list) const noexcept { 135 const auto& segment = segment_list[item]; 136 return reverse ? segment.second().location() : segment.first().location(); 137 } 138 node_refosmium::area::detail::BasicAssembler::slocation139 const osmium::NodeRef& node_ref(const SegmentList& segment_list) const noexcept { 140 const auto& segment = segment_list[item]; 141 return reverse ? segment.second() : segment.first(); 142 } 143 locationosmium::area::detail::BasicAssembler::slocation144 osmium::Location location(const SegmentList& segment_list, const osmium::Location& default_location) const noexcept { 145 if (item == invalid_item) { 146 return default_location; 147 } 148 return location(segment_list); 149 } 150 151 }; // struct slocation 152 153 // Configuration settings for this Assembler 154 const AssemblerConfig& m_config; 155 156 // List of segments (connection between two nodes) 157 SegmentList m_segment_list; 158 159 // The rings we are building from the segments 160 std::list<ProtoRing> m_rings; 161 162 // All node locations 163 std::vector<slocation> m_locations; 164 165 // All locations where more than two segments start/end 166 std::vector<Location> m_split_locations; 167 168 // Statistics 169 area_stats m_stats; 170 171 // The number of members the multipolygon relation has 172 std::size_t m_num_members = 0; 173 174 template <typename TBuilder> build_ring_from_proto_ring(osmium::builder::AreaBuilder & builder,const ProtoRing & ring)175 static void build_ring_from_proto_ring(osmium::builder::AreaBuilder& builder, const ProtoRing& ring) { 176 TBuilder ring_builder{builder}; 177 ring_builder.add_node_ref(ring.get_node_ref_start()); 178 for (const auto& segment : ring.segments()) { 179 ring_builder.add_node_ref(segment->stop()); 180 } 181 } 182 check_inner_outer_roles()183 void check_inner_outer_roles() { 184 if (debug()) { 185 std::cerr << " Checking inner/outer roles\n"; 186 } 187 188 std::unordered_map<const osmium::Way*, const ProtoRing*> way_rings; 189 std::unordered_set<const osmium::Way*> ways_in_multiple_rings; 190 191 for (const ProtoRing& ring : m_rings) { 192 for (const auto& segment : ring.segments()) { 193 assert(segment->way()); 194 195 if (!segment->role_empty() && (ring.is_outer() ? !segment->role_outer() : !segment->role_inner())) { 196 ++m_stats.wrong_role; 197 if (debug()) { 198 std::cerr << " Segment " << *segment << " from way " << segment->way()->id() << " has role '" << segment->role_name() 199 << "', but should have role '" << (ring.is_outer() ? "outer" : "inner") << "'\n"; 200 } 201 if (m_config.problem_reporter) { 202 if (ring.is_outer()) { 203 m_config.problem_reporter->report_role_should_be_outer(segment->way()->id(), segment->first().location(), segment->second().location()); 204 } else { 205 m_config.problem_reporter->report_role_should_be_inner(segment->way()->id(), segment->first().location(), segment->second().location()); 206 } 207 } 208 } 209 210 auto& r = way_rings[segment->way()]; 211 if (!r) { 212 r = ˚ 213 } else if (r != &ring) { 214 ways_in_multiple_rings.insert(segment->way()); 215 } 216 217 } 218 } 219 220 for (const osmium::Way* way : ways_in_multiple_rings) { 221 ++m_stats.ways_in_multiple_rings; 222 if (debug()) { 223 std::cerr << " Way " << way->id() << " is in multiple rings\n"; 224 } 225 if (m_config.problem_reporter) { 226 m_config.problem_reporter->report_way_in_multiple_rings(*way); 227 } 228 } 229 230 } 231 get_next_segment(const osmium::Location & location)232 NodeRefSegment* get_next_segment(const osmium::Location& location) { 233 auto it = std::lower_bound(m_locations.begin(), m_locations.end(), slocation{}, [this, &location](const slocation& lhs, const slocation& rhs) { 234 return lhs.location(m_segment_list, location) < rhs.location(m_segment_list, location); 235 }); 236 237 assert(it != m_locations.end()); 238 if (m_segment_list[it->item].is_done()) { 239 ++it; 240 } 241 assert(it != m_locations.end()); 242 243 assert(!m_segment_list[it->item].is_done()); 244 return &m_segment_list[it->item]; 245 } 246 247 class rings_stack_element { 248 249 double m_y; 250 ProtoRing* m_ring_ptr; 251 252 public: 253 rings_stack_element(double y,ProtoRing * ring_ptr)254 rings_stack_element(double y, ProtoRing* ring_ptr) : 255 m_y(y), 256 m_ring_ptr(ring_ptr) { 257 } 258 y() const259 double y() const noexcept { 260 return m_y; 261 } 262 ring() const263 const ProtoRing& ring() const noexcept { 264 return *m_ring_ptr; 265 } 266 ring_ptr()267 ProtoRing* ring_ptr() noexcept { 268 return m_ring_ptr; 269 } 270 operator ==(const rings_stack_element & rhs) const271 bool operator==(const rings_stack_element& rhs) const noexcept { 272 return m_ring_ptr == rhs.m_ring_ptr; 273 } 274 operator <(const rings_stack_element & rhs) const275 bool operator<(const rings_stack_element& rhs) const noexcept { 276 return m_y < rhs.m_y; 277 } 278 279 }; // class rings_stack_element 280 281 using rings_stack = std::vector<rings_stack_element>; 282 remove_duplicates(rings_stack & outer_rings)283 static void remove_duplicates(rings_stack& outer_rings) { 284 while (true) { 285 const auto it = std::adjacent_find(outer_rings.begin(), outer_rings.end()); 286 if (it == outer_rings.end()) { 287 return; 288 } 289 outer_rings.erase(it, std::next(it, 2)); 290 } 291 } 292 find_enclosing_ring(NodeRefSegment * segment)293 ProtoRing* find_enclosing_ring(NodeRefSegment* segment) { 294 if (debug()) { 295 std::cerr << " Looking for ring enclosing " << *segment << "\n"; 296 } 297 298 const auto location = segment->first().location(); 299 const auto end_location = segment->second().location(); 300 301 while (segment->first().location() == location) { 302 if (segment == &m_segment_list.back()) { 303 break; 304 } 305 ++segment; 306 } 307 308 int nesting = 0; 309 310 rings_stack outer_rings; 311 while (segment >= &m_segment_list.front()) { 312 if (!segment->is_direction_done()) { 313 --segment; 314 continue; 315 } 316 if (debug()) { 317 std::cerr << " Checking against " << *segment << "\n"; 318 } 319 const osmium::Location& a = segment->first().location(); 320 const osmium::Location& b = segment->second().location(); 321 322 if (segment->first().location() == location) { 323 const int64_t ax = a.x(); 324 const int64_t bx = b.x(); 325 const int64_t lx = end_location.x(); 326 const int64_t ay = a.y(); 327 const int64_t by = b.y(); 328 const int64_t ly = end_location.y(); 329 const auto z = (bx - ax)*(ly - ay) - (by - ay)*(lx - ax); 330 if (debug()) { 331 std::cerr << " Segment z=" << z << '\n'; 332 } 333 if (z > 0) { 334 nesting += segment->is_reverse() ? -1 : 1; 335 if (debug()) { 336 std::cerr << " Segment is below (nesting=" << nesting << ")\n"; 337 } 338 if (segment->ring()->is_outer()) { 339 if (debug()) { 340 std::cerr << " Segment belongs to outer ring (y=" << a.y() << " ring=" << *segment->ring() << ")\n"; 341 } 342 outer_rings.emplace_back(a.y(), segment->ring()); 343 } 344 } 345 } else if (a.x() <= location.x() && location.x() < b.x()) { 346 if (debug()) { 347 std::cerr << " Is in x range\n"; 348 } 349 350 const int64_t ax = a.x(); 351 const int64_t bx = b.x(); 352 const int64_t lx = location.x(); 353 const int64_t ay = a.y(); 354 const int64_t by = b.y(); 355 const int64_t ly = location.y(); 356 const auto z = (bx - ax)*(ly - ay) - (by - ay)*(lx - ax); 357 358 if (z >= 0) { 359 nesting += segment->is_reverse() ? -1 : 1; 360 if (debug()) { 361 std::cerr << " Segment is below (nesting=" << nesting << ")\n"; 362 } 363 if (segment->ring()->is_outer()) { 364 const double y = static_cast<double>(ay) + 365 static_cast<double>((by - ay) * (lx - ax)) / static_cast<double>(bx - ax); 366 if (debug()) { 367 std::cerr << " Segment belongs to outer ring (y=" << y << " ring=" << *segment->ring() << ")\n"; 368 } 369 outer_rings.emplace_back(y, segment->ring()); 370 } 371 } 372 } 373 --segment; 374 } 375 376 if (nesting % 2 == 0) { 377 if (debug()) { 378 std::cerr << " Decided that this is an outer ring\n"; 379 } 380 return nullptr; 381 } 382 383 if (debug()) { 384 std::cerr << " Decided that this is an inner ring\n"; 385 } 386 assert(!outer_rings.empty()); 387 388 std::stable_sort(outer_rings.rbegin(), outer_rings.rend()); 389 if (debug()) { 390 for (const auto& o : outer_rings) { 391 std::cerr << " y=" << o.y() << " " << o.ring() << "\n"; 392 } 393 } 394 395 remove_duplicates(outer_rings); 396 if (debug()) { 397 std::cerr << " after remove duplicates:\n"; 398 for (const auto& o : outer_rings) { 399 std::cerr << " y=" << o.y() << " " << o.ring() << "\n"; 400 } 401 } 402 403 assert(!outer_rings.empty()); 404 return outer_rings.front().ring_ptr(); 405 } 406 is_split_location(const osmium::Location & location) const407 bool is_split_location(const osmium::Location& location) const noexcept { 408 return std::find(m_split_locations.cbegin(), m_split_locations.cend(), location) != m_split_locations.cend(); 409 } 410 add_new_ring(const slocation & node)411 uint32_t add_new_ring(const slocation& node) { 412 NodeRefSegment* segment = &m_segment_list[node.item]; 413 assert(!segment->is_done()); 414 415 if (debug()) { 416 std::cerr << " Starting new ring at location " << node.location(m_segment_list) << " with segment " << *segment << "\n"; 417 } 418 419 if (node.reverse) { 420 segment->reverse(); 421 } 422 423 ProtoRing* outer_ring = nullptr; 424 425 if (segment != &m_segment_list.front()) { 426 outer_ring = find_enclosing_ring(segment); 427 } 428 segment->mark_direction_done(); 429 430 m_rings.emplace_back(segment); 431 ProtoRing* ring = &m_rings.back(); 432 if (outer_ring) { 433 if (debug()) { 434 std::cerr << " This is an inner ring. Outer ring is " << *outer_ring << "\n"; 435 } 436 outer_ring->add_inner_ring(ring); 437 ring->set_outer_ring(outer_ring); 438 } else if (debug()) { 439 std::cerr << " This is an outer ring\n"; 440 } 441 442 const osmium::Location& first_location = node.location(m_segment_list); 443 osmium::Location last_location = segment->stop().location(); 444 445 uint32_t nodes = 1; 446 while (first_location != last_location) { 447 ++nodes; 448 NodeRefSegment* next_segment = get_next_segment(last_location); 449 next_segment->mark_direction_done(); 450 if (next_segment->start().location() != last_location) { 451 next_segment->reverse(); 452 } 453 ring->add_segment_back(next_segment); 454 if (debug()) { 455 std::cerr << " Next segment is " << *next_segment << "\n"; 456 } 457 last_location = next_segment->stop().location(); 458 } 459 460 ring->fix_direction(); 461 462 if (debug()) { 463 std::cerr << " Completed ring: " << *ring << "\n"; 464 } 465 466 return nodes; 467 } 468 add_new_ring_complex(const slocation & node)469 uint32_t add_new_ring_complex(const slocation& node) { 470 NodeRefSegment* segment = &m_segment_list[node.item]; 471 assert(!segment->is_done()); 472 473 if (debug()) { 474 std::cerr << " Starting new ring at location " << node.location(m_segment_list) << " with segment " << *segment << "\n"; 475 } 476 477 if (node.reverse) { 478 segment->reverse(); 479 } 480 481 m_rings.emplace_back(segment); 482 ProtoRing* ring = &m_rings.back(); 483 484 const osmium::Location& first_location = node.location(m_segment_list); 485 osmium::Location last_location = segment->stop().location(); 486 487 uint32_t nodes = 1; 488 while (first_location != last_location && !is_split_location(last_location)) { 489 ++nodes; 490 NodeRefSegment* next_segment = get_next_segment(last_location); 491 if (next_segment->start().location() != last_location) { 492 next_segment->reverse(); 493 } 494 ring->add_segment_back(next_segment); 495 if (debug()) { 496 std::cerr << " Next segment is " << *next_segment << "\n"; 497 } 498 last_location = next_segment->stop().location(); 499 } 500 501 if (debug()) { 502 if (first_location == last_location) { 503 std::cerr << " Completed ring: " << *ring << "\n"; 504 } else { 505 std::cerr << " Completed partial ring: " << *ring << "\n"; 506 } 507 } 508 509 return nodes; 510 } 511 create_locations_list()512 void create_locations_list() { 513 m_locations.reserve(m_segment_list.size() * 2); 514 515 // static_cast is okay here: The 32bit limit is way past 516 // anything that makes sense here and even if there are 517 // 2^32 segments here, it would simply not go through 518 // all of them not building the multipolygon correctly. 519 assert(m_segment_list.size() < std::numeric_limits<uint32_t>::max()); 520 for (uint32_t n = 0; n < static_cast<uint32_t>(m_segment_list.size()); ++n) { 521 m_locations.emplace_back(n, false); 522 m_locations.emplace_back(n, true); 523 } 524 525 std::stable_sort(m_locations.begin(), m_locations.end(), [this](const slocation& lhs, const slocation& rhs) { 526 return lhs.location(m_segment_list) < rhs.location(m_segment_list); 527 }); 528 } 529 find_inner_outer_complex(ProtoRing * ring)530 void find_inner_outer_complex(ProtoRing* ring) { 531 ProtoRing* outer_ring = find_enclosing_ring(ring->min_segment()); 532 if (outer_ring) { 533 outer_ring->add_inner_ring(ring); 534 ring->set_outer_ring(outer_ring); 535 } 536 ring->fix_direction(); 537 ring->mark_direction_done(); 538 } 539 find_inner_outer_complex()540 void find_inner_outer_complex() { 541 if (debug()) { 542 std::cerr << " Finding inner/outer rings\n"; 543 } 544 std::vector<ProtoRing*> rings; 545 rings.reserve(m_rings.size()); 546 for (auto& ring : m_rings) { 547 if (ring.closed()) { 548 rings.push_back(&ring); 549 } 550 } 551 552 if (rings.empty()) { 553 return; 554 } 555 556 std::stable_sort(rings.begin(), rings.end(), [](ProtoRing* a, ProtoRing* b) { 557 return a->min_segment() < b->min_segment(); 558 }); 559 560 rings.front()->fix_direction(); 561 rings.front()->mark_direction_done(); 562 if (debug()) { 563 std::cerr << " First ring is outer: " << *rings.front() << "\n"; 564 } 565 for (auto it = std::next(rings.begin()); it != rings.end(); ++it) { 566 if (debug()) { 567 std::cerr << " Checking (at min segment " << *((*it)->min_segment()) << ") ring " << **it << "\n"; 568 } 569 find_inner_outer_complex(*it); 570 if (debug()) { 571 std::cerr << " Ring is " << ((*it)->is_outer() ? "OUTER: " : "INNER: ") << **it << "\n"; 572 } 573 } 574 } 575 576 /** 577 * Finds all locations where more than two segments meet. If there 578 * are any open rings found along the way, they are reported 579 * and the function returns false. 580 */ find_split_locations()581 bool find_split_locations() { 582 osmium::Location previous_location; 583 for (auto it = m_locations.cbegin(); it != m_locations.cend(); ++it) { 584 const osmium::NodeRef& nr = it->node_ref(m_segment_list); 585 const osmium::Location& loc = nr.location(); 586 if (std::next(it) == m_locations.cend() || loc != std::next(it)->location(m_segment_list)) { 587 if (debug()) { 588 std::cerr << " Found open ring at " << nr << "\n"; 589 } 590 if (m_config.problem_reporter) { 591 const auto& segment = m_segment_list[it->item]; 592 m_config.problem_reporter->report_ring_not_closed(nr, segment.way()); 593 } 594 ++m_stats.open_rings; 595 } else { 596 if (loc == previous_location && (m_split_locations.empty() || m_split_locations.back() != previous_location )) { 597 m_split_locations.push_back(previous_location); 598 } 599 ++it; 600 if (it == m_locations.end()) { 601 break; 602 } 603 } 604 previous_location = loc; 605 } 606 return m_stats.open_rings == 0; 607 } 608 create_rings_simple_case()609 void create_rings_simple_case() { 610 auto count_remaining = m_segment_list.size(); 611 for (slocation& sl : m_locations) { 612 const NodeRefSegment& segment = m_segment_list[sl.item]; 613 if (!segment.is_done()) { 614 count_remaining -= add_new_ring(sl); 615 if (count_remaining == 0) { 616 return; 617 } 618 } 619 } 620 } 621 create_location_to_ring_map(open_ring_its_type & open_ring_its) const622 std::vector<location_to_ring_map> create_location_to_ring_map(open_ring_its_type& open_ring_its) const { 623 std::vector<location_to_ring_map> xrings; 624 xrings.reserve(open_ring_its.size() * 2); 625 626 for (auto it = open_ring_its.begin(); it != open_ring_its.end(); ++it) { 627 if (debug()) { 628 std::cerr << " " << **it << '\n'; 629 } 630 xrings.emplace_back((*it)->get_node_ref_start().location(), it, true); 631 xrings.emplace_back((*it)->get_node_ref_stop().location(), it, false); 632 } 633 634 std::stable_sort(xrings.begin(), xrings.end()); 635 636 return xrings; 637 } 638 merge_two_rings(open_ring_its_type & open_ring_its,const location_to_ring_map & m1,const location_to_ring_map & m2)639 void merge_two_rings(open_ring_its_type& open_ring_its, const location_to_ring_map& m1, const location_to_ring_map& m2) { 640 const auto r1 = *m1.ring_it; 641 const auto r2 = *m2.ring_it; 642 643 if (r1->get_node_ref_stop().location() == r2->get_node_ref_start().location()) { 644 r1->join_forward(*r2); 645 } else if (r1->get_node_ref_stop().location() == r2->get_node_ref_stop().location()) { 646 r1->join_backward(*r2); 647 } else if (r1->get_node_ref_start().location() == r2->get_node_ref_start().location()) { 648 r1->reverse(); 649 r1->join_forward(*r2); 650 } else if (r1->get_node_ref_start().location() == r2->get_node_ref_stop().location()) { 651 r1->reverse(); 652 r1->join_backward(*r2); 653 } else { 654 assert(false); 655 } 656 657 open_ring_its.erase(std::find(open_ring_its.begin(), open_ring_its.end(), r2)); 658 m_rings.erase(r2); 659 660 if (r1->closed()) { 661 open_ring_its.erase(std::find(open_ring_its.begin(), open_ring_its.end(), r1)); 662 } 663 } 664 try_to_merge(open_ring_its_type & open_ring_its)665 bool try_to_merge(open_ring_its_type& open_ring_its) { 666 if (open_ring_its.empty()) { 667 return false; 668 } 669 670 if (debug()) { 671 std::cerr << " Trying to merge " << open_ring_its.size() << " open rings (try_to_merge)\n"; 672 } 673 674 std::vector<location_to_ring_map> xrings = create_location_to_ring_map(open_ring_its); 675 676 auto it = xrings.cbegin(); 677 while (it != xrings.cend()) { 678 it = std::adjacent_find(it, xrings.cend()); 679 if (it == xrings.cend()) { 680 return false; 681 } 682 auto after = std::next(it, 2); 683 if (after == xrings.cend() || after->location != it->location) { 684 if (debug()) { 685 std::cerr << " Merging two rings\n"; 686 } 687 merge_two_rings(open_ring_its, *it, *std::next(it)); 688 return true; 689 } 690 while (it != xrings.cend() && it->location == after->location) { 691 ++it; 692 } 693 } 694 695 return false; 696 } 697 there_are_open_rings() const698 bool there_are_open_rings() const noexcept { 699 return std::any_of(m_rings.cbegin(), m_rings.cend(), [](const ProtoRing& ring){ 700 return !ring.closed(); 701 }); 702 } 703 704 struct candidate { 705 int64_t sum; 706 std::vector<std::pair<location_to_ring_map, bool>> rings{}; 707 osmium::Location start_location; 708 osmium::Location stop_location; 709 candidateosmium::area::detail::BasicAssembler::candidate710 explicit candidate(location_to_ring_map& ring, bool reverse) : 711 sum(ring.ring().sum()), 712 start_location(ring.ring().get_node_ref_start().location()), 713 stop_location(ring.ring().get_node_ref_stop().location()) { 714 rings.emplace_back(ring, reverse); 715 } 716 closedosmium::area::detail::BasicAssembler::candidate717 bool closed() const noexcept { 718 return start_location == stop_location; 719 } 720 721 }; 722 723 struct exceeded_max_depth : public std::exception {}; 724 725 using location_set = std::vector<osmium::Location>; 726 find_candidates(std::vector<candidate> & candidates,location_set & loc_done,const std::vector<location_to_ring_map> & xrings,const candidate & cand,unsigned depth=0)727 void find_candidates(std::vector<candidate>& candidates, location_set& loc_done, const std::vector<location_to_ring_map>& xrings, const candidate& cand, unsigned depth = 0) { 728 if (depth > max_depth) { 729 throw exceeded_max_depth{}; 730 } 731 732 if (debug()) { 733 std::cerr << " find_candidates sum=" << cand.sum << " start=" << cand.start_location << " stop=" << cand.stop_location << "\n"; 734 for (const auto& ring : cand.rings) { 735 std::cerr << " " << ring.first.ring() << (ring.second ? " reverse" : "") << "\n"; 736 } 737 } 738 739 const auto connections = make_range(std::equal_range(xrings.cbegin(), 740 xrings.cend(), 741 location_to_ring_map{cand.stop_location})); 742 743 assert(connections.begin() != connections.end()); 744 745 assert(!cand.rings.empty()); 746 const ProtoRing* ring_leading_here = &cand.rings.back().first.ring(); 747 for (const location_to_ring_map& m : connections) { 748 const ProtoRing& ring = m.ring(); 749 750 if (&ring != ring_leading_here) { 751 if (debug()) { 752 std::cerr << " next possible connection: " << ring << (m.start ? "" : " reverse") << "\n"; 753 } 754 755 candidate c = cand; 756 if (m.start) { 757 c.rings.emplace_back(m, false); 758 c.stop_location = ring.get_node_ref_stop().location(); 759 c.sum += ring.sum(); 760 } else { 761 c.rings.emplace_back(m, true); 762 c.stop_location = ring.get_node_ref_start().location(); 763 c.sum -= ring.sum(); 764 } 765 if (c.closed()) { 766 if (debug()) { 767 std::cerr << " found candidate\n"; 768 } 769 770 if (candidates.empty()) { 771 candidates.push_back(c); 772 } else if (candidates.size() == 1) { 773 // add new candidate to vector, keep sorted 774 if (std::abs(c.sum) < std::abs(candidates.front().sum)) { 775 candidates.insert(candidates.begin(), c); 776 } else { 777 candidates.push_back(c); 778 } 779 } else { 780 // add new candidate if it has either smallest or largest area 781 if (std::abs(c.sum) < std::abs(candidates.front().sum)) { 782 candidates.front() = c; 783 } else if (std::abs(c.sum) > std::abs(candidates.back().sum)) { 784 candidates.back() = c; 785 } 786 } 787 } else if (std::find(loc_done.cbegin(), loc_done.cend(), c.stop_location) == loc_done.cend()) { 788 if (debug()) { 789 std::cerr << " recurse... (depth=" << depth << " candidates.size=" << candidates.size() << " loc_done.size=" << loc_done.size() << ")\n"; 790 } 791 loc_done.push_back(c.stop_location); 792 find_candidates(candidates, loc_done, xrings, c, depth + 1); 793 assert(!loc_done.empty() && loc_done.back() == c.stop_location); 794 loc_done.pop_back(); 795 if (debug()) { 796 std::cerr << " ...back\n"; 797 } 798 } else if (debug()) { 799 std::cerr << " loop found\n"; 800 } 801 } 802 } 803 } 804 805 /** 806 * If there are multiple open rings and multiple ways to join them, 807 * this function is called. It will take the first open ring and 808 * try recursively all ways of closing it. Of all the candidates 809 * the one with the smallest area is chosen and closed. If it 810 * can't close this ring, an error is reported and the function 811 * returns false. 812 */ join_connected_rings(open_ring_its_type & open_ring_its)813 bool join_connected_rings(open_ring_its_type& open_ring_its) { 814 assert(!open_ring_its.empty()); 815 816 if (debug()) { 817 std::cerr << " Trying to merge " << open_ring_its.size() << " open rings (join_connected_rings)\n"; 818 } 819 820 std::vector<location_to_ring_map> xrings = create_location_to_ring_map(open_ring_its); 821 822 const auto ring_min = std::min_element(xrings.begin(), xrings.end(), [](const location_to_ring_map& lhs, const location_to_ring_map& rhs) { 823 return lhs.ring().min_segment() < rhs.ring().min_segment(); 824 }); 825 826 find_inner_outer_complex(); 827 ProtoRing* outer_ring = find_enclosing_ring(ring_min->ring().min_segment()); 828 bool ring_min_is_outer = !outer_ring; 829 if (debug()) { 830 std::cerr << " Open ring is " << (ring_min_is_outer ? "outer" : "inner") << " ring\n"; 831 } 832 for (auto& ring : m_rings) { 833 ring.reset(); 834 } 835 836 const candidate cand{*ring_min, false}; 837 838 // Locations we have visited while finding candidates, used 839 // to detect loops. 840 location_set loc_done; 841 842 loc_done.push_back(cand.stop_location); 843 844 std::vector<candidate> candidates; 845 try { 846 find_candidates(candidates, loc_done, xrings, cand); 847 } catch (const exceeded_max_depth&) { 848 if (m_config.debug_level > 0) { 849 std::cerr << " Exceeded max depth (" << static_cast<unsigned>(max_depth) << ")\n"; 850 } 851 return false; 852 } 853 854 if (candidates.empty()) { 855 if (debug()) { 856 std::cerr << " Found no candidates\n"; 857 } 858 if (!open_ring_its.empty()) { 859 ++m_stats.open_rings; 860 if (m_config.problem_reporter) { 861 for (auto& it : open_ring_its) { 862 m_config.problem_reporter->report_ring_not_closed(it->get_node_ref_start(), nullptr); 863 m_config.problem_reporter->report_ring_not_closed(it->get_node_ref_stop(), nullptr); 864 } 865 } 866 } 867 return false; 868 } 869 870 if (debug()) { 871 std::cerr << " Found candidates:\n"; 872 for (const auto& c : candidates) { 873 std::cerr << " sum=" << c.sum << "\n"; 874 for (const auto& ring : c.rings) { 875 std::cerr << " " << ring.first.ring() << (ring.second ? " reverse" : "") << "\n"; 876 } 877 } 878 } 879 880 // Find the candidate with the smallest/largest area 881 const auto chosen_cand = ring_min_is_outer ? candidates.front() : candidates.back(); 882 883 if (debug()) { 884 std::cerr << " Decided on: sum=" << chosen_cand.sum << "\n"; 885 for (const auto& ring : chosen_cand.rings) { 886 std::cerr << " " << ring.first.ring() << (ring.second ? " reverse" : "") << "\n"; 887 } 888 } 889 890 // Join all (open) rings in the candidate to get one closed ring. 891 assert(chosen_cand.rings.size() > 1); 892 const auto& first_ring = chosen_cand.rings.front().first; 893 const ProtoRing& remaining_ring = first_ring.ring(); 894 for (auto it = std::next(chosen_cand.rings.begin()); it != chosen_cand.rings.end(); ++it) { 895 merge_two_rings(open_ring_its, first_ring, it->first); 896 } 897 898 if (debug()) { 899 std::cerr << " Merged to " << remaining_ring << '\n'; 900 } 901 902 return true; 903 } 904 create_rings_complex_case()905 bool create_rings_complex_case() { 906 // First create all the (partial) rings starting at the split locations 907 auto count_remaining = m_segment_list.size(); 908 for (const osmium::Location& location : m_split_locations) { 909 const auto locs = make_range(std::equal_range(m_locations.begin(), 910 m_locations.end(), 911 slocation{}, 912 [this, &location](const slocation& lhs, const slocation& rhs) { 913 return lhs.location(m_segment_list, location) < rhs.location(m_segment_list, location); 914 })); 915 for (auto& loc : locs) { 916 if (!m_segment_list[loc.item].is_done()) { 917 count_remaining -= add_new_ring_complex(loc); 918 if (count_remaining == 0) { 919 break; 920 } 921 } 922 } 923 } 924 925 // Now find all the rest of the rings (ie not starting at split locations) 926 if (count_remaining > 0) { 927 for (slocation& sl : m_locations) { 928 const NodeRefSegment& segment = m_segment_list[sl.item]; 929 if (!segment.is_done()) { 930 count_remaining -= add_new_ring_complex(sl); 931 if (count_remaining == 0) { 932 break; 933 } 934 } 935 } 936 } 937 938 // Now all segments are in exactly one (partial) ring. 939 940 // If there are open rings, try to join them to create closed 941 // rings. 942 if (there_are_open_rings()) { 943 ++m_stats.area_really_complex_case; 944 945 open_ring_its_type open_ring_its; 946 for (auto it = m_rings.begin(); it != m_rings.end(); ++it) { 947 if (!it->closed()) { 948 open_ring_its.push_back(it); 949 } 950 } 951 952 while (!open_ring_its.empty()) { 953 if (debug()) { 954 std::cerr << " There are " << open_ring_its.size() << " open rings\n"; 955 } 956 while (try_to_merge(open_ring_its)) { 957 // intentionally left blank 958 } 959 960 if (!open_ring_its.empty()) { 961 if (debug()) { 962 std::cerr << " After joining obvious cases there are still " << open_ring_its.size() << " open rings\n"; 963 } 964 if (!join_connected_rings(open_ring_its)) { 965 return false; 966 } 967 } 968 } 969 970 if (debug()) { 971 std::cerr << " Joined all open rings\n"; 972 } 973 } 974 975 // Now all rings are complete. 976 977 find_inner_outer_complex(); 978 979 return true; 980 } 981 982 #ifdef OSMIUM_WITH_TIMER print_header()983 static bool print_header() { 984 std::cout << "nodes outer_rings inner_rings sort dupl intersection locations split simple_case complex_case roles_check\n"; 985 return true; 986 } 987 init_header()988 static bool init_header() { 989 static bool printed_print_header = print_header(); 990 return printed_print_header; 991 } 992 #endif 993 994 protected: 995 rings() const996 const std::list<ProtoRing>& rings() const noexcept { 997 return m_rings; 998 } 999 set_num_members(std::size_t size)1000 void set_num_members(std::size_t size) noexcept { 1001 m_num_members = size; 1002 } 1003 segment_list()1004 SegmentList& segment_list() noexcept { 1005 return m_segment_list; 1006 } 1007 1008 /** 1009 * Append each outer ring together with its inner rings to the 1010 * area in the buffer. 1011 */ add_rings_to_area(osmium::builder::AreaBuilder & builder) const1012 void add_rings_to_area(osmium::builder::AreaBuilder& builder) const { 1013 for (const ProtoRing& ring : m_rings) { 1014 if (ring.is_outer()) { 1015 build_ring_from_proto_ring<osmium::builder::OuterRingBuilder>(builder, ring); 1016 for (const ProtoRing* inner : ring.inner_rings()) { 1017 build_ring_from_proto_ring<osmium::builder::InnerRingBuilder>(builder, *inner); 1018 } 1019 } 1020 } 1021 } 1022 1023 /** 1024 * Create rings from segments. 1025 */ create_rings()1026 bool create_rings() { 1027 m_stats.nodes += m_segment_list.size(); 1028 1029 // Sort the list of segments (from left to right and bottom 1030 // to top). 1031 osmium::Timer timer_sort; 1032 m_segment_list.sort(); 1033 timer_sort.stop(); 1034 1035 // Remove duplicate segments. Removal is in pairs, so if there 1036 // are two identical segments, they will both be removed. If 1037 // there are three, two will be removed and one remains. 1038 osmium::Timer timer_dupl; 1039 m_segment_list.erase_duplicate_segments(m_config.problem_reporter, m_stats.duplicate_segments, m_stats.overlapping_segments); 1040 timer_dupl.stop(); 1041 1042 // If there are no segments left at this point, this isn't 1043 // a valid area. 1044 if (m_segment_list.empty()) { 1045 if (debug()) { 1046 std::cerr << " No segments left\n"; 1047 } 1048 return false; 1049 } 1050 1051 if (m_config.debug_level >= 3) { 1052 std::cerr << "Sorted de-duplicated segment list:\n"; 1053 for (const auto& s : m_segment_list) { 1054 std::cerr << " " << s << "\n"; 1055 } 1056 } 1057 1058 // Now we look for segments crossing each other. If there are 1059 // any, the multipolygon is invalid. 1060 // In the future this could be improved by trying to fix those 1061 // cases. 1062 osmium::Timer timer_intersection; 1063 m_stats.intersections = m_segment_list.find_intersections(m_config.problem_reporter); 1064 timer_intersection.stop(); 1065 1066 if (m_stats.intersections) { 1067 return false; 1068 } 1069 1070 // This creates an ordered list of locations of both endpoints 1071 // of all segments with pointers back to the segments. We will 1072 // use this list later to quickly find which segment(s) fits 1073 // onto a known segment. 1074 osmium::Timer timer_locations_list; 1075 create_locations_list(); 1076 timer_locations_list.stop(); 1077 1078 // Find all locations where more than two segments start or 1079 // end. We call those "split" locations. If there are any 1080 // "spike" segments found while doing this, we know the area 1081 // geometry isn't valid and return. 1082 osmium::Timer timer_split; 1083 if (!find_split_locations()) { 1084 return false; 1085 } 1086 timer_split.stop(); 1087 1088 // Now report all split locations to the problem reporter. 1089 m_stats.touching_rings += m_split_locations.size(); 1090 if (!m_split_locations.empty()) { 1091 if (debug()) { 1092 std::cerr << " Found split locations:\n"; 1093 } 1094 for (const auto& location : m_split_locations) { 1095 if (m_config.problem_reporter) { 1096 auto it = std::lower_bound(m_locations.cbegin(), m_locations.cend(), slocation{}, [this, &location](const slocation& lhs, const slocation& rhs) { 1097 return lhs.location(m_segment_list, location) < rhs.location(m_segment_list, location); 1098 }); 1099 assert(it != m_locations.cend()); 1100 const osmium::object_id_type id = it->node_ref(m_segment_list).ref(); 1101 m_config.problem_reporter->report_touching_ring(id, location); 1102 } 1103 if (debug()) { 1104 std::cerr << " " << location << "\n"; 1105 } 1106 } 1107 } 1108 1109 // From here on we use two different algorithms depending on 1110 // whether there were any split locations or not. If there 1111 // are no splits, we use the faster "simple algorithm", if 1112 // there are, we use the slower "complex algorithm". 1113 osmium::Timer timer; 1114 if (m_split_locations.empty()) { 1115 if (debug()) { 1116 std::cerr << " No split locations -> using simple algorithm\n"; 1117 } 1118 ++m_stats.area_simple_case; 1119 1120 timer.start(); 1121 create_rings_simple_case(); 1122 timer.stop(); 1123 } else if (m_split_locations.size() > max_split_locations) { 1124 if (m_config.debug_level > 0) { 1125 std::cerr << " Ignoring polygon with " 1126 << m_split_locations.size() 1127 << " split locations (>" 1128 << max_split_locations 1129 << ")\n"; 1130 } 1131 return false; 1132 } else { 1133 if (m_config.debug_level > 0) { 1134 std::cerr << " Found " 1135 << m_split_locations.size() 1136 << " split locations -> using complex algorithm\n"; 1137 } 1138 ++m_stats.area_touching_rings_case; 1139 1140 timer.start(); 1141 if (!create_rings_complex_case()) { 1142 return false; 1143 } 1144 timer.stop(); 1145 } 1146 1147 // If the assembler was so configured, now check whether the 1148 // member roles are correctly tagged. 1149 if (m_config.check_roles && m_stats.from_relations) { 1150 osmium::Timer timer_roles; 1151 check_inner_outer_roles(); 1152 timer_roles.stop(); 1153 } 1154 1155 m_stats.outer_rings = std::count_if(m_rings.cbegin(), m_rings.cend(), [](const ProtoRing& ring){ 1156 return ring.is_outer(); 1157 }); 1158 m_stats.inner_rings = m_rings.size() - m_stats.outer_rings; 1159 1160 #ifdef OSMIUM_WITH_TIMER 1161 std::cout << m_stats.nodes << ' ' << m_stats.outer_rings << ' ' << m_stats.inner_rings << 1162 ' ' << timer_sort.elapsed_microseconds() << 1163 ' ' << timer_dupl.elapsed_microseconds() << 1164 ' ' << timer_intersection.elapsed_microseconds() << 1165 ' ' << timer_locations_list.elapsed_microseconds() << 1166 ' ' << timer_split.elapsed_microseconds(); 1167 1168 if (m_split_locations.empty()) { 1169 std::cout << ' ' << timer.elapsed_microseconds() << " 0"; 1170 } else { 1171 std::cout << " 0" << ' ' << timer.elapsed_microseconds(); 1172 } 1173 1174 std::cout << 1175 # ifdef OSMIUM_AREA_CHECK_INNER_OUTER_ROLES 1176 ' ' << timer_roles.elapsed_microseconds() << 1177 # else 1178 " 0" << 1179 # endif 1180 '\n'; 1181 #endif 1182 1183 return true; 1184 } 1185 1186 public: 1187 1188 using config_type = osmium::area::AssemblerConfig; 1189 BasicAssembler(const config_type & config)1190 explicit BasicAssembler(const config_type& config) : 1191 m_config(config), 1192 m_segment_list(config.debug_level > 1) { 1193 #ifdef OSMIUM_WITH_TIMER 1194 init_header(); 1195 #endif 1196 } 1197 config() const1198 const AssemblerConfig& config() const noexcept { 1199 return m_config; 1200 } 1201 debug() const1202 bool debug() const noexcept { 1203 return m_config.debug_level > 1; 1204 } 1205 1206 /** 1207 * Get statistics from assembler. Call this after running the 1208 * assembler to get statistics and data about errors. 1209 */ stats() const1210 const osmium::area::area_stats& stats() const noexcept { 1211 return m_stats; 1212 } 1213 stats()1214 osmium::area::area_stats& stats() noexcept { 1215 return m_stats; 1216 } 1217 1218 }; // class BasicAssembler 1219 1220 } // namespace detail 1221 1222 } // namespace area 1223 1224 } // namespace osmium 1225 1226 #endif // OSMIUM_AREA_DETAIL_BASIC_ASSEMBLER_HPP 1227