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