Libosmium  2.11.4
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  double m_y;
478  detail::ProtoRing* m_ring_ptr;
479 
480  public:
481 
482  rings_stack_element(double y, detail::ProtoRing* ring_ptr) :
483  m_y(y),
484  m_ring_ptr(ring_ptr) {
485  }
486 
487  double 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 rings_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 double y = ay + (by - ay) * (lx - ax) / double(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  std::list<detail::ProtoRing>::iterator r1 = *m1.ring_it;
863  std::list<detail::ProtoRing>::iterator 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  open_ring_its.erase(std::find(open_ring_its.begin(), open_ring_its.end(), r2));
880  m_rings.erase(r2);
881 
882  if (r1->closed()) {
883  open_ring_its.erase(std::find(open_ring_its.begin(), open_ring_its.end(), 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  loc_done.erase(c.stop_location);
992  if (debug()) {
993  std::cerr << " ...back\n";
994  }
995  } else if (debug()) {
996  std::cerr << " loop found\n";
997  }
998  }
999  }
1000  }
1001 
1011  assert(!open_ring_its.empty());
1012 
1013  if (debug()) {
1014  std::cerr << " Trying to merge " << open_ring_its.size() << " open rings\n";
1015  }
1016 
1017  std::vector<location_to_ring_map> xrings = create_location_to_ring_map(open_ring_its);
1018 
1019  const auto ring_min = std::min_element(xrings.begin(), xrings.end(), [](const location_to_ring_map& lhs, const location_to_ring_map& rhs) {
1020  return lhs.ring().min_segment() < rhs.ring().min_segment();
1021  });
1022 
1023  find_inner_outer_complex();
1024  detail::ProtoRing* outer_ring = find_enclosing_ring(ring_min->ring().min_segment());
1025  bool ring_min_is_outer = !outer_ring;
1026  if (debug()) {
1027  std::cerr << " Open ring is " << (ring_min_is_outer ? "outer" : "inner") << " ring\n";
1028  }
1029  for (auto& ring : m_rings) {
1030  ring.reset();
1031  }
1032 
1033  candidate cand{*ring_min, false};
1034 
1035  // Locations we have visited while finding candidates, used
1036  // to detect loops.
1037  std::unordered_set<osmium::Location> loc_done;
1038 
1039  loc_done.insert(cand.stop_location);
1040 
1041  std::vector<candidate> candidates;
1042  find_candidates(candidates, loc_done, xrings, cand);
1043 
1044  if (candidates.empty()) {
1045  if (debug()) {
1046  std::cerr << " Found no candidates\n";
1047  }
1048  if (!open_ring_its.empty()) {
1049  ++m_stats.open_rings;
1050  if (m_config.problem_reporter) {
1051  for (auto& it : open_ring_its) {
1052  m_config.problem_reporter->report_ring_not_closed(it->get_node_ref_start());
1053  m_config.problem_reporter->report_ring_not_closed(it->get_node_ref_stop());
1054  }
1055  }
1056  }
1057  return false;
1058  }
1059 
1060  if (debug()) {
1061  std::cerr << " Found candidates:\n";
1062  for (const auto& cand : candidates) {
1063  std::cerr << " sum=" << cand.sum << "\n";
1064  for (const auto& ring : cand.rings) {
1065  std::cerr << " " << ring.first.ring() << (ring.second ? " reverse" : "") << "\n";
1066  }
1067  }
1068  }
1069 
1070  // Find the candidate with the smallest/largest area
1071  const auto chosen_cand = ring_min_is_outer ?
1072  std::min_element(candidates.cbegin(), candidates.cend(), [](const candidate& lhs, const candidate& rhs) {
1073  return std::abs(lhs.sum) < std::abs(rhs.sum);
1074  }) :
1075  std::max_element(candidates.cbegin(), candidates.cend(), [](const candidate& lhs, const candidate& rhs) {
1076  return std::abs(lhs.sum) < std::abs(rhs.sum);
1077  });
1078 
1079  if (debug()) {
1080  std::cerr << " Decided on: sum=" << chosen_cand->sum << "\n";
1081  for (const auto& ring : chosen_cand->rings) {
1082  std::cerr << " " << ring.first.ring() << (ring.second ? " reverse" : "") << "\n";
1083  }
1084  }
1085 
1086  // Join all (open) rings in the candidate to get one closed ring.
1087  assert(chosen_cand->rings.size() > 1);
1088  const auto& first_ring = chosen_cand->rings.front().first;
1089  const detail::ProtoRing& remaining_ring = first_ring.ring();
1090  for (auto it = std::next(chosen_cand->rings.begin()); it != chosen_cand->rings.end(); ++it) {
1091  merge_two_rings(open_ring_its, first_ring, it->first);
1092  }
1093 
1094  if (debug()) {
1095  std::cerr << " Merged to " << remaining_ring << "\n";
1096  }
1097 
1098  return true;
1099  }
1100 
1102  // First create all the (partial) rings starting at the split locations
1103  auto count_remaining = m_segment_list.size();
1104  for (const osmium::Location& location : m_split_locations) {
1105  const auto locs = make_range(std::equal_range(m_locations.begin(),
1106  m_locations.end(),
1107  slocation{},
1108  [this, &location](const slocation& lhs, const slocation& rhs) {
1109  return lhs.location(m_segment_list, location) < rhs.location(m_segment_list, location);
1110  }));
1111  for (auto& loc : locs) {
1112  if (!m_segment_list[loc.item].is_done()) {
1113  count_remaining -= add_new_ring_complex(loc);
1114  if (count_remaining == 0) {
1115  break;
1116  }
1117  }
1118  }
1119  }
1120 
1121  // Now find all the rest of the rings (ie not starting at split locations)
1122  if (count_remaining > 0) {
1123  for (slocation& sl : m_locations) {
1124  const detail::NodeRefSegment& segment = m_segment_list[sl.item];
1125  if (!segment.is_done()) {
1126  count_remaining -= add_new_ring_complex(sl);
1127  if (count_remaining == 0) {
1128  break;
1129  }
1130  }
1131  }
1132  }
1133 
1134  // Now all segments are in exactly one (partial) ring.
1135 
1136  // If there are open rings, try to join them to create closed
1137  // rings.
1138  if (there_are_open_rings()) {
1139  ++m_stats.area_really_complex_case;
1140 
1141  open_ring_its_type open_ring_its;
1142  for (auto it = m_rings.begin(); it != m_rings.end(); ++it) {
1143  if (!it->closed()) {
1144  open_ring_its.push_back(it);
1145  }
1146  }
1147 
1148  while (!open_ring_its.empty()) {
1149  if (debug()) {
1150  std::cerr << " There are " << open_ring_its.size() << " open rings\n";
1151  }
1152  while (try_to_merge(open_ring_its));
1153 
1154  if (!open_ring_its.empty()) {
1155  if (debug()) {
1156  std::cerr << " After joining obvious cases there are still " << open_ring_its.size() << " open rings\n";
1157  }
1158  if (!join_connected_rings(open_ring_its)) {
1159  return false;
1160  }
1161  }
1162  }
1163 
1164  if (debug()) {
1165  std::cerr << " Joined all open rings\n";
1166  }
1167  }
1168 
1169  // Now all rings are complete.
1170 
1171  find_inner_outer_complex();
1172 
1173  return true;
1174  }
1175 
1181  std::unordered_set<const osmium::Way*> ways_in_segments;
1182 
1183  for (const auto& segment : m_segment_list) {
1184  ways_in_segments.insert(segment.way());
1185  }
1186 
1187  return ways_in_segments.size() < m_num_members;
1188  }
1189 
1193  bool create_rings() {
1194  m_stats.nodes += m_segment_list.size();
1195 
1196  // Sort the list of segments (from left to right and bottom
1197  // to top).
1198  osmium::Timer timer_sort;
1199  m_segment_list.sort();
1200  timer_sort.stop();
1201 
1202  // Remove duplicate segments. Removal is in pairs, so if there
1203  // are two identical segments, they will both be removed. If
1204  // there are three, two will be removed and one remains.
1205  osmium::Timer timer_dupl;
1206  m_stats.duplicate_segments = m_segment_list.erase_duplicate_segments(m_config.problem_reporter);
1207  timer_dupl.stop();
1208 
1209  // If there are no segments left at this point, this isn't
1210  // a valid area.
1211  if (m_segment_list.empty()) {
1212  if (debug()) {
1213  std::cerr << " No segments left\n";
1214  }
1215  return false;
1216  }
1217 
1218  // If one or more complete ways was removed because of
1219  // duplicate segments, this isn't a valid area.
1220  if (ways_were_lost()) {
1221  if (debug()) {
1222  std::cerr << " Complete ways removed because of duplicate segments\n";
1223  }
1224  return false;
1225  }
1226 
1227  if (m_config.debug_level >= 3) {
1228  std::cerr << "Sorted de-duplicated segment list:\n";
1229  for (const auto& s : m_segment_list) {
1230  std::cerr << " " << s << "\n";
1231  }
1232  }
1233 
1234  // Now we look for segments crossing each other. If there are
1235  // any, the multipolygon is invalid.
1236  // In the future this could be improved by trying to fix those
1237  // cases.
1238  osmium::Timer timer_intersection;
1239  m_stats.intersections = m_segment_list.find_intersections(m_config.problem_reporter);
1240  timer_intersection.stop();
1241 
1242  if (m_stats.intersections) {
1243  return false;
1244  }
1245 
1246  // This creates an ordered list of locations of both endpoints
1247  // of all segments with pointers back to the segments. We will
1248  // use this list later to quickly find which segment(s) fits
1249  // onto a known segment.
1250  osmium::Timer timer_locations_list;
1251  create_locations_list();
1252  timer_locations_list.stop();
1253 
1254  // Find all locations where more than two segments start or
1255  // end. We call those "split" locations. If there are any
1256  // "spike" segments found while doing this, we know the area
1257  // geometry isn't valid and return.
1258  osmium::Timer timer_split;
1259  if (!find_split_locations()) {
1260  return false;
1261  }
1262  timer_split.stop();
1263 
1264  // Now report all split locations to the problem reporter.
1265  m_stats.touching_rings += m_split_locations.size();
1266  if (!m_split_locations.empty()) {
1267  if (debug()) {
1268  std::cerr << " Found split locations:\n";
1269  }
1270  for (const auto& location : m_split_locations) {
1271  if (m_config.problem_reporter) {
1272  auto it = std::lower_bound(m_locations.cbegin(), m_locations.cend(), slocation{}, [this, &location](const slocation& lhs, const slocation& rhs) {
1273  return lhs.location(m_segment_list, location) < rhs.location(m_segment_list, location);
1274  });
1275  assert(it != m_locations.cend());
1276  const osmium::object_id_type id = it->node_ref(m_segment_list).ref();
1277  m_config.problem_reporter->report_touching_ring(id, location);
1278  }
1279  if (debug()) {
1280  std::cerr << " " << location << "\n";
1281  }
1282  }
1283  }
1284 
1285  // From here on we use two different algorithms depending on
1286  // whether there were any split locations or not. If there
1287  // are no splits, we use the faster "simple algorithm", if
1288  // there are, we use the slower "complex algorithm".
1289  osmium::Timer timer_simple_case;
1290  osmium::Timer timer_complex_case;
1291  if (m_split_locations.empty()) {
1292  if (debug()) {
1293  std::cerr << " No split locations -> using simple algorithm\n";
1294  }
1295  ++m_stats.area_simple_case;
1296 
1297  timer_simple_case.start();
1298  create_rings_simple_case();
1299  timer_simple_case.stop();
1300  } else {
1301  if (debug()) {
1302  std::cerr << " Found split locations -> using complex algorithm\n";
1303  }
1304  ++m_stats.area_touching_rings_case;
1305 
1306  timer_complex_case.start();
1307  if (!create_rings_complex_case()) {
1308  return false;
1309  }
1310  timer_complex_case.stop();
1311  }
1312 
1313  // If the assembler was so configured, now check whether the
1314  // member roles are correctly tagged.
1315  if (m_config.check_roles && m_stats.from_relations) {
1316  osmium::Timer timer_roles;
1317  check_inner_outer_roles();
1318  timer_roles.stop();
1319  }
1320 
1321  m_stats.outer_rings = std::count_if(m_rings.cbegin(), m_rings.cend(), [](const detail::ProtoRing& ring){
1322  return ring.is_outer();
1323  });
1324  m_stats.inner_rings = m_rings.size() - m_stats.outer_rings;
1325 
1326 #ifdef OSMIUM_WITH_TIMER
1327  std::cout << m_stats.nodes << ' ' << m_stats.outer_rings << ' ' << m_stats.inner_rings <<
1328  ' ' << timer_sort.elapsed_microseconds() <<
1329  ' ' << timer_dupl.elapsed_microseconds() <<
1330  ' ' << timer_intersection.elapsed_microseconds() <<
1331  ' ' << timer_locations_list.elapsed_microseconds() <<
1332  ' ' << timer_split.elapsed_microseconds();
1333 
1334  if (m_split_locations.empty()) {
1335  std::cout << ' ' << timer_simple_case.elapsed_microseconds() <<
1336  " 0";
1337  } else {
1338  std::cout << " 0" <<
1339  ' ' << timer_complex_case.elapsed_microseconds();
1340  }
1341 
1342  std::cout <<
1343 # ifdef OSMIUM_AREA_CHECK_INNER_OUTER_ROLES
1344  ' ' << timer_roles.elapsed_microseconds() <<
1345 # else
1346  " 0" <<
1347 # endif
1348  '\n';
1349 #endif
1350 
1351  return true;
1352  }
1353 
1354 #ifdef OSMIUM_WITH_TIMER
1355  static bool print_header() {
1356  std::cout << "nodes outer_rings inner_rings sort dupl intersection locations split simple_case complex_case roles_check\n";
1357  return true;
1358  }
1359 
1360  static bool init_header() {
1361  static bool printed_print_header = print_header();
1362  return printed_print_header;
1363  }
1364 #endif
1365 
1366  bool create_area(osmium::memory::Buffer& out_buffer, const osmium::Way& way) {
1367  osmium::builder::AreaBuilder builder{out_buffer};
1368  builder.initialize_from_object(way);
1369 
1370  const bool area_okay = create_rings();
1371  if (area_okay || m_config.create_empty_areas) {
1372  add_tags_to_area(builder, way);
1373  }
1374  if (area_okay) {
1375  add_rings_to_area(builder);
1376  }
1377 
1378  if (report_ways()) {
1379  m_config.problem_reporter->report_way(way);
1380  }
1381 
1382  return area_okay || m_config.create_empty_areas;
1383  }
1384 
1385  bool create_area(osmium::memory::Buffer& out_buffer, const osmium::Relation& relation, const std::vector<const osmium::Way*>& members) {
1386  m_num_members = members.size();
1387  osmium::builder::AreaBuilder builder{out_buffer};
1388  builder.initialize_from_object(relation);
1389 
1390  const bool area_okay = create_rings();
1391  if (area_okay || m_config.create_empty_areas) {
1392  add_tags_to_area(builder, relation);
1393  }
1394  if (area_okay) {
1395  add_rings_to_area(builder);
1396  }
1397 
1398  if (report_ways()) {
1399  for (const osmium::Way* way : members) {
1400  m_config.problem_reporter->report_way(*way);
1401  }
1402  }
1403 
1404  return area_okay || m_config.create_empty_areas;
1405  }
1406 
1407  public:
1408 
1410 
1411  explicit Assembler(const config_type& config) :
1412  m_config(config),
1413  m_segment_list(config.debug_level > 1) {
1414 #ifdef OSMIUM_WITH_TIMER
1415  init_header();
1416 #endif
1417  }
1418 
1419  ~Assembler() noexcept = default;
1420 
1425  void operator()(const osmium::Way& way, osmium::memory::Buffer& out_buffer) {
1426  if (!m_config.create_way_polygons) {
1427  return;
1428  }
1429 
1430  if (way.tags().has_tag("area", "no")) {
1431  return;
1432  }
1433 
1434  if (m_config.problem_reporter) {
1436  m_config.problem_reporter->set_nodes(way.nodes().size());
1437  }
1438 
1439  // Ignore (but count) ways without segments.
1440  if (way.nodes().size() < 2) {
1441  ++m_stats.short_ways;
1442  return;
1443  }
1444 
1445  if (!way.ends_have_same_id()) {
1446  ++m_stats.duplicate_nodes;
1447  if (m_config.problem_reporter) {
1448  m_config.problem_reporter->report_duplicate_node(way.nodes().front().ref(), way.nodes().back().ref(), way.nodes().front().location());
1449  }
1450  }
1451 
1452  ++m_stats.from_ways;
1453  m_stats.duplicate_nodes += m_segment_list.extract_segments_from_way(m_config.problem_reporter, way);
1454 
1455  if (m_config.debug_level > 0) {
1456  std::cerr << "\nAssembling way " << way.id() << " containing " << m_segment_list.size() << " nodes\n";
1457  }
1458 
1459  // Now create the Area object and add the attributes and tags
1460  // from the way.
1461  if (create_area(out_buffer, way)) {
1462  out_buffer.commit();
1463  } else {
1464  out_buffer.rollback();
1465  }
1466 
1467  if (debug()) {
1468  std::cerr << "Done: " << m_stats << "\n";
1469  }
1470  }
1471 
1482  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) {
1483  std::vector<const osmium::Way*> ways;
1484  for (size_t offset : members) {
1485  const osmium::Way& way = in_buffer.get<const osmium::Way>(offset);
1486  ways.push_back(&way);
1487  }
1488  operator()(relation, ways, out_buffer);
1489  }
1490 
1495  void operator()(const osmium::Relation& relation, const std::vector<const osmium::Way*>& members, osmium::memory::Buffer& out_buffer) {
1496  assert(relation.members().size() >= members.size());
1497 
1498  if (m_config.problem_reporter) {
1500  }
1501 
1502  if (relation.members().empty()) {
1503  ++m_stats.no_way_in_mp_relation;
1504  return;
1505  }
1506 
1507  ++m_stats.from_relations;
1508  m_stats.duplicate_nodes += m_segment_list.extract_segments_from_ways(m_config.problem_reporter, relation, members);
1509  m_stats.member_ways = members.size();
1510 
1511  if (m_stats.member_ways == 1) {
1512  ++m_stats.single_way_in_mp_relation;
1513  }
1514 
1515  if (m_config.debug_level > 0) {
1516  std::cerr << "\nAssembling relation " << relation.id() << " containing " << members.size() << " way members with " << m_segment_list.size() << " nodes\n";
1517  }
1518 
1519  const size_t area_offset = out_buffer.committed();
1520 
1521  // Now create the Area object and add the attributes and tags
1522  // from the relation.
1523  if (create_area(out_buffer, relation, members)) {
1524  if ((m_config.create_new_style_polygons && m_stats.no_tags_on_relation == 0) ||
1525  (m_config.create_old_style_polygons && m_stats.no_tags_on_relation != 0)) {
1526  out_buffer.commit();
1527  } else {
1528  out_buffer.rollback();
1529  }
1530  } else {
1531  out_buffer.rollback();
1532  }
1533 
1534  const osmium::TagList& area_tags = out_buffer.get<osmium::Area>(area_offset).tags(); // tags of the area we just built
1535 
1536  // Find all closed ways that are inner rings and check their
1537  // tags. If they are not the same as the tags of the area we
1538  // just built, add them to a list and later build areas for
1539  // them, too.
1540  std::vector<const osmium::Way*> ways_that_should_be_areas;
1541  if (m_stats.wrong_role == 0) {
1542  detail::for_each_member(relation, members, [this, &ways_that_should_be_areas, &area_tags](const osmium::RelationMember& member, const osmium::Way& way) {
1543  if (!std::strcmp(member.role(), "inner")) {
1544  if (!way.nodes().empty() && way.is_closed() && way.tags().size() > 0) {
1545  const auto d = std::count_if(way.tags().cbegin(), way.tags().cend(), filter());
1546  if (d > 0) {
1547  osmium::tags::KeyFilter::iterator way_fi_begin(filter(), way.tags().cbegin(), way.tags().cend());
1548  osmium::tags::KeyFilter::iterator way_fi_end(filter(), way.tags().cend(), way.tags().cend());
1549  osmium::tags::KeyFilter::iterator area_fi_begin(filter(), area_tags.cbegin(), area_tags.cend());
1550  osmium::tags::KeyFilter::iterator area_fi_end(filter(), area_tags.cend(), area_tags.cend());
1551 
1552  if (!std::equal(way_fi_begin, way_fi_end, area_fi_begin) || d != std::distance(area_fi_begin, area_fi_end)) {
1553  ways_that_should_be_areas.push_back(&way);
1554  } else {
1555  ++m_stats.inner_with_same_tags;
1556  if (m_config.problem_reporter) {
1558  }
1559  }
1560  }
1561  }
1562  }
1563  });
1564  }
1565 
1566  if (debug()) {
1567  std::cerr << "Done: " << m_stats << "\n";
1568  }
1569 
1570  // Now build areas for all ways found in the last step.
1571  for (const osmium::Way* way : ways_that_should_be_areas) {
1572  Assembler assembler(m_config);
1573  assembler(*way, out_buffer);
1574  }
1575  }
1576 
1581  const osmium::area::area_stats& stats() const noexcept {
1582  return m_stats;
1583  }
1584 
1585  }; // class Assembler
1586 
1587  } // namespace area
1588 
1589 } // namespace osmium
1590 
1591 #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:1495
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
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
rings_stack_element(double y, detail::ProtoRing *ring_ptr)
Definition: assembler.hpp:482
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:1425
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
double m_y
Definition: assembler.hpp:477
Definition: assembler.hpp:82
const_iterator cbegin() const noexcept
Definition: collection.hpp:164
bool ways_were_lost()
Definition: assembler.hpp:1180
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:1101
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:1366
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
double y() const noexcept
Definition: assembler.hpp:487
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:1010
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:359
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:1581
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
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:1411
Definition: location.hpp:273
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:268
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
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:1385
uint64_t single_way_in_mp_relation
Multipolygon relation containing a single way.
Definition: stats.hpp:67
bool create_rings()
Definition: assembler.hpp:1193
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:355
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:379
T & get(const size_t offset) const
Definition: buffer.hpp:413
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:1482
Definition: osm_object_builder.hpp:71
size_t commit()
Definition: buffer.hpp:363
void add_tags_to_area(osmium::builder::AreaBuilder &builder, const osmium::Way &way) const
Definition: assembler.hpp:290
Definition: osm_object_builder.hpp:528