[generator:streets] Highway tracing: detect street's regions

7 files changed, 375 insertions, 49 deletions

diff --git a/generator/CMakeLists.txt b/generator/CMakeLists.txt
index ef398f1541..543cbb9ed3 100644
--- a/generator/CMakeLists.txt
+++ b/generator/CMakeLists.txt
@@ -193,6 +193,8 @@ set(SRC
   statistics.hpp
   streets/street_geometry.cpp
   streets/street_geometry.hpp
+  streets/street_regions_tracing.cpp
+  streets/street_regions_tracing.hpp
   streets/streets.cpp
   streets/streets.hpp
   streets/streets_builder.cpp
diff --git a/generator/generator_tests/CMakeLists.txt b/generator/generator_tests/CMakeLists.txt
index ac72beef87..0a9fbdeff6 100644
--- a/generator/generator_tests/CMakeLists.txt
+++ b/generator/generator_tests/CMakeLists.txt
@@ -35,6 +35,7 @@ set(
   sponsored_storage_tests.cpp
   srtm_parser_test.cpp
   street_geometry_tests.cpp
+  street_regions_tracing_tests.cpp
   tag_admixer_test.cpp
   tesselator_test.cpp
   triangles_tree_coding_test.cpp
diff --git a/generator/generator_tests/street_regions_tracing_tests.cpp b/generator/generator_tests/street_regions_tracing_tests.cpp
new file mode 100644
index 0000000000..1bf05f2922
--- /dev/null
+++ b/generator/generator_tests/street_regions_tracing_tests.cpp
@@ -0,0 +1,64 @@
+#include "testing/testing.hpp"
+
+#include "generator/streets/street_regions_tracing.hpp"
+
+#include "base/geo_object_id.hpp"
+
+using namespace generator::streets;
+using generator::KeyValue;
+
+UNIT_TEST(StreetRegionTracingTest_StreetInOneRegion)
+{
+  auto regionGetter = [] (auto &&) { return KeyValue{1, {}}; };
+  auto && tracing = StreetRegionsTracing{{{0.0, 0.0}, {1.0, 1.0}}, regionGetter};
+  auto && segments = tracing.StealPathSegments();
+
+  TEST_EQUAL(segments.size(), 1, ());
+  TEST_EQUAL(segments.front().m_region.first, 1, ());
+}
+
+UNIT_TEST(StreetRegionTracingTest_OutgoingStreet)
+{
+  auto regionGetter = [] (auto && point) {
+    if (point.x < 0.001)
+      return KeyValue{1, {}};
+    return KeyValue{2, {}};
+  };
+  auto && tracing = StreetRegionsTracing{{{0.0, 0.0}, {1.0, 0.0}}, regionGetter};
+  auto && segments = tracing.StealPathSegments();
+
+  TEST_EQUAL(segments.size(), 2, ());
+  TEST_EQUAL(segments.front().m_region.first, 1, ());
+  TEST_EQUAL(segments.back().m_region.first, 2, ());
+}
+
+UNIT_TEST(StreetRegionTracingTest_IncomingStreet)
+{
+  auto regionGetter = [] (auto && point) {
+    if (point.x < 0.999)
+      return KeyValue{1, {}};
+    return KeyValue{2, {}};
+  };
+  auto && tracing = StreetRegionsTracing{{{0.0, 0.0}, {1.0, 0.0}}, regionGetter};
+  auto && segments = tracing.StealPathSegments();
+
+  TEST_EQUAL(segments.size(), 2, ());
+  TEST_EQUAL(segments.front().m_region.first, 1, ());
+  TEST_EQUAL(segments.back().m_region.first, 2, ());
+}
+
+UNIT_TEST(StreetRegionTracingTest_StreetWithTransitRegion)
+{
+  auto regionGetter = [] (auto && point) {
+    if (0.5 <= point.x && point.x <= 0.501)
+      return KeyValue{2, {}};
+    return KeyValue{1, {}};
+  };
+  auto && tracing = StreetRegionsTracing{{{0.0, 0.0}, {1.0, 0.0}}, regionGetter};
+  auto && segments = tracing.StealPathSegments();
+
+  TEST_EQUAL(segments.size(), 3, ());
+  TEST_EQUAL(segments[0].m_region.first, 1, ());
+  TEST_EQUAL(segments[1].m_region.first, 2, ());
+  TEST_EQUAL(segments[2].m_region.first, 1, ());
+}
diff --git a/generator/streets/street_regions_tracing.cpp b/generator/streets/street_regions_tracing.cpp
new file mode 100644
index 0000000000..17fa9769ee
--- /dev/null
+++ b/generator/streets/street_regions_tracing.cpp
@@ -0,0 +1,193 @@
+#include "generator/streets/street_regions_tracing.hpp"
+
+#include "geometry/mercator.hpp"
+
+#include <algorithm>
+#include <iterator>
+
+#include <boost/optional.hpp>
+
+namespace generator
+{
+namespace streets
+{
+constexpr m2::Meter const StreetRegionsTracing::kRegionCheckStepDistance;
+constexpr m2::Meter const StreetRegionsTracing::kRegionBoundarySearchStepDistance;
+
+StreetRegionsTracing::StreetRegionsTracing(Path const & path,
+                                           StreetRegionInfoGetter const & streetRegionInfoGetter)
+  : m_path{path}, m_streetRegionInfoGetter{streetRegionInfoGetter}
+{
+  CHECK_GREATER_OR_EQUAL(m_path.size(), 2, ());
+
+  m_currentPoint = m_path.front();
+  m_nextPathPoint = std::next(m_path.begin());
+
+  m_currentRegion = m_streetRegionInfoGetter(m_currentPoint);
+  if (m_currentRegion)
+    StartNewSegment();
+
+  Trace();
+}
+
+StreetRegionsTracing::PathSegments && StreetRegionsTracing::StealPathSegments()
+{
+  return std::move(m_pathSegments);
+}
+
+void StreetRegionsTracing::Trace()
+{
+  while (m_nextPathPoint != m_path.end())
+  {
+    if (!TraceToNextCheckPointInCurrentRegion())
+      TraceUpToNextRegion();
+  }
+
+  if (m_currentRegion)
+    ReleaseCurrentSegment();
+}
+
+bool StreetRegionsTracing::TraceToNextCheckPointInCurrentRegion()
+{
+  Meter distanceToCheckPoint{};
+  auto newNextPathPoint = m_nextPathPoint;
+  auto checkPoint = FollowToNextPoint(m_currentPoint, kRegionCheckStepDistance, m_nextPathPoint,
+                                      distanceToCheckPoint, newNextPathPoint);
+
+  auto checkPointRegion = m_streetRegionInfoGetter(checkPoint);
+  if (!IsSameRegion(checkPointRegion))
+    return false;
+
+  AdvanceTo(checkPoint, distanceToCheckPoint, newNextPathPoint);
+  return true;
+}
+
+void StreetRegionsTracing::TraceUpToNextRegion()
+{
+  while (m_nextPathPoint != m_path.end())
+  {
+    Meter distanceToNextPoint{};
+    auto newNextPathPoint = m_nextPathPoint;
+    auto nextPoint = FollowToNextPoint(m_currentPoint, kRegionBoundarySearchStepDistance, m_nextPathPoint,
+                                       distanceToNextPoint, newNextPathPoint);
+
+    auto nextPointRegion = m_streetRegionInfoGetter(nextPoint);
+    if (!IsSameRegion(nextPointRegion))
+    {
+      AdvanceToBoundary(nextPointRegion, nextPoint, distanceToNextPoint, newNextPathPoint);
+      return;
+    }
+
+    AdvanceTo(nextPoint, distanceToNextPoint, newNextPathPoint);
+  }
+}
+
+void StreetRegionsTracing::AdvanceToBoundary(boost::optional<KeyValue> const & newRegion,
+    m2::PointD const newRegionPoint, Meter distance, Path::const_iterator nextPathPoint)
+{
+  if (m_currentRegion)
+    CloseCurrentSegment(newRegionPoint, distance, nextPathPoint);
+
+  m_currentRegion = newRegion;
+  if (m_currentRegion)
+    StartNewSegment();
+
+  AdvanceTo(newRegionPoint, distance, nextPathPoint);
+}
+
+void StreetRegionsTracing::AdvanceTo(m2::PointD const toPoint, Meter distance,
+                                     Path::const_iterator nextPathPoint)
+{
+  CHECK(0.0 <= distance || m_nextPathPoint != nextPathPoint, ());
+
+  if (m_currentRegion)
+  {
+    CHECK(!m_pathSegments.empty(), ());
+    auto & currentSegment = m_pathSegments.back();
+    std::copy(m_nextPathPoint, nextPathPoint, std::back_inserter(currentSegment.m_path));
+    currentSegment.m_pathLengthMeters += distance;
+  }
+
+  m_currentPoint = toPoint;
+  m_nextPathPoint = nextPathPoint;
+}
+
+void StreetRegionsTracing::StartNewSegment()
+{
+  CHECK(m_currentRegion, ());
+  m_pathSegments.push_back({*m_currentRegion, {m_currentPoint}, 0.0 /* m_pathLengthMeters */});
+}
+
+void StreetRegionsTracing::CloseCurrentSegment(m2::PointD const endPoint, Meter distance,
+                                               Path::const_iterator pathEndPoint)
+{
+  CHECK(0.0 <= distance || m_nextPathPoint != pathEndPoint, ());
+
+  CHECK(!m_pathSegments.empty(), ());
+  auto & currentSegment = m_pathSegments.back();
+
+  std::copy(m_nextPathPoint, pathEndPoint, std::back_inserter(currentSegment.m_path));
+  if (currentSegment.m_path.back() != endPoint)
+    currentSegment.m_path.push_back(endPoint);
+
+  currentSegment.m_pathLengthMeters += distance;
+
+  ReleaseCurrentSegment();
+}
+
+void StreetRegionsTracing::ReleaseCurrentSegment()
+{
+  CHECK(!m_pathSegments.empty(), ());
+  auto & currentSegment = m_pathSegments.back();
+
+  CHECK_GREATER_OR_EQUAL(currentSegment.m_path.size(), 2, ());
+
+  constexpr auto kSegmentLengthMin = 1.0_m;
+  if (m_pathSegments.back().m_pathLengthMeters < kSegmentLengthMin)
+    m_pathSegments.pop_back();
+}
+
+m2::PointD StreetRegionsTracing::FollowToNextPoint(m2::PointD const & startPoint, Meter stepDistance,
+    Path::const_iterator nextPathPoint, Meter & distance, Path::const_iterator & newNextPathPoint) const
+{
+  auto point = startPoint;
+  distance = 0.0_m;
+  newNextPathPoint = nextPathPoint;
+  for (; newNextPathPoint != m_path.end(); ++newNextPathPoint)
+  {
+    auto nextPoint = *newNextPathPoint;
+    auto distanceToNextPoint = Meter{MercatorBounds::DistanceOnEarth(point, nextPoint)};
+    CHECK_LESS(distance, stepDistance, ());
+    auto restDistance = stepDistance - distance;
+
+    constexpr auto kDistancePrecision = 2.0_m;
+    if (std::fabs(restDistance - distanceToNextPoint) <= kDistancePrecision)
+    {
+      ++newNextPathPoint;
+      distance += distanceToNextPoint;
+      return nextPoint;
+    }
+
+    if (restDistance < distanceToNextPoint)
+    {
+      point += (nextPoint - point) * restDistance / distanceToNextPoint;
+      distance = stepDistance;
+      return point;
+    }
+
+    point = nextPoint;
+    distance += distanceToNextPoint;
+  }
+
+  return point;
+}
+
+bool StreetRegionsTracing::IsSameRegion(boost::optional<KeyValue> const & region) const
+{
+  if (m_currentRegion && region)
+    return m_currentRegion->first == region->first;
+
+  return !m_currentRegion && !region;
+}
+}  // namespace streets
+}  // namespace generator
diff --git a/generator/streets/street_regions_tracing.hpp b/generator/streets/street_regions_tracing.hpp
new file mode 100644
index 0000000000..134317c08e
--- /dev/null
+++ b/generator/streets/street_regions_tracing.hpp
@@ -0,0 +1,62 @@
+#pragma once
+
+#include "generator/key_value_storage.hpp"
+
+#include "geometry/meter.hpp"
+#include "geometry/point2d.hpp"
+
+#include <functional>
+#include <vector>
+
+namespace generator
+{
+namespace streets
+{
+using m2::literals::operator"" _m;
+
+class StreetRegionsTracing final
+{
+public:
+  using Meter = m2::Meter;
+  using StreetRegionInfoGetter = std::function<boost::optional<KeyValue>(m2::PointD const & pathPoint)>;
+  using Path = std::vector<m2::PointD>;
+
+  constexpr static auto const kRegionCheckStepDistance = 100.0_m;
+  constexpr static auto const kRegionBoundarySearchStepDistance = 10.0_m;
+
+  struct Segment
+  {
+    KeyValue m_region;
+    Path m_path;
+    Meter m_pathLengthMeters;
+  };
+
+  using PathSegments = std::vector<Segment>;
+
+  StreetRegionsTracing(Path const & path, StreetRegionInfoGetter const & streetRegionInfoGetter);
+
+  PathSegments && StealPathSegments();
+
+private:
+  void Trace();
+  bool TraceToNextCheckPointInCurrentRegion();
+  void TraceUpToNextRegion();
+  void AdvanceTo(m2::PointD const toPoint, Meter distance, Path::const_iterator nextPathPoint);
+  void AdvanceToBoundary(boost::optional<KeyValue> const & newRegion, m2::PointD const newRegionPoint,
+                         Meter distance, Path::const_iterator nextPathPoint);
+  void StartNewSegment();
+  void CloseCurrentSegment(m2::PointD const endPoint, Meter distance, Path::const_iterator pathEndPoint);
+  void ReleaseCurrentSegment();
+  m2::PointD FollowToNextPoint(m2::PointD const & startPoint, Meter stepDistance,
+      Path::const_iterator nextPathPoint, Meter & distance, Path::const_iterator & newNextPathPoint) const;
+  bool IsSameRegion(boost::optional<KeyValue> const & region) const;
+
+  Path const & m_path;
+  StreetRegionInfoGetter const & m_streetRegionInfoGetter;
+  m2::PointD m_currentPoint;
+  Path::const_iterator m_nextPathPoint;
+  boost::optional<KeyValue> m_currentRegion;
+  PathSegments m_pathSegments;
+};
+}  // namespace streets
+}  // namesapce generator
diff --git a/generator/streets/streets_builder.cpp b/generator/streets/streets_builder.cpp
index a32381d3c2..af1058320c 100644
--- a/generator/streets/streets_builder.cpp
+++ b/generator/streets/streets_builder.cpp
@@ -1,5 +1,7 @@
 #include "generator/streets/streets_builder.hpp"
 
+#include "generator/streets/street_regions_tracing.hpp"
+
 #include "indexer/classificator.hpp"
 #include "indexer/ftypes_matcher.hpp"
 
@@ -65,45 +67,63 @@ void StreetsBuilder::SaveRegionStreetsKv(std::ostream & streamStreetsKv, uint64_
 
 void StreetsBuilder::AddStreet(FeatureBuilder & fb)
 {
-  auto const region = FindStreetRegionOwner(fb);
-  if (!region)
-    return;
+  if (fb.IsArea())
+    return AddStreetArea(fb);
 
-  InsertStreet(*region, fb);
+  if (fb.IsPoint())
+    return AddStreetPoint(fb);
+
+  CHECK(fb.IsLine(), ());
+  AddStreetHighway(fb);
 }
 
-void StreetsBuilder::AddStreetBinding(std::string && streetName, FeatureBuilder & fb)
+void StreetsBuilder::AddStreetHighway(FeatureBuilder & fb)
 {
-  auto const region = FindStreetRegionOwner(fb.GetKeyPoint());
+  auto streetRegionInfoGetter = [this] (auto const & pathPoint) {
+    return this->FindStreetRegionOwner(pathPoint);
+  };
+  StreetRegionsTracing regionsTracing(fb.GetOuterGeometry(), streetRegionInfoGetter);
+
+  auto && pathSegments = regionsTracing.StealPathSegments();
+  for (auto & segment : pathSegments)
+  {
+    auto && region = segment.m_region;
+    auto & street = InsertStreet(region.first, fb.GetName());
+    auto const osmId = pathSegments.size() == 1 ? fb.GetMostGenericOsmId() : NextOsmSurrogateId();
+    street.AddHighwayLine(osmId, std::move(segment.m_path));
+  }
+}
+
+void StreetsBuilder::AddStreetArea(FeatureBuilder & fb)
+{
+  auto && region = FindStreetRegionOwner(fb.GetGeometryCenter(), true);
   if (!region)
     return;
 
-  InsertStreetBinding(*region, std::move(streetName), fb);
+  auto & street = InsertStreet(region->first, fb.GetName());
+  auto osmId = fb.GetMostGenericOsmId();
+  street.AddHighwayArea(osmId, fb.GetOuterGeometry());
 }
 
-boost::optional<KeyValue> StreetsBuilder::FindStreetRegionOwner(FeatureBuilder & fb)
+void StreetsBuilder::AddStreetPoint(FeatureBuilder & fb)
 {
-  if (fb.IsPoint())
-    return FindStreetRegionOwner(fb.GetKeyPoint(), true /* needLocality */);
-  if (fb.IsArea())
-    return FindStreetRegionOwner(fb.GetGeometryCenter(), true /* needLocality */);
+  auto && region = FindStreetRegionOwner(fb.GetKeyPoint(), true);
+  if (!region)
+    return;
 
-  auto const & line = fb.GetOuterGeometry();
-  CHECK_GREATER_OR_EQUAL(line.size(), 2, ());
-  auto const & startPoint = line.front();
-  auto const & owner = FindStreetRegionOwner(startPoint);
-  if (!owner)
-    return {};
+  auto osmId = fb.GetMostGenericOsmId();
+  auto & street = InsertStreet(region->first, fb.GetName());
+  street.SetPin({fb.GetKeyPoint(), osmId});
+}
 
-  auto const & finishPoint = line.back();
-  if (startPoint != finishPoint)
-  {
-    auto const & finishPointOwner = FindStreetRegionOwner(finishPoint);
-    if (!finishPointOwner || finishPointOwner->first != owner->first)
-      LOG(LDEBUG, ("Street", fb.GetMostGenericOsmId(), fb.GetName(), "is in several regions"));
-  }
+void StreetsBuilder::AddStreetBinding(std::string && streetName, FeatureBuilder & fb)
+{
+  auto const region = FindStreetRegionOwner(fb.GetKeyPoint());
+  if (!region)
+    return;
 
-  return owner;
+  auto & street = InsertStreet(region->first, std::move(streetName));
+  street.AddBinding(NextOsmSurrogateId(), fb.GetKeyPoint());
 }
 
 boost::optional<KeyValue> StreetsBuilder::FindStreetRegionOwner(m2::PointD const & point, bool needLocality)
@@ -126,26 +146,10 @@ boost::optional<KeyValue> StreetsBuilder::FindStreetRegionOwner(m2::PointD const
   return m_regionInfoGetter.FindDeepest(point, isStreetAdministrator);
 }
 
-void StreetsBuilder::InsertStreet(KeyValue const & region, FeatureBuilder & fb)
-{
-  auto & regionStreets = m_regions[region.first];
-  auto & street = regionStreets[fb.GetName()];
-  auto const osmId = fb.GetMostGenericOsmId();
-
-  if (fb.IsArea())
-    street.AddHighwayArea(osmId, fb.GetOuterGeometry());
-  else if (fb.IsLine())
-    street.AddHighwayLine(osmId, fb.GetOuterGeometry());
-  else
-    street.SetPin({fb.GetKeyPoint(), osmId});
-}
-
-void StreetsBuilder::InsertStreetBinding(KeyValue const & region, std::string && streetName,
-                                         FeatureBuilder & fb)
+StreetGeometry & StreetsBuilder::InsertStreet(uint64_t regionId, std::string && streetName)
 {
-  auto & regionStreets = m_regions[region.first];
-  auto & street = regionStreets[std::move(streetName)];
-  street.AddBinding(NextOsmSurrogateId(), fb.GetKeyPoint());
+  auto & regionStreets = m_regions[regionId];
+  return regionStreets[std::move(streetName)];
 }
 
 std::unique_ptr<char, JSONFreeDeleter> StreetsBuilder::MakeStreetValue(
diff --git a/generator/streets/streets_builder.hpp b/generator/streets/streets_builder.hpp
index 065b13f796..f9b6b1c1e8 100644
--- a/generator/streets/streets_builder.hpp
+++ b/generator/streets/streets_builder.hpp
@@ -46,12 +46,12 @@ private:
                            RegionStreets const & streets);
 
   void AddStreet(feature::FeatureBuilder & fb);
+  void AddStreetHighway(feature::FeatureBuilder & fb);
+  void AddStreetArea(feature::FeatureBuilder & fb);
+  void AddStreetPoint(feature::FeatureBuilder & fb);
   void AddStreetBinding(std::string && streetName, feature::FeatureBuilder & fb);
-  boost::optional<KeyValue> FindStreetRegionOwner(feature::FeatureBuilder & fb);
   boost::optional<KeyValue> FindStreetRegionOwner(m2::PointD const & point, bool needLocality = false);
-  void InsertStreet(KeyValue const & region, feature::FeatureBuilder & fb);
-  void InsertStreetBinding(KeyValue const & region, std::string && streetName,
-      feature::FeatureBuilder & fb);
+  StreetGeometry & InsertStreet(uint64_t regionId, std::string && streetName);
   std::unique_ptr<char, JSONFreeDeleter> MakeStreetValue(
       uint64_t regionId, JsonValue const & regionObject, std::string const & streetName,
       m2::RectD const & bbox, m2::PointD const & pinPoint);