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