diff options
author | Anatoly Serdtcev <serdtcev@maps.me> | 2019-05-06 17:38:11 +0300 |
---|---|---|
committer | Anatoly Serdtcev <serdtcev@maps.me> | 2019-06-06 19:02:30 +0300 |
commit | cd6fe4606d40a94760d4e9e17e71219fa493d08f (patch) | |
tree | 1c17753b3cddf667c853ecb9933f939ec367f9c1 /generator | |
parent | 96acf26e9af6e5a96200b48fe08e54b6e2ea6566 (diff) |
[generator:streets] Highway tracing: detect street's regions
Diffstat (limited to 'generator')
-rw-r--r-- | generator/CMakeLists.txt | 2 | ||||
-rw-r--r-- | generator/generator_tests/CMakeLists.txt | 1 | ||||
-rw-r--r-- | generator/generator_tests/street_regions_tracing_tests.cpp | 64 | ||||
-rw-r--r-- | generator/streets/street_regions_tracing.cpp | 193 | ||||
-rw-r--r-- | generator/streets/street_regions_tracing.hpp | 62 | ||||
-rw-r--r-- | generator/streets/streets_builder.cpp | 94 | ||||
-rw-r--r-- | generator/streets/streets_builder.hpp | 8 |
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); |