Libosmium  2.11.1
Fast and flexible C++ library for working with OpenStreetMap data
assembler.hpp
Go to the documentation of this file.
1 #ifndef OSMIUM_AREA_ASSEMBLER_HPP
2 #define OSMIUM_AREA_ASSEMBLER_HPP
3 
4 /*
5 
6 This file is part of Osmium (http://osmcode.org/libosmium).
7 
8 Copyright 2013-2017 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 <algorithm>
37 #include <cassert>
38 #include <cstdint>
39 #include <cstdlib>
40 #include <cstring>
41 #include <iostream>
42 #include <iterator>
43 #include <list>
44 #include <set>
45 #include <string>
46 #include <map>
47 #include <unordered_map>
48 #include <unordered_set>
49 #include <utility>
50 #include <vector>
51 
53 #include <osmium/memory/buffer.hpp>
54 #include <osmium/osm/area.hpp>
55 #include <osmium/osm/item_type.hpp>
56 #include <osmium/osm/location.hpp>
57 #include <osmium/osm/node_ref.hpp>
58 #include <osmium/osm/relation.hpp>
59 #include <osmium/osm/tag.hpp>
60 #include <osmium/osm/types.hpp>
61 #include <osmium/osm/way.hpp>
62 #include <osmium/tags/filter.hpp>
64 #include <osmium/util/iterator.hpp>
65 #include <osmium/util/timer.hpp>
66 
67 #include <osmium/area/detail/proto_ring.hpp>
68 #include <osmium/area/detail/node_ref_segment.hpp>
69 #include <osmium/area/detail/segment_list.hpp>
71 #include <osmium/area/stats.hpp>
72 
73 namespace osmium {
74 
75  namespace area {
76 
82  struct AssemblerConfig {
83 
88 
94  int debug_level = 0;
95 
104  bool check_roles = false;
105 
114  bool create_empty_areas = true;
115 
123 
131 
137  bool create_way_polygons = true;
138 
144  bool keep_type_tag = false;
145 
146  AssemblerConfig() noexcept = default;
147 
152  explicit AssemblerConfig(osmium::area::ProblemReporter* pr, bool d = false) :
153  problem_reporter(pr),
154  debug_level(d) {
155  }
156 
164  debug_level = d;
165  }
166 
167  }; // struct AssemblerConfig
168 
169  namespace detail {
170 
171  using open_ring_its_type = std::list<std::list<detail::ProtoRing>::iterator>;
172 
173  struct location_to_ring_map {
174  osmium::Location location;
175  open_ring_its_type::iterator ring_it;
176  bool start;
177 
178  location_to_ring_map(const osmium::Location& l, const open_ring_its_type::iterator& r, bool s) noexcept :
179  location(l),
180  ring_it(r),
181  start(s) {
182  }
183 
184  explicit location_to_ring_map(const osmium::Location& l) noexcept :
185  location(l),
186  ring_it(),
187  start(false) {
188  }
189 
190  const detail::ProtoRing& ring() const noexcept {
191  return **ring_it;
192  }
193 
194  }; // struct location_to_ring_map
195 
196  inline bool operator==(const location_to_ring_map& lhs, const location_to_ring_map& rhs) noexcept {
197  return lhs.location == rhs.location;
198  }
199 
200  inline bool operator<(const location_to_ring_map& lhs, const location_to_ring_map& rhs) noexcept {
201  return lhs.location < rhs.location;
202  }
203 
204  } // namespace detail
205 
210  class Assembler {
211 
212  using open_ring_its_type = detail::open_ring_its_type;
213  using location_to_ring_map = detail::location_to_ring_map;
214 
215  struct slocation {
216 
217  static constexpr const uint32_t invalid_item = 1 << 30;
218 
219  uint32_t item : 31;
220  uint32_t reverse : 1;
221 
222  slocation() noexcept :
223  item(invalid_item),
224  reverse(false) {
225  }
226 
227  explicit slocation(uint32_t n, bool r = false) noexcept :
228  item(n),
229  reverse(r) {
230  }
231 
232  osmium::Location location(const detail::SegmentList& segment_list) const noexcept {
233  const auto& segment = segment_list[item];
234  return reverse ? segment.second().location() : segment.first().location();
235  }
236 
237  const osmium::NodeRef& node_ref(const detail::SegmentList& segment_list) const noexcept {
238  const auto& segment = segment_list[item];
239  return reverse ? segment.second() : segment.first();
240  }
241 
242  osmium::Location location(const detail::SegmentList& segment_list, const osmium::Location& default_location) const noexcept {
243  if (item == invalid_item) {
244  return default_location;
245  }
246  return location(segment_list);
247  }
248 
249  }; // struct slocation
250 
251  // Configuration settings for this Assembler
253 
254  // List of segments (connection between two nodes)
255  osmium::area::detail::SegmentList m_segment_list;
256 
257  // The rings we are building from the segments
258  std::list<detail::ProtoRing> m_rings;
259 
260  // All node locations
261  std::vector<slocation> m_locations;
262 
263  // All locations where more than two segments start/end
264  std::vector<Location> m_split_locations;
265 
266  // Statistics
268 
269  // The number of members the multipolygon relation has
270  size_t m_num_members = 0;
271 
272  bool debug() const noexcept {
273  return m_config.debug_level > 1;
274  }
275 
276  bool report_ways() const noexcept {
277  if (!m_config.problem_reporter) {
278  return false;
279  }
280  return m_stats.duplicate_nodes ||
281  m_stats.duplicate_segments ||
282  m_stats.intersections ||
283  m_stats.open_rings ||
284  m_stats.short_ways ||
285  m_stats.touching_rings ||
286  m_stats.ways_in_multiple_rings ||
287  m_stats.wrong_role;
288  }
289 
290  void add_tags_to_area(osmium::builder::AreaBuilder& builder, const osmium::Way& way) const {
291  builder.add_item(way.tags());
292  }
293 
294  void add_common_tags(osmium::builder::TagListBuilder& tl_builder, std::set<const osmium::Way*>& ways) const {
295  std::map<std::string, size_t> counter;
296  for (const osmium::Way* way : ways) {
297  for (const auto& tag : way->tags()) {
298  std::string kv {tag.key()};
299  kv.append(1, '\0');
300  kv.append(tag.value());
301  ++counter[kv];
302  }
303  }
304 
305  const size_t num_ways = ways.size();
306  for (const auto& t_c : counter) {
307  if (debug()) {
308  std::cerr << " tag " << t_c.first << " is used " << t_c.second << " times in " << num_ways << " ways\n";
309  }
310  if (t_c.second == num_ways) {
311  const size_t len = std::strlen(t_c.first.c_str());
312  tl_builder.add_tag(t_c.first.c_str(), t_c.first.c_str() + len + 1);
313  }
314  }
315  }
316 
318 
319  MPFilter() : osmium::tags::KeyFilter(true) {
320  add(false, "type");
321  add(false, "created_by");
322  add(false, "source");
323  add(false, "note");
324  add(false, "test:id");
325  add(false, "test:section");
326  }
327 
328  }; // struct MPFilter
329 
330  static const MPFilter& filter() noexcept {
331  static const MPFilter filter;
332  return filter;
333  }
334 
336  osmium::builder::TagListBuilder tl_builder{builder};
337  for (const osmium::Tag& tag : tags) {
338  if (std::strcmp(tag.key(), "type")) {
339  tl_builder.add_tag(tag.key(), tag.value());
340  }
341  }
342  }
343 
345  const auto count = std::count_if(relation.tags().cbegin(), relation.tags().cend(), filter());
346 
347  if (debug()) {
348  std::cerr << " found " << count << " tags on relation (without ignored ones)\n";
349  }
350 
351  if (count > 0) {
352  if (debug()) {
353  std::cerr << " use tags from relation\n";
354  }
355 
356  if (m_config.keep_type_tag) {
357  builder.add_item(relation.tags());
358  } else {
359  copy_tags_without_type(builder, relation.tags());
360  }
361  } else {
362  ++m_stats.no_tags_on_relation;
363  if (debug()) {
364  std::cerr << " use tags from outer ways\n";
365  }
366  std::set<const osmium::Way*> ways;
367  for (const auto& ring : m_rings) {
368  if (ring.is_outer()) {
369  ring.get_ways(ways);
370  }
371  }
372  if (ways.size() == 1) {
373  if (debug()) {
374  std::cerr << " only one outer way\n";
375  }
376  builder.add_item((*ways.cbegin())->tags());
377  } else {
378  if (debug()) {
379  std::cerr << " multiple outer ways, get common tags\n";
380  }
381  osmium::builder::TagListBuilder tl_builder{builder};
382  add_common_tags(tl_builder, ways);
383  }
384  }
385  }
386 
387  template <typename TBuilder>
388  static void build_ring_from_proto_ring(osmium::builder::AreaBuilder& builder, const detail::ProtoRing& ring) {
389  TBuilder ring_builder{builder};
390  ring_builder.add_node_ref(ring.get_node_ref_start());
391  for (const auto& segment : ring.segments()) {
392  ring_builder.add_node_ref(segment->stop());
393  }
394  }
395 
401  for (const detail::ProtoRing& ring : m_rings) {
402  if (ring.is_outer()) {
403  build_ring_from_proto_ring<osmium::builder::OuterRingBuilder>(builder, ring);
404  for (const detail::ProtoRing* inner : ring.inner_rings()) {
405  build_ring_from_proto_ring<osmium::builder::InnerRingBuilder>(builder, *inner);
406  }
407  }
408  }
409  }
410 
412  if (debug()) {
413  std::cerr << " Checking inner/outer roles\n";
414  }
415 
416  std::unordered_map<const osmium::Way*, const detail::ProtoRing*> way_rings;
417  std::unordered_set<const osmium::Way*> ways_in_multiple_rings;
418 
419  for (const detail::ProtoRing& ring : m_rings) {
420  for (const auto& segment : ring.segments()) {
421  assert(segment->way());
422 
423  if (!segment->role_empty() && (ring.is_outer() ? !segment->role_outer() : !segment->role_inner())) {
424  ++m_stats.wrong_role;
425  if (debug()) {
426  std::cerr << " Segment " << *segment << " from way " << segment->way()->id() << " has role '" << segment->role_name()
427  << "', but should have role '" << (ring.is_outer() ? "outer" : "inner") << "'\n";
428  }
429  if (m_config.problem_reporter) {
430  if (ring.is_outer()) {
431  m_config.problem_reporter->report_role_should_be_outer(segment->way()->id(), segment->first().location(), segment->second().location());
432  } else {
433  m_config.problem_reporter->report_role_should_be_inner(segment->way()->id(), segment->first().location(), segment->second().location());
434  }
435  }
436  }
437 
438  auto& r = way_rings[segment->way()];
439  if (!r) {
440  r = &ring;
441  } else if (r != &ring) {
442  ways_in_multiple_rings.insert(segment->way());
443  }
444 
445  }
446  }
447 
448  for (const osmium::Way* way : ways_in_multiple_rings) {
449  ++m_stats.ways_in_multiple_rings;
450  if (debug()) {
451  std::cerr << " Way " << way->id() << " is in multiple rings\n";
452  }
453  if (m_config.problem_reporter) {
455  }
456  }
457 
458  }
459 
460  detail::NodeRefSegment* get_next_segment(const osmium::Location& location) {
461  auto it = std::lower_bound(m_locations.begin(), m_locations.end(), slocation{}, [this, &location](const slocation& lhs, const slocation& rhs) {
462  return lhs.location(m_segment_list, location) < rhs.location(m_segment_list, location);
463  });
464 
465  assert(it != m_locations.end());
466  if (m_segment_list[it->item].is_done()) {
467  ++it;
468  }
469  assert(it != m_locations.end());
470 
471  assert(!m_segment_list[it->item].is_done());
472  return &m_segment_list[it->item];
473  }
474 
476 
477  int32_t m_y;
478  detail::ProtoRing* m_ring_ptr;
479 
480  public:
481 
482  rings_stack_element(int32_t y, detail::ProtoRing* ring_ptr) :
483  m_y(y),
484  m_ring_ptr(ring_ptr) {
485  }
486 
487  int32_t y() const noexcept {
488  return m_y;
489  }
490 
491  const detail::ProtoRing& ring() const noexcept {
492  return *m_ring_ptr;
493  }
494 
495  detail::ProtoRing* ring_ptr() noexcept {
496  return m_ring_ptr;
497  }
498 
499  bool operator==(const rings_stack_element& rhs) const noexcept {
500  return m_ring_ptr == rhs.m_ring_ptr;
501  }
502 
503  bool operator<(const rings_stack_element& rhs) const noexcept {
504  return m_y < rhs.m_y;
505  }
506 
507  }; // class ring_stack_element
508 
509  using rings_stack = std::vector<rings_stack_element>;
510 
511  void remove_duplicates(rings_stack& outer_rings) {
512  while (true) {
513  const auto it = std::adjacent_find(outer_rings.begin(), outer_rings.end());
514  if (it == outer_rings.end()) {
515  return;
516  }
517  outer_rings.erase(it, std::next(it, 2));
518  }
519  }
520 
521  detail::ProtoRing* find_enclosing_ring(detail::NodeRefSegment* segment) {
522  if (debug()) {
523  std::cerr << " Looking for ring enclosing " << *segment << "\n";
524  }
525 
526  const auto location = segment->first().location();
527  const auto end_location = segment->second().location();
528 
529  while (segment->first().location() == location) {
530  if (segment == &m_segment_list.back()) {
531  break;
532  }
533  ++segment;
534  }
535 
536  int nesting = 0;
537 
538  rings_stack outer_rings;
539  while (segment >= &m_segment_list.front()) {
540  if (!segment->is_direction_done()) {
541  --segment;
542  continue;
543  }
544  if (debug()) {
545  std::cerr << " Checking against " << *segment << "\n";
546  }
547  const osmium::Location& a = segment->first().location();
548  const osmium::Location& b = segment->second().location();
549 
550  if (segment->first().location() == location) {
551  const int64_t ax = a.x();
552  const int64_t bx = b.x();
553  const int64_t lx = end_location.x();
554  const int64_t ay = a.y();
555  const int64_t by = b.y();
556  const int64_t ly = end_location.y();
557  const auto z = (bx - ax)*(ly - ay) - (by - ay)*(lx - ax);
558  if (debug()) {
559  std::cerr << " Segment XXXX z=" << z << "\n";
560  }
561  if (z > 0) {
562  nesting += segment->is_reverse() ? -1 : 1;
563  if (debug()) {
564  std::cerr << " Segment is below (nesting=" << nesting << ")\n";
565  }
566  if (segment->ring()->is_outer()) {
567  if (debug()) {
568  std::cerr << " Segment belongs to outer ring\n";
569  }
570  outer_rings.emplace_back(a.y(), segment->ring());
571  }
572  }
573  } else if (a.x() <= location.x() && location.x() < b.x()) {
574  if (debug()) {
575  std::cerr << " Is in x range\n";
576  }
577 
578  const int64_t ax = a.x();
579  const int64_t bx = b.x();
580  const int64_t lx = location.x();
581  const int64_t ay = a.y();
582  const int64_t by = b.y();
583  const int64_t ly = location.y();
584  const auto z = (bx - ax)*(ly - ay) - (by - ay)*(lx - ax);
585 
586  if (z >= 0) {
587  nesting += segment->is_reverse() ? -1 : 1;
588  if (debug()) {
589  std::cerr << " Segment is below (nesting=" << nesting << ")\n";
590  }
591  if (segment->ring()->is_outer()) {
592  if (debug()) {
593  std::cerr << " Segment belongs to outer ring\n";
594  }
595  const int32_t y = int32_t(ay + (by - ay) * (lx - ax) / (bx - ax));
596  outer_rings.emplace_back(y, segment->ring());
597  }
598  }
599  }
600  --segment;
601  }
602 
603  if (nesting % 2 == 0) {
604  if (debug()) {
605  std::cerr << " Decided that this is an outer ring\n";
606  }
607  return nullptr;
608  } else {
609  if (debug()) {
610  std::cerr << " Decided that this is an inner ring\n";
611  }
612  assert(!outer_rings.empty());
613 
614  std::sort(outer_rings.rbegin(), outer_rings.rend());
615  if (debug()) {
616  for (const auto& o : outer_rings) {
617  std::cerr << " y=" << o.y() << " " << o.ring() << "\n";
618  }
619  }
620 
621  remove_duplicates(outer_rings);
622  if (debug()) {
623  std::cerr << " after remove duplicates:\n";
624  for (const auto& o : outer_rings) {
625  std::cerr << " y=" << o.y() << " " << o.ring() << "\n";
626  }
627  }
628 
629  assert(!outer_rings.empty());
630  return outer_rings.front().ring_ptr();
631  }
632  }
633 
634  bool is_split_location(const osmium::Location& location) const noexcept {
635  return std::find(m_split_locations.cbegin(), m_split_locations.cend(), location) != m_split_locations.cend();
636  }
637 
638  uint32_t add_new_ring(slocation& node) {
639  detail::NodeRefSegment* segment = &m_segment_list[node.item];
640  assert(!segment->is_done());
641 
642  if (debug()) {
643  std::cerr << " Starting new ring at location " << node.location(m_segment_list) << " with segment " << *segment << "\n";
644  }
645 
646  if (node.reverse) {
647  segment->reverse();
648  }
649 
650  detail::ProtoRing* outer_ring = nullptr;
651 
652  if (segment != &m_segment_list.front()) {
653  outer_ring = find_enclosing_ring(segment);
654  }
655  segment->mark_direction_done();
656 
657  m_rings.emplace_back(segment);
658  detail::ProtoRing* ring = &m_rings.back();
659  if (outer_ring) {
660  if (debug()) {
661  std::cerr << " This is an inner ring. Outer ring is " << *outer_ring << "\n";
662  }
663  outer_ring->add_inner_ring(ring);
664  ring->set_outer_ring(outer_ring);
665  } else if (debug()) {
666  std::cerr << " This is an outer ring\n";
667  }
668 
669  const osmium::Location& first_location = node.location(m_segment_list);
670  osmium::Location last_location = segment->stop().location();
671 
672  uint32_t nodes = 1;
673  while (first_location != last_location) {
674  ++nodes;
675  detail::NodeRefSegment* next_segment = get_next_segment(last_location);
676  next_segment->mark_direction_done();
677  if (next_segment->start().location() != last_location) {
678  next_segment->reverse();
679  }
680  ring->add_segment_back(next_segment);
681  if (debug()) {
682  std::cerr << " Next segment is " << *next_segment << "\n";
683  }
684  last_location = next_segment->stop().location();
685  }
686 
687  ring->fix_direction();
688 
689  if (debug()) {
690  std::cerr << " Completed ring: " << *ring << "\n";
691  }
692 
693  return nodes;
694  }
695 
696  uint32_t add_new_ring_complex(slocation& node) {
697  detail::NodeRefSegment* segment = &m_segment_list[node.item];
698  assert(!segment->is_done());
699 
700  if (debug()) {
701  std::cerr << " Starting new ring at location " << node.location(m_segment_list) << " with segment " << *segment << "\n";
702  }
703 
704  if (node.reverse) {
705  segment->reverse();
706  }
707 
708  m_rings.emplace_back(segment);
709  detail::ProtoRing* ring = &m_rings.back();
710 
711  const osmium::Location& first_location = node.location(m_segment_list);
712  osmium::Location last_location = segment->stop().location();
713 
714  uint32_t nodes = 1;
715  while (first_location != last_location && !is_split_location(last_location)) {
716  ++nodes;
717  detail::NodeRefSegment* next_segment = get_next_segment(last_location);
718  if (next_segment->start().location() != last_location) {
719  next_segment->reverse();
720  }
721  ring->add_segment_back(next_segment);
722  if (debug()) {
723  std::cerr << " Next segment is " << *next_segment << "\n";
724  }
725  last_location = next_segment->stop().location();
726  }
727 
728  if (debug()) {
729  if (first_location == last_location) {
730  std::cerr << " Completed ring: " << *ring << "\n";
731  } else {
732  std::cerr << " Completed partial ring: " << *ring << "\n";
733  }
734  }
735 
736  return nodes;
737  }
738 
740  m_locations.reserve(m_segment_list.size() * 2);
741 
742  for (uint32_t n = 0; n < m_segment_list.size(); ++n) {
743  m_locations.emplace_back(n, false);
744  m_locations.emplace_back(n, true);
745  }
746 
747  std::stable_sort(m_locations.begin(), m_locations.end(), [this](const slocation& lhs, const slocation& rhs) {
748  return lhs.location(m_segment_list) < rhs.location(m_segment_list);
749  });
750  }
751 
752  void find_inner_outer_complex(detail::ProtoRing* ring) {
753  detail::ProtoRing* outer_ring = find_enclosing_ring(ring->min_segment());
754  if (outer_ring) {
755  outer_ring->add_inner_ring(ring);
756  ring->set_outer_ring(outer_ring);
757  }
758  ring->fix_direction();
759  ring->mark_direction_done();
760  }
761 
763  if (debug()) {
764  std::cerr << " Finding inner/outer rings\n";
765  }
766  std::vector<detail::ProtoRing*> rings;
767  rings.reserve(m_rings.size());
768  for (auto& ring : m_rings) {
769  if (ring.closed()) {
770  rings.push_back(&ring);
771  }
772  }
773 
774  if (rings.empty()) {
775  return;
776  }
777 
778  std::sort(rings.begin(), rings.end(), [](detail::ProtoRing* a, detail::ProtoRing* b) {
779  return a->min_segment() < b->min_segment();
780  });
781 
782  rings.front()->fix_direction();
783  rings.front()->mark_direction_done();
784  if (debug()) {
785  std::cerr << " First ring is outer: " << *rings.front() << "\n";
786  }
787  for (auto it = std::next(rings.begin()); it != rings.end(); ++it) {
788  if (debug()) {
789  std::cerr << " Checking (at min segment " << *((*it)->min_segment()) << ") ring " << **it << "\n";
790  }
791  find_inner_outer_complex(*it);
792  if (debug()) {
793  std::cerr << " Ring is " << ((*it)->is_outer() ? "OUTER: " : "INNER: ") << **it << "\n";
794  }
795  }
796  }
797 
804  osmium::Location previous_location;
805  for (auto it = m_locations.cbegin(); it != m_locations.cend(); ++it) {
806  const osmium::NodeRef& nr = it->node_ref(m_segment_list);
807  const osmium::Location& loc = nr.location();
808  if (std::next(it) == m_locations.cend() || loc != std::next(it)->location(m_segment_list)) {
809  if (debug()) {
810  std::cerr << " Found open ring at " << nr << "\n";
811  }
812  if (m_config.problem_reporter) {
813  const auto& segment = m_segment_list[it->item];
814  m_config.problem_reporter->report_ring_not_closed(nr, segment.way());
815  }
816  ++m_stats.open_rings;
817  } else {
818  if (loc == previous_location && (m_split_locations.empty() || m_split_locations.back() != previous_location )) {
819  m_split_locations.push_back(previous_location);
820  }
821  ++it;
822  if (it == m_locations.end()) {
823  break;
824  }
825  }
826  previous_location = loc;
827  }
828  return m_stats.open_rings == 0;
829  }
830 
832  auto count_remaining = m_segment_list.size();
833  for (slocation& sl : m_locations) {
834  const detail::NodeRefSegment& segment = m_segment_list[sl.item];
835  if (!segment.is_done()) {
836  count_remaining -= add_new_ring(sl);
837  if (count_remaining == 0) {
838  return;
839  }
840  }
841  }
842  }
843 
844  std::vector<location_to_ring_map> create_location_to_ring_map(open_ring_its_type& open_ring_its) {
845  std::vector<location_to_ring_map> xrings;
846  xrings.reserve(open_ring_its.size() * 2);
847 
848  for (auto it = open_ring_its.begin(); it != open_ring_its.end(); ++it) {
849  if (debug()) {
850  std::cerr << " Ring: " << **it << "\n";
851  }
852  xrings.emplace_back((*it)->get_node_ref_start().location(), it, true);
853  xrings.emplace_back((*it)->get_node_ref_stop().location(), it, false);
854  }
855 
856  std::sort(xrings.begin(), xrings.end());
857 
858  return xrings;
859  }
860 
862  auto& r1 = *m1.ring_it;
863  auto& r2 = *m2.ring_it;
864 
865  if (r1->get_node_ref_stop().location() == r2->get_node_ref_start().location()) {
866  r1->join_forward(*r2);
867  } else if (r1->get_node_ref_stop().location() == r2->get_node_ref_stop().location()) {
868  r1->join_backward(*r2);
869  } else if (r1->get_node_ref_start().location() == r2->get_node_ref_start().location()) {
870  r1->reverse();
871  r1->join_forward(*r2);
872  } else if (r1->get_node_ref_start().location() == r2->get_node_ref_stop().location()) {
873  r1->reverse();
874  r1->join_backward(*r2);
875  } else {
876  assert(false);
877  }
878 
879  m_rings.erase(r2);
880  open_ring_its.remove(r2);
881 
882  if (r1->closed()) {
883  open_ring_its.remove(r1);
884  }
885  }
886 
887  bool try_to_merge(open_ring_its_type& open_ring_its) {
888  if (open_ring_its.empty()) {
889  return false;
890  }
891 
892  if (debug()) {
893  std::cerr << " Trying to merge " << open_ring_its.size() << " open rings\n";
894  }
895 
896  std::vector<location_to_ring_map> xrings = create_location_to_ring_map(open_ring_its);
897 
898  auto it = xrings.cbegin();
899  while (it != xrings.cend()) {
900  it = std::adjacent_find(it, xrings.cend());
901  if (it == xrings.cend()) {
902  return false;
903  }
904  auto after = std::next(it, 2);
905  if (after == xrings.cend() || after->location != it->location) {
906  if (debug()) {
907  std::cerr << " Merging two rings\n";
908  }
909  merge_two_rings(open_ring_its, *it, *std::next(it));
910  return true;
911  }
912  while (it != xrings.cend() && it->location == after->location) {
913  ++it;
914  }
915  }
916 
917  return false;
918  }
919 
920  bool there_are_open_rings() const noexcept {
921  return std::any_of(m_rings.cbegin(), m_rings.cend(), [](const detail::ProtoRing& ring){
922  return !ring.closed();
923  });
924  }
925 
926  struct candidate {
927  int64_t sum;
928  std::vector<std::pair<location_to_ring_map, bool>> rings;
931 
932  explicit candidate(location_to_ring_map& ring, bool reverse) :
933  sum(ring.ring().sum()),
934  rings(),
935  start_location(ring.ring().get_node_ref_start().location()),
936  stop_location(ring.ring().get_node_ref_stop().location()) {
937  rings.emplace_back(ring, reverse);
938  }
939 
940  bool closed() const noexcept {
941  return start_location == stop_location;
942  }
943 
944  };
945 
946  void find_candidates(std::vector<candidate>& candidates, std::unordered_set<osmium::Location>& loc_done, const std::vector<location_to_ring_map>& xrings, candidate& cand) {
947  if (debug()) {
948  std::cerr << " find_candidates sum=" << cand.sum << " start=" << cand.start_location << " stop=" << cand.stop_location << "\n";
949  for (const auto& ring : cand.rings) {
950  std::cerr << " " << ring.first.ring() << (ring.second ? " reverse" : "") << "\n";
951  }
952  }
953 
954  const auto connections = make_range(std::equal_range(xrings.cbegin(),
955  xrings.cend(),
957 
958  assert(connections.begin() != connections.end());
959 
960  assert(!cand.rings.empty());
961  const detail::ProtoRing* ring_leading_here = &cand.rings.back().first.ring();
962  for (const location_to_ring_map& m : connections) {
963  const detail::ProtoRing& ring = m.ring();
964 
965  if (&ring != ring_leading_here) {
966  if (debug()) {
967  std::cerr << " next possible connection: " << ring << (m.start ? "" : " reverse") << "\n";
968  }
969 
970  candidate c = cand;
971  if (m.start) {
972  c.rings.emplace_back(m, false);
973  c.stop_location = ring.get_node_ref_stop().location();
974  c.sum += ring.sum();
975  } else {
976  c.rings.emplace_back(m, true);
977  c.stop_location = ring.get_node_ref_start().location();
978  c.sum -= ring.sum();
979  }
980  if (c.closed()) {
981  if (debug()) {
982  std::cerr << " found candidate\n";
983  }
984  candidates.push_back(c);
985  } else if (loc_done.count(c.stop_location) == 0) {
986  if (debug()) {
987  std::cerr << " recurse...\n";
988  }
989  loc_done.insert(c.stop_location);
990  find_candidates(candidates, loc_done, xrings, c);
991  if (debug()) {
992  std::cerr << " ...back\n";
993  }
994  } else if (debug()) {
995  std::cerr << " loop found\n";
996  }
997  }
998  }
999  }
1000 
1010  assert(!open_ring_its.empty());
1011 
1012  if (debug()) {
1013  std::cerr << " Trying to merge " << open_ring_its.size() << " open rings\n";
1014  }
1015 
1016  std::vector<location_to_ring_map> xrings = create_location_to_ring_map(open_ring_its);
1017 
1018  const auto ring_min = std::min_element(xrings.begin(), xrings.end(), [](const location_to_ring_map& lhs, const location_to_ring_map& rhs) {
1019  return lhs.ring().min_segment() < rhs.ring().min_segment();
1020  });
1021 
1022  find_inner_outer_complex();
1023  detail::ProtoRing* outer_ring = find_enclosing_ring(ring_min->ring().min_segment());
1024  bool ring_min_is_outer = !outer_ring;
1025  if (debug()) {
1026  std::cerr << " Open ring is " << (ring_min_is_outer ? "outer" : "inner") << " ring\n";
1027  }
1028  for (auto& ring : m_rings) {
1029  ring.reset();
1030  }
1031 
1032  candidate cand{*ring_min, false};
1033 
1034  // Locations we have visited while finding candidates, used
1035  // to detect loops.
1036  std::unordered_set<osmium::Location> loc_done;
1037 
1038  loc_done.insert(cand.stop_location);
1039 
1040  std::vector<candidate> candidates;
1041  find_candidates(candidates, loc_done, xrings, cand);
1042 
1043  if (candidates.empty()) {
1044  if (debug()) {
1045  std::cerr << " Found no candidates\n";
1046  }
1047  if (!open_ring_its.empty()) {
1048  ++m_stats.open_rings;
1049  if (m_config.problem_reporter) {
1050  for (auto& it : open_ring_its) {
1051  m_config.problem_reporter->report_ring_not_closed(it->get_node_ref_start());
1052  m_config.problem_reporter->report_ring_not_closed(it->get_node_ref_stop());
1053  }
1054  }
1055  }
1056  return false;
1057  }
1058 
1059  if (debug()) {
1060  std::cerr << " Found candidates:\n";
1061  for (const auto& cand : candidates) {
1062  std::cerr << " sum=" << cand.sum << "\n";
1063  for (const auto& ring : cand.rings) {
1064  std::cerr << " " << ring.first.ring() << (ring.second ? " reverse" : "") << "\n";
1065  }
1066  }
1067  }
1068 
1069  // Find the candidate with the smallest/largest area
1070  const auto chosen_cand = ring_min_is_outer ?
1071  std::min_element(candidates.cbegin(), candidates.cend(), [](const candidate& lhs, const candidate& rhs) {
1072  return std::abs(lhs.sum) < std::abs(rhs.sum);
1073  }) :
1074  std::max_element(candidates.cbegin(), candidates.cend(), [](const candidate& lhs, const candidate& rhs) {
1075  return std::abs(lhs.sum) < std::abs(rhs.sum);
1076  });
1077 
1078  if (debug()) {
1079  std::cerr << " Decided on: sum=" << chosen_cand->sum << "\n";
1080  for (const auto& ring : chosen_cand->rings) {
1081  std::cerr << " " << ring.first.ring() << (ring.second ? " reverse" : "") << "\n";
1082  }
1083  }
1084 
1085  // Join all (open) rings in the candidate to get one closed ring.
1086  assert(chosen_cand->rings.size() > 1);
1087  const auto& first_ring = chosen_cand->rings.front().first;
1088  for (auto it = chosen_cand->rings.begin() + 1; it != chosen_cand->rings.end(); ++it) {
1089  merge_two_rings(open_ring_its, first_ring, it->first);
1090  }
1091 
1092  if (debug()) {
1093  std::cerr << " Merged to " << first_ring.ring() << "\n";
1094  }
1095 
1096  return true;
1097  }
1098 
1100  // First create all the (partial) rings starting at the split locations
1101  auto count_remaining = m_segment_list.size();
1102  for (const osmium::Location& location : m_split_locations) {
1103  const auto locs = make_range(std::equal_range(m_locations.begin(),
1104  m_locations.end(),
1105  slocation{},
1106  [this, &location](const slocation& lhs, const slocation& rhs) {
1107  return lhs.location(m_segment_list, location) < rhs.location(m_segment_list, location);
1108  }));
1109  for (auto& loc : locs) {
1110  if (!m_segment_list[loc.item].is_done()) {
1111  count_remaining -= add_new_ring_complex(loc);
1112  if (count_remaining == 0) {
1113  break;
1114  }
1115  }
1116  }
1117  }
1118 
1119  // Now find all the rest of the rings (ie not starting at split locations)
1120  if (count_remaining > 0) {
1121  for (slocation& sl : m_locations) {
1122  const detail::NodeRefSegment& segment = m_segment_list[sl.item];
1123  if (!segment.is_done()) {
1124  count_remaining -= add_new_ring_complex(sl);
1125  if (count_remaining == 0) {
1126  break;
1127  }
1128  }
1129  }
1130  }
1131 
1132  // Now all segments are in exactly one (partial) ring.
1133 
1134  // If there are open rings, try to join them to create closed
1135  // rings.
1136  if (there_are_open_rings()) {
1137  ++m_stats.area_really_complex_case;
1138 
1139  open_ring_its_type open_ring_its;
1140  for (auto it = m_rings.begin(); it != m_rings.end(); ++it) {
1141  if (!it->closed()) {
1142  open_ring_its.push_back(it);
1143  }
1144  }
1145 
1146  while (!open_ring_its.empty()) {
1147  if (debug()) {
1148  std::cerr << " There are " << open_ring_its.size() << " open rings\n";
1149  }
1150  while (try_to_merge(open_ring_its));
1151 
1152  if (!open_ring_its.empty()) {
1153  if (debug()) {
1154  std::cerr << " After joining obvious cases there are still " << open_ring_its.size() << " open rings\n";
1155  }
1156  if (!join_connected_rings(open_ring_its)) {
1157  return false;
1158  }
1159  }
1160  }
1161 
1162  if (debug()) {
1163  std::cerr << " Joined all open rings\n";
1164  }
1165  }
1166 
1167  // Now all rings are complete.
1168 
1169  find_inner_outer_complex();
1170 
1171  return true;
1172  }
1173 
1179  std::unordered_set<const osmium::Way*> ways_in_segments;
1180 
1181  for (const auto& segment : m_segment_list) {
1182  ways_in_segments.insert(segment.way());
1183  }
1184 
1185  return ways_in_segments.size() < m_num_members;
1186  }
1187 
1191  bool create_rings() {
1192  m_stats.nodes += m_segment_list.size();
1193 
1194  // Sort the list of segments (from left to right and bottom
1195  // to top).
1196  osmium::Timer timer_sort;
1197  m_segment_list.sort();
1198  timer_sort.stop();
1199 
1200  // Remove duplicate segments. Removal is in pairs, so if there
1201  // are two identical segments, they will both be removed. If
1202  // there are three, two will be removed and one remains.
1203  osmium::Timer timer_dupl;
1204  m_stats.duplicate_segments = m_segment_list.erase_duplicate_segments(m_config.problem_reporter);
1205  timer_dupl.stop();
1206 
1207  // If there are no segments left at this point, this isn't
1208  // a valid area.
1209  if (m_segment_list.empty()) {
1210  if (debug()) {
1211  std::cerr << " No segments left\n";
1212  }
1213  return false;
1214  }
1215 
1216  // If one or more complete ways was removed because of
1217  // duplicate segments, this isn't a valid area.
1218  if (ways_were_lost()) {
1219  if (debug()) {
1220  std::cerr << " Complete ways removed because of duplicate segments\n";
1221  }
1222  return false;
1223  }
1224 
1225  if (m_config.debug_level >= 3) {
1226  std::cerr << "Sorted de-duplicated segment list:\n";
1227  for (const auto& s : m_segment_list) {
1228  std::cerr << " " << s << "\n";
1229  }
1230  }
1231 
1232  // Now we look for segments crossing each other. If there are
1233  // any, the multipolygon is invalid.
1234  // In the future this could be improved by trying to fix those
1235  // cases.
1236  osmium::Timer timer_intersection;
1237  m_stats.intersections = m_segment_list.find_intersections(m_config.problem_reporter);
1238  timer_intersection.stop();
1239 
1240  if (m_stats.intersections) {
1241  return false;
1242  }
1243 
1244  // This creates an ordered list of locations of both endpoints
1245  // of all segments with pointers back to the segments. We will
1246  // use this list later to quickly find which segment(s) fits
1247  // onto a known segment.
1248  osmium::Timer timer_locations_list;
1249  create_locations_list();
1250  timer_locations_list.stop();
1251 
1252  // Find all locations where more than two segments start or
1253  // end. We call those "split" locations. If there are any
1254  // "spike" segments found while doing this, we know the area
1255  // geometry isn't valid and return.
1256  osmium::Timer timer_split;
1257  if (!find_split_locations()) {
1258  return false;
1259  }
1260  timer_split.stop();
1261 
1262  // Now report all split locations to the problem reporter.
1263  m_stats.touching_rings += m_split_locations.size();
1264  if (!m_split_locations.empty()) {
1265  if (debug()) {
1266  std::cerr << " Found split locations:\n";
1267  }
1268  for (const auto& location : m_split_locations) {
1269  if (m_config.problem_reporter) {
1270  auto it = std::lower_bound(m_locations.cbegin(), m_locations.cend(), slocation{}, [this, &location](const slocation& lhs, const slocation& rhs) {
1271  return lhs.location(m_segment_list, location) < rhs.location(m_segment_list, location);
1272  });
1273  assert(it != m_locations.cend());
1274  const osmium::object_id_type id = it->node_ref(m_segment_list).ref();
1275  m_config.problem_reporter->report_touching_ring(id, location);
1276  }
1277  if (debug()) {
1278  std::cerr << " " << location << "\n";
1279  }
1280  }
1281  }
1282 
1283  // From here on we use two different algorithms depending on
1284  // whether there were any split locations or not. If there
1285  // are no splits, we use the faster "simple algorithm", if
1286  // there are, we use the slower "complex algorithm".
1287  osmium::Timer timer_simple_case;
1288  osmium::Timer timer_complex_case;
1289  if (m_split_locations.empty()) {
1290  if (debug()) {
1291  std::cerr << " No split locations -> using simple algorithm\n";
1292  }
1293  ++m_stats.area_simple_case;
1294 
1295  timer_simple_case.start();
1296  create_rings_simple_case();
1297  timer_simple_case.stop();
1298  } else {
1299  if (debug()) {
1300  std::cerr << " Found split locations -> using complex algorithm\n";
1301  }
1302  ++m_stats.area_touching_rings_case;
1303 
1304  timer_complex_case.start();
1305  if (!create_rings_complex_case()) {
1306  return false;
1307  }
1308  timer_complex_case.stop();
1309  }
1310 
1311  // If the assembler was so configured, now check whether the
1312  // member roles are correctly tagged.
1313  if (m_config.check_roles && m_stats.from_relations) {
1314  osmium::Timer timer_roles;
1315  check_inner_outer_roles();
1316  timer_roles.stop();
1317  }
1318 
1319  m_stats.outer_rings = std::count_if(m_rings.cbegin(), m_rings.cend(), [](const detail::ProtoRing& ring){
1320  return ring.is_outer();
1321  });
1322  m_stats.inner_rings = m_rings.size() - m_stats.outer_rings;
1323 
1324 #ifdef OSMIUM_WITH_TIMER
1325  std::cout << m_stats.nodes << ' ' << m_stats.outer_rings << ' ' << m_stats.inner_rings <<
1326  ' ' << timer_sort.elapsed_microseconds() <<
1327  ' ' << timer_dupl.elapsed_microseconds() <<
1328  ' ' << timer_intersection.elapsed_microseconds() <<
1329  ' ' << timer_locations_list.elapsed_microseconds() <<
1330  ' ' << timer_split.elapsed_microseconds();
1331 
1332  if (m_split_locations.empty()) {
1333  std::cout << ' ' << timer_simple_case.elapsed_microseconds() <<
1334  " 0";
1335  } else {
1336  std::cout << " 0" <<
1337  ' ' << timer_complex_case.elapsed_microseconds();
1338  }
1339 
1340  std::cout <<
1341 # ifdef OSMIUM_AREA_CHECK_INNER_OUTER_ROLES
1342  ' ' << timer_roles.elapsed_microseconds() <<
1343 # else
1344  " 0" <<
1345 # endif
1346  '\n';
1347 #endif
1348 
1349  return true;
1350  }
1351 
1352 #ifdef OSMIUM_WITH_TIMER
1353  static bool print_header() {
1354  std::cout << "nodes outer_rings inner_rings sort dupl intersection locations split simple_case complex_case roles_check\n";
1355  return true;
1356  }
1357 
1358  static bool init_header() {
1359  static bool printed_print_header = print_header();
1360  return printed_print_header;
1361  }
1362 #endif
1363 
1364  bool create_area(osmium::memory::Buffer& out_buffer, const osmium::Way& way) {
1365  osmium::builder::AreaBuilder builder{out_buffer};
1366  builder.initialize_from_object(way);
1367 
1368  const bool area_okay = create_rings();
1369  if (area_okay || m_config.create_empty_areas) {
1370  add_tags_to_area(builder, way);
1371  }
1372  if (area_okay) {
1373  add_rings_to_area(builder);
1374  }
1375 
1376  if (report_ways()) {
1377  m_config.problem_reporter->report_way(way);
1378  }
1379 
1380  return area_okay || m_config.create_empty_areas;
1381  }
1382 
1383  bool create_area(osmium::memory::Buffer& out_buffer, const osmium::Relation& relation, const std::vector<const osmium::Way*>& members) {
1384  m_num_members = members.size();
1385  osmium::builder::AreaBuilder builder{out_buffer};
1386  builder.initialize_from_object(relation);
1387 
1388  const bool area_okay = create_rings();
1389  if (area_okay || m_config.create_empty_areas) {
1390  add_tags_to_area(builder, relation);
1391  }
1392  if (area_okay) {
1393  add_rings_to_area(builder);
1394  }
1395 
1396  if (report_ways()) {
1397  for (const osmium::Way* way : members) {
1398  m_config.problem_reporter->report_way(*way);
1399  }
1400  }
1401 
1402  return area_okay || m_config.create_empty_areas;
1403  }
1404 
1405  public:
1406 
1408 
1409  explicit Assembler(const config_type& config) :
1410  m_config(config),
1411  m_segment_list(config.debug_level > 1) {
1412 #ifdef OSMIUM_WITH_TIMER
1413  init_header();
1414 #endif
1415  }
1416 
1417  ~Assembler() noexcept = default;
1418 
1423  void operator()(const osmium::Way& way, osmium::memory::Buffer& out_buffer) {
1424  if (!m_config.create_way_polygons) {
1425  return;
1426  }
1427 
1428  if (way.tags().has_tag("area", "no")) {
1429  return;
1430  }
1431 
1432  if (m_config.problem_reporter) {
1434  m_config.problem_reporter->set_nodes(way.nodes().size());
1435  }
1436 
1437  // Ignore (but count) ways without segments.
1438  if (way.nodes().size() < 2) {
1439  ++m_stats.short_ways;
1440  return;
1441  }
1442 
1443  if (!way.ends_have_same_id()) {
1444  ++m_stats.duplicate_nodes;
1445  if (m_config.problem_reporter) {
1446  m_config.problem_reporter->report_duplicate_node(way.nodes().front().ref(), way.nodes().back().ref(), way.nodes().front().location());
1447  }
1448  }
1449 
1450  ++m_stats.from_ways;
1451  m_stats.duplicate_nodes += m_segment_list.extract_segments_from_way(m_config.problem_reporter, way);
1452 
1453  if (m_config.debug_level > 0) {
1454  std::cerr << "\nAssembling way " << way.id() << " containing " << m_segment_list.size() << " nodes\n";
1455  }
1456 
1457  // Now create the Area object and add the attributes and tags
1458  // from the way.
1459  if (create_area(out_buffer, way)) {
1460  out_buffer.commit();
1461  } else {
1462  out_buffer.rollback();
1463  }
1464 
1465  if (debug()) {
1466  std::cerr << "Done: " << m_stats << "\n";
1467  }
1468  }
1469 
1480  OSMIUM_DEPRECATED void operator()(const osmium::Relation& relation, const std::vector<size_t>& members, const osmium::memory::Buffer& in_buffer, osmium::memory::Buffer& out_buffer) {
1481  std::vector<const osmium::Way*> ways;
1482  for (size_t offset : members) {
1483  const osmium::Way& way = in_buffer.get<const osmium::Way>(offset);
1484  ways.push_back(&way);
1485  }
1486  operator()(relation, ways, out_buffer);
1487  }
1488 
1493  void operator()(const osmium::Relation& relation, const std::vector<const osmium::Way*>& members, osmium::memory::Buffer& out_buffer) {
1494  assert(relation.members().size() >= members.size());
1495 
1496  if (m_config.problem_reporter) {
1498  }
1499 
1500  if (relation.members().empty()) {
1501  ++m_stats.no_way_in_mp_relation;
1502  return;
1503  }
1504 
1505  ++m_stats.from_relations;
1506  m_stats.duplicate_nodes += m_segment_list.extract_segments_from_ways(m_config.problem_reporter, relation, members);
1507  m_stats.member_ways = members.size();
1508 
1509  if (m_stats.member_ways == 1) {
1510  ++m_stats.single_way_in_mp_relation;
1511  }
1512 
1513  if (m_config.debug_level > 0) {
1514  std::cerr << "\nAssembling relation " << relation.id() << " containing " << members.size() << " way members with " << m_segment_list.size() << " nodes\n";
1515  }
1516 
1517  const size_t area_offset = out_buffer.committed();
1518 
1519  // Now create the Area object and add the attributes and tags
1520  // from the relation.
1521  if (create_area(out_buffer, relation, members)) {
1522  if ((m_config.create_new_style_polygons && m_stats.no_tags_on_relation == 0) ||
1523  (m_config.create_old_style_polygons && m_stats.no_tags_on_relation != 0)) {
1524  out_buffer.commit();
1525  } else {
1526  out_buffer.rollback();
1527  }
1528  } else {
1529  out_buffer.rollback();
1530  }
1531 
1532  const osmium::TagList& area_tags = out_buffer.get<osmium::Area>(area_offset).tags(); // tags of the area we just built
1533 
1534  // Find all closed ways that are inner rings and check their
1535  // tags. If they are not the same as the tags of the area we
1536  // just built, add them to a list and later build areas for
1537  // them, too.
1538  std::vector<const osmium::Way*> ways_that_should_be_areas;
1539  if (m_stats.wrong_role == 0) {
1540  detail::for_each_member(relation, members, [this, &ways_that_should_be_areas, &area_tags](const osmium::RelationMember& member, const osmium::Way& way) {
1541  if (!std::strcmp(member.role(), "inner")) {
1542  if (!way.nodes().empty() && way.is_closed() && way.tags().size() > 0) {
1543  const auto d = std::count_if(way.tags().cbegin(), way.tags().cend(), filter());
1544  if (d > 0) {
1545  osmium::tags::KeyFilter::iterator way_fi_begin(filter(), way.tags().cbegin(), way.tags().cend());
1546  osmium::tags::KeyFilter::iterator way_fi_end(filter(), way.tags().cend(), way.tags().cend());
1547  osmium::tags::KeyFilter::iterator area_fi_begin(filter(), area_tags.cbegin(), area_tags.cend());
1548  osmium::tags::KeyFilter::iterator area_fi_end(filter(), area_tags.cend(), area_tags.cend());
1549 
1550  if (!std::equal(way_fi_begin, way_fi_end, area_fi_begin) || d != std::distance(area_fi_begin, area_fi_end)) {
1551  ways_that_should_be_areas.push_back(&way);
1552  } else {
1553  ++m_stats.inner_with_same_tags;
1554  if (m_config.problem_reporter) {
1556  }
1557  }
1558  }
1559  }
1560  }
1561  });
1562  }
1563 
1564  if (debug()) {
1565  std::cerr << "Done: " << m_stats << "\n";
1566  }
1567 
1568  // Now build areas for all ways found in the last step.
1569  for (const osmium::Way* way : ways_that_should_be_areas) {
1570  Assembler assembler(m_config);
1571  assembler(*way, out_buffer);
1572  }
1573  }
1574 
1579  const osmium::area::area_stats& stats() const noexcept {
1580  return m_stats;
1581  }
1582 
1583  }; // class Assembler
1584 
1585  } // namespace area
1586 
1587 } // namespace osmium
1588 
1589 #endif // OSMIUM_AREA_ASSEMBLER_HPP
area_stats m_stats
Definition: assembler.hpp:267
void operator()(const osmium::Relation &relation, const std::vector< const osmium::Way *> &members, osmium::memory::Buffer &out_buffer)
Definition: assembler.hpp:1493
WayNodeList & nodes()
Definition: way.hpp:89
detail::location_to_ring_map location_to_ring_map
Definition: assembler.hpp:213
Definition: tag.hpp:48
osmium::area::ProblemReporter * problem_reporter
Definition: assembler.hpp:87
#define OSMIUM_DEPRECATED
Definition: compatibility.hpp:50
Definition: filter.hpp:78
void add_item(const osmium::memory::Item &item)
Definition: builder.hpp:217
bool operator==(const rings_stack_element &rhs) const noexcept
Definition: assembler.hpp:499
const TagList & tags() const
Get the list of tags for this object.
Definition: object.hpp:325
Definition: tag.hpp:107
const osmium::NodeRef & node_ref(const detail::SegmentList &segment_list) const noexcept
Definition: assembler.hpp:237
rings_stack_element(int32_t y, detail::ProtoRing *ring_ptr)
Definition: assembler.hpp:482
iterator_range< It > make_range(P &&p)
Definition: iterator.hpp:77
int64_t sum
Definition: assembler.hpp:927
RelationMemberList & members()
Definition: relation.hpp:185
virtual void report_way_in_multiple_rings(const osmium::Way &way)
Definition: problem_reporter.hpp:180
uint64_t member_ways
Number of ways in the area.
Definition: stats.hpp:60
uint64_t area_really_complex_case
Most difficult case with rings touching in multiple points.
Definition: stats.hpp:50
virtual void report_duplicate_node(osmium::object_id_type node_id1, osmium::object_id_type node_id2, osmium::Location location)
Definition: problem_reporter.hpp:106
static void copy_tags_without_type(osmium::builder::AreaBuilder &builder, const osmium::TagList &tags)
Definition: assembler.hpp:335
uint64_t wrong_role
Member has wrong role (not "outer", "inner", or empty)
Definition: stats.hpp:70
virtual void report_role_should_be_inner(osmium::object_id_type way_id, osmium::Location seg_start, osmium::Location seg_end)
Definition: problem_reporter.hpp:172
constexpr bool operator==(const Box &lhs, const Box &rhs) noexcept
Definition: box.hpp:221
void operator()(const osmium::Way &way, osmium::memory::Buffer &out_buffer)
Definition: assembler.hpp:1423
Definition: relation.hpp:168
virtual void report_way(const osmium::Way &way)
Definition: problem_reporter.hpp:198
bool report_ways() const noexcept
Definition: assembler.hpp:276
AssemblerConfig() noexcept=default
void start()
Definition: timer.hpp:82
void add_rings_to_area(osmium::builder::AreaBuilder &builder) const
Definition: assembler.hpp:400
static const MPFilter & filter() noexcept
Definition: assembler.hpp:330
uint64_t no_way_in_mp_relation
Multipolygon relation with no way members.
Definition: stats.hpp:62
Definition: area.hpp:126
Definition: assembler.hpp:82
const_iterator cbegin() const noexcept
Definition: collection.hpp:164
bool ways_were_lost()
Definition: assembler.hpp:1178
Definition: entity_bits.hpp:72
void add_tags_to_area(osmium::builder::AreaBuilder &builder, const osmium::Relation &relation)
Definition: assembler.hpp:344
size_type size() const noexcept
Definition: collection.hpp:152
uint64_t outer_rings
Number of outer rings in the area.
Definition: stats.hpp:65
candidate(location_to_ring_map &ring, bool reverse)
Definition: assembler.hpp:932
bool has_tag(const char *key, const char *value) const noexcept
Definition: tag.hpp:159
double distance(const osmium::geom::Coordinates &c1, const osmium::geom::Coordinates &c2)
Definition: haversine.hpp:66
bool create_rings_complex_case()
Definition: assembler.hpp:1099
bool is_closed() const
Definition: way.hpp:112
void remove_duplicates(rings_stack &outer_rings)
Definition: assembler.hpp:511
Definition: way.hpp:72
std::list< detail::ProtoRing > m_rings
Definition: assembler.hpp:258
osmium::Location stop_location
Definition: assembler.hpp:930
std::vector< location_to_ring_map > create_location_to_ring_map(open_ring_its_type &open_ring_its)
Definition: assembler.hpp:844
slocation() noexcept
Definition: assembler.hpp:222
bool create_way_polygons
Definition: assembler.hpp:137
bool closed() const noexcept
Definition: assembler.hpp:940
bool create_area(osmium::memory::Buffer &out_buffer, const osmium::Way &way)
Definition: assembler.hpp:1364
const AssemblerConfig & m_config
Definition: assembler.hpp:252
uint64_t short_ways
Number of ways with less than two nodes.
Definition: stats.hpp:66
const detail::ProtoRing & ring() const noexcept
Definition: assembler.hpp:491
virtual void report_role_should_be_outer(osmium::object_id_type way_id, osmium::Location seg_start, osmium::Location seg_end)
Definition: problem_reporter.hpp:162
Filter< std::string > KeyFilter
Definition: filter.hpp:156
uint64_t duplicate_segments
Segments duplicated (going back and forth)
Definition: stats.hpp:54
std::vector< slocation > m_locations
Definition: assembler.hpp:261
osmium::area::detail::SegmentList m_segment_list
Definition: assembler.hpp:255
constexpr osmium::object_id_type ref() const noexcept
Definition: node_ref.hpp:65
bool empty() const noexcept
Definition: node_ref_list.hpp:74
bool operator<(const Changeset &lhs, const Changeset &rhs)
Definition: changeset.hpp:447
Definition: relation.hpp:57
void find_inner_outer_complex()
Definition: assembler.hpp:762
bool check_roles
Definition: assembler.hpp:104
Namespace for everything in the Osmium library.
Definition: assembler.hpp:73
void check_inner_outer_roles()
Definition: assembler.hpp:411
uint32_t item
Definition: assembler.hpp:219
Definition: attr.hpp:333
bool is_split_location(const osmium::Location &location) const noexcept
Definition: assembler.hpp:634
uint64_t from_relations
Area created from multipolygon relation.
Definition: stats.hpp:55
uint64_t area_touching_rings_case
More difficult case with touching rings.
Definition: stats.hpp:52
Definition: assembler.hpp:215
uint64_t from_ways
Area created from way.
Definition: stats.hpp:56
OSMIUM_DEPRECATED void enable_debug_output(bool d=true)
Definition: assembler.hpp:163
const_iterator cend() const noexcept
Definition: collection.hpp:168
Definition: problem_reporter.hpp:60
bool create_new_style_polygons
Definition: assembler.hpp:122
slocation(uint32_t n, bool r=false) noexcept
Definition: assembler.hpp:227
bool join_connected_rings(open_ring_its_type &open_ring_its)
Definition: assembler.hpp:1009
bool empty() const noexcept
Definition: collection.hpp:143
void set_object(osmium::item_type object_type, osmium::object_id_type object_id) noexcept
Definition: problem_reporter.hpp:85
detail::NodeRefSegment * get_next_segment(const osmium::Location &location)
Definition: assembler.hpp:460
void create_rings_simple_case()
Definition: assembler.hpp:831
void find_candidates(std::vector< candidate > &candidates, std::unordered_set< osmium::Location > &loc_done, const std::vector< location_to_ring_map > &xrings, candidate &cand)
Definition: assembler.hpp:946
Definition: assembler.hpp:317
constexpr int32_t y() const noexcept
Definition: location.hpp:352
Definition: stats.hpp:49
int64_t object_id_type
Type for OSM object (node, way, or relation) IDs.
Definition: types.hpp:45
const osmium::area::area_stats & stats() const noexcept
Definition: assembler.hpp:1579
void merge_two_rings(open_ring_its_type &open_ring_its, const location_to_ring_map &m1, const location_to_ring_map &m2)
Definition: assembler.hpp:861
std::vector< std::pair< location_to_ring_map, bool > > rings
Definition: assembler.hpp:928
void create_locations_list()
Definition: assembler.hpp:739
bool keep_type_tag
Definition: assembler.hpp:144
int debug_level
Definition: assembler.hpp:94
uint32_t add_new_ring(slocation &node)
Definition: assembler.hpp:638
void set_nodes(size_t nodes) noexcept
Definition: problem_reporter.hpp:90
int32_t m_y
Definition: assembler.hpp:477
bool operator<(const rings_stack_element &rhs) const noexcept
Definition: assembler.hpp:503
virtual void report_touching_ring(osmium::object_id_type node_id, osmium::Location location)
Definition: problem_reporter.hpp:116
osmium::Location start_location
Definition: assembler.hpp:929
osmium::Location location(const detail::SegmentList &segment_list, const osmium::Location &default_location) const noexcept
Definition: assembler.hpp:242
uint64_t inner_with_same_tags
Number of inner ways with same tags as area.
Definition: stats.hpp:58
Assembler(const config_type &config)
Definition: assembler.hpp:1409
Definition: location.hpp:266
std::vector< rings_stack_element > rings_stack
Definition: assembler.hpp:509
uint64_t intersections
Number of intersections between segments.
Definition: stats.hpp:59
osmium::Location & location() noexcept
Definition: node_ref.hpp:79
detail::ProtoRing * m_ring_ptr
Definition: assembler.hpp:478
void stop()
Definition: timer.hpp:85
uint64_t inner_rings
Number of inner rings.
Definition: stats.hpp:57
Definition: assembler.hpp:926
void add_common_tags(osmium::builder::TagListBuilder &tl_builder, std::set< const osmium::Way *> &ways) const
Definition: assembler.hpp:294
virtual void report_ring_not_closed(const osmium::NodeRef &nr, const osmium::Way *way=nullptr)
Definition: problem_reporter.hpp:152
uint64_t ways_in_multiple_rings
Different segments of a way ended up in different rings.
Definition: stats.hpp:69
detail::open_ring_its_type open_ring_its_type
Definition: assembler.hpp:212
object_id_type id() const noexcept
Get ID of this object.
Definition: object.hpp:126
size_t committed() const noexcept
Definition: buffer.hpp:259
bool debug() const noexcept
Definition: assembler.hpp:272
bool ends_have_same_id() const
Definition: way.hpp:116
bool find_split_locations()
Definition: assembler.hpp:803
Definition: buffer.hpp:97
const char * role() const noexcept
Definition: relation.hpp:138
uint64_t open_rings
Number of open rings in the area.
Definition: stats.hpp:64
uint64_t no_tags_on_relation
No tags on relation (old-style multipolygon with tags on outer ways)
Definition: stats.hpp:61
void find_inner_outer_complex(detail::ProtoRing *ring)
Definition: assembler.hpp:752
static void build_ring_from_proto_ring(osmium::builder::AreaBuilder &builder, const detail::ProtoRing &ring)
Definition: assembler.hpp:388
Definition: timer.hpp:76
int32_t y() const noexcept
Definition: assembler.hpp:487
uint64_t nodes
Number of nodes in the area.
Definition: stats.hpp:63
osmium::Location location(const detail::SegmentList &segment_list) const noexcept
Definition: assembler.hpp:232
bool create_area(osmium::memory::Buffer &out_buffer, const osmium::Relation &relation, const std::vector< const osmium::Way *> &members)
Definition: assembler.hpp:1383
uint64_t single_way_in_mp_relation
Multipolygon relation containing a single way.
Definition: stats.hpp:67
bool create_rings()
Definition: assembler.hpp:1191
const NodeRef & front() const noexcept
Definition: node_ref_list.hpp:126
virtual void report_inner_with_same_tags(const osmium::Way &way)
Definition: problem_reporter.hpp:189
uint32_t add_new_ring_complex(slocation &node)
Definition: assembler.hpp:696
constexpr int32_t x() const noexcept
Definition: location.hpp:348
const NodeRef & back() const noexcept
Definition: node_ref_list.hpp:138
MPFilter()
Definition: assembler.hpp:319
Definition: node_ref.hpp:50
detail::ProtoRing * ring_ptr() noexcept
Definition: assembler.hpp:495
bool create_empty_areas
Definition: assembler.hpp:114
Definition: assembler.hpp:210
std::vector< Location > m_split_locations
Definition: assembler.hpp:264
void rollback()
Definition: buffer.hpp:370
T & get(const size_t offset) const
Definition: buffer.hpp:404
bool try_to_merge(open_ring_its_type &open_ring_its)
Definition: assembler.hpp:887
uint64_t area_simple_case
Simple case, no touching rings.
Definition: stats.hpp:51
bool there_are_open_rings() const noexcept
Definition: assembler.hpp:920
uint64_t duplicate_nodes
Consecutive identical nodes or consecutive nodes with same location.
Definition: stats.hpp:53
detail::ProtoRing * find_enclosing_ring(detail::NodeRefSegment *segment)
Definition: assembler.hpp:521
size_type size() const noexcept
Definition: node_ref_list.hpp:83
int64_t elapsed_microseconds() const
Definition: timer.hpp:88
uint32_t reverse
Definition: assembler.hpp:220
bool create_old_style_polygons
Definition: assembler.hpp:130
void add_tag(const char *key, const char *value)
Definition: osm_object_builder.hpp:95
boost::filter_iterator< filter_type, osmium::TagList::const_iterator > iterator
Definition: filter.hpp:113
uint64_t touching_rings
Rings touching in a node.
Definition: stats.hpp:68
OSMIUM_DEPRECATED void operator()(const osmium::Relation &relation, const std::vector< size_t > &members, const osmium::memory::Buffer &in_buffer, osmium::memory::Buffer &out_buffer)
Definition: assembler.hpp:1480
Definition: osm_object_builder.hpp:71
size_t commit()
Definition: buffer.hpp:354
void add_tags_to_area(osmium::builder::AreaBuilder &builder, const osmium::Way &way) const
Definition: assembler.hpp:290
Definition: osm_object_builder.hpp:528