Libosmium  2.7.2
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 
156  void enable_debug_output(bool d = true) {
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 // std::cerr << "z=" << z << "\n";
577 
578  if (z >= 0) {
579  nesting += segment->is_reverse() ? -1 : 1;
580  if (debug()) {
581  std::cerr << " Segment is below (nesting=" << nesting << ")\n";
582  }
583  if (segment->ring()->is_outer()) {
584  if (debug()) {
585  std::cerr << " Segment belongs to outer ring\n";
586  }
587  int32_t y = int32_t(ay + (by - ay) * (lx - ax) / (bx - ax));
588  outer_rings.emplace_back(y, segment->ring());
589  }
590  }
591  }
592  --segment;
593  }
594 
595  if (nesting % 2 == 0) {
596  if (debug()) {
597  std::cerr << " Decided that this is an outer ring\n";
598  }
599  return nullptr;
600  } else {
601  if (debug()) {
602  std::cerr << " Decided that this is an inner ring\n";
603  }
604  assert(!outer_rings.empty());
605 
606  std::sort(outer_rings.rbegin(), outer_rings.rend());
607  if (debug()) {
608  for (const auto& o : outer_rings) {
609  std::cerr << " y=" << o.y() << " " << o.ring() << "\n";
610  }
611  }
612 
613  remove_duplicates(outer_rings);
614  if (debug()) {
615  std::cerr << " after remove duplicates:\n";
616  for (const auto& o : outer_rings) {
617  std::cerr << " y=" << o.y() << " " << o.ring() << "\n";
618  }
619  }
620 
621  assert(!outer_rings.empty());
622  return outer_rings.front().ring_ptr();
623  }
624  }
625 
626  bool is_split_location(const osmium::Location& location) const noexcept {
627  return std::find(m_split_locations.cbegin(), m_split_locations.cend(), location) != m_split_locations.cend();
628  }
629 
630  uint32_t add_new_ring(slocation& node) {
631  detail::NodeRefSegment* segment = &m_segment_list[node.item];
632  assert(!segment->is_done());
633 
634  if (debug()) {
635  std::cerr << " Starting new ring at location " << node.location(m_segment_list) << " with segment " << *segment << "\n";
636  }
637 
638  if (node.reverse) {
639  segment->reverse();
640  }
641 
642  detail::ProtoRing* outer_ring = nullptr;
643 
644  if (segment != &m_segment_list.front()) {
645  outer_ring = find_enclosing_ring(segment);
646  }
647  segment->mark_direction_done();
648 
649  m_rings.emplace_back(segment);
650  detail::ProtoRing* ring = &m_rings.back();
651  if (outer_ring) {
652  if (debug()) {
653  std::cerr << " This is an inner ring. Outer ring is " << *outer_ring << "\n";
654  }
655  outer_ring->add_inner_ring(ring);
656  ring->set_outer_ring(outer_ring);
657  } else if (debug()) {
658  std::cerr << " This is an outer ring\n";
659  }
660 
661  const osmium::Location& first_location = node.location(m_segment_list);
662  osmium::Location last_location = segment->stop().location();
663 
664  uint32_t nodes = 1;
665  while (first_location != last_location) {
666  ++nodes;
667  detail::NodeRefSegment* next_segment = get_next_segment(last_location);
668  next_segment->mark_direction_done();
669  if (next_segment->start().location() != last_location) {
670  next_segment->reverse();
671  }
672  ring->add_segment_back(next_segment);
673  if (debug()) {
674  std::cerr << " Next segment is " << *next_segment << "\n";
675  }
676  last_location = next_segment->stop().location();
677  }
678 
679  ring->fix_direction();
680 
681  if (debug()) {
682  std::cerr << " Completed ring: " << *ring << "\n";
683  }
684 
685  return nodes;
686  }
687 
688  uint32_t add_new_ring_complex(slocation& node) {
689  detail::NodeRefSegment* segment = &m_segment_list[node.item];
690  assert(!segment->is_done());
691 
692  if (debug()) {
693  std::cerr << " Starting new ring at location " << node.location(m_segment_list) << " with segment " << *segment << "\n";
694  }
695 
696  if (node.reverse) {
697  segment->reverse();
698  }
699 
700  m_rings.emplace_back(segment);
701  detail::ProtoRing* ring = &m_rings.back();
702 
703  const osmium::Location& first_location = node.location(m_segment_list);
704  osmium::Location last_location = segment->stop().location();
705 
706  uint32_t nodes = 1;
707  while (first_location != last_location && !is_split_location(last_location)) {
708  ++nodes;
709  detail::NodeRefSegment* next_segment = get_next_segment(last_location);
710  if (next_segment->start().location() != last_location) {
711  next_segment->reverse();
712  }
713  ring->add_segment_back(next_segment);
714  if (debug()) {
715  std::cerr << " Next segment is " << *next_segment << "\n";
716  }
717  last_location = next_segment->stop().location();
718  }
719 
720  if (debug()) {
721  if (first_location == last_location) {
722  std::cerr << " Completed ring: " << *ring << "\n";
723  } else {
724  std::cerr << " Completed partial ring: " << *ring << "\n";
725  }
726  }
727 
728  return nodes;
729  }
730 
732  m_locations.reserve(m_segment_list.size() * 2);
733 
734  for (uint32_t n = 0; n < m_segment_list.size(); ++n) {
735  m_locations.emplace_back(n, false);
736  m_locations.emplace_back(n, true);
737  }
738 
739  std::stable_sort(m_locations.begin(), m_locations.end(), [this](const slocation& a, const slocation& b) {
740  return a.location(m_segment_list) < b.location(m_segment_list);
741  });
742  }
743 
744  void find_inner_outer_complex(detail::ProtoRing* ring) {
745  detail::ProtoRing* outer_ring = find_enclosing_ring(ring->min_segment());
746  if (outer_ring) {
747  outer_ring->add_inner_ring(ring);
748  ring->set_outer_ring(outer_ring);
749  }
750  ring->fix_direction();
751  ring->mark_direction_done();
752  }
753 
755  if (debug()) {
756  std::cerr << " Finding inner/outer rings\n";
757  }
758  std::vector<detail::ProtoRing*> rings;
759  rings.reserve(m_rings.size());
760  for (auto& ring : m_rings) {
761  if (ring.closed()) {
762  rings.push_back(&ring);
763  }
764  }
765 
766  if (rings.empty()) {
767  return;
768  }
769 
770  std::sort(rings.begin(), rings.end(), [](detail::ProtoRing* a, detail::ProtoRing* b) {
771  return a->min_segment() < b->min_segment();
772  });
773 
774  rings.front()->fix_direction();
775  rings.front()->mark_direction_done();
776  if (debug()) {
777  std::cerr << " First ring is outer: " << *rings.front() << "\n";
778  }
779  for (auto it = std::next(rings.begin()); it != rings.end(); ++it) {
780  if (debug()) {
781  std::cerr << " Checking (at min segment " << *((*it)->min_segment()) << ") ring " << **it << "\n";
782  }
783  find_inner_outer_complex(*it);
784  if (debug()) {
785  std::cerr << " Ring is " << ((*it)->is_outer() ? "OUTER: " : "INNER: ") << **it << "\n";
786  }
787  }
788  }
789 
796  osmium::Location previous_location;
797  for (auto it = m_locations.cbegin(); it != m_locations.cend(); ++it) {
798  const osmium::NodeRef& nr = it->node_ref(m_segment_list);
799  const osmium::Location& loc = nr.location();
800  if (std::next(it) == m_locations.cend() || loc != std::next(it)->location(m_segment_list)) {
801  if (debug()) {
802  std::cerr << " Found open ring at " << nr << "\n";
803  }
804  if (m_config.problem_reporter) {
805  const auto& segment = m_segment_list[it->item];
806  m_config.problem_reporter->report_ring_not_closed(nr, segment.way());
807  }
808  ++m_stats.open_rings;
809  } else {
810  if (loc == previous_location && (m_split_locations.empty() || m_split_locations.back() != previous_location )) {
811  m_split_locations.push_back(previous_location);
812  }
813  ++it;
814  if (it == m_locations.end()) {
815  break;
816  }
817  }
818  previous_location = loc;
819  }
820  return m_stats.open_rings == 0;
821  }
822 
824  uint32_t count_remaining = m_segment_list.size();
825  for (slocation& sl : m_locations) {
826  const detail::NodeRefSegment& segment = m_segment_list[sl.item];
827  if (!segment.is_done()) {
828  count_remaining -= add_new_ring(sl);
829  if (count_remaining == 0) {
830  return;
831  }
832  }
833  }
834  }
835 
836  std::vector<location_to_ring_map> create_location_to_ring_map(open_ring_its_type& open_ring_its) {
837  std::vector<location_to_ring_map> xrings;
838  xrings.reserve(open_ring_its.size() * 2);
839 
840  for (auto it = open_ring_its.begin(); it != open_ring_its.end(); ++it) {
841  if (debug()) {
842  std::cerr << " Ring: " << **it << "\n";
843  }
844  xrings.emplace_back((*it)->get_node_ref_start().location(), it, true);
845  xrings.emplace_back((*it)->get_node_ref_stop().location(), it, false);
846  }
847 
848  std::sort(xrings.begin(), xrings.end());
849 
850  return xrings;
851  }
852 
854  auto& r1 = *m1.ring_it;
855  auto& r2 = *m2.ring_it;
856 
857  if (r1->get_node_ref_stop().location() == r2->get_node_ref_start().location()) {
858  r1->join_forward(*r2);
859  } else if (r1->get_node_ref_stop().location() == r2->get_node_ref_stop().location()) {
860  r1->join_backward(*r2);
861  } else if (r1->get_node_ref_start().location() == r2->get_node_ref_start().location()) {
862  r1->reverse();
863  r1->join_forward(*r2);
864  } else if (r1->get_node_ref_start().location() == r2->get_node_ref_stop().location()) {
865  r1->reverse();
866  r1->join_backward(*r2);
867  } else {
868  assert(false);
869  }
870 
871  m_rings.erase(r2);
872  open_ring_its.remove(r2);
873 
874  if (r1->closed()) {
875  open_ring_its.remove(r1);
876  }
877  }
878 
879  bool try_to_merge(open_ring_its_type& open_ring_its) {
880  if (open_ring_its.empty()) {
881  return false;
882  }
883 
884  if (debug()) {
885  std::cerr << " Trying to merge " << open_ring_its.size() << " open rings\n";
886  }
887 
888  std::vector<location_to_ring_map> xrings = create_location_to_ring_map(open_ring_its);
889 
890  auto it = xrings.cbegin();
891  while (it != xrings.cend()) {
892  it = std::adjacent_find(it, xrings.cend());
893  if (it == xrings.cend()) {
894  return false;
895  }
896  auto after = std::next(it, 2);
897  if (after == xrings.cend() || after->location != it->location) {
898  if (debug()) {
899  std::cerr << " Merging two rings\n";
900  }
901  merge_two_rings(open_ring_its, *it, *std::next(it));
902  return true;
903  }
904  while (it != xrings.cend() && it->location == after->location) {
905  ++it;
906  }
907  }
908 
909  return false;
910  }
911 
912  bool there_are_open_rings() const noexcept {
913  return std::any_of(m_rings.cbegin(), m_rings.cend(), [](const detail::ProtoRing& ring){
914  return !ring.closed();
915  });
916  }
917 
918  struct candidate {
919  int64_t sum;
920  std::vector<std::pair<location_to_ring_map, bool>> rings;
923 
924  explicit candidate(location_to_ring_map& ring, bool reverse) :
925  sum(ring.ring().sum()),
926  rings(),
927  start_location(ring.ring().get_node_ref_start().location()),
928  stop_location(ring.ring().get_node_ref_stop().location()) {
929  rings.emplace_back(ring, reverse);
930  }
931 
932  bool closed() const noexcept {
933  return start_location == stop_location;
934  }
935 
936  };
937 
938  void find_candidates(std::vector<candidate>& candidates, std::unordered_set<osmium::Location>& loc_done, const std::vector<location_to_ring_map>& xrings, candidate& cand) {
939  if (debug()) {
940  std::cerr << " find_candidates sum=" << cand.sum << " start=" << cand.start_location << " stop=" << cand.stop_location << "\n";
941  for (const auto& ring : cand.rings) {
942  std::cerr << " " << ring.first.ring() << (ring.second ? " reverse" : "") << "\n";
943  }
944  }
945 
946  const auto connections = make_range(std::equal_range(xrings.cbegin(),
947  xrings.cend(),
949 
950  assert(connections.begin() != connections.end());
951 
952  assert(!cand.rings.empty());
953  const detail::ProtoRing* ring_leading_here = &cand.rings.back().first.ring();
954  for (const location_to_ring_map& m : connections) {
955  const detail::ProtoRing& ring = m.ring();
956 
957  if (&ring != ring_leading_here) {
958  if (debug()) {
959  std::cerr << " next possible connection: " << ring << (m.start ? "" : " reverse") << "\n";
960  }
961 
962  candidate c = cand;
963  if (m.start) {
964  c.rings.emplace_back(m, false);
965  c.stop_location = ring.get_node_ref_stop().location();
966  c.sum += ring.sum();
967  } else {
968  c.rings.emplace_back(m, true);
969  c.stop_location = ring.get_node_ref_start().location();
970  c.sum -= ring.sum();
971  }
972  if (c.closed()) {
973  if (debug()) {
974  std::cerr << " found candidate\n";
975  }
976  candidates.push_back(c);
977  } else if (loc_done.count(c.stop_location) == 0) {
978  if (debug()) {
979  std::cerr << " recurse...\n";
980  }
981  loc_done.insert(c.stop_location);
982  find_candidates(candidates, loc_done, xrings, c);
983  if (debug()) {
984  std::cerr << " ...back\n";
985  }
986  } else if (debug()) {
987  std::cerr << " loop found\n";
988  }
989  }
990  }
991  }
992 
1002  assert(!open_ring_its.empty());
1003 
1004  if (debug()) {
1005  std::cerr << " Trying to merge " << open_ring_its.size() << " open rings\n";
1006  }
1007 
1008  std::vector<location_to_ring_map> xrings = create_location_to_ring_map(open_ring_its);
1009 
1010  auto ring_min = std::min_element(xrings.begin(), xrings.end(), [](const location_to_ring_map& a, const location_to_ring_map& b) {
1011  return a.ring().min_segment() < b.ring().min_segment();
1012  });
1013 
1014  find_inner_outer_complex();
1015  detail::ProtoRing* outer_ring = find_enclosing_ring(ring_min->ring().min_segment());
1016  bool ring_min_is_outer = !outer_ring;
1017  if (debug()) {
1018  std::cerr << " Open ring is " << (ring_min_is_outer ? "outer" : "inner") << " ring\n";
1019  }
1020  for (auto& ring : m_rings) {
1021  ring.reset();
1022  }
1023 
1024  candidate cand{*ring_min, false};
1025 
1026  // Locations we have visited while finding candidates, used
1027  // to detect loops.
1028  std::unordered_set<osmium::Location> loc_done;
1029 
1030  loc_done.insert(cand.stop_location);
1031 
1032  std::vector<candidate> candidates;
1033  find_candidates(candidates, loc_done, xrings, cand);
1034 
1035  if (candidates.empty()) {
1036  if (debug()) {
1037  std::cerr << " Found no candidates\n";
1038  }
1039  if (!open_ring_its.empty()) {
1040  ++m_stats.open_rings;
1041  if (m_config.problem_reporter) {
1042  for (auto& it : open_ring_its) {
1043  m_config.problem_reporter->report_ring_not_closed(it->get_node_ref_start());
1044  m_config.problem_reporter->report_ring_not_closed(it->get_node_ref_stop());
1045  }
1046  }
1047  }
1048  return false;
1049  }
1050 
1051  if (debug()) {
1052  std::cerr << " Found candidates:\n";
1053  for (const auto& cand : candidates) {
1054  std::cerr << " sum=" << cand.sum << "\n";
1055  for (const auto& ring : cand.rings) {
1056  std::cerr << " " << ring.first.ring() << (ring.second ? " reverse" : "") << "\n";
1057  }
1058  }
1059  }
1060 
1061  // Find the candidate with the smallest/largest area
1062  auto chosen_cand = ring_min_is_outer ?
1063  std::min_element(candidates.cbegin(), candidates.cend(), [](const candidate& a, const candidate& b) {
1064  return std::abs(a.sum) < std::abs(b.sum);
1065  }) :
1066  std::max_element(candidates.cbegin(), candidates.cend(), [](const candidate& a, const candidate& b) {
1067  return std::abs(a.sum) < std::abs(b.sum);
1068  });
1069 
1070  if (debug()) {
1071  std::cerr << " Decided on: sum=" << chosen_cand->sum << "\n";
1072  for (const auto& ring : chosen_cand->rings) {
1073  std::cerr << " " << ring.first.ring() << (ring.second ? " reverse" : "") << "\n";
1074  }
1075  }
1076 
1077  // Join all (open) rings in the candidate to get one closed ring.
1078  assert(chosen_cand->rings.size() > 1);
1079  const auto& first_ring = chosen_cand->rings.front().first;
1080  for (auto it = chosen_cand->rings.begin() + 1; it != chosen_cand->rings.end(); ++it) {
1081  merge_two_rings(open_ring_its, first_ring, it->first);
1082  }
1083 
1084  if (debug()) {
1085  std::cerr << " Merged to " << first_ring.ring() << "\n";
1086  }
1087 
1088  return true;
1089  }
1090 
1092  // First create all the (partial) rings starting at the split locations
1093  uint32_t count_remaining = m_segment_list.size();
1094  for (const osmium::Location& location : m_split_locations) {
1095  const auto locs = make_range(std::equal_range(m_locations.begin(),
1096  m_locations.end(),
1097  slocation{},
1098  [this, &location](const slocation& a, const slocation& b) {
1099  return a.location(m_segment_list, location) < b.location(m_segment_list, location);
1100  }));
1101  for (auto& loc : locs) {
1102  if (!m_segment_list[loc.item].is_done()) {
1103  count_remaining -= add_new_ring_complex(loc);
1104  if (count_remaining == 0) {
1105  break;
1106  }
1107  }
1108  }
1109  }
1110 
1111  // Now find all the rest of the rings (ie not starting at split locations)
1112  if (count_remaining > 0) {
1113  for (slocation& sl : m_locations) {
1114  const detail::NodeRefSegment& segment = m_segment_list[sl.item];
1115  if (!segment.is_done()) {
1116  count_remaining -= add_new_ring_complex(sl);
1117  if (count_remaining == 0) {
1118  break;
1119  }
1120  }
1121  }
1122  }
1123 
1124  // Now all segments are in exactly one (partial) ring.
1125 
1126  // If there are open rings, try to join them to create closed
1127  // rings.
1128  if (there_are_open_rings()) {
1129  ++m_stats.area_really_complex_case;
1130 
1131  open_ring_its_type open_ring_its;
1132  for (auto it = m_rings.begin(); it != m_rings.end(); ++it) {
1133  if (!it->closed()) {
1134  open_ring_its.push_back(it);
1135  }
1136  }
1137 
1138  while (!open_ring_its.empty()) {
1139  if (debug()) {
1140  std::cerr << " There are " << open_ring_its.size() << " open rings\n";
1141  }
1142  while (try_to_merge(open_ring_its));
1143 
1144  if (!open_ring_its.empty()) {
1145  if (debug()) {
1146  std::cerr << " After joining obvious cases there are still " << open_ring_its.size() << " open rings\n";
1147  }
1148  if (!join_connected_rings(open_ring_its)) {
1149  return false;
1150  }
1151  }
1152  }
1153 
1154  if (debug()) {
1155  std::cerr << " Joined all open rings\n";
1156  }
1157  }
1158 
1159  // Now all rings are complete.
1160 
1161  find_inner_outer_complex();
1162 
1163  return true;
1164  }
1165 
1169  bool create_rings() {
1170  m_stats.nodes += m_segment_list.size();
1171 
1172  // Sort the list of segments (from left to right and bottom
1173  // to top).
1174  osmium::Timer timer_sort;
1175  m_segment_list.sort();
1176  timer_sort.stop();
1177 
1178  // Remove duplicate segments. Removal is in pairs, so if there
1179  // are two identical segments, they will both be removed. If
1180  // there are three, two will be removed and one remains.
1181  osmium::Timer timer_dupl;
1182  m_stats.duplicate_segments = m_segment_list.erase_duplicate_segments(m_config.problem_reporter);
1183  timer_dupl.stop();
1184 
1185  // If there are no segments left at this point, this isn't
1186  // a valid area.
1187  if (m_segment_list.empty()) {
1188  if (debug()) {
1189  std::cerr << " No segments left\n";
1190  }
1191  return false;
1192  }
1193 
1194  if (m_config.debug_level >= 3) {
1195  std::cerr << "Sorted de-duplicated segment list:\n";
1196  for (const auto& s : m_segment_list) {
1197  std::cerr << " " << s << "\n";
1198  }
1199  }
1200 
1201  // Now we look for segments crossing each other. If there are
1202  // any, the multipolygon is invalid.
1203  // In the future this could be improved by trying to fix those
1204  // cases.
1205  osmium::Timer timer_intersection;
1206  m_stats.intersections = m_segment_list.find_intersections(m_config.problem_reporter);
1207  timer_intersection.stop();
1208 
1209  if (m_stats.intersections) {
1210  return false;
1211  }
1212 
1213  // This creates an ordered list of locations of both endpoints
1214  // of all segments with pointers back to the segments. We will
1215  // use this list later to quickly find which segment(s) fits
1216  // onto a known segment.
1217  osmium::Timer timer_locations_list;
1218  create_locations_list();
1219  timer_locations_list.stop();
1220 
1221  // Find all locations where more than two segments start or
1222  // end. We call those "split" locations. If there are any
1223  // "spike" segments found while doing this, we know the area
1224  // geometry isn't valid and return.
1225  osmium::Timer timer_split;
1226  if (!find_split_locations()) {
1227  return false;
1228  }
1229  timer_split.stop();
1230 
1231  // Now report all split locations to the problem reporter.
1232  m_stats.touching_rings += m_split_locations.size();
1233  if (!m_split_locations.empty()) {
1234  if (debug()) {
1235  std::cerr << " Found split locations:\n";
1236  }
1237  for (const auto& location : m_split_locations) {
1238  if (m_config.problem_reporter) {
1239  auto it = std::lower_bound(m_locations.cbegin(), m_locations.cend(), slocation{}, [this, &location](const slocation& a, const slocation& b) {
1240  return a.location(m_segment_list, location) < b.location(m_segment_list, location);
1241  });
1242  assert(it != m_locations.cend());
1243  const osmium::object_id_type id = it->node_ref(m_segment_list).ref();
1244  m_config.problem_reporter->report_touching_ring(id, location);
1245  }
1246  if (debug()) {
1247  std::cerr << " " << location << "\n";
1248  }
1249  }
1250  }
1251 
1252  // From here on we use two different algorithms depending on
1253  // whether there were any split locations or not. If there
1254  // are no splits, we use the faster "simple algorithm", if
1255  // there are, we use the slower "complex algorithm".
1256  osmium::Timer timer_simple_case;
1257  osmium::Timer timer_complex_case;
1258  if (m_split_locations.empty()) {
1259  if (debug()) {
1260  std::cerr << " No split locations -> using simple algorithm\n";
1261  }
1262  ++m_stats.area_simple_case;
1263 
1264  timer_simple_case.start();
1265  create_rings_simple_case();
1266  timer_simple_case.stop();
1267  } else {
1268  if (debug()) {
1269  std::cerr << " Found split locations -> using complex algorithm\n";
1270  }
1271  ++m_stats.area_touching_rings_case;
1272 
1273  timer_complex_case.start();
1274  if (!create_rings_complex_case()) {
1275  return false;
1276  }
1277  timer_complex_case.stop();
1278  }
1279 
1280  // If the assembler was so configured, now check whether the
1281  // member roles are correctly tagged.
1282  if (m_config.check_roles && m_stats.from_relations) {
1283  osmium::Timer timer_roles;
1284  check_inner_outer_roles();
1285  timer_roles.stop();
1286  }
1287 
1288  m_stats.outer_rings = std::count_if(m_rings.cbegin(), m_rings.cend(), [](const detail::ProtoRing& ring){
1289  return ring.is_outer();
1290  });
1291  m_stats.inner_rings = m_rings.size() - m_stats.outer_rings;
1292 
1293 #ifdef OSMIUM_WITH_TIMER
1294  std::cout << m_stats.nodes << ' ' << m_stats.outer_rings << ' ' << m_stats.inner_rings <<
1295  ' ' << timer_sort.elapsed_microseconds() <<
1296  ' ' << timer_dupl.elapsed_microseconds() <<
1297  ' ' << timer_intersection.elapsed_microseconds() <<
1298  ' ' << timer_locations_list.elapsed_microseconds() <<
1299  ' ' << timer_split.elapsed_microseconds();
1300 
1301  if (m_split_locations.empty()) {
1302  std::cout << ' ' << timer_simple_case.elapsed_microseconds() <<
1303  " 0";
1304  } else {
1305  std::cout << " 0" <<
1306  ' ' << timer_complex_case.elapsed_microseconds();
1307  }
1308 
1309  std::cout <<
1310 # ifdef OSMIUM_AREA_CHECK_INNER_OUTER_ROLES
1311  ' ' << timer_roles.elapsed_microseconds() <<
1312 # else
1313  " 0" <<
1314 # endif
1315  '\n';
1316 #endif
1317 
1318  return true;
1319  }
1320 
1321 #ifdef OSMIUM_WITH_TIMER
1322  static bool print_header() {
1323  std::cout << "nodes outer_rings inner_rings sort dupl intersection locations split simple_case complex_case roles_check\n";
1324  return true;
1325  }
1326 
1327  static bool init_header() {
1328  static bool printed_print_header = print_header();
1329  return printed_print_header;
1330  }
1331 #endif
1332 
1333  bool create_area(osmium::memory::Buffer& out_buffer, const osmium::Way& way) {
1334  osmium::builder::AreaBuilder builder(out_buffer);
1335  builder.initialize_from_object(way);
1336 
1337  const bool area_okay = create_rings();
1338  if (area_okay || m_config.create_empty_areas) {
1339  add_tags_to_area(builder, way);
1340  }
1341  if (area_okay) {
1342  add_rings_to_area(builder);
1343  }
1344 
1345  if (report_ways()) {
1346  m_config.problem_reporter->report_way(way);
1347  }
1348 
1349  return area_okay || m_config.create_empty_areas;
1350  }
1351 
1352  bool create_area(osmium::memory::Buffer& out_buffer, const osmium::Relation& relation, const std::vector<const osmium::Way*>& members) {
1353  osmium::builder::AreaBuilder builder(out_buffer);
1354  builder.initialize_from_object(relation);
1355 
1356  const bool area_okay = create_rings();
1357  if (area_okay || m_config.create_empty_areas) {
1358  add_tags_to_area(builder, relation);
1359  }
1360  if (area_okay) {
1361  add_rings_to_area(builder);
1362  }
1363 
1364  if (report_ways()) {
1365  for (const osmium::Way* way : members) {
1366  m_config.problem_reporter->report_way(*way);
1367  }
1368  }
1369 
1370  return area_okay || m_config.create_empty_areas;
1371  }
1372 
1373  public:
1374 
1376 
1377  explicit Assembler(const config_type& config) :
1378  m_config(config),
1379  m_segment_list(config.debug_level > 1) {
1380 #ifdef OSMIUM_WITH_TIMER
1381  init_header();
1382 #endif
1383  }
1384 
1385  ~Assembler() noexcept = default;
1386 
1391  void operator()(const osmium::Way& way, osmium::memory::Buffer& out_buffer) {
1392  if (!m_config.create_way_polygons) {
1393  return;
1394  }
1395 
1396  if (way.tags().has_tag("area", "no")) {
1397  return;
1398  }
1399 
1400  if (m_config.problem_reporter) {
1402  m_config.problem_reporter->set_nodes(way.nodes().size());
1403  }
1404 
1405  // Ignore (but count) ways without segments.
1406  if (way.nodes().size() < 2) {
1407  ++m_stats.short_ways;
1408  return;
1409  }
1410 
1411  if (!way.ends_have_same_id()) {
1412  ++m_stats.duplicate_nodes;
1413  if (m_config.problem_reporter) {
1414  m_config.problem_reporter->report_duplicate_node(way.nodes().front().ref(), way.nodes().back().ref(), way.nodes().front().location());
1415  }
1416  }
1417 
1418  ++m_stats.from_ways;
1419  m_stats.duplicate_nodes += m_segment_list.extract_segments_from_way(m_config.problem_reporter, way);
1420 
1421  if (m_config.debug_level > 0) {
1422  std::cerr << "\nAssembling way " << way.id() << " containing " << m_segment_list.size() << " nodes\n";
1423  }
1424 
1425  // Now create the Area object and add the attributes and tags
1426  // from the way.
1427  if (create_area(out_buffer, way)) {
1428  out_buffer.commit();
1429  } else {
1430  out_buffer.rollback();
1431  }
1432 
1433  if (debug()) {
1434  std::cerr << "Done: " << m_stats << "\n";
1435  }
1436  }
1437 
1448  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) {
1449  std::vector<const osmium::Way*> ways;
1450  for (size_t offset : members) {
1451  const osmium::Way& way = in_buffer.get<const osmium::Way>(offset);
1452  ways.push_back(&way);
1453  }
1454  operator()(relation, ways, out_buffer);
1455  }
1456 
1461  void operator()(const osmium::Relation& relation, const std::vector<const osmium::Way*>& members, osmium::memory::Buffer& out_buffer) {
1462  assert(relation.members().size() >= members.size());
1463 
1464  if (m_config.problem_reporter) {
1466  }
1467 
1468  if (relation.members().empty()) {
1469  ++m_stats.no_way_in_mp_relation;
1470  return;
1471  }
1472 
1473  ++m_stats.from_relations;
1474  m_stats.duplicate_nodes += m_segment_list.extract_segments_from_ways(m_config.problem_reporter, relation, members);
1475  m_stats.member_ways = members.size();
1476 
1477  if (m_stats.member_ways == 1) {
1478  ++m_stats.single_way_in_mp_relation;
1479  }
1480 
1481  if (m_config.debug_level > 0) {
1482  std::cerr << "\nAssembling relation " << relation.id() << " containing " << members.size() << " way members with " << m_segment_list.size() << " nodes\n";
1483  }
1484 
1485  const size_t area_offset = out_buffer.committed();
1486 
1487  // Now create the Area object and add the attributes and tags
1488  // from the relation.
1489  if (create_area(out_buffer, relation, members)) {
1490  if ((m_config.create_new_style_polygons && m_stats.no_tags_on_relation == 0) ||
1491  (m_config.create_old_style_polygons && m_stats.no_tags_on_relation != 0)) {
1492  out_buffer.commit();
1493  } else {
1494  out_buffer.rollback();
1495  }
1496  } else {
1497  out_buffer.rollback();
1498  }
1499 
1500  const osmium::TagList& area_tags = out_buffer.get<osmium::Area>(area_offset).tags(); // tags of the area we just built
1501 
1502  // Find all closed ways that are inner rings and check their
1503  // tags. If they are not the same as the tags of the area we
1504  // just built, add them to a list and later build areas for
1505  // them, too.
1506  std::vector<const osmium::Way*> ways_that_should_be_areas;
1507  if (m_stats.wrong_role == 0) {
1508  detail::for_each_member(relation, members, [this, &ways_that_should_be_areas, &area_tags](const osmium::RelationMember& member, const osmium::Way& way) {
1509  if (!std::strcmp(member.role(), "inner")) {
1510  if (!way.nodes().empty() && way.is_closed() && way.tags().size() > 0) {
1511  const auto d = std::count_if(way.tags().cbegin(), way.tags().cend(), filter());
1512  if (d > 0) {
1513  osmium::tags::KeyFilter::iterator way_fi_begin(filter(), way.tags().cbegin(), way.tags().cend());
1514  osmium::tags::KeyFilter::iterator way_fi_end(filter(), way.tags().cend(), way.tags().cend());
1515  osmium::tags::KeyFilter::iterator area_fi_begin(filter(), area_tags.cbegin(), area_tags.cend());
1516  osmium::tags::KeyFilter::iterator area_fi_end(filter(), area_tags.cend(), area_tags.cend());
1517 
1518  if (!std::equal(way_fi_begin, way_fi_end, area_fi_begin) || d != std::distance(area_fi_begin, area_fi_end)) {
1519  ways_that_should_be_areas.push_back(&way);
1520  } else {
1521  ++m_stats.inner_with_same_tags;
1522  if (m_config.problem_reporter) {
1524  }
1525  }
1526  }
1527  }
1528  }
1529  });
1530  }
1531 
1532  if (debug()) {
1533  std::cerr << "Done: " << m_stats << "\n";
1534  }
1535 
1536  // Now build areas for all ways found in the last step.
1537  for (const osmium::Way* way : ways_that_should_be_areas) {
1538  Assembler assembler(m_config);
1539  assembler(*way, out_buffer);
1540  }
1541  }
1542 
1547  const osmium::area::area_stats& stats() const noexcept {
1548  return m_stats;
1549  }
1550 
1551  }; // class Assembler
1552 
1553  } // namespace area
1554 
1555 } // namespace osmium
1556 
1557 #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:919
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:1391
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:1461
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:924
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:1091
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:922
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:1352
std::vector< location_to_ring_map > create_location_to_ring_map(open_ring_its_type &open_ring_its)
Definition: assembler.hpp:836
slocation() noexcept
Definition: assembler.hpp:215
bool create_way_polygons
Definition: assembler.hpp:130
bool closed() const noexcept
Definition: assembler.hpp:932
bool create_area(osmium::memory::Buffer &out_buffer, const osmium::Way &way)
Definition: assembler.hpp:1333
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:754
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:626
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
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:1001
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:823
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:938
Definition: assembler.hpp:307
constexpr int32_t y() const noexcept
Definition: location.hpp:302
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:1547
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:853
std::vector< std::pair< location_to_ring_map, bool > > rings
Definition: assembler.hpp:920
const TagList & tags() const
Get the list of tags for this object.
Definition: object.hpp:297
void create_locations_list()
Definition: assembler.hpp:731
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:630
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:921
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:1377
Definition: location.hpp:216
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:918
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:795
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:744
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:1169
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:688
constexpr int32_t x() const noexcept
Definition: location.hpp:298
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:879
uint64_t area_simple_case
Simple case, no touching rings.
Definition: stats.hpp:51
bool there_are_open_rings() const noexcept
Definition: assembler.hpp:912
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
void enable_debug_output(bool d=true)
Definition: assembler.hpp:156
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:1448
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