diff options
55 files changed, 3479 insertions, 114 deletions
diff --git a/CMakeLists.txt b/CMakeLists.txt index 783f796cb0..a5b880e87d 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -228,6 +228,7 @@ add_subdirectory(search) add_subdirectory(tracking) add_subdirectory(traffic) add_subdirectory(partners_api) +add_subdirectory(openlr) if (PLATFORM_DESKTOP) add_subdirectory(generator) diff --git a/base/base_tests/math_test.cpp b/base/base_tests/math_test.cpp index 16eb1e5f9c..cc79055856 100644 --- a/base/base_tests/math_test.cpp +++ b/base/base_tests/math_test.cpp @@ -158,3 +158,25 @@ UNIT_TEST(GCD_Test) TEST_EQUAL(my::GCD(8, 3), 1, ()); TEST_EQUAL(my::GCD(9, 3), 3, ()); } + +UNIT_TEST(LCM_Test) +{ + TEST_EQUAL(my::LCM(6, 3), 6, ()); + TEST_EQUAL(my::LCM(14, 7), 14, ()); + TEST_EQUAL(my::LCM(100, 100), 100, ()); + TEST_EQUAL(my::LCM(7, 3), 21, ()); + TEST_EQUAL(my::LCM(8, 3), 24, ()); + TEST_EQUAL(my::LCM(9, 3), 9, ()); +} + +UNIT_TEST(Sign_test) +{ + TEST_EQUAL(1, my::Sign(1), ()); + TEST_EQUAL(1, my::Sign(10.4), ()); + + TEST_EQUAL(0, my::Sign(0), ()); + TEST_EQUAL(0, my::Sign(0.0), ()); + + TEST_EQUAL(-1, my::Sign(-11), ()); + TEST_EQUAL(-1, my::Sign(-10.4), ()); +} diff --git a/base/exception.hpp b/base/exception.hpp index 87be96775e..41b614e236 100644 --- a/base/exception.hpp +++ b/base/exception.hpp @@ -32,7 +32,7 @@ private: class exception_name : public base_exception \ { \ public: \ - exception_name(char const * what, string const & msg) : base_exception(what, msg) {} \ + exception_name(char const * what, std::string const & msg) : base_exception(what, msg) {} \ } // TODO: Use SRC_LOGGING macro. diff --git a/base/math.hpp b/base/math.hpp index 396be414ea..6549fe059a 100644 --- a/base/math.hpp +++ b/base/math.hpp @@ -180,50 +180,17 @@ inline uint32_t NextPowOf2(uint32_t v) return v + 1; } +template <typename Number, + typename EnableIf = typename std::enable_if< + std::is_integral<Number>::value, void>::type> // Greatest Common Divisor -template <typename T> T GCD(T a, T b) -{ - T multiplier = 1; - T gcd = 1; - while (true) - { - if (a == 0 || b == 0) - { - gcd = std::max(a, b); - break; - } - - if (a == 1 || b == 1) - { - gcd = 1; - break; - } - - if ((a & 0x1) == 0 && (b & 0x1) == 0) - { - multiplier <<= 1; - a >>= 1; - b >>= 1; - continue; - } - - if ((a & 0x1) != 0 && (b & 0x1) != 0) - { - T const minV = std::min(a, b); - T const maxV = std::max(a, b); - a = (maxV - minV) >> 1; - b = minV; - continue; - } - - if ((a & 0x1) != 0) - std::swap(a, b); - - a >>= 1; - } - - return multiplier * gcd; -} +Number constexpr GCD(Number const a, Number const b) { return b == 0 ? a : GCD(b, a % b); } + +template <typename Number, + typename EnableIf = typename std::enable_if< + std::is_integral<Number>::value, void>::type> +// Lowest common multiple. +Number constexpr LCM(Number const a, Number const b) { return a / GCD(a, b) * b; } /// Calculate hash for the pair of values. template <typename T1, typename T2> @@ -233,4 +200,12 @@ size_t Hash(T1 const & t1, T2 const & t2) return (std::hash<T1>()(t1) ^ (std::hash<T2>()(t2) << 1)); } +template <typename Number, + typename EnableIf = typename std::enable_if< + std::is_integral<Number>::value || std::is_floating_point<Number>::value, + void>::type> +int constexpr Sign(Number const number) noexcept +{ + return number == 0 ? 0 : number > 0 ? 1 : -1; +} } diff --git a/coding/file_name_utils.cpp b/coding/file_name_utils.cpp index 1d13245cf6..a1def51637 100644 --- a/coding/file_name_utils.cpp +++ b/coding/file_name_utils.cpp @@ -12,6 +12,12 @@ void GetNameWithoutExt(string & name) name.erase(i); } +string FilenameWithoutExt(string name) +{ + GetNameWithoutExt(name); + return name; +} + string GetFileExtension(string const & name) { size_t const pos = name.find_last_of("./\\"); diff --git a/coding/file_name_utils.hpp b/coding/file_name_utils.hpp index 76629660c9..1e3ffe83d1 100644 --- a/coding/file_name_utils.hpp +++ b/coding/file_name_utils.hpp @@ -7,6 +7,7 @@ namespace my { /// Remove extension from file name. void GetNameWithoutExt(string & name); + string FilenameWithoutExt(string name); /// @return File extension with the dot or empty string if no extension found. string GetFileExtension(string const & name); diff --git a/geometry/distance.hpp b/geometry/distance.hpp index ec520e037f..cfa8ed9d0e 100644 --- a/geometry/distance.hpp +++ b/geometry/distance.hpp @@ -60,7 +60,7 @@ protected: double m_D2; }; -} +} // namespace impl template <typename PointT> class DistanceToLineSquare : public impl::CalculatedSection<PointT> { diff --git a/geometry/segment2d.cpp b/geometry/segment2d.cpp index bf7d05a12f..578dd9e7fd 100644 --- a/geometry/segment2d.cpp +++ b/geometry/segment2d.cpp @@ -6,18 +6,12 @@ namespace m2 { -bool IsPointOnSegment(m2::PointD const & pt, m2::PointD const & p1, m2::PointD const & p2) +bool IsPointOnSegmentEps(m2::PointD const & pt, m2::PointD const & p1, m2::PointD const & p2, + double eps) { - // The epsilon here is chosen quite arbitrarily, to pass paranoid - // tests and to match our real-data geometry precision. If you have - // better ideas how to check whether pt belongs to (p1, p2) segment - // more precisely or without kEps, feel free to submit a pull - // request. - double const kEps = 1e-100; - double const t = robust::OrientedS(p1, p2, pt); - if (fabs(t) > kEps) + if (fabs(t) > eps) return false; double minX = p1.x; @@ -30,6 +24,17 @@ bool IsPointOnSegment(m2::PointD const & pt, m2::PointD const & p1, m2::PointD c if (maxY < minY) swap(maxY, minY); - return pt.x >= minX && pt.x <= maxX && pt.y >= minY && pt.y <= maxY; + return pt.x >= minX - eps && pt.x <= maxX + eps && pt.y >= minY - eps && pt.y <= maxY + eps; +} + +bool IsPointOnSegment(m2::PointD const & pt, m2::PointD const & p1, m2::PointD const & p2) +{ + // The epsilon here is chosen quite arbitrarily, to pass paranoid + // tests and to match our real-data geometry precision. If you have + // better ideas how to check whether pt belongs to (p1, p2) segment + // more precisely or without kEps, feel free to submit a pull + // request. + double const kEps = 1e-100; + return IsPointOnSegmentEps(pt, p1, p2, kEps); } } // namespace m2 diff --git a/geometry/segment2d.hpp b/geometry/segment2d.hpp index e5e64bb054..838fc52e74 100644 --- a/geometry/segment2d.hpp +++ b/geometry/segment2d.hpp @@ -4,5 +4,7 @@ namespace m2 { +bool IsPointOnSegmentEps(m2::PointD const & pt, m2::PointD const & p1, m2::PointD const & p2, + double eps); bool IsPointOnSegment(m2::PointD const & pt, m2::PointD const & p1, m2::PointD const & p2); } // namespace m2 diff --git a/indexer/index.hpp b/indexer/index.hpp index 3f43d2b707..077dc5bdf9 100644 --- a/indexer/index.hpp +++ b/indexer/index.hpp @@ -208,21 +208,21 @@ private: public: template <typename F> - void ForEachInRect(F & f, m2::RectD const & rect, uint32_t scale) const + void ForEachInRect(F && f, m2::RectD const & rect, uint32_t scale) const { ReadMWMFunctor<F> implFunctor(f); ForEachInIntervals(implFunctor, covering::ViewportWithLowLevels, rect, scale); } template <typename F> - void ForEachFeatureIDInRect(F & f, m2::RectD const & rect, uint32_t scale) const + void ForEachFeatureIDInRect(F && f, m2::RectD const & rect, uint32_t scale) const { ReadFeatureIndexFunctor<F> implFunctor(f); ForEachInIntervals(implFunctor, covering::LowLevelsOnly, rect, scale); } template <typename F> - void ForEachInScale(F & f, uint32_t scale) const + void ForEachInScale(F && f, uint32_t scale) const { ReadMWMFunctor<F> implFunctor(f); ForEachInIntervals(implFunctor, covering::FullCover, m2::RectD::GetInfiniteRect(), scale); @@ -230,7 +230,7 @@ public: // "features" must be sorted using FeatureID::operator< as predicate. template <typename F> - void ReadFeatures(F & f, vector<FeatureID> const & features) const + void ReadFeatures(F && f, vector<FeatureID> const & features) const { auto fidIter = features.begin(); auto const endIter = features.end(); @@ -297,7 +297,7 @@ public: }; template <typename F> - void ForEachInRectForMWM(F & f, m2::RectD const & rect, uint32_t scale, MwmId const & id) const + void ForEachInRectForMWM(F && f, m2::RectD const & rect, uint32_t scale, MwmId const & id) const { MwmHandle const handle = GetMwmHandleById(id); if (handle.IsAlive()) @@ -311,7 +311,7 @@ public: private: template <typename F> - void ForEachInIntervals(F & f, covering::CoveringMode mode, m2::RectD const & rect, + void ForEachInIntervals(F && f, covering::CoveringMode mode, m2::RectD const & rect, uint32_t scale) const { vector<shared_ptr<MwmInfo>> mwms; diff --git a/indexer/new_feature_categories.cpp b/indexer/new_feature_categories.cpp index cded82d8f2..cc67efb220 100644 --- a/indexer/new_feature_categories.cpp +++ b/indexer/new_feature_categories.cpp @@ -17,7 +17,7 @@ NewFeatureCategories::NewFeatureCategories(editor::EditorConfig const & config) // TODO(mgsergio): Load types user can create from XML file. // TODO: Not every editable type can be created by user. // TODO(mgsergio): Store in Settings:: recent history of created types and use them here. - // Max history items count shoud be set in the config. + // Max history items count should be set in the config. Classificator const & cl = classif(); for (auto const & classificatorType : config.GetTypesThatCanBeAdded()) { diff --git a/map/framework.cpp b/map/framework.cpp index 1cce5b23d4..1a0b0c29da 100644 --- a/map/framework.cpp +++ b/map/framework.cpp @@ -3307,7 +3307,7 @@ namespace }; } // namespace -void Framework::VizualizeRoadsInRect(m2::RectD const & rect) +void Framework::VisualizeRoadsInRect(m2::RectD const & rect) { int constexpr kScale = scales::GetUpperScale(); size_t counter = 0; diff --git a/map/framework.hpp b/map/framework.hpp index 687896699c..e9c09e1e70 100644 --- a/map/framework.hpp +++ b/map/framework.hpp @@ -276,6 +276,8 @@ public: storage::CountryInfoGetter & GetCountryInfoGetter() { return *m_infoGetter; } StorageDownloadingPolicy & GetDownloadingPolicy() { return m_storageDownloadingPolicy; } + Index const & GetIndex() const { return m_model.GetIndex(); } + /// @name Bookmarks, Tracks and other UserMarks //@{ /// Scans and loads all kml files with bookmarks in WritableDir. @@ -313,7 +315,7 @@ public: m2::PointD GetSearchMarkSize(SearchMarkType searchMarkType); // Utilities - void VizualizeRoadsInRect(m2::RectD const & rect); + void VisualizeRoadsInRect(m2::RectD const & rect); protected: // search::ViewportSearchCallback::Delegate overrides: @@ -655,7 +657,7 @@ public: } /// Set parse to false if you don't need all feature fields ready. /// TODO(AlexZ): Refactor code which uses this method to get rid of it. - /// FeatureType instances shoud not be used outside ForEach* core methods. + /// FeatureType instances should not be used outside ForEach* core methods. WARN_UNUSED_RESULT bool GetFeatureByID(FeatureID const & fid, FeatureType & ft) const; void MemoryWarning(); @@ -23,7 +23,7 @@ HEADERS += defines.hpp CONFIG *= desktop } -SUBDIRS = 3party base coding geometry editor indexer routing search +SUBDIRS = 3party base coding geometry editor indexer routing search openlr !CONFIG(osrm) { SUBDIRS *= platform stats storage @@ -34,6 +34,10 @@ SUBDIRS = 3party base coding geometry editor indexer routing search generator_tool.subdir = generator/generator_tool generator_tool.depends = $$SUBDIRS SUBDIRS *= generator_tool + + openlr_stat.subdir = openlr/openlr_stat + openlr_stat.depends = $$SUBDIRS + SUBDIRS *= openlr_stat } # Integration tests dependencies for gtool. @@ -251,11 +255,15 @@ SUBDIRS = 3party base coding geometry editor indexer routing search SUBDIRS *= partners_api_tests tracking_tests.subdir = tracking/tracking_tests - tracking_tests.depends = 3party base routing tracking platform_tests_support platform coding geometry + tracking_tests.depends = 3party base routing tracking platform_tests_support platform coding geometry SUBDIRS *= tracking_tests traffic_tests.subdir = traffic/traffic_tests traffic_tests.depends = 3party base routing traffic platform_tests_support platform coding geometry SUBDIRS *= traffic_tests + + openlr_tests.subdir = openlr/openlr_tests + opnelr_tests.depends = $$SUBDIRS platform_tests_support + SUBDIRS *= openlr_tests } # !no-tests } # !gtool diff --git a/openlr/CMakeLists.txt b/openlr/CMakeLists.txt new file mode 100644 index 0000000000..747ff52bba --- /dev/null +++ b/openlr/CMakeLists.txt @@ -0,0 +1,24 @@ +project(openlr) + +set( + SRC + openlr_model.cpp + openlr_model.hpp + openlr_sample.cpp + openlr_sample.hpp + openlr_simple_decoder.cpp + openlr_simple_decoder.hpp + openlr_simple_parser.cpp + openlr_simple_parser.hpp + road_info_getter.cpp + road_info_getter.hpp + road_type_checkers.cpp + road_type_checkers.hpp + router.cpp + router.hpp + way_point.hpp +) + +add_library(${PROJECT_NAME} ${SRC}) +add_subdirectory(openlr_stat) +omim_add_test_subdirectory(openlr_tests) diff --git a/openlr/openlr.pro b/openlr/openlr.pro new file mode 100644 index 0000000000..c332f3d51d --- /dev/null +++ b/openlr/openlr.pro @@ -0,0 +1,27 @@ +# Match OpenLR data to MWMs. +TARGET = openlr +TEMPLATE = lib +CONFIG += staticlib warn_on + +ROOT_DIR = .. + +include($$ROOT_DIR/common.pri) + +SOURCES += \ + openlr_model.cpp \ + openlr_sample.cpp \ + openlr_simple_decoder.cpp \ + openlr_simple_parser.cpp \ + road_info_getter.cpp \ + road_type_checkers.cpp \ + router.cpp \ + +HEADERS += \ + openlr_model.hpp \ + openlr_sample.hpp \ + openlr_simple_decoder.hpp \ + openlr_simple_parser.hpp \ + road_info_getter.hpp \ + road_type_checkers.hpp \ + router.hpp \ + way_point.hpp \ diff --git a/openlr/openlr_model.cpp b/openlr/openlr_model.cpp new file mode 100644 index 0000000000..8c6cfb2af1 --- /dev/null +++ b/openlr/openlr_model.cpp @@ -0,0 +1,15 @@ +#include "openlr/openlr_model.hpp" + +#include "geometry/mercator.hpp" + +namespace openlr +{ +// LinearSegment ----------------------------------------------------------------------------------- +std::vector<m2::PointD> LinearSegment::GetMercatorPoints() const +{ + std::vector<m2::PointD> points; + for (auto const & point : m_locationReference.m_points) + points.push_back(MercatorBounds::FromLatLon(point.m_latLon)); + return points; +} +} // namespace openlr diff --git a/openlr/openlr_model.hpp b/openlr/openlr_model.hpp new file mode 100644 index 0000000000..d68fca99ad --- /dev/null +++ b/openlr/openlr_model.hpp @@ -0,0 +1,107 @@ +#pragma once + +#include "geometry/latlon.hpp" +#include "geometry/point2d.hpp" + +#include <limits> + +namespace openlr +{ +// The form of way (FOW) describes the physical road type of a line. +enum class FormOfWay +{ + // The physical road type is unknown. + Undefined, + // A road permitted for motorized vehicles only in combination with a prescribed minimum speed. + // It has two or more physically separated carriageways and no single level-crossings. + Motorway, + // A road with physically separated carriageways regardless of the number of lanes. + // If a road is also a motorway, it should be coded as such and not as a multiple carriageway. + MultipleCarriageway, + // All roads without separate carriageways are considered as roads with a single carriageway. + SingleCarriageway, + // A road which forms a ring on which traffic traveling in only one direction is allowed. + Roundabout, + // An open area (partly) enclosed by roads which is used for non-traffic purposes + // and which is not a Roundabout. + Trafficsquare, + // A road especially designed to enter or leave a line. + Sliproad, + // The physical road type is known, but does not fit into one of the other categories. + Other, + // A path only allowed for bikes. + BikePath, + // A path only allowed for pedestrians. + Footpath, + NotAValue +}; + +// The functional road class (FRC) of a line is a road classification based on the importance +// of the road represented by the line. +enum class FunctionalRoadClass +{ + // Main road, highest importance. + FRC0, + // First class road. + FRC1, + + // Other road classes. + + FRC2, + FRC3, + FRC4, + FRC5, + FRC6, + FRC7, + NotAValue +}; + +struct LocationReferencePoint +{ + // Coordinates of the point of interest. + ms::LatLon m_latLon = ms::LatLon::Zero(); + // The bearing (BEAR) describes the angle between the true North and a line which is defined + // by the coordinate of the LocationReferencePoint and a coordinate which is BEARDIST along + // the line defined by the LocationReference-point attributes. + // For more information see OpenLR-Whitepaper `Bearing' section. + uint8_t m_bearing = 0; + FunctionalRoadClass m_functionalRoadClass = FunctionalRoadClass::NotAValue; + FormOfWay m_formOfWay = FormOfWay::NotAValue; + + // The distance to next point field describes the distance to the next LocationReferencePoint + // in the topological connection of the LocationReferencePoints. The distance is measured in meters + // and is calculated along the location reference path between two subsequent LR-points. + // The last LRP has the distance value 0. + // Should not be used in the last point of a segment. + uint32_t m_distanceToNextPoint = 0; + // The lowest FunctionalRoadClass to the next point (LFRCNP) is the lowest FunctionalRoadClass + // value which appears in the location reference path between two consecutive LR-points. + // This information could be used to limit the number of road classes which need to be + // scanned during the decoding. + // Should not be used in the last point of a segment. + FunctionalRoadClass m_lfrcnp = FunctionalRoadClass::NotAValue; + bool m_againstDrivingDirection = false; +}; + +struct LinearLocationReference +{ + std::vector<LocationReferencePoint> m_points; + uint32_t m_positiveOffsetMeters = 0; + uint32_t m_negativeOffsetMeters = 0; +}; + +struct LinearSegment +{ + static auto constexpr kInvalidSegmentId = std::numeric_limits<uint32_t>::max(); + + std::vector<m2::PointD> GetMercatorPoints() const; + + // TODO(mgsergio): Think of using openlr::PartnerSegmentId + uint32_t m_segmentId = kInvalidSegmentId; + // TODO(mgsergio): Make sure that one segment cannot contain + // more than one location reference. + LinearLocationReference m_locationReference; + uint32_t m_segmentLengthMeters = 0; + // uint32_t m_segmentRefSpeed; Always null in partners data. (No docs found). +}; +} // namespace openlr diff --git a/openlr/openlr_sample.cpp b/openlr/openlr_sample.cpp new file mode 100644 index 0000000000..68efa6f9ee --- /dev/null +++ b/openlr/openlr_sample.cpp @@ -0,0 +1,161 @@ +#include "openlr/openlr_sample.hpp" + +#include "indexer/index.hpp" + +#include "base/string_utils.hpp" + +#include <cerrno> +#include <cstring> +#include <fstream> + +namespace +{ +void ParseMWMSegments(std::string const & line, uint32_t const lineNumber, + std::vector<openlr::SampleItem::MWMSegment> & segments, Index const & index) +{ + std::vector<string> parts; + strings::ParseCSVRow(line, '=', parts); + + for (auto const & seg : parts) + { + std::vector<string> segParts; + strings::ParseCSVRow(seg, '-', segParts); + CHECK_EQUAL(segParts.size(), 5, ()); + + auto const mwmId = index.GetMwmIdByCountryFile(platform::CountryFile(segParts[0])); + + uint32_t featureIndex; + if (!strings::to_uint(segParts[1], featureIndex)) + MYTHROW(openlr::SamplePoolLoadError, ("Can't parse MWMSegment", seg, "line:", lineNumber)); + + uint32_t segId; + if (!strings::to_uint(segParts[2], segId)) + MYTHROW(openlr::SamplePoolLoadError, ("Can't parse MWMSegment", seg, "line:", lineNumber)); + + bool const isForward = (segParts[3] == "fwd"); + double length = 0; + if (!strings::to_double(segParts[4], length)) + MYTHROW(openlr::SamplePoolLoadError, ("Can't parse MWMSegment", seg, "line:", lineNumber)); + + segments.push_back({FeatureID(mwmId, featureIndex), segId, isForward, length}); + } +} + +void ParseSampleItem(std::string const & line, uint32_t const lineNumber, openlr::SampleItem & item, + Index const & index) +{ + std::vector<string> parts; + strings::ParseCSVRow(line, '\t', parts); + CHECK_GREATER_OR_EQUAL(parts.size(), 2, ()); + CHECK_LESS_OR_EQUAL(parts.size(), 3, ()); + + auto nextFieldIndex = 0; + if (parts.size() == 3) + { + item.m_evaluation = openlr::ParseItemEvaluation(parts[nextFieldIndex]); + ++nextFieldIndex; + } + else + { + item.m_evaluation = openlr::ItemEvaluation::Unevaluated; + } + + if (!strings::to_uint(parts[nextFieldIndex], item.m_partnerSegmentId.Get())) + { + MYTHROW(openlr::SamplePoolLoadError, ("Error: can't parse field", nextFieldIndex, + "(number expected) in line:", lineNumber)); + } + ++nextFieldIndex; + + ParseMWMSegments(parts[nextFieldIndex], lineNumber, item.m_segments, index); +} +} // namepsace + +namespace openlr +{ +ItemEvaluation ParseItemEvaluation(std::string const & s) +{ + if (s == "Unevaluated") + return openlr::ItemEvaluation::Unevaluated; + + if (s == "Positive") + return openlr::ItemEvaluation::Positive; + + if (s == "Negative") + return openlr::ItemEvaluation::Negative; + + if (s == "RelPositive") + return openlr::ItemEvaluation::RelPositive; + + if (s == "RelNegative") + return openlr::ItemEvaluation::RelNegative; + + if (s == "Ignore") + return openlr::ItemEvaluation::Ignore; + + return openlr::ItemEvaluation::NotAValue; +} + +std::string ToString(ItemEvaluation const e) +{ + switch (e) + { + case openlr::ItemEvaluation::Unevaluated: return "Unevaluated"; + case openlr::ItemEvaluation::Positive: return "Positive"; + case openlr::ItemEvaluation::Negative: return "Negative"; + case openlr::ItemEvaluation::RelPositive: return "RelPositive"; + case openlr::ItemEvaluation::RelNegative: return "RelNegative"; + case openlr::ItemEvaluation::Ignore: return "Ignore"; + default: return "NotAValue"; + } +} + +SamplePool LoadSamplePool(std::string const & fileName, Index const & index) +{ + std::ifstream sample(fileName); + if (!sample.is_open()) + MYTHROW(SamplePoolLoadError, ("Can't read from file", fileName, strerror(errno))); + + SamplePool pool; + for (struct {uint32_t lineNumber = 0; string line; } st; getline(sample, st.line); ++st.lineNumber) + { + SampleItem item = SampleItem::Uninitialized(); + ParseSampleItem(st.line, st.lineNumber, item, index); + pool.push_back(item); + } + + return pool; +} + +void SaveSamplePool(std::string const & fileName, SamplePool const & sample, + bool const saveEvaluation) +{ + LOG(LDEBUG, ("Saving sample to file:", fileName)); + std::ofstream out(fileName); + if (!out.is_open()) + MYTHROW(SamplePoolSaveError, ("Can't write to file", fileName, strerror(errno))); + out << std::fixed; // Avoid scientific notation cause '-' is used as fields separator. + for (auto const & item : sample) + { + if (saveEvaluation) + out << ToString(item.m_evaluation) << '\t'; + + out << item.m_partnerSegmentId.Get() << '\t'; + + for (auto it = begin(item.m_segments); it != end(item.m_segments); ++it) + { + auto const & fid = it->m_fid; + out << fid.m_mwmId.GetInfo()->GetCountryName() << '-' + << fid.m_index << '-' << it->m_segId + << '-' << (it->m_isForward ? "fwd" : "bwd") + << '-' << it->m_length; + + if (next(it) != end(item.m_segments)) + out << '='; + } + out << endl; + } + if (out.fail()) + MYTHROW(SamplePoolSaveError, ("An error occured while writing file", fileName, strerror(errno))); +} +} // namespace openlr diff --git a/openlr/openlr_sample.hpp b/openlr/openlr_sample.hpp new file mode 100644 index 0000000000..cefff0df8f --- /dev/null +++ b/openlr/openlr_sample.hpp @@ -0,0 +1,75 @@ +#pragma once + +#include "indexer/feature_decl.hpp" + +#include "base/exception.hpp" +#include "base/newtype.hpp" + +#include <string> +#include <vector> + +class Index; + +namespace openlr +{ +NEWTYPE(uint32_t, PartnerSegmentId); + +enum class ItemEvaluation +{ + Unevaluated, + Positive, + Negative, + RelPositive, + RelNegative, + Ignore, + NotAValue +}; + +ItemEvaluation ParseItemEvaluation(std::string const & s); +std::string ToString(ItemEvaluation const e); + +struct SampleItem +{ + struct MWMSegment + { + MWMSegment(FeatureID const & fid, uint32_t const segId, bool const isForward, + double const length) + : m_fid(fid) + , m_segId(segId) + , m_isForward(isForward) + , m_length(length) + { + } + + FeatureID const m_fid; + uint32_t const m_segId; + bool const m_isForward; + double const m_length; + }; + + explicit SampleItem(PartnerSegmentId const partnerSegmentId, + ItemEvaluation const evaluation = ItemEvaluation::Unevaluated) + : m_partnerSegmentId(partnerSegmentId) + , m_evaluation(evaluation) + { + } + + static SampleItem Uninitialized() { return {}; } + + PartnerSegmentId m_partnerSegmentId; + std::vector<MWMSegment> m_segments; + ItemEvaluation m_evaluation; + +private: + SampleItem() = default; +}; + +DECLARE_EXCEPTION(SamplePoolLoadError, RootException); +DECLARE_EXCEPTION(SamplePoolSaveError, RootException); + +using SamplePool = std::vector<SampleItem>; + +SamplePool LoadSamplePool(std::string const & fileName, Index const & index); +void SaveSamplePool(std::string const & fileName, SamplePool const & sample, + bool const saveEvaluation); +} // namespace openlr diff --git a/openlr/openlr_simple_decoder.cpp b/openlr/openlr_simple_decoder.cpp new file mode 100644 index 0000000000..2ba8d2e8f7 --- /dev/null +++ b/openlr/openlr_simple_decoder.cpp @@ -0,0 +1,228 @@ +#include "openlr/openlr_simple_decoder.hpp" + +#include "openlr/openlr_model.hpp" +#include "openlr/openlr_sample.hpp" +#include "openlr/openlr_simple_parser.hpp" +#include "openlr/road_info_getter.hpp" +#include "openlr/router.hpp" +#include "openlr/way_point.hpp" + +#include "routing/car_model.hpp" +#include "routing/features_road_graph.hpp" +#include "routing/road_graph.hpp" + +#include "indexer/classificator.hpp" +#include "indexer/index.hpp" + +#include "geometry/polyline2d.hpp" + +#include "base/logging.hpp" +#include "base/math.hpp" + +#include "std/algorithm.hpp" +#include "std/fstream.hpp" +#include "std/thread.hpp" + +using namespace routing; + +namespace openlr +{ +namespace +{ +size_t constexpr kCacheLineSize = 64; + +struct alignas(kCacheLineSize) Stats +{ + void Add(Stats const & rhs) + { + m_shortRoutes += rhs.m_shortRoutes; + m_zeroCanditates += rhs.m_zeroCanditates; + m_moreThanOneCandidate += rhs.m_moreThanOneCandidate; + m_routeIsNotCalculated += rhs.m_routeIsNotCalculated; + m_total += rhs.m_total; + } + + uint32_t m_shortRoutes = 0; + uint32_t m_zeroCanditates = 0; + uint32_t m_moreThanOneCandidate = 0; + uint32_t m_routeIsNotCalculated = 0; + uint32_t m_total = 0; +}; + +openlr::SamplePool MakeSamplePool(std::vector<LinearSegment> const & segments, + std::vector<IRoadGraph::TEdgeVector> const & paths) +{ + openlr::SamplePool pool; + for (size_t i = 0; i < segments.size(); ++i) + { + auto const & segment = segments[i]; + auto const & path = paths[i]; + + if (path.empty()) + continue; + + pool.emplace_back(openlr::PartnerSegmentId(segment.m_segmentId)); + auto & sampleItem = pool.back(); + + for (auto const & edge : path) + { + CHECK(!edge.IsFake(), ("There should be no fake edges in the path.")); + + sampleItem.m_segments.emplace_back( + edge.GetFeatureId(), edge.GetSegId(), edge.IsForward(), + MercatorBounds::DistanceOnEarth(edge.GetStartJunction().GetPoint(), + edge.GetEndJunction().GetPoint())); + } + } + return pool; +} +} // namespace + +// OpenLRSimpleDecoder::SegmentsFilter ------------------------------------------------------------- +OpenLRSimpleDecoder::SegmentsFilter::SegmentsFilter(string const & idsPath, + bool const multipointsOnly) + : m_idsSet(false), m_multipointsOnly(multipointsOnly) +{ + if (idsPath.empty()) + return; + + ifstream ifs(idsPath); + CHECK(ifs, ("Can't find", idsPath)); + m_ids.insert(istream_iterator<uint32_t>(ifs), istream_iterator<uint32_t>()); + + CHECK(!ifs, ("Garbage in", idsPath)); + m_idsSet = true; +} + +bool OpenLRSimpleDecoder::SegmentsFilter::Matches(LinearSegment const & segment) const +{ + if (m_multipointsOnly && segment.m_locationReference.m_points.size() == 2) + return false; + if (m_idsSet && m_ids.count(segment.m_segmentId) == 0) + return false; + return true; +} + +// OpenLRSimpleDecoder ----------------------------------------------------------------------------- +// static +int const OpenLRSimpleDecoder::kHandleAllSegments = -1; + +OpenLRSimpleDecoder::OpenLRSimpleDecoder(string const & dataFilename, vector<Index> const & indexes) + : m_indexes(indexes) +{ + auto const load_result = m_document.load_file(dataFilename.data()); + if (!load_result) + MYTHROW(DecoderError, ("Can't load file", dataFilename, ":", load_result.description())); +} + +void OpenLRSimpleDecoder::Decode(string const & outputFilename, int const segmentsToHandle, + SegmentsFilter const & filter, int const numThreads) +{ + // TODO(mgsergio): Feed segments directly to the decoder. Parsing should not + // take place inside decoder process. + vector<LinearSegment> segments; + if (!ParseOpenlr(m_document, segments)) + MYTHROW(DecoderError, ("Can't parse data.")); + + my::EraseIf(segments, + [&filter](LinearSegment const & segment) { return !filter.Matches(segment); }); + + if (segmentsToHandle != kHandleAllSegments && segmentsToHandle < segments.size()) + segments.resize(segmentsToHandle); + + sort(segments.begin(), segments.end(), my::LessBy(&LinearSegment::m_segmentId)); + + vector<IRoadGraph::TEdgeVector> paths(segments.size()); + + // This code computes the most optimal (in the sense of cache lines + // occupancy) batch size. + size_t constexpr a = my::LCM(sizeof(LinearSegment), kCacheLineSize) / sizeof(LinearSegment); + size_t constexpr b = + my::LCM(sizeof(IRoadGraph::TEdgeVector), kCacheLineSize) / sizeof(IRoadGraph::TEdgeVector); + size_t constexpr kBatchSize = my::LCM(a, b); + size_t constexpr kProgressFrequency = 100; + + auto worker = [&segments, &paths, kBatchSize, kProgressFrequency, numThreads, this]( + size_t threadNum, Index const & index, Stats & stats) { + FeaturesRoadGraph roadGraph(index, IRoadGraph::Mode::ObeyOnewayTag, + make_unique<CarModelFactory>()); + RoadInfoGetter roadInfoGetter(index); + Router router(roadGraph, roadInfoGetter); + + size_t const numSegments = segments.size(); + + vector<WayPoint> points; + + for (size_t i = threadNum * kBatchSize; i < numSegments; i += numThreads * kBatchSize) + { + for (size_t j = i; j < numSegments && j < i + kBatchSize; ++j) + { + auto const & segment = segments[j]; + auto const & ref = segment.m_locationReference; + + points.clear(); + for (auto const & point : ref.m_points) + points.emplace_back(point); + + auto positiveOffsetM = ref.m_positiveOffsetMeters; + if (positiveOffsetM >= points[0].m_distanceToNextPointM) + { + LOG(LWARNING, ("Wrong positive offset for segment:", segment.m_segmentId)); + positiveOffsetM = 0; + } + + auto negativeOffsetM = ref.m_negativeOffsetMeters; + if (negativeOffsetM >= points[points.size() - 2].m_distanceToNextPointM) + { + LOG(LWARNING, ("Wrong negative offset for segment:", segment.m_segmentId)); + negativeOffsetM = 0; + } + + { + double expectedLength = 0; + for (size_t i = 0; i + 1 < points.size(); ++i) + expectedLength += points[i].m_distanceToNextPointM; + + if (positiveOffsetM + negativeOffsetM >= expectedLength) + { + LOG(LINFO, + ("Skipping", segment.m_segmentId, "due to wrong positive/negative offsets.")); + ++stats.m_routeIsNotCalculated; + continue; + } + } + + auto & path = paths[j]; + if (!router.Go(points, positiveOffsetM, negativeOffsetM, path)) + ++stats.m_routeIsNotCalculated; + + ++stats.m_total; + + if (stats.m_total % kProgressFrequency == 0) + LOG(LINFO, ("Thread", threadNum, "processed:", stats.m_total)); + } + } + }; + + vector<Stats> stats(numThreads); + vector<thread> workers; + for (size_t i = 1; i < numThreads; ++i) + workers.emplace_back(worker, i, ref(m_indexes[i]), ref(stats[i])); + worker(0 /* threadNum */, m_indexes[0], stats[0]); + for (auto & worker : workers) + worker.join(); + + auto const samplePool = MakeSamplePool(segments, paths); + SaveSamplePool(outputFilename, samplePool, false /* saveEvaluation */); + + Stats allStats; + for (auto const & s : stats) + allStats.Add(s); + + LOG(LINFO, ("Parsed segments:", allStats.m_total, + "Routes failed:", allStats.m_routeIsNotCalculated, + "Short routes:", allStats.m_shortRoutes, + "Ambiguous routes:", allStats.m_moreThanOneCandidate, + "Path is not reconstructed:", allStats.m_zeroCanditates)); +} +} // namespace openlr diff --git a/openlr/openlr_simple_decoder.hpp b/openlr/openlr_simple_decoder.hpp new file mode 100644 index 0000000000..977e109c2a --- /dev/null +++ b/openlr/openlr_simple_decoder.hpp @@ -0,0 +1,47 @@ +#pragma once + +#include "base/exception.hpp" + +#include "3party/pugixml/src/pugixml.hpp" + +#include <cstdint> +#include <string> +#include <unordered_set> +#include <vector> + +class Index; + +namespace openlr +{ +struct LinearSegment; + +DECLARE_EXCEPTION(DecoderError, RootException); + +class OpenLRSimpleDecoder +{ +public: + class SegmentsFilter + { + public: + SegmentsFilter(std::string const & idsPath, bool const multipointsOnly); + + bool Matches(LinearSegment const & segment) const; + + private: + std::unordered_set<uint32_t> m_ids; + bool m_idsSet; + bool const m_multipointsOnly; + }; + + static int const kHandleAllSegments; + + OpenLRSimpleDecoder(std::string const & dataFilename, std::vector<Index> const & indexes); + + void Decode(std::string const & outputFilename, int segmentsToHandle, + SegmentsFilter const & filter, int numThreads); + +private: + std::vector<Index> const & m_indexes; + pugi::xml_document m_document; +}; +} // namespace openlr diff --git a/openlr/openlr_simple_parser.cpp b/openlr/openlr_simple_parser.cpp new file mode 100644 index 0000000000..d329cdf65f --- /dev/null +++ b/openlr/openlr_simple_parser.cpp @@ -0,0 +1,275 @@ +#include "openlr/openlr_simple_parser.hpp" +#include "openlr/openlr_model.hpp" + +#include "geometry/mercator.hpp" + +#include "base/logging.hpp" + +#include "std/cstring.hpp" +#include "std/type_traits.hpp" + +#include "3party/pugixml/src/pugixml.hpp" + +namespace // Primitive utilities to handle simple OpenLR-like XML data. +{ +template <typename Value> +bool ParseInteger(pugi::xml_node const & node, Value & value) +{ + if (!node) + return false; + value = static_cast<Value>(is_signed<Value>::value + ? node.text().as_int() + : node.text().as_uint()); + return true; +} + +bool GetLatLon(pugi::xml_node const & node, int32_t & lat, int32_t & lon) +{ + if (!ParseInteger(node.child("olr:latitude"), lat) || + !ParseInteger(node.child("olr:longitude"), lon)) + { + return false; + } + + return true; +} + +// This helper is used to parse records like this: +// <olr:lfrcnp olr:table="olr001_FunctionalRoadClass" olr:code="4"/> +template <typename Value> +bool ParseTableValue(pugi::xml_node const & node, Value & value) +{ + if (!node) + return false; + value = static_cast<Value>(is_signed<Value>::value + ? node.attribute("olr:code").as_int() + : node.attribute("olr:code").as_uint()); + return true; +} + +pugi::xml_node GetLinearLocationReference(pugi::xml_node const & node) +{ + // There should be only one linear location reference child of a location reference. + return node.select_node(".//olr:locationReference/olr:optionLinearLocationReference").node(); +} + +// This helper is used do deal with xml nodes of the form +// <node> +// <value>integer<value> +// </node> +template <typename Value> +bool ParseValue(pugi::xml_node const & node, Value & value) +{ + auto const valueNode = node.child("olr:value"); + return ParseInteger(valueNode, value); +} + +template <typename Value> +bool ParseValueIfExists(pugi::xml_node const & node, Value & value) +{ + if (!node) + return true; + return ParseValue(node, value); +} +} // namespace + +namespace // OpenLR tools and abstractions +{ +bool GetFirstCoordinate(pugi::xml_node const & node, ms::LatLon & latLon) +{ + int32_t lat, lon; + if (!GetLatLon(node.child("olr:coordinate"), lat, lon)) + return false; + + latLon.lat = ((lat - my::Sign(lat) * 0.5) * 360) / (1 << 24); + latLon.lon = ((lon - my::Sign(lon) * 0.5) * 360) / (1 << 24); + + return true; +} + +bool GetCoordinate(pugi::xml_node const & node, ms::LatLon const & firstCoord, ms::LatLon & latLon) +{ + int32_t lat, lon; + if (!GetLatLon(node.child("olr:coordinate"), lat, lon)) + return false; + + latLon.lat = firstCoord.lat + static_cast<double>(lat) / 100000; + latLon.lon = firstCoord.lon + static_cast<double>(lon) / 100000; + + return true; +} + +bool ParseLineProperties(pugi::xml_node const & linePropNode, + openlr::LocationReferencePoint & locPoint) +{ + if (!linePropNode) + { + LOG(LERROR, ("linePropNode is NULL")); + return false; + } + + if (!ParseTableValue(linePropNode.child("olr:frc"), locPoint.m_functionalRoadClass)) + { + LOG(LERROR, ("Can't parse functional road class")); + return false; + } + + if (!ParseTableValue(linePropNode.child("olr:fow"), locPoint.m_formOfWay)) + { + LOG(LERROR, ("Can't parse form of a way")); + return false; + } + + if (!ParseValue(linePropNode.child("olr:bearing"), locPoint.m_bearing)) + { + LOG(LERROR, ("Can't parse bearing")); + return false; + } + + return true; +} + +bool ParsePathProperties(pugi::xml_node const & locPointNode, + openlr::LocationReferencePoint & locPoint) +{ + // Last point does not contain path properties. + if (strcmp(locPointNode.name(), "olr:last") == 0) + return true; + + auto const propNode = locPointNode.child("olr:pathProperties"); + if (!propNode) + { + LOG(LERROR, ("Can't parse path properties")); + return false; + } + + if (!ParseValue(propNode.child("olr:dnp"), locPoint.m_distanceToNextPoint)) + { + LOG(LERROR, ("Can't parse dnp")); + return false; + } + + if (!ParseTableValue(propNode.child("olr:lfrcnp"), locPoint.m_lfrcnp)) + { + LOG(LERROR, ("Can't parse lfrcnp")); + return false; + } + + auto const directionNode = propNode.child("olr:againstDrivingDirection"); + if (!directionNode) + { + LOG(LERROR, ("Can't parse driving direction")); + return false; + } + locPoint.m_againstDrivingDirection = directionNode.text().as_bool(); + + return true; +} + +bool ParseLocationReferencePoint(pugi::xml_node const & locPointNode, + openlr::LocationReferencePoint & locPoint) +{ + if (!GetFirstCoordinate(locPointNode, locPoint.m_latLon)) + { + LOG(LERROR, ("Can't get first coordinate")); + return false; + } + + return ParseLineProperties(locPointNode.child("olr:lineProperties"), locPoint) && + ParsePathProperties(locPointNode, locPoint); +} + +bool ParseLocationReferencePoint(pugi::xml_node const & locPointNode, ms::LatLon const & firstPoint, + openlr::LocationReferencePoint & locPoint) +{ + if (!GetCoordinate(locPointNode, firstPoint, locPoint.m_latLon)) + { + LOG(LERROR, ("Can't get last coordinate")); + return false; + } + + return ParseLineProperties(locPointNode.child("olr:lineProperties"), locPoint) && + ParsePathProperties(locPointNode, locPoint); +} + +bool ParseLinearLocationReference(pugi::xml_node const & locRefNode, + openlr::LinearLocationReference & locRef) +{ + if (!locRefNode) + { + LOG(LERROR, ("Can't get loaction reference")); + return false; + } + + { + openlr::LocationReferencePoint point; + if (!ParseLocationReferencePoint(locRefNode.child("olr:first"), point)) + return false; + locRef.m_points.push_back(point); + } + + for (auto const pointNode : locRefNode.select_nodes("olr:intermediates")) + { + openlr::LocationReferencePoint point; + if (!ParseLocationReferencePoint(pointNode.node(), locRef.m_points.back().m_latLon, point)) + return false; + locRef.m_points.push_back(point); + } + + { + openlr::LocationReferencePoint point; + if (!ParseLocationReferencePoint(locRefNode.child("olr:last"), locRef.m_points.back().m_latLon, + point)) + return false; + locRef.m_points.push_back(point); + } + + if (!ParseValueIfExists(locRefNode.child("olr:positiveOffset"), locRef.m_positiveOffsetMeters)) + { + LOG(LERROR, ("Can't parse positive offset")); + return false; + } + + if(!ParseValueIfExists(locRefNode.child("olr:negativeOffset"), locRef.m_negativeOffsetMeters)) + { + LOG(LERROR, ("Can't parse negative offset")); + return false; + } + + return true; +} + +bool ParseSegment(pugi::xml_node const & segmentNode, openlr::LinearSegment & segment) +{ + if (!ParseInteger(segmentNode.child("ReportSegmentID"), segment.m_segmentId)) + { + LOG(LERROR, ("Can't parse segment id")); + return false; + } + + if (!ParseInteger(segmentNode.child("segmentLength"), segment.m_segmentLengthMeters)) + { + LOG(LERROR, ("Can't parse segment length")); + return false; + } + + auto const locRefNode = GetLinearLocationReference(segmentNode); + return ParseLinearLocationReference(locRefNode, segment.m_locationReference); +} +} // namespace + +namespace openlr +{ +// Functions --------------------------------------------------------------------------------------- +bool ParseOpenlr(pugi::xml_document const & document, vector<LinearSegment> & segments) +{ + for (auto const segmentXpathNode : document.select_nodes("//reportSegments")) + { + LinearSegment segment; + if (!ParseSegment(segmentXpathNode.node(), segment)) + return false; + segments.push_back(segment); + } + return true; +} +} // namespace openlr diff --git a/openlr/openlr_simple_parser.hpp b/openlr/openlr_simple_parser.hpp new file mode 100644 index 0000000000..20a3d58f48 --- /dev/null +++ b/openlr/openlr_simple_parser.hpp @@ -0,0 +1,14 @@ +#pragma once + +#include "std/vector.hpp" + +namespace pugi +{ +class xml_document; +} // namespace pugi + +namespace openlr +{ +struct LinearSegment; +bool ParseOpenlr(pugi::xml_document const & document, vector<LinearSegment> & segments); +} // namespace openlr diff --git a/openlr/openlr_stat/CMakeLists.txt b/openlr/openlr_stat/CMakeLists.txt new file mode 100644 index 0000000000..dbaaaaf697 --- /dev/null +++ b/openlr/openlr_stat/CMakeLists.txt @@ -0,0 +1,27 @@ +project(openlr_stat) + +set( + SRC + openlr_stat.cpp +) + +add_executable(${PROJECT_NAME} ${SRC}) +omim_link_libraries(${PROJECT_NAME} + openlr + routing + indexer + editor + platform + geometry + coding + base + gflags + jansson + oauthcpp + opening_hours + protobuf + pugixml + stats_client + ${Qt5Core_LIBRARIES} + ${LIBZ} +) diff --git a/openlr/openlr_stat/openlr_stat.cpp b/openlr/openlr_stat/openlr_stat.cpp new file mode 100644 index 0000000000..f2448aa633 --- /dev/null +++ b/openlr/openlr_stat/openlr_stat.cpp @@ -0,0 +1,119 @@ +#include "openlr/openlr_simple_decoder.hpp" + +#include "indexer/classificator_loader.hpp" +#include "indexer/index.hpp" + +#include "platform/local_country_file.hpp" +#include "platform/local_country_file_utils.hpp" +#include "platform/platform.hpp" + +#include "coding/file_name_utils.hpp" + +#include "std/cstdint.hpp" +#include "std/cstdio.hpp" +#include "std/vector.hpp" + +#include "3party/gflags/src/gflags/gflags.h" + +DEFINE_string(input, "", "Path to OpenLR file."); +DEFINE_string(output, "output.txt", "Path to output file"); +DEFINE_string(mwms_path, "", "Path to a folder with mwms."); +DEFINE_int32(limit, -1, "Max number of segments to handle. -1 for all."); +DEFINE_bool(multipoints_only, false, "Only segments with multiple points to handle."); +DEFINE_int32(num_threads, 1, "Number of threads."); +DEFINE_string(ids_path, "", "Path to a file with segment ids to process."); + +using namespace openlr; + +namespace +{ +const int32_t kMinNumThreads = 1; +const int32_t kMaxNumThreads = 128; + +void LoadIndexes(string const & pathToMWMFolder, vector<Index> & indexes) +{ + Platform::FilesList files; + Platform::GetFilesByRegExp(pathToMWMFolder, string(".*\\") + DATA_FILE_EXTENSION, files); + for (auto const & fileName : files) + { + + auto const fullFileName = my::JoinFoldersToPath({pathToMWMFolder}, fileName); + ModelReaderPtr reader(GetPlatform().GetReader(fullFileName, "f")); + platform::LocalCountryFile localFile(pathToMWMFolder, + platform::CountryFile(my::FilenameWithoutExt(fileName)), + version::ReadVersionDate(reader)); + LOG(LINFO, ("Found mwm:", fullFileName)); + try + { + localFile.SyncWithDisk(); + for (auto & index : indexes) + { + CHECK_EQUAL(index.RegisterMap(localFile).second, MwmSet::RegResult::Success, + ("Can't register mwm:", localFile)); + } + } + catch (RootException const & ex) + { + CHECK(false, (ex.Msg(), "Bad mwm file:", localFile)); + } + } +} + +bool ValidateLimit(char const * flagname, int32_t value) +{ + if (value < -1) + { + printf("Invalid value for --%s: %d, must be greater or equal to -1\n", flagname, + static_cast<int>(value)); + return false; + } + + return true; +} + +bool ValidateNumThreads(char const * flagname, int32_t value) +{ + if (value < kMinNumThreads || value > kMaxNumThreads) + { + printf("Invalid value for --%s: %d, must be between %d and %d inclusively\n", flagname, + static_cast<int>(value), static_cast<int>(kMinNumThreads), + static_cast<int>(kMaxNumThreads)); + return false; + } + + return true; +} + +bool ValidataMwmPath(char const * flagname, string const & value) +{ + if (value.empty()) + { + printf("--%s should be specified\n", flagname); + return false; + } + + return true; +} + +bool const g_limitDummy = google::RegisterFlagValidator(&FLAGS_limit, &ValidateLimit); +bool const g_numThreadsDummy = + google::RegisterFlagValidator(&FLAGS_num_threads, &ValidateNumThreads); +bool const g_mwmsPathDummy = google::RegisterFlagValidator(&FLAGS_mwms_path, &ValidataMwmPath); +} // namespace + +int main(int argc, char * argv[]) +{ + google::SetUsageMessage("OpenLR stats tool."); + google::ParseCommandLineFlags(&argc, &argv, true); + + classificator::Load(); + + vector<Index> indexes(FLAGS_num_threads); + LoadIndexes(FLAGS_mwms_path, indexes); + + OpenLRSimpleDecoder::SegmentsFilter filter(FLAGS_ids_path, FLAGS_multipoints_only); + OpenLRSimpleDecoder decoder(FLAGS_input, indexes); + decoder.Decode(FLAGS_output, FLAGS_limit, filter, FLAGS_num_threads); + + return 0; +} diff --git a/openlr/openlr_stat/openlr_stat.pro b/openlr/openlr_stat/openlr_stat.pro new file mode 100644 index 0000000000..bf3d233c7a --- /dev/null +++ b/openlr/openlr_stat/openlr_stat.pro @@ -0,0 +1,26 @@ +# A tool to check matching on mwm + +ROOT_DIR = ../.. + +DEPENDENCIES = openlr routing search storage indexer editor platform geometry coding base protobuf \ + osrm stats_client pugixml jansson succinct gflags + +include($$ROOT_DIR/common.pri) + +INCLUDEPATH *= $$ROOT_DIR/3party/gflags/src + +CONFIG += console warn_on +CONFIG -= app_bundle +TEMPLATE = app + +# needed for Platform::WorkingDir() and unicode combining +QT *= core + +macx-* { + LIBS *= "-framework IOKit" "-framework SystemConfiguration" +} + +SOURCES += \ + openlr_stat.cpp \ + +HEADERS += \ diff --git a/openlr/openlr_tests/CMakeLists.txt b/openlr/openlr_tests/CMakeLists.txt new file mode 100644 index 0000000000..39c11f7d71 --- /dev/null +++ b/openlr/openlr_tests/CMakeLists.txt @@ -0,0 +1,27 @@ +project(openlr_tests) + +set( + SRC + openlr_sample_test.cpp + ) + +omim_add_test(${PROJECT_NAME} ${SRC}) + +omim_link_libraries( + ${PROJECT_NAME} + openlr + indexer + editor + platform_tests_support + platform + coding + geometry + base + jansson + oauthcpp + opening_hours + pugixml + stats_client + ${Qt5Core_LIBRARIES} + ${LIBZ} +) diff --git a/openlr/openlr_tests/openlr_sample_test.cpp b/openlr/openlr_tests/openlr_sample_test.cpp new file mode 100644 index 0000000000..a7057e687d --- /dev/null +++ b/openlr/openlr_tests/openlr_sample_test.cpp @@ -0,0 +1,150 @@ +#include "testing/testing.hpp" + +#include "openlr/openlr_model.hpp" +#include "openlr/openlr_sample.hpp" +#include "openlr/openlr_simple_parser.hpp" + +#include "indexer/index.hpp" + +#include "platform/platform_tests_support/scoped_file.hpp" + +#include "3party/pugixml/src/pugixml.hpp" + +using namespace openlr; + +UNIT_TEST(ParseOpenlr) +{ + auto const openlrData = "<?xml version=\"1.0\"?>" + " <Report dictionaryUpdateDateTime=\"2016-09-15T03:40:51\" dictionaryVersion=\"16.2\">" + " <reportSegments>" + " <ReportSegmentID>8446643</ReportSegmentID>" + " <ReportSegmentLRC>" + " <method>" + " <olr:version>1.0</olr:version>" + " <olr:locationReference>" + " <olr:optionLinearLocationReference>" + " <olr:first>" + " <olr:coordinate>" + " <olr:longitude>1738792</olr:longitude>" + " <olr:latitude>2577486</olr:latitude>" + " </olr:coordinate>" + " <olr:lineProperties>" + " <olr:frc olr:table=\"olr001_FunctionalRoadClass\" olr:code=\"6\"/>" + " <olr:fow olr:table=\"olr002_FormOfWay\" olr:code=\"2\"/>" + " <olr:bearing>" + " <olr:value>8</olr:value>" + " </olr:bearing>" + " </olr:lineProperties>" + " <olr:pathProperties>" + " <olr:lfrcnp olr:table=\"olr001_FunctionalRoadClass\" olr:code=\"7\"/>" + " <olr:dnp>" + " <olr:value>3572</olr:value>" + " </olr:dnp>" + " <olr:againstDrivingDirection>true</olr:againstDrivingDirection>" + " </olr:pathProperties>" + " </olr:first>" + " <olr:last>" + " <olr:coordinate>" + " <olr:longitude>-1511</olr:longitude>" + " <olr:latitude>2858</olr:latitude>" + " </olr:coordinate>" + " <olr:lineProperties>" + " <olr:frc olr:table=\"olr001_FunctionalRoadClass\" olr:code=\"7\"/>" + " <olr:fow olr:table=\"olr002_FormOfWay\" olr:code=\"3\"/>" + " <olr:bearing>" + " <olr:value>105</olr:value>" + " </olr:bearing>" + " </olr:lineProperties>" + " </olr:last>" + " <olr:positiveOffset>" + " <olr:value>1637</olr:value>" + " </olr:positiveOffset>" + " <olr:negativeOffset>" + " <olr:value>919</olr:value>" + " </olr:negativeOffset>" + " </olr:optionLinearLocationReference>" + " </olr:locationReference>" + " </method>" + " </ReportSegmentLRC>" + " <LinearConnectivity>" + " <negLink>" + " <ReportSegmentID>8446642</ReportSegmentID>" + " </negLink>" + " <posLink>" + " <ReportSegmentID>91840286</ReportSegmentID>" + " </posLink>" + " </LinearConnectivity>" + " <segmentLength>1018</segmentLength>" + " <segmentRefSpeed>0</segmentRefSpeed>" + " </reportSegments>"; + + vector<openlr::LinearSegment> segments; + pugi::xml_document doc; + TEST_EQUAL(doc.load(openlrData), pugi::xml_parse_status::status_ok, ()); + TEST(openlr::ParseOpenlr(doc, segments), ()); + + TEST_EQUAL(segments.size(), 1, ()); + + auto const & segment = segments.front(); + TEST_EQUAL(segment.m_segmentId, 8446643, ()); + TEST_EQUAL(segment.m_segmentLengthMeters, 1018, ()); + + auto const locRef = segment.m_locationReference; + TEST_EQUAL(locRef.m_points.size(), 2, ()); + + auto const firstPoint = locRef.m_points.front(); + auto expectedLatLon = ms::LatLon{55.30683, 37.31041}; + TEST(firstPoint.m_latLon.EqualDxDy(expectedLatLon, 1e-5), (firstPoint.m_latLon, "!=", expectedLatLon)); + TEST_EQUAL(firstPoint.m_bearing, 8, ()); + TEST(firstPoint.m_formOfWay == openlr::FormOfWay::MultipleCarriageway, + ("Wrong form of a way.")); + TEST(firstPoint.m_functionalRoadClass == openlr::FunctionalRoadClass::FRC6, + ("Wrong functional road class.")); + TEST_EQUAL(firstPoint.m_distanceToNextPoint, 3572, ()); + TEST(firstPoint.m_lfrcnp == openlr::FunctionalRoadClass::FRC7, ("Wrong functional road class.")); + TEST_EQUAL(firstPoint.m_againstDrivingDirection, true, ()); + + auto const secondPoint = locRef.m_points.back(); + expectedLatLon = ms::LatLon{55.33541, 37.29530}; + TEST(secondPoint.m_latLon.EqualDxDy(expectedLatLon, 1e-5), (secondPoint.m_latLon, "!=", expectedLatLon)); + TEST_EQUAL(secondPoint.m_bearing, 105, ()); + TEST(secondPoint.m_formOfWay == openlr::FormOfWay::SingleCarriageway, ("Wrong form of way.")); + TEST(secondPoint.m_functionalRoadClass == openlr::FunctionalRoadClass::FRC7, + ("Wrong functional road class.")); + + TEST_EQUAL(locRef.m_positiveOffsetMeters, 1637, ()); + TEST_EQUAL(locRef.m_negativeOffsetMeters, 919, ()); +} + +UNIT_TEST(LoadSamplePool_Test) +{ + platform::tests_support::ScopedFile sample( + "sample.txt", + "8442794\tRussia_Moscow Oblast_East-36328-0-fwd-58.3775=Russia_Moscow Oblast_East-36328-1-fwd-14.0846\n" + "8442817\tRussia_Moscow Oblast_East-36324-11-bwd-101.362=Russia_Moscow Oblast_East-36324-10-bwd-48.2464=Russia_Moscow Oblast_East-36324-9-bwd-92.06\n" + "8442983\tRussia_Moscow Oblast_East-45559-1-bwd-614.231=Russia_Moscow Oblast_East-45559-0-bwd-238.259\n" + "8442988\tRussia_Moscow Oblast_East-36341-3-bwd-81.3394\n"); + + Index emptyIndex; // Empty is ok for this test. + auto const pool = LoadSamplePool(sample.GetFullPath(), emptyIndex); + + TEST_EQUAL(pool.size(), 4, ()); + + TEST(pool[0].m_evaluation == openlr::ItemEvaluation::Unevaluated, + ("pool[0].m_evaluation != openlr::ItemEvaluation::Unevaluated")); + TEST_EQUAL(pool[0].m_partnerSegmentId.Get(), 8442794, ()); + TEST_EQUAL(pool[1].m_partnerSegmentId.Get(), 8442817, ()); + TEST_EQUAL(pool[2].m_partnerSegmentId.Get(), 8442983, ()); + + TEST_EQUAL(pool[0].m_segments.size(), 2, ()); + TEST_EQUAL(pool[1].m_segments.size(), 3, ()); + TEST_EQUAL(pool[2].m_segments.size(), 2, ()); + + TEST_EQUAL(pool[0].m_segments[0].m_segId, 0, ()); + TEST_EQUAL(pool[1].m_segments[0].m_segId, 11, ()); + TEST_EQUAL(pool[2].m_segments[0].m_segId, 1, ()); + + TEST(pool[0].m_segments[0].m_isForward, ()); + TEST(!pool[1].m_segments[0].m_isForward, ()); + TEST(!pool[2].m_segments[0].m_isForward, ()); +} diff --git a/openlr/openlr_tests/openlr_tests.pro b/openlr/openlr_tests/openlr_tests.pro new file mode 100644 index 0000000000..1d2cf5116e --- /dev/null +++ b/openlr/openlr_tests/openlr_tests.pro @@ -0,0 +1,23 @@ +TARGET = openlr_tests +CONFIG += console warn_on +CONFIG -= app_bundle +TEMPLATE = app + +ROOT_DIR = ../.. +DEPENDENCIES = routing search storage indexer editor platform_tests_support platform \ + geometry coding base protobuf \ + osrm stats_client pugixml openlr jansson succinct + +include($$ROOT_DIR/common.pri) + +QT *= core + +macx-* { + LIBS *= "-framework SystemConfiguration" +} + +HEADERS += \ + +SOURCES += \ + $$ROOT_DIR/testing/testingmain.cpp \ + openlr_sample_test.cpp \ diff --git a/openlr/road_info_getter.cpp b/openlr/road_info_getter.cpp new file mode 100644 index 0000000000..859cf0f8aa --- /dev/null +++ b/openlr/road_info_getter.cpp @@ -0,0 +1,66 @@ +#include "openlr/road_info_getter.hpp" + +#include "indexer/classificator.hpp" +#include "indexer/feature.hpp" +#include "indexer/index.hpp" + +#include "base/assert.hpp" + +#include "std/iterator.hpp" + +namespace openlr +{ +RoadInfoGetter::RoadInfoGetter(Index const & index) : m_index(index), m_c(classif()) {} + +RoadInfoGetter::RoadInfo RoadInfoGetter::Get(FeatureID const & fid) +{ + auto it = m_cache.find(fid); + if (it != end(m_cache)) + return it->second; + + Index::FeaturesLoaderGuard g(m_index, fid.m_mwmId); + FeatureType ft; + CHECK(g.GetOriginalFeatureByIndex(fid.m_index, ft), ()); + + RoadInfo info; + info.m_frc = GetFunctionalRoadClass(ft); + info.m_fow = GetFormOfWay(ft); + it = m_cache.emplace(fid, info).first; + + return it->second; +} + +FunctionalRoadClass RoadInfoGetter::GetFunctionalRoadClass(feature::TypesHolder const & types) const +{ + if (m_trunkChecker(types)) + return FunctionalRoadClass::FRC0; + + if (m_primaryChecker(types)) + return FunctionalRoadClass::FRC1; + + if (m_secondaryChecker(types)) + return FunctionalRoadClass::FRC2; + + if (m_tertiaryChecker(types)) + return FunctionalRoadClass::FRC3; + + if (m_residentialChecker(types)) + return FunctionalRoadClass::FRC4; + + if (m_livingStreetChecker(types)) + return FunctionalRoadClass::FRC5; + + return FunctionalRoadClass::FRC7; +} + +FormOfWay RoadInfoGetter::GetFormOfWay(feature::TypesHolder const & types) const +{ + if (m_trunkChecker(types)) + return FormOfWay::Motorway; + + if (m_primaryChecker(types)) + return FormOfWay::MultipleCarriageway; + + return FormOfWay::SingleCarriageway; +} +} // namespace openlr diff --git a/openlr/road_info_getter.hpp b/openlr/road_info_getter.hpp new file mode 100644 index 0000000000..83a648d040 --- /dev/null +++ b/openlr/road_info_getter.hpp @@ -0,0 +1,51 @@ +#pragma once + +#include "openlr/openlr_model.hpp" +#include "openlr/road_type_checkers.hpp" + +#include "indexer/feature_data.hpp" + +#include "std/map.hpp" + +class Classificator; +class Index; + +namespace feature +{ +class TypesHolder; +} + +namespace openlr +{ +class RoadInfoGetter final +{ +public: + struct RoadInfo + { + RoadInfo() = default; + + FunctionalRoadClass m_frc = FunctionalRoadClass::NotAValue; + FormOfWay m_fow = FormOfWay::NotAValue; + }; + + RoadInfoGetter(Index const & index); + + RoadInfo Get(FeatureID const & fid); + + private: + FunctionalRoadClass GetFunctionalRoadClass(feature::TypesHolder const & types) const; + FormOfWay GetFormOfWay(feature::TypesHolder const & types) const; + + Index const & m_index; + Classificator const & m_c; + + TrunkChecker const m_trunkChecker; + PrimaryChecker const m_primaryChecker; + SecondaryChecker const m_secondaryChecker; + TertiaryChecker const m_tertiaryChecker; + ResidentialChecker const m_residentialChecker; + LivingStreetChecker const m_livingStreetChecker; + + map<FeatureID, RoadInfo> m_cache; +}; +} // namespace openlr diff --git a/openlr/road_type_checkers.cpp b/openlr/road_type_checkers.cpp new file mode 100644 index 0000000000..c9b1e9b704 --- /dev/null +++ b/openlr/road_type_checkers.cpp @@ -0,0 +1,56 @@ +#include "openlr/road_type_checkers.hpp" + +#include "indexer/classificator.hpp" + +namespace openlr +{ +// TrunkChecker ------------------------------------------------------------------------------------ +TrunkChecker::TrunkChecker() +{ + auto const & c = classif(); + m_types.push_back(c.GetTypeByPath({"highway", "motorway"})); + m_types.push_back(c.GetTypeByPath({"highway", "motorway_link"})); + m_types.push_back(c.GetTypeByPath({"highway", "trunk"})); + m_types.push_back(c.GetTypeByPath({"highway", "trunk_link"})); +} + +// PrimaryChecker ---------------------------------------------------------------------------------- +PrimaryChecker::PrimaryChecker() +{ + auto const & c = classif(); + m_types.push_back(c.GetTypeByPath({"highway", "primary"})); + m_types.push_back(c.GetTypeByPath({"highway", "primary_link"})); +} + +// SecondaryChecker -------------------------------------------------------------------------------- +SecondaryChecker::SecondaryChecker() +{ + auto const & c = classif(); + m_types.push_back(c.GetTypeByPath({"highway", "secondary"})); + m_types.push_back(c.GetTypeByPath({"highway", "secondary_link"})); +} + +// TertiaryChecker --------------------------------------------------------------------------------- +TertiaryChecker::TertiaryChecker() +{ + auto const & c = classif(); + m_types.push_back(c.GetTypeByPath({"highway", "tertiary"})); + m_types.push_back(c.GetTypeByPath({"highway", "tertiary_link"})); +} + +// ResidentialChecker ------------------------------------------------------------------------------ +ResidentialChecker::ResidentialChecker() +{ + auto const & c = classif(); + m_types.push_back(c.GetTypeByPath({"highway", "road"})); + m_types.push_back(c.GetTypeByPath({"highway", "unclassified"})); + m_types.push_back(c.GetTypeByPath({"highway", "residential"})); +} + +// LivingStreetChecker ----------------------------------------------------------------------------- +LivingStreetChecker::LivingStreetChecker() +{ + auto const & c = classif(); + m_types.push_back(c.GetTypeByPath({"highway", "living_street"})); +} +} // namespace openlr diff --git a/openlr/road_type_checkers.hpp b/openlr/road_type_checkers.hpp new file mode 100644 index 0000000000..689743ca11 --- /dev/null +++ b/openlr/road_type_checkers.hpp @@ -0,0 +1,42 @@ +#pragma once + +#include "indexer/ftypes_matcher.hpp" + +namespace openlr +{ +class TrunkChecker final : public ftypes::BaseChecker +{ +public: + TrunkChecker(); +}; + +class PrimaryChecker final : public ftypes::BaseChecker +{ +public: + PrimaryChecker(); +}; + +class SecondaryChecker final : public ftypes::BaseChecker +{ +public: + SecondaryChecker(); +}; + +class TertiaryChecker final : public ftypes::BaseChecker +{ +public: + TertiaryChecker(); +}; + +class ResidentialChecker final : public ftypes::BaseChecker +{ +public: + ResidentialChecker(); +}; + +class LivingStreetChecker final : public ftypes::BaseChecker +{ +public: + LivingStreetChecker(); +}; +} // namespace openlr diff --git a/openlr/router.cpp b/openlr/router.cpp new file mode 100644 index 0000000000..896f1176a8 --- /dev/null +++ b/openlr/router.cpp @@ -0,0 +1,791 @@ +#include "openlr/router.hpp" + +#include "openlr/road_info_getter.hpp" + +#include "routing/features_road_graph.hpp" + +#include "platform/location.hpp" + +#include "geometry/angles.hpp" +#include "geometry/segment2d.hpp" + +#include "base/assert.hpp" +#include "base/math.hpp" + +#include "std/transform_iterator.hpp" + +#include <algorithm> +#include <queue> +#include <utility> + +namespace openlr +{ +namespace +{ +size_t const kMaxRoadCandidates = 10; +double const kDistanceAccuracyM = 1000; +double const kEps = 1e-9; +double const kBearingDist = 25; + +int const kNumBuckets = 256; +double const kAnglesInBucket = 360.0 / kNumBuckets; + +uint32_t Bearing(m2::PointD const & a, m2::PointD const & b) +{ + auto const angle = location::AngleToBearing(my::RadToDeg(ang::AngleTo(a, b))); + CHECK_LESS_OR_EQUAL(angle, 360, ("Angle should be less than or equal to 360.")); + CHECK_GREATER_OR_EQUAL(angle, 0, ("Angle should be greater than or equal to 0")); + return my::clamp(angle / kAnglesInBucket, 0, 255); +} + +class Score final +{ +public: + // A weight for total length of true fake edges. + static const int kTrueFakeCoeff = 3; + + // A weight for total length of fake edges that are parts of some + // real edges. + static constexpr double kFakeCoeff = 0.001; + + // A weight for passing too far from pivot points. + static const int kIntermediateErrorCoeff = 3; + + // A weight for excess of distance limit. + static const int kDistanceErrorCoeff = 3; + + // A weight for deviation from bearing. + static const int kBearingErrorCoeff = 5; + + void AddDistance(double p) { m_distance += p; } + + void AddFakePenalty(double p, bool partOfReal) + { + m_penalty += (partOfReal ? kFakeCoeff : kTrueFakeCoeff) * p; + } + + void AddIntermediateErrorPenalty(double p) + { + m_penalty += kIntermediateErrorCoeff * p; + } + + void AddDistanceErrorPenalty(double p) + { + m_penalty += kDistanceErrorCoeff * p; + } + + void AddBearingPenalty(int expected, int actual) + { + ASSERT_LESS(expected, kNumBuckets, ()); + ASSERT_GREATER_OR_EQUAL(expected, 0, ()); + + ASSERT_LESS(actual, kNumBuckets, ()); + ASSERT_GREATER_OR_EQUAL(actual, 0, ()); + + int const diff = abs(expected - actual); + double angle = my::DegToRad(min(diff, kNumBuckets - diff) * kAnglesInBucket); + m_penalty += kBearingErrorCoeff * angle * kBearingDist; + } + + double GetDistance() const { return m_distance; } + double GetPenalty() const { return m_penalty; } + double GetScore() const { return m_distance + m_penalty; } + + bool operator<(Score const & rhs) const + { + auto const ls = GetScore(); + auto const rs = rhs.GetScore(); + if (ls != rs) + return ls < rs; + + if (m_distance != rhs.m_distance) + return m_distance < rhs.m_distance; + return m_penalty < rhs.m_penalty; + } + + bool operator>(Score const & rhs) const { return rhs < *this; } + + bool operator==(Score const & rhs) const + { + return m_distance == rhs.m_distance && m_penalty == rhs.m_penalty; + } + + bool operator!=(Score const & rhs) const { return !(*this == rhs); } + +private: + // Reduced length of path in meters. + double m_distance = 0.0; + + double m_penalty = 0.0; +}; +} // namespace + +// Router::Vertex ---------------------------------------------------------------------------------- +Router::Vertex::Vertex(routing::Junction const & junction, routing::Junction const & stageStart, + double stageStartDistance, size_t stage, bool bearingChecked) + : m_junction(junction) + , m_stageStart(stageStart) + , m_stageStartDistance(stageStartDistance) + , m_stage(stage) + , m_bearingChecked(bearingChecked) +{ +} + +bool Router::Vertex::operator<(Vertex const & rhs) const +{ + if (m_junction != rhs.m_junction) + return m_junction < rhs.m_junction; + if (m_stageStart != rhs.m_stageStart) + return m_stageStart < rhs.m_stageStart; + if (m_stageStartDistance != rhs.m_stageStartDistance) + return m_stageStartDistance < rhs.m_stageStartDistance; + if (m_stage != rhs.m_stage) + return m_stage < rhs.m_stage; + return m_bearingChecked < rhs.m_bearingChecked; +} + +bool Router::Vertex::operator==(Vertex const & rhs) const +{ + return m_junction == rhs.m_junction && m_stageStart == rhs.m_stageStart && + m_stageStartDistance == rhs.m_stageStartDistance && m_stage == rhs.m_stage && + m_bearingChecked == rhs.m_bearingChecked; +} + +// Router::Edge ------------------------------------------------------------------------------------ +Router::Edge::Edge(Vertex const & u, Vertex const & v, routing::Edge const & raw, bool isSpecial) + : m_u(u), m_v(v), m_raw(raw), m_isSpecial(isSpecial) +{ +} + +// static +Router::Edge Router::Edge::MakeNormal(Vertex const & u, Vertex const & v, + routing::Edge const & raw) +{ + return Edge(u, v, raw, false /* isSpecial */); +} + +// static +Router::Edge Router::Edge::MakeSpecial(Vertex const & u, Vertex const & v) +{ + return Edge(u, v, routing::Edge::MakeFake(u.m_junction, v.m_junction, false /* partOfReal */), + true /* isSpecial */); +} + +pair<m2::PointD, m2::PointD> Router::Edge::ToPair() const +{ + auto const & e = m_raw; + return make_pair(e.GetStartJunction().GetPoint(), e.GetEndJunction().GetPoint()); +} + +pair<m2::PointD, m2::PointD> Router::Edge::ToPairRev() const +{ + auto const & e = m_raw; + return make_pair(e.GetEndJunction().GetPoint(), e.GetStartJunction().GetPoint()); +} + +// Router::Router ---------------------------------------------------------------------------------- +Router::Router(routing::FeaturesRoadGraph & graph, RoadInfoGetter & roadInfoGetter) + : m_graph(graph), m_roadInfoGetter(roadInfoGetter) +{ +} + +bool Router::Go(std::vector<WayPoint> const & points, double positiveOffsetM, double negativeOffsetM, + std::vector<routing::Edge> & path) +{ + if (!Init(points, positiveOffsetM, negativeOffsetM)) + return false; + return FindPath(path); +} + +bool Router::Init(std::vector<WayPoint> const & points, double positiveOffsetM, double negativeOffsetM) +{ + CHECK_GREATER_OR_EQUAL(points.size(), 2, ()); + + m_points = points; + m_positiveOffsetM = positiveOffsetM; + m_negativeOffsetM = negativeOffsetM; + + m_graph.ResetFakes(); + + m_pivots.clear(); + for (size_t i = 1; i + 1 < m_points.size(); ++i) + { + m_pivots.emplace_back(); + auto & ps = m_pivots.back(); + + std::vector<std::pair<routing::Edge, routing::Junction>> vicinity; + m_graph.FindClosestEdges(m_points[i].m_point, kMaxRoadCandidates, vicinity); + for (auto const & v : vicinity) + { + auto const & e = v.first; + ps.push_back(e.GetStartJunction().GetPoint()); + ps.push_back(e.GetEndJunction().GetPoint()); + } + + if (ps.empty()) + return false; + } + + m_pivots.push_back({m_points.back().m_point}); + CHECK_EQUAL(m_pivots.size() + 1, m_points.size(), ()); + + { + m_sourceJunction = routing::Junction(m_points.front().m_point, 0 /* altitude */); + std::vector<std::pair<routing::Edge, routing::Junction>> sourceVicinity; + m_graph.FindClosestEdges(m_sourceJunction.GetPoint(), kMaxRoadCandidates, sourceVicinity); + m_graph.AddFakeEdges(m_sourceJunction, sourceVicinity); + } + + { + m_targetJunction = routing::Junction(m_points.back().m_point, 0 /* altitude */); + std::vector<std::pair<routing::Edge, routing::Junction>> targetVicinity; + m_graph.FindClosestEdges(m_targetJunction.GetPoint(), kMaxRoadCandidates, targetVicinity); + m_graph.AddFakeEdges(m_targetJunction, targetVicinity); + } + + return true; +} + +bool Router::FindPath(std::vector<routing::Edge> & path) +{ + using State = std::pair<Score, Vertex>; + std::priority_queue<State, std::vector<State>, greater<State>> queue; + std::map<Vertex, Score> scores; + Links links; + + auto pushVertex = [&queue, &scores, &links](Vertex const & u, Vertex const & v, Score const & sv, + Edge const & e) { + if ((scores.count(v) == 0 || scores[v].GetScore() > sv.GetScore() + kEps) && u != v) + { + scores[v] = sv; + links[v] = make_pair(u, e); + queue.emplace(sv, v); + } + }; + + Vertex const s(m_sourceJunction, m_sourceJunction, 0 /* stageStartDistance */, 0 /* stage */, + false /* bearingChecked */); + CHECK(!NeedToCheckBearing(s, 0 /* distance */), ()); + + scores[s] = Score(); + queue.emplace(scores[s], s); + + double const piS = GetPotential(s); + + while (!queue.empty()) + { + auto const p = queue.top(); + queue.pop(); + + Score const & su = p.first; + Vertex const & u = p.second; + + if (su != scores[u]) + continue; + + if (IsFinalVertex(u)) + { + std::vector<Edge> edges; + auto cur = u; + while (cur != s) + { + auto const & p = links[cur]; + + edges.push_back(p.second); + cur = p.first; + } + reverse(edges.begin(), edges.end()); + return ReconstructPath(edges, path); + } + + size_t const stage = u.m_stage; + double const distanceToNextPointM = m_points[stage].m_distanceToNextPointM; + double const piU = GetPotential(u); + double const ud = su.GetDistance() + piS - piU; // real distance to u + + CHECK_LESS(stage, m_pivots.size(), ()); + + // max(kDistanceAccuracyM, m_distanceToNextPointM) is added here + // to throw out quite long paths. + if (ud > u.m_stageStartDistance + distanceToNextPointM + + max(kDistanceAccuracyM, distanceToNextPointM)) + { + continue; + } + + if (NearNextStage(u, piU) && !u.m_bearingChecked) + { + Vertex v = u; + + Score sv = su; + if (u.m_junction != u.m_stageStart) + { + int const expected = m_points[stage].m_bearing; + int const actual = Bearing(u.m_stageStart.GetPoint(), u.m_junction.GetPoint()); + sv.AddBearingPenalty(expected, actual); + } + v.m_bearingChecked = true; + + pushVertex(u, v, sv, Edge::MakeSpecial(u, v)); + } + + if (MayMoveToNextStage(u, piU)) + { + Vertex v(u.m_junction, u.m_junction, ud /* stageStartDistance */, stage + 1, + false /* bearingChecked */); + double const piV = GetPotential(v); + + Score sv = su; + sv.AddDistance(max(piV - piU, 0.0)); + sv.AddIntermediateErrorPenalty( + MercatorBounds::DistanceOnEarth(v.m_junction.GetPoint(), m_points[v.m_stage].m_point)); + + if (IsFinalVertex(v)) + { + int const expected = m_points.back().m_bearing; + int const actual = GetReverseBearing(u, links); + sv.AddBearingPenalty(expected, actual); + } + + pushVertex(u, v, sv, Edge::MakeSpecial(u, v)); + } + + ForEachEdge(u, true /* outgoing */, m_points[stage].m_lfrcnp, [&](routing::Edge const & edge) { + Vertex v = u; + v.m_junction = edge.GetEndJunction(); + + double const piV = GetPotential(v); + + Score sv = su; + double const w = GetWeight(edge); + sv.AddDistance(max(w + piV - piU, 0.0)); + + double const vd = ud + w; // real distance to v + if (NeedToCheckBearing(v, vd)) + { + CHECK(!NeedToCheckBearing(u, ud), ()); + + double const delta = vd - v.m_stageStartDistance - kBearingDist; + auto const p = PointAtSegment(edge.GetStartJunction().GetPoint(), + edge.GetEndJunction().GetPoint(), delta); + if (v.m_stageStart.GetPoint() != p) + { + int const expected = m_points[stage].m_bearing; + int const actual = Bearing(v.m_stageStart.GetPoint(), p); + sv.AddBearingPenalty(expected, actual); + } + v.m_bearingChecked = true; + } + + if (vd > v.m_stageStartDistance + distanceToNextPointM) + sv.AddDistanceErrorPenalty(std::min(vd - v.m_stageStartDistance - distanceToNextPointM, w)); + + if (edge.IsFake()) + sv.AddFakePenalty(w, edge.IsPartOfReal()); + + pushVertex(u, v, sv, Edge::MakeNormal(u, v, edge)); + }); + } + + return false; +} + +bool Router::NeedToCheckBearing(Vertex const & u, double distanceM) const +{ + if (IsFinalVertex(u) || u.m_bearingChecked) + return false; + return distanceM >= u.m_stageStartDistance + kBearingDist; +} + +double Router::GetPotential(Vertex const & u) const +{ + if (IsFinalVertex(u)) + return 0.0; + + CHECK_LESS(u.m_stage, m_pivots.size(), ()); + + auto const & pivots = m_pivots[u.m_stage]; + CHECK(!pivots.empty(), ("Empty list of pivots")); + + double potential = numeric_limits<double>::max(); + + auto const & point = u.m_junction.GetPoint(); + for (auto const & pivot : pivots) + potential = min(potential, MercatorBounds::DistanceOnEarth(pivot, point)); + return potential; +} + +bool Router::NearNextStage(Vertex const & u, double pi) const +{ + return u.m_stage < m_pivots.size() && pi < kEps; +} + +bool Router::MayMoveToNextStage(Vertex const & u, double pi) const +{ + return NearNextStage(u, pi) && u.m_bearingChecked; +} + +bool Router::PassesRestriction(routing::Edge const & edge, + FunctionalRoadClass const restriction) const +{ + if (edge.IsFake()) + return true; + + auto const frc = m_roadInfoGetter.Get(edge.GetFeatureId()).m_frc; + return frc <= restriction; +} + +uint32_t Router::GetReverseBearing(Vertex const & u, Links const & links) const +{ + m2::PointD const a = u.m_junction.GetPoint(); + m2::PointD b = m2::PointD::Zero(); + + Vertex curr = u; + double passed = 0; + bool found = false; + while (true) + { + auto const it = links.find(curr); + if (it == links.end()) + break; + + auto const & p = it->second; + auto const & prev = p.first; + auto const & edge = p.second.m_raw; + + if (prev.m_stage != curr.m_stage) + break; + + double const weight = GetWeight(edge); + + if (passed + weight >= kBearingDist) + { + double const delta = kBearingDist - passed; + b = PointAtSegment(edge.GetEndJunction().GetPoint(), edge.GetStartJunction().GetPoint(), + delta); + found = true; + break; + } + + passed += weight; + curr = prev; + } + if (!found) + b = curr.m_junction.GetPoint(); + return Bearing(a, b); +} + +template <typename Fn> +void Router::ForEachEdge(Vertex const & u, bool outgoing, FunctionalRoadClass restriction, Fn && fn) +{ + routing::IRoadGraph::TEdgeVector edges; + if (outgoing) + GetOutgoingEdges(u.m_junction, edges); + else + GetIngoingEdges(u.m_junction, edges); + for (auto const & edge : edges) + { + if (!PassesRestriction(edge, restriction)) + continue; + fn(edge); + } +} + +void Router::GetOutgoingEdges(routing::Junction const & u, routing::IRoadGraph::TEdgeVector & edges) +{ + GetEdges(u, &routing::IRoadGraph::GetRegularOutgoingEdges, + &routing::IRoadGraph::GetFakeOutgoingEdges, m_outgoingCache, edges); +} + +void Router::GetIngoingEdges(routing::Junction const & u, routing::IRoadGraph::TEdgeVector & edges) +{ + GetEdges(u, &routing::IRoadGraph::GetRegularIngoingEdges, + &routing::IRoadGraph::GetFakeIngoingEdges, m_ingoingCache, edges); +} + +void Router::GetEdges(routing::Junction const & u, RoadGraphEdgesGetter getRegular, + RoadGraphEdgesGetter getFake, + std::map<routing::Junction, routing::IRoadGraph::TEdgeVector> & cache, + routing::IRoadGraph::TEdgeVector & edges) +{ + auto const it = cache.find(u); + if (it == cache.end()) + { + auto & es = cache[u]; + (m_graph.*getRegular)(u, es); + edges.insert(edges.end(), es.begin(), es.end()); + } + else + { + auto const & es = it->second; + edges.insert(edges.end(), es.begin(), es.end()); + } + (m_graph.*getFake)(u, edges); +} + +template <typename Fn> +void Router::ForEachNonFakeEdge(Vertex const & u, bool outgoing, FunctionalRoadClass restriction, + Fn && fn) +{ + ForEachEdge(u, outgoing, restriction, [&fn](routing::Edge const & edge) { + if (!edge.IsFake()) + fn(edge); + }); +} + +template <typename Fn> +void Router::ForEachNonFakeClosestEdge(Vertex const & u, FunctionalRoadClass const restriction, + Fn && fn) +{ + std::vector<std::pair<routing::Edge, routing::Junction>> vicinity; + m_graph.FindClosestEdges(u.m_junction.GetPoint(), kMaxRoadCandidates, vicinity); + + for (auto const & p : vicinity) + { + auto const & edge = p.first; + if (edge.IsFake()) + continue; + if (!PassesRestriction(edge, restriction)) + continue; + fn(edge); + } +} + +template <typename It> +size_t Router::FindPrefixLengthToConsume(It b, It const e, double lengthM) +{ + size_t n = 0; + while (b != e && lengthM > 0.0) + { + auto const & u = b->first; + auto const & v = b->second; + double const len = MercatorBounds::DistanceOnEarth(u, v); + if (2 * lengthM < len) + break; + + lengthM -= len; + ++n; + ++b; + } + return n; +} + +template <typename It> +double Router::GetCoverage(m2::PointD const & u, m2::PointD const & v, It b, It e) +{ + double const kEps = 1e-5; + + m2::PointD const uv = v - u; + double const sqlen = u.SquareLength(v); + + if (sqlen < kEps) + return 0; + + std::vector<std::pair<double, double>> covs; + for (; b != e; ++b) + { + auto const s = b->m_u.m_junction.GetPoint(); + auto const t = b->m_v.m_junction.GetPoint(); + if (!m2::IsPointOnSegmentEps(s, u, v, kEps) || !m2::IsPointOnSegmentEps(t, u, v, kEps)) + continue; + + if (DotProduct(uv, t - s) < -kEps) + continue; + + double const sp = DotProduct(uv, s - u) / sqlen; + double const tp = DotProduct(uv, t - u) / sqlen; + + double const start = my::clamp(min(sp, tp), 0, 1); + double const finish = my::clamp(max(sp, tp), 0, 1); + covs.emplace_back(start, finish); + } + + sort(covs.begin(), covs.end()); + + double coverage = 0; + + size_t i = 0; + while (i != covs.size()) + { + size_t j = i; + + double const first = covs[i].first; + double last = covs[i].second; + while (j != covs.size() && covs[j].first <= last) + { + last = max(last, covs[j].second); + ++j; + } + + coverage += last - first; + i = j; + } + + CHECK_LESS_OR_EQUAL(coverage, 1.0 + kEps, ()); + + return coverage; +} + +template <typename It> +double Router::GetMatchingScore(m2::PointD const & u, m2::PointD const & v, It b, It e) +{ + double const kEps = 1e-5; + + double const len = MercatorBounds::DistanceOnEarth(u, v); + + m2::PointD const uv = v - u; + + double cov = 0; + for (; b != e; ++b) + { + auto const & s = b->first; + auto const & t = b->second; + if (!m2::IsPointOnSegmentEps(s, u, v, kEps) || !m2::IsPointOnSegmentEps(t, u, v, kEps)) + break; + + m2::PointD const st = t - s; + if (DotProduct(uv, st) < -kEps) + break; + + cov += MercatorBounds::DistanceOnEarth(s, t); + } + + return len == 0 ? 0 : my::clamp(cov / len, 0, 1); +} + +template <typename It, typename Fn> +void Router::ForStagePrefix(It b, It e, size_t stage, Fn && fn) +{ + while (b != e && b->m_raw.IsFake() && b->m_u.m_stage == stage && b->m_v.m_stage == stage) + ++b; + if (b != e && !b->m_raw.IsFake()) + fn(b); +} + +bool Router::ReconstructPath(std::vector<Edge> & edges, vector<routing::Edge> & path) +{ + CHECK_GREATER_OR_EQUAL(m_points.size(), 2, ()); + + using EdgeIt = std::vector<Edge>::iterator; + using EdgeItRev = std::vector<Edge>::reverse_iterator; + + double const kFakeCoverageThreshold = 0.5; + + my::EraseIf(edges, mem_fn(&Edge::IsSpecial)); + + { + size_t const n = FindPrefixLengthToConsume( + make_transform_iterator(edges.begin(), mem_fn(&Edge::ToPair)), + make_transform_iterator(edges.end(), mem_fn(&Edge::ToPair)), m_positiveOffsetM); + CHECK_LESS_OR_EQUAL(n, edges.size(), ()); + edges.erase(edges.begin(), edges.begin() + n); + } + + { + size_t const n = FindPrefixLengthToConsume( + make_transform_iterator(edges.rbegin(), mem_fn(&Edge::ToPairRev)), + make_transform_iterator(edges.rend(), mem_fn(&Edge::ToPairRev)), m_negativeOffsetM); + CHECK_LESS_OR_EQUAL(n, edges.size(), ()); + edges.erase(edges.begin() + edges.size() - n, edges.end()); + } + + double frontEdgeScore = -1.0; + routing::Edge frontEdge; + ForStagePrefix(edges.begin(), edges.end(), 0, [&](EdgeIt e) { + ForEachNonFakeEdge( + e->m_u, false /* outgoing */, m_points[0].m_lfrcnp, [&](routing::Edge const & edge) { + double const score = + GetMatchingScore(edge.GetEndJunction().GetPoint(), edge.GetStartJunction().GetPoint(), + make_transform_iterator(EdgeItRev(e), mem_fn(&Edge::ToPairRev)), + make_transform_iterator(edges.rend(), mem_fn(&Edge::ToPairRev))); + if (score > frontEdgeScore) + { + frontEdgeScore = score; + frontEdge = edge; + } + }); + }); + + double backEdgeScore = -1.0; + routing::Edge backEdge; + ForStagePrefix(edges.rbegin(), edges.rend(), m_points.size() - 2 /* stage */, [&](EdgeItRev e) { + ForEachNonFakeEdge(e->m_v, true /* outgoing */, m_points[m_points.size() - 2].m_lfrcnp, + [&](routing::Edge const & edge) { + double const score = GetMatchingScore( + edge.GetStartJunction().GetPoint(), edge.GetEndJunction().GetPoint(), + make_transform_iterator(e.base(), mem_fn(&Edge::ToPair)), + make_transform_iterator(edges.end(), mem_fn(&Edge::ToPair))); + if (score > backEdgeScore) + { + backEdgeScore = score; + backEdge = edge; + } + }); + }); + + path.clear(); + for (auto const e : edges) + { + if (!e.IsFake()) + path.push_back(e.m_raw); + } + + if (frontEdgeScore >= kFakeCoverageThreshold) + path.insert(path.begin(), frontEdge); + + if (backEdgeScore >= kFakeCoverageThreshold) + path.insert(path.end(), backEdge); + + if (path.empty()) + { + // This is the case for routes from fake edges only. + FindSingleEdgeApproximation(edges, path); + } + + return !path.empty(); +} + +void Router::FindSingleEdgeApproximation(std::vector<Edge> const & edges, std::vector<routing::Edge> & path) +{ + double const kThreshold = 0.95; + + CHECK(all_of(edges.begin(), edges.end(), mem_fn(&Edge::IsFake)), ()); + + double expectedLength = 0; + for (auto const & edge : edges) + expectedLength += GetWeight(edge); + + if (expectedLength < kEps) + return; + + double bestCoverage = -1.0; + routing::Edge bestEdge; + + auto checkEdge = [&](routing::Edge const & edge) { + double const weight = GetWeight(edge); + double const fraction = + GetCoverage(edge.GetStartJunction().GetPoint(), edge.GetEndJunction().GetPoint(), + edges.begin(), edges.end()); + double const coverage = weight * fraction; + if (fraction >= kThreshold && coverage >= bestCoverage) + { + bestCoverage = coverage; + bestEdge = edge; + } + }; + + for (auto const & edge : edges) + { + auto const & u = edge.m_u; + auto const & v = edge.m_v; + CHECK_EQUAL(u.m_stage, v.m_stage, ()); + auto const stage = u.m_stage; + + ForEachNonFakeClosestEdge(u, m_points[stage].m_lfrcnp, checkEdge); + ForEachNonFakeClosestEdge(v, m_points[stage].m_lfrcnp, checkEdge); + } + + if (bestCoverage >= expectedLength * kThreshold) + path = {bestEdge}; +} +} // namespace openlr diff --git a/openlr/router.hpp b/openlr/router.hpp new file mode 100644 index 0000000000..9685269e35 --- /dev/null +++ b/openlr/router.hpp @@ -0,0 +1,158 @@ +#pragma once + +#include "openlr/way_point.hpp" + +#include "routing/road_graph.hpp" + +#include "geometry/point2d.hpp" + +#include "std/map.hpp" +#include "std/utility.hpp" +#include "std/vector.hpp" + +namespace routing +{ +class FeaturesRoadGraph; +} + +namespace openlr +{ +class RoadInfoGetter; + +class Router final +{ +public: + Router(routing::FeaturesRoadGraph & graph, RoadInfoGetter & roadInfoGetter); + + bool Go(vector<WayPoint> const & points, double positiveOffsetM, double negativeOffsetM, + vector<routing::Edge> & path); + +private: + struct Vertex final + { + Vertex() = default; + Vertex(routing::Junction const & junction, routing::Junction const & stageStart, + double stageStartDistance, size_t stage, bool bearingChecked); + + bool operator<(Vertex const & rhs) const; + bool operator==(Vertex const & rhs) const; + bool operator!=(Vertex const & rhs) const { return !(*this == rhs); } + + routing::Junction m_junction; + routing::Junction m_stageStart; + double m_stageStartDistance = 0.0; + size_t m_stage = 0; + bool m_bearingChecked = false; + }; + + struct Edge final + { + Edge() = default; + Edge(Vertex const & u, Vertex const & v, routing::Edge const & raw, bool isSpecial); + + static Edge MakeNormal(Vertex const & u, Vertex const & v, routing::Edge const & raw); + static Edge MakeSpecial(Vertex const & u, Vertex const & v); + + bool IsFake() const { return m_raw.IsFake(); } + bool IsSpecial() const { return m_isSpecial; } + + pair<m2::PointD, m2::PointD> ToPair() const; + pair<m2::PointD, m2::PointD> ToPairRev() const; + + Vertex m_u; + Vertex m_v; + routing::Edge m_raw; + bool m_isSpecial = false; + }; + + using Links = map<Vertex, pair<Vertex, Edge>>; + + using RoadGraphEdgesGetter = void (routing::IRoadGraph::*)( + routing::Junction const & junction, routing::IRoadGraph::TEdgeVector & edges) const; + + bool Init(vector<WayPoint> const & points, double positiveOffsetM, double negativeOffsetM); + bool FindPath(vector<routing::Edge> & path); + + // Returns true if the bearing should be checked for |u|, if the + // real passed distance from the source vertex is |distanceM|. + bool NeedToCheckBearing(Vertex const & u, double distanceM) const; + + double GetPotential(Vertex const & u) const; + + // Returns true if |u| is located near portal to the next stage. + // |pi| is the potential of |u|. + bool NearNextStage(Vertex const & u, double pi) const; + + // Returns true if it's possible to move to the next stage from |u|. + // |pi| is the potential of |u|. + bool MayMoveToNextStage(Vertex const & u, double pi) const; + + // Returns true if |u| is a final vertex and the router may stop now. + bool IsFinalVertex(Vertex const & u) const { return u.m_stage == m_pivots.size(); } + + double GetWeight(routing::Edge const & e) const + { + return MercatorBounds::DistanceOnEarth(e.GetStartJunction().GetPoint(), + e.GetEndJunction().GetPoint()); + } + + double GetWeight(Edge const & e) const { return GetWeight(e.m_raw); } + + bool PassesRestriction(routing::Edge const & edge, FunctionalRoadClass const restriction) const; + + uint32_t GetReverseBearing(Vertex const & u, Links const & links) const; + + template <typename Fn> + void ForEachEdge(Vertex const & u, bool outgoing, FunctionalRoadClass restriction, Fn && fn); + + void GetOutgoingEdges(routing::Junction const & u, routing::IRoadGraph::TEdgeVector & edges); + void GetIngoingEdges(routing::Junction const & u, routing::IRoadGraph::TEdgeVector & edges); + void GetEdges(routing::Junction const & u, RoadGraphEdgesGetter getRegular, + RoadGraphEdgesGetter getFake, + map<routing::Junction, routing::IRoadGraph::TEdgeVector> & cache, + routing::IRoadGraph::TEdgeVector & edges); + + template <typename Fn> + void ForEachNonFakeEdge(Vertex const & u, bool outgoing, FunctionalRoadClass restriction, + Fn && fn); + + template <typename Fn> + void ForEachNonFakeClosestEdge(Vertex const & u, FunctionalRoadClass const restriction, Fn && fn); + + template <typename It> + size_t FindPrefixLengthToConsume(It b, It const e, double lengthM); + + // Finds all edges that are on (u, v) and have the same direction as + // (u, v). Then, computes the fraction of the union of these edges + // to the total length of (u, v). + template <typename It> + double GetCoverage(m2::PointD const & u, m2::PointD const & v, It b, It e); + + // Finds the longest prefix of [b, e) that covers edge (u, v). + // Returns the fraction of the coverage to the length of the (u, v). + template <typename It> + double GetMatchingScore(m2::PointD const & u, m2::PointD const & v, It b, It e); + + // Finds the longest prefix of fake edges of [b, e) that have the + // same stage as |stage|. If the prefix exists, passes its bounding + // iterator to |fn|. + template <typename It, typename Fn> + void ForStagePrefix(It b, It e, size_t stage, Fn && fn); + + bool ReconstructPath(vector<Edge> & edges, vector<routing::Edge> & path); + + void FindSingleEdgeApproximation(vector<Edge> const & edges, vector<routing::Edge> & path); + + routing::FeaturesRoadGraph & m_graph; + map<routing::Junction, routing::IRoadGraph::TEdgeVector> m_outgoingCache; + map<routing::Junction, routing::IRoadGraph::TEdgeVector> m_ingoingCache; + RoadInfoGetter & m_roadInfoGetter; + + vector<WayPoint> m_points; + double m_positiveOffsetM; + double m_negativeOffsetM; + vector<vector<m2::PointD>> m_pivots; + routing::Junction m_sourceJunction; + routing::Junction m_targetJunction; +}; +} // namespace openlr diff --git a/openlr/way_point.hpp b/openlr/way_point.hpp new file mode 100644 index 0000000000..b6f26f90dd --- /dev/null +++ b/openlr/way_point.hpp @@ -0,0 +1,29 @@ +#pragma once + +#include "openlr/openlr_model.hpp" + +#include "geometry/mercator.hpp" +#include "geometry/point2d.hpp" + +#include "std/cstdint.hpp" + +namespace openlr +{ +struct WayPoint final +{ + WayPoint() = default; + + WayPoint(openlr::LocationReferencePoint const & lrp) + : m_point(MercatorBounds::FromLatLon(lrp.m_latLon)) + , m_distanceToNextPointM(lrp.m_distanceToNextPoint) + , m_bearing(lrp.m_bearing) + , m_lfrcnp(lrp.m_functionalRoadClass) + { + } + + m2::PointD m_point = m2::PointD::Zero(); + double m_distanceToNextPointM = 0.0; + uint8_t m_bearing = 0; + openlr::FunctionalRoadClass m_lfrcnp = openlr::FunctionalRoadClass::NotAValue; +}; +} // namespace openlr diff --git a/qt/draw_widget.cpp b/qt/draw_widget.cpp index d70dcfb960..b86817e789 100644 --- a/qt/draw_widget.cpp +++ b/qt/draw_widget.cpp @@ -434,7 +434,7 @@ void DrawWidget::mouseReleaseEvent(QMouseEvent * e) m2::RectD rect; rect.Add(m_framework->PtoG(m2::PointD(L2D(lt.x()), L2D(lt.y())))); rect.Add(m_framework->PtoG(m2::PointD(L2D(rb.x()), L2D(rb.y())))); - m_framework->VizualizeRoadsInRect(rect); + m_framework->VisualizeRoadsInRect(rect); m_rubberBand->hide(); } } diff --git a/qt/mainwindow.cpp b/qt/mainwindow.cpp index 3f197a57eb..18acbbe095 100644 --- a/qt/mainwindow.cpp +++ b/qt/mainwindow.cpp @@ -5,17 +5,23 @@ #include "qt/preferences_dialog.hpp" #include "qt/search_panel.hpp" #include "qt/slider_ctrl.hpp" +#include "qt/traffic_mode.hpp" +#include "qt/traffic_panel.hpp" +#include "qt/trafficmodeinitdlg.h" -#include "defines.hpp" +#include "openlr/openlr_sample.hpp" #include "platform/settings.hpp" #include "platform/platform.hpp" -#include "std/bind.hpp" -#include "std/sstream.hpp" +#include "defines.hpp" + +#include <sstream> + #include "std/target_os.hpp" #include <QtGui/QCloseEvent> +#include <QFileDialog> #if QT_VERSION < QT_VERSION_CHECK(5, 0, 0) #include <QtGui/QAction> @@ -39,7 +45,6 @@ #include <QtWidgets/QLabel> #endif - #define IDM_ABOUT_DIALOG 1001 #define IDM_PREFERENCES_DIALOG 1002 @@ -54,6 +59,60 @@ #endif // NO_DOWNLOADER +namespace +{ +// TODO(mgsergio): Consider getting rid of this class: just put everything +// in TrafficMode. +class TrafficDrawerDelegate : public TrafficDrawerDelegateBase +{ +public: + explicit TrafficDrawerDelegate(qt::DrawWidget & drawWidget) + : m_framework(drawWidget.GetFramework()) + , m_drapeApi(m_framework.GetDrapeApi()) + { + } + + void SetViewportCenter(m2::PointD const & center) override + { + m_framework.SetViewportCenter(center); + } + + void DrawDecodedSegments(DecodedSample const & sample, int const sampleIndex) override + { + CHECK(!sample.GetItems().empty(), ("Sample must not be empty.")); + auto const & points = sample.GetPoints(sampleIndex); + + LOG(LINFO, ("Decoded segment", points)); + m_drapeApi.AddLine(NextLineId(), + df::DrapeApiLineData(points, dp::Color(0, 0, 255, 255)) + .Width(3.0f).ShowPoints(true /* markPoints */)); + } + + void DrawEncodedSegment(openlr::LinearSegment const & segment) override + { + auto const & points = segment.GetMercatorPoints(); + + LOG(LINFO, ("Encoded segment", points)); + m_drapeApi.AddLine(NextLineId(), + df::DrapeApiLineData(points, dp::Color(255, 0, 0, 255)) + .Width(3.0f).ShowPoints(true /* markPoints */)); + } + + void Clear() override + { + m_drapeApi.Clear(); + } + +private: + string NextLineId() { return strings::to_string(m_lineId++); } + + uint32_t m_lineId = 0; + + Framework & m_framework; + df::DrapeApi & m_drapeApi; +}; +} // namespace + namespace qt { @@ -61,7 +120,9 @@ namespace qt extern char const * kTokenKeySetting; extern char const * kTokenSecretSetting; -MainWindow::MainWindow() : m_locationService(CreateDesktopLocationService(*this)) +MainWindow::MainWindow() + : m_Docks{} + , m_locationService(CreateDesktopLocationService(*this)) { // Always runs on the first desktop QDesktopWidget const * desktop(QApplication::desktop()); @@ -98,6 +159,21 @@ MainWindow::MainWindow() : m_locationService(CreateDesktopLocationService(*this) setWindowTitle(tr("MAPS.ME")); setWindowIcon(QIcon(":/ui/logo.png")); + QMenu * trafficMarkup = new QMenu(tr("Traffic"), this); + menuBar()->addMenu(trafficMarkup); + trafficMarkup->addAction(tr("Open sample"), this, SLOT(OnOpenTrafficSample())); + m_saveTrafficSampleAction = trafficMarkup->addAction(tr("Save sample"), this, + SLOT(OnSaveTrafficSample())); + m_saveTrafficSampleAction->setEnabled(false); + + m_quitTrafficModeAction = new QAction(tr("Quit traffic mode"), this); + // On Macos actions with names started with quit or exit are threadet specially, + // see QMenuBar documentation. + m_quitTrafficModeAction->setMenuRole(QAction::MenuRole::NoRole); + m_quitTrafficModeAction->setEnabled(false); + connect(m_quitTrafficModeAction, SIGNAL(triggered()), this, SLOT(OnQuitTrafficMode())); + trafficMarkup->addAction(m_quitTrafficModeAction); + #ifndef OMIM_OS_WINDOWS QMenu * helpMenu = new QMenu(tr("Help"), this); menuBar()->addMenu(helpMenu); @@ -404,7 +480,7 @@ void MainWindow::CreateCountryStatusControls() string units; size_t sizeToDownload = 0; FormatMapSize(sizeInBytes, units, sizeToDownload); - stringstream str; + std::stringstream str; str << "Download (" << countryName << ") " << sizeToDownload << units; m_downloadButton->setText(str.str().c_str()); } @@ -414,7 +490,7 @@ void MainWindow::CreateCountryStatusControls() m_retryButton->setVisible(false); m_downloadingStatusLabel->setVisible(true); - stringstream str; + std::stringstream str; str << "Downloading (" << countryName << ") " << (int)progress << "%"; m_downloadingStatusLabel->setText(str.str().c_str()); } @@ -424,7 +500,7 @@ void MainWindow::CreateCountryStatusControls() m_retryButton->setVisible(false); m_downloadingStatusLabel->setVisible(true); - stringstream str; + std::stringstream str; str << countryName << " is waiting for downloading"; m_downloadingStatusLabel->setText(str.str().c_str()); } @@ -434,7 +510,7 @@ void MainWindow::CreateCountryStatusControls() m_retryButton->setVisible(true); m_downloadingStatusLabel->setVisible(false); - stringstream str; + std::stringstream str; str << "Retry to download " << countryName; m_retryButton->setText(str.str().c_str()); } @@ -560,7 +636,7 @@ void MainWindow::CreateSearchBarAndPanel() void MainWindow::CreatePanelImpl(size_t i, Qt::DockWidgetArea area, QString const & name, QKeySequence const & hotkey, char const * slot) { - ASSERT_LESS(i, ARRAY_SIZE(m_Docks), ()); + ASSERT_LESS(i, m_Docks.size(), ()); m_Docks[i] = new QDockWidget(name, this); addDockWidget(area, m_Docks[i]); @@ -578,6 +654,24 @@ void MainWindow::CreatePanelImpl(size_t i, Qt::DockWidgetArea area, QString cons } } +void MainWindow::CreateTrafficPanel(string const & dataFilePath, string const & sampleFilePath) +{ + CreatePanelImpl(1, Qt::RightDockWidgetArea, tr("Traffic"), QKeySequence(), nullptr); + + m_trafficMode = new TrafficMode(dataFilePath, sampleFilePath, + m_pDrawWidget->GetFramework().GetIndex(), + make_unique<TrafficDrawerDelegate>(*m_pDrawWidget)); + m_Docks[1]->setWidget(new TrafficPanel(m_trafficMode, m_Docks[1])); + m_Docks[1]->adjustSize(); +} + +void MainWindow::DestroyTrafficPanel() +{ + removeDockWidget(m_Docks[1]); + delete m_Docks[1]; + m_Docks[1] = nullptr; +} + void MainWindow::closeEvent(QCloseEvent * e) { m_pDrawWidget->PrepareShutdown(); @@ -594,6 +688,7 @@ void MainWindow::OnRetryDownloadClicked() m_pDrawWidget->RetryToDownloadCountry(m_lastCountry); } + void MainWindow::OnTrafficEnabled() { bool const enabled = m_trafficEnableAction->isChecked(); @@ -601,4 +696,37 @@ void MainWindow::OnTrafficEnabled() m_pDrawWidget->GetFramework().SaveTrafficEnabled(enabled); } +void MainWindow::OnOpenTrafficSample() +{ + TrafficModeInitDlg dlg; + dlg.exec(); + if (dlg.result() != QDialog::DialogCode::Accepted) + return; + + LOG(LDEBUG, ("Traffic mode enabled")); + CreateTrafficPanel(dlg.GetDataFilePath(), dlg.GetSampleFilePath()); + m_quitTrafficModeAction->setEnabled(true); + m_saveTrafficSampleAction->setEnabled(true); + m_Docks[1]->show(); +} + +void MainWindow::OnSaveTrafficSample() +{ + auto const & fileName = QFileDialog::getSaveFileName(this, tr("Save sample")); + if (fileName.isEmpty()) + return; + + if (!m_trafficMode->SaveSampleAs(fileName.toStdString())) + ;// TODO(mgsergio): Show error dlg; +} + +void MainWindow::OnQuitTrafficMode() +{ + // If not saved, ask a user if he/she wants to save. + // OnSaveTrafficSample() + m_quitTrafficModeAction->setEnabled(false); + m_saveTrafficSampleAction->setEnabled(false); + DestroyTrafficPanel(); + m_trafficMode = nullptr; } +} // namespace qt diff --git a/qt/mainwindow.hpp b/qt/mainwindow.hpp index 7f8a8f9f46..16fc563072 100644 --- a/qt/mainwindow.hpp +++ b/qt/mainwindow.hpp @@ -5,6 +5,7 @@ #include "platform/location.hpp" #include "platform/location_service.hpp" +#include "std/array.hpp" #include "std/unique_ptr.hpp" #include <QtWidgets/QApplication> @@ -17,6 +18,7 @@ class QDockWidget; class QPushButton; class QLabel; +class TrafficMode; namespace search { class Result; } @@ -32,9 +34,12 @@ namespace qt QAction * m_clearSelection; QAction * m_pSearchAction; QAction * m_trafficEnableAction; + QAction * m_saveTrafficSampleAction; + QAction * m_quitTrafficModeAction; DrawWidget * m_pDrawWidget; - QDockWidget * m_Docks[1]; + // TODO(mgsergio): Make indexing more informative. + array<QDockWidget *, 2> m_Docks; QPushButton * m_downloadButton; QPushButton * m_retryButton; @@ -43,6 +48,9 @@ namespace qt unique_ptr<location::LocationService> const m_locationService; + // This object is managed by Qt memory system. + TrafficMode * m_trafficMode = nullptr; + Q_OBJECT public: @@ -63,6 +71,9 @@ namespace qt void CreateSearchBarAndPanel(); void CreateCountryStatusControls(); + void CreateTrafficPanel(string const & dataFilePath, string const & sampleFilePath); + void DestroyTrafficPanel(); + #if defined(Q_WS_WIN) /// to handle menu messages virtual bool winEvent(MSG * msg, long * result); @@ -92,5 +103,8 @@ namespace qt void OnClearSelection(); void OnTrafficEnabled(); + void OnOpenTrafficSample(); + void OnSaveTrafficSample(); + void OnQuitTrafficMode(); }; } @@ -1,6 +1,6 @@ # Main application in qt. ROOT_DIR = .. -DEPENDENCIES = map drape_frontend routing search storage tracking traffic indexer drape partners_api platform editor geometry \ +DEPENDENCIES = map drape_frontend openlr routing search storage tracking traffic indexer drape partners_api platform editor geometry \ coding base freetype expat fribidi jansson protobuf osrm stats_client \ minizip succinct pugixml oauthcpp @@ -116,6 +116,9 @@ SOURCES += \ qtoglcontextfactory.cpp \ search_panel.cpp \ slider_ctrl.cpp \ + traffic_mode.cpp \ + traffic_panel.cpp \ + trafficmodeinitdlg.cpp \ update_dialog.cpp \ HEADERS += \ @@ -133,6 +136,12 @@ HEADERS += \ qtoglcontextfactory.hpp \ search_panel.hpp \ slider_ctrl.hpp \ + traffic_mode.hpp \ + traffic_panel.hpp \ + trafficmodeinitdlg.h \ update_dialog.hpp \ RESOURCES += res/resources.qrc + +FORMS += \ + trafficmodeinitdlg.ui diff --git a/qt/search_panel.cpp b/qt/search_panel.cpp index cd73224c6d..194e7b9109 100644 --- a/qt/search_panel.cpp +++ b/qt/search_panel.cpp @@ -243,7 +243,7 @@ bool SearchPanel::TryDisplacementModeCmd(QString const & str) { bool const isDefaultDisplacementMode = (str == "?dm:default"); bool const isHotelDisplacementMode = (str == "?dm:hotel"); - + if (!isDefaultDisplacementMode && !isHotelDisplacementMode) return false; diff --git a/qt/traffic_mode.cpp b/qt/traffic_mode.cpp new file mode 100644 index 0000000000..eb54b25034 --- /dev/null +++ b/qt/traffic_mode.cpp @@ -0,0 +1,207 @@ +#include "qt/traffic_mode.hpp" + +#include "openlr/openlr_simple_parser.hpp" + +#include "indexer/index.hpp" + +#include "3party/pugixml/src/pugixml.hpp" + +#include <QItemSelection> + +// DecodedSample ----------------------------------------------------------------------------------- +DecodedSample::DecodedSample(Index const & index, openlr::SamplePool const & sample) +{ + for (auto const & item : sample) + { + m_decodedItems.push_back(item); + for (auto const & mwmSegment : item.m_segments) + { + auto const & fid = mwmSegment.m_fid; + Index::FeaturesLoaderGuard g(index, fid.m_mwmId); + CHECK(fid.m_mwmId.IsAlive(), ("Mwm id is not alive.")); + if (m_features.find(fid) == end(m_features)) + { + auto & ft = m_features[fid]; + CHECK(g.GetFeatureByIndex(fid.m_index, ft), ("Can't read feature", fid)); + ft.ParseEverything(); + } + } + } +} + +vector<m2::PointD> DecodedSample::GetPoints(size_t const index) const +{ + vector<m2::PointD> points; + + auto const pushPoint = [&points](m2::PointD const & p) + { + if (points.empty() || !(points.back() - p).IsAlmostZero()) + points.push_back(p); + }; + + auto const & item = m_decodedItems[index]; + for (auto const & seg : item.m_segments) + { + auto const ftIt = m_features.find(seg.m_fid); + CHECK(ftIt != end(m_features), ("Can't find feature with id:", seg.m_fid)); + auto const & ft = ftIt->second; + auto const firstP = ft.GetPoint(seg.m_segId); + auto const secondP = ft.GetPoint(seg.m_segId + 1); + if (seg.m_isForward) + { + pushPoint(firstP); + pushPoint(secondP); + } + else + { + pushPoint(secondP); + pushPoint(firstP); + } + } + + return points; +} + +// TrafficMode ------------------------------------------------------------------------------------- +TrafficMode::TrafficMode(string const & dataFileName, string const & sampleFileName, + Index const & index, unique_ptr<TrafficDrawerDelegateBase> drawerDelagate, + QObject * parent) + : QAbstractTableModel(parent) + , m_drawerDelegate(move(drawerDelagate)) +{ + try + { + auto const & sample = openlr::LoadSamplePool(sampleFileName, index); + m_decodedSample = make_unique<DecodedSample>(index, sample); + } + catch (openlr::SamplePoolLoadError const & e) + { + LOG(LERROR, (e.Msg())); + return; + } + + pugi::xml_document doc; + if (!doc.load_file(dataFileName.data())) + { + LOG(LERROR, ("Can't load file:", dataFileName)); + return; + } + + vector<openlr::LinearSegment> segments; + if (!ParseOpenlr(doc, segments)) + { + LOG(LERROR, ("Can't parse data:", dataFileName)); + return; + } + for (auto const & segment : segments) + { + CHECK(!segment.m_locationReference.m_points.empty(), ()); + m_partnerSegments[segment.m_segmentId] = segment; + } + + m_valid = true; +} + +bool TrafficMode::SaveSampleAs(string const & fileName) const +{ + try + { + auto const & samplePool = m_decodedSample->GetItems(); + openlr::SaveSamplePool(fileName, samplePool, true /* saveEvaluation */); + } + catch (openlr::SamplePoolSaveError const & e) + { + LOG(LERROR, (e.Msg())); + return false; + } + return true; +} + +int TrafficMode::rowCount(const QModelIndex & parent) const +{ + if (!m_decodedSample) + return 0; + return m_decodedSample->m_decodedItems.size(); +} + +int TrafficMode::columnCount(const QModelIndex & parent) const +{ + return 2; +} + +QVariant TrafficMode::data(const QModelIndex & index, int role) const +{ + if (!index.isValid()) + return QVariant(); + + if (index.row() >= rowCount()) + return QVariant(); + + if (role != Qt::DisplayRole && role != Qt::EditRole) + return QVariant(); + + if (index.column() == 0) + return ToString(m_decodedSample->m_decodedItems[index.row()].m_evaluation).data(); + + if (index.column() == 1) + return m_decodedSample->m_decodedItems[index.row()].m_partnerSegmentId.Get(); + + return QVariant(); +} + +void TrafficMode::OnItemSelected(QItemSelection const & selected, QItemSelection const &) +{ + ASSERT(!selected.empty(), ("The selection should not be empty. RTFM for qt5.")); + auto const row = selected.front().top(); + + // TODO(mgsergio): Use algo for center calculation. + // Now viewport is set to the first point of the first segment. + auto const partnerSegmentId = m_decodedSample->m_decodedItems[row].m_partnerSegmentId; + + if (m_decodedSample->m_decodedItems[row].m_segments.empty()) + { + LOG(LERROR, ("Empty mwm segments for partner id", partnerSegmentId.Get())); + return; + } + + auto const & firstSegment = m_decodedSample->m_decodedItems[row].m_segments[0]; + auto const & firstSegmentFeatureId = firstSegment.m_fid; + auto const & firstSegmentFeature = m_decodedSample->m_features.at(firstSegmentFeatureId); + + LOG(LDEBUG, ("PartnerSegmentId:", partnerSegmentId.Get(), + "Segment points:", m_partnerSegments[partnerSegmentId.Get()].GetMercatorPoints(), + "Featrue segment id", firstSegment.m_segId, + "Feature segment points", firstSegmentFeature.GetPoint(firstSegment.m_segId), + firstSegmentFeature.GetPoint(firstSegment.m_segId + 1))); + + m_drawerDelegate->Clear(); + m_drawerDelegate->SetViewportCenter(firstSegmentFeature.GetPoint(firstSegment.m_segId)); + m_drawerDelegate->DrawEncodedSegment(m_partnerSegments.at(partnerSegmentId.Get())); + m_drawerDelegate->DrawDecodedSegments(*m_decodedSample, row); +} + +Qt::ItemFlags TrafficMode::flags(QModelIndex const & index) const +{ + if (!index.isValid()) + return Qt::ItemIsEnabled; + + if (index.column() != 0) + QAbstractItemModel::flags(index); + + return QAbstractItemModel::flags(index) | Qt::ItemIsEditable; +} + +bool TrafficMode::setData(QModelIndex const & index, QVariant const & value, int const role) +{ + if (!index.isValid() || role != Qt::EditRole) + return false; + + auto const newValue = value.toString(); + auto evaluation = openlr::ParseItemEvaluation(newValue.toStdString()); + if (evaluation == openlr::ItemEvaluation::NotAValue) + return false; + + m_decodedSample->m_decodedItems[index.row()].m_evaluation = evaluation; + emit dataChanged(index, index); + return true; +} diff --git a/qt/traffic_mode.hpp b/qt/traffic_mode.hpp new file mode 100644 index 0000000000..ea97af27b8 --- /dev/null +++ b/qt/traffic_mode.hpp @@ -0,0 +1,74 @@ +#pragma once + +#include "indexer/feature.hpp" + +#include "openlr/openlr_model.hpp" +#include "openlr/openlr_sample.hpp" + +#include "std/string.hpp" +#include "std/unique_ptr.hpp" +#include "std/unordered_map.hpp" + +#include <QAbstractTableModel> + +class Index; +class QItemSelection; + +struct DecodedSample +{ + DecodedSample(Index const & index, openlr::SamplePool const & sample); + + openlr::SamplePool const & GetItems() const { return m_decodedItems; } + vector<m2::PointD> GetPoints(size_t const index) const; + + map<FeatureID, FeatureType> m_features; + vector<openlr::SampleItem> m_decodedItems; +}; + +/// This class is used to delegate segments drawing to the DrapeEngine. +class TrafficDrawerDelegateBase +{ +public: + virtual ~TrafficDrawerDelegateBase() = default; + + virtual void SetViewportCenter(m2::PointD const & center) = 0; + + virtual void DrawDecodedSegments(DecodedSample const & sample, int sampleIndex) = 0; + virtual void DrawEncodedSegment(openlr::LinearSegment const & segment) = 0; + virtual void Clear() = 0; +}; + +/// This class is used to map sample ids to real data +/// and change sample evaluations. +class TrafficMode : public QAbstractTableModel +{ + Q_OBJECT + +public: + TrafficMode(string const & dataFileName, string const & sampleFileName, Index const & index, + unique_ptr<TrafficDrawerDelegateBase> drawerDelagate, QObject * parent = Q_NULLPTR); + + bool SaveSampleAs(string const & fileName) const; + bool IsValid() const { return m_valid; } + + int rowCount(const QModelIndex & parent = QModelIndex()) const Q_DECL_OVERRIDE; + int columnCount(const QModelIndex & parent = QModelIndex()) const Q_DECL_OVERRIDE; + + QVariant data(const QModelIndex & index, int role) const Q_DECL_OVERRIDE; + // QVariant headerData(int section, Qt::Orientation orientation, + // int role = Qt::DisplayRole) const Q_DECL_OVERRIDE; + + Qt::ItemFlags flags(QModelIndex const & index) const Q_DECL_OVERRIDE; + bool setData(QModelIndex const & index, QVariant const & value, int role = Qt::EditRole) Q_DECL_OVERRIDE; + +public slots: + void OnItemSelected(QItemSelection const & selected, QItemSelection const &); + +private: + unique_ptr<DecodedSample> m_decodedSample; + unordered_map<decltype(openlr::LinearSegment::m_segmentId), openlr::LinearSegment> m_partnerSegments; + + unique_ptr<TrafficDrawerDelegateBase> m_drawerDelegate; + + bool m_valid = false; +}; diff --git a/qt/traffic_panel.cpp b/qt/traffic_panel.cpp new file mode 100644 index 0000000000..57e79c75dd --- /dev/null +++ b/qt/traffic_panel.cpp @@ -0,0 +1,75 @@ +#include "qt/traffic_panel.hpp" +#include "qt/traffic_mode.hpp" + +#include <QAbstractTableModel> +#include <QBoxLayout> +#include <QComboBox> +#include <QHeaderView> +#include <QStyledItemDelegate> +#include <QTableView> + +// ComboBoxDelegate -------------------------------------------------------------------------------- +ComboBoxDelegate::ComboBoxDelegate(QObject * parent) + : QStyledItemDelegate(parent) +{ +} + +QWidget * ComboBoxDelegate::createEditor(QWidget * parent, QStyleOptionViewItem const & option, + QModelIndex const & index) const +{ + auto * editor = new QComboBox(parent); + editor->setFrame(false); + editor->setEditable(false); + editor->addItems({"Unevaluated", "Positive", "Negative", "RelPositive", "RelNegative", "Ignore"}); + + return editor; +} + +void ComboBoxDelegate::setEditorData(QWidget * editor, QModelIndex const & index) const +{ + auto const value = index.model()->data(index, Qt::EditRole).toString(); + static_cast<QComboBox*>(editor)->setCurrentText(value); +} + +void ComboBoxDelegate::setModelData(QWidget * editor, QAbstractItemModel * model, + QModelIndex const & index) const +{ + model->setData(index, static_cast<QComboBox*>(editor)->currentText(), Qt::EditRole); +} + +void ComboBoxDelegate::updateEditorGeometry(QWidget * editor, QStyleOptionViewItem const & option, + QModelIndex const & index) const +{ + editor->setGeometry(option.rect); +} + +// TrafficPanel ------------------------------------------------------------------------------------ +TrafficPanel::TrafficPanel(QAbstractItemModel * trafficModel, QWidget * parent) + : QWidget(parent) +{ + CreateTable(trafficModel); + + auto * layout = new QVBoxLayout(); + layout->addWidget(m_table); + setLayout(layout); +} + +void TrafficPanel::CreateTable(QAbstractItemModel * trafficModel) +{ + m_table = new QTableView(); + m_table->setFocusPolicy(Qt::NoFocus); + m_table->setAlternatingRowColors(true); + m_table->setShowGrid(false); + m_table->setSelectionBehavior(QAbstractItemView::SelectionBehavior::SelectRows); + m_table->setSelectionMode(QAbstractItemView::SelectionMode::SingleSelection); + m_table->verticalHeader()->setVisible(false); + m_table->horizontalHeader()->setVisible(false); + m_table->horizontalHeader()->setSectionResizeMode(QHeaderView::Stretch); + + m_table->setModel(trafficModel); + m_table->setItemDelegate(new ComboBoxDelegate()); + + connect(m_table->selectionModel(), + SIGNAL(selectionChanged(QItemSelection const &, QItemSelection const &)), + trafficModel, SLOT(OnItemSelected(QItemSelection const &, QItemSelection const &))); +} diff --git a/qt/traffic_panel.hpp b/qt/traffic_panel.hpp new file mode 100644 index 0000000000..833d061555 --- /dev/null +++ b/qt/traffic_panel.hpp @@ -0,0 +1,47 @@ +#pragma once + +#include <QStyledItemDelegate> + +class QAbstractItemModel; +class QComboBox; +class QTableView; +class QWidget; + +class ComboBoxDelegate : public QStyledItemDelegate +{ + Q_OBJECT + +public: + ComboBoxDelegate(QObject * parent = 0); + + QWidget * createEditor(QWidget * parent, QStyleOptionViewItem const & option, + QModelIndex const & index) const Q_DECL_OVERRIDE; + + void setEditorData(QWidget * editor, QModelIndex const & index) const Q_DECL_OVERRIDE; + + void setModelData(QWidget * editor, QAbstractItemModel * model, + QModelIndex const & index) const Q_DECL_OVERRIDE; + + void updateEditorGeometry(QWidget * editor, QStyleOptionViewItem const & option, + QModelIndex const & index) const Q_DECL_OVERRIDE; +}; + +class TrafficPanel : public QWidget +{ + Q_OBJECT + +public: + explicit TrafficPanel(QAbstractItemModel * trafficModel, QWidget * parent); + +private: + void CreateTable(QAbstractItemModel * trafficModel); + void FillTable(); + +signals: + +public slots: + // void OnCheckBoxClicked(int row, int state); + +private: + QTableView * m_table = Q_NULLPTR; +}; diff --git a/qt/trafficmodeinitdlg.cpp b/qt/trafficmodeinitdlg.cpp new file mode 100644 index 0000000000..fef3a16232 --- /dev/null +++ b/qt/trafficmodeinitdlg.cpp @@ -0,0 +1,62 @@ +#include "qt/trafficmodeinitdlg.h" +#include "ui_trafficmodeinitdlg.h" + +#include "platform/settings.hpp" + +#include <QFileDialog> + +namespace +{ +string const kDataFilePath = "LastTrafficDataFilePath"; +string const kSampleFilePath = "LastTrafficSampleFilePath"; +} // namespace + +TrafficModeInitDlg::TrafficModeInitDlg(QWidget * parent) : + QDialog(parent), + m_ui(new Ui::TrafficModeInitDlg) +{ + m_ui->setupUi(this); + + string lastDataFilePath; + string lastSampleFilePath; + if (settings::Get(kDataFilePath, lastDataFilePath)) + m_ui->dataFileName->setText(QString::fromStdString(lastDataFilePath)); + if (settings::Get(kSampleFilePath, lastSampleFilePath)) + m_ui->sampleFileName->setText(QString::fromStdString(lastSampleFilePath)); + + connect(m_ui->chooseDataFileButton, &QPushButton::clicked, [this](bool) + { + SetFilePathViaDialog(*m_ui->dataFileName, tr("Choose traffic data file"), "*.xml"); + }); + connect(m_ui->chooseSampleFileButton, &QPushButton::clicked, [this](bool) + { + SetFilePathViaDialog(*m_ui->sampleFileName, tr("Choose traffic sample file")); + }); +} + +TrafficModeInitDlg::~TrafficModeInitDlg() +{ + delete m_ui; +} + +void TrafficModeInitDlg::accept() +{ + m_dataFileName = m_ui->dataFileName->text().trimmed().toStdString(); + m_sampleFileName = m_ui->sampleFileName->text().trimmed().toStdString(); + + settings::Set(kDataFilePath, m_dataFileName); + settings::Set(kSampleFilePath, m_sampleFileName); + + QDialog::accept(); +} + +void TrafficModeInitDlg::SetFilePathViaDialog(QLineEdit & dest, QString const & title, + QString const & filter) +{ + QFileDialog openFileDlg(nullptr, title, {} /* directory */, filter); + openFileDlg.exec(); + if (openFileDlg.result() != QDialog::DialogCode::Accepted) + return; + + dest.setText(openFileDlg.selectedFiles().first()); +} diff --git a/qt/trafficmodeinitdlg.h b/qt/trafficmodeinitdlg.h new file mode 100644 index 0000000000..d182507a50 --- /dev/null +++ b/qt/trafficmodeinitdlg.h @@ -0,0 +1,35 @@ +#pragma once + +#include <string> + +#include <QDialog> + +class QLineEdit; + +namespace Ui { +class TrafficModeInitDlg; +} + +class TrafficModeInitDlg : public QDialog +{ + Q_OBJECT + +public: + explicit TrafficModeInitDlg(QWidget * parent = nullptr); + ~TrafficModeInitDlg(); + + std::string GetDataFilePath() const { return m_dataFileName; } + std::string GetSampleFilePath() const { return m_sampleFileName; } + +private: + void SetFilePathViaDialog(QLineEdit & dest, QString const & title, + QString const & filter = {}); +public slots: + void accept() override; + +private: + Ui::TrafficModeInitDlg * m_ui; + + std::string m_dataFileName; + std::string m_sampleFileName; +}; diff --git a/qt/trafficmodeinitdlg.ui b/qt/trafficmodeinitdlg.ui new file mode 100644 index 0000000000..1ce7c4fe58 --- /dev/null +++ b/qt/trafficmodeinitdlg.ui @@ -0,0 +1,128 @@ +<?xml version="1.0" encoding="UTF-8"?> +<ui version="4.0"> + <class>TrafficModeInitDlg</class> + <widget class="QDialog" name="TrafficModeInitDlg"> + <property name="geometry"> + <rect> + <x>0</x> + <y>0</y> + <width>478</width> + <height>130</height> + </rect> + </property> + <property name="windowTitle"> + <string>Select traffic files</string> + </property> + <property name="modal"> + <bool>true</bool> + </property> + <widget class="QWidget" name="gridLayoutWidget"> + <property name="geometry"> + <rect> + <x>20</x> + <y>10</y> + <width>441</width> + <height>111</height> + </rect> + </property> + <layout class="QGridLayout" name="gridLayout"> + <item row="2" column="3"> + <widget class="QPushButton" name="chooseSampleFileButton"> + <property name="text"> + <string>Choose...</string> + </property> + </widget> + </item> + <item row="0" column="0"> + <widget class="QLabel" name="dataLabel"> + <property name="mouseTracking"> + <bool>true</bool> + </property> + <property name="text"> + <string><html><head/><body><p>Traffic data:</p></body></html></string> + </property> + </widget> + </item> + <item row="0" column="1" colspan="2"> + <widget class="QLineEdit" name="dataFileName"/> + </item> + <item row="2" column="1" colspan="2"> + <widget class="QLineEdit" name="sampleFileName"> + <property name="text"> + <string/> + </property> + </widget> + </item> + <item row="3" column="3"> + <widget class="QPushButton" name="okButton"> + <property name="text"> + <string>Ok</string> + </property> + </widget> + </item> + <item row="2" column="0"> + <widget class="QLabel" name="label_2"> + <property name="text"> + <string>Traffic sample:</string> + </property> + </widget> + </item> + <item row="0" column="3"> + <widget class="QPushButton" name="chooseDataFileButton"> + <property name="text"> + <string>Choose...</string> + </property> + </widget> + </item> + <item row="3" column="2"> + <widget class="QPushButton" name="cancelButton"> + <property name="text"> + <string>Cancel</string> + </property> + </widget> + </item> + </layout> + </widget> + </widget> + <tabstops> + <tabstop>dataFileName</tabstop> + <tabstop>chooseDataFileButton</tabstop> + <tabstop>sampleFileName</tabstop> + <tabstop>chooseSampleFileButton</tabstop> + </tabstops> + <resources/> + <connections> + <connection> + <sender>cancelButton</sender> + <signal>clicked()</signal> + <receiver>TrafficModeInitDlg</receiver> + <slot>reject()</slot> + <hints> + <hint type="sourcelabel"> + <x>290</x> + <y>103</y> + </hint> + <hint type="destinationlabel"> + <x>164</x> + <y>98</y> + </hint> + </hints> + </connection> + <connection> + <sender>okButton</sender> + <signal>clicked()</signal> + <receiver>TrafficModeInitDlg</receiver> + <slot>accept()</slot> + <hints> + <hint type="sourcelabel"> + <x>405</x> + <y>105</y> + </hint> + <hint type="destinationlabel"> + <x>59</x> + <y>94</y> + </hint> + </hints> + </connection> + </connections> +</ui> diff --git a/routing/features_road_graph.hpp b/routing/features_road_graph.hpp index 7657e7dc6f..9634a1b307 100644 --- a/routing/features_road_graph.hpp +++ b/routing/features_road_graph.hpp @@ -76,6 +76,8 @@ public: IRoadGraph::Mode GetMode() const override; void ClearState() override; + bool IsRoad(FeatureType const & ft) const; + private: friend class CrossFeaturesLoader; @@ -90,7 +92,6 @@ private: unique_ptr<feature::AltitudeLoader> m_altitudeLoader; }; - bool IsRoad(FeatureType const & ft) const; bool IsOneWay(FeatureType const & ft) const; double GetSpeedKMPHFromFt(FeatureType const & ft) const; diff --git a/routing/road_graph.cpp b/routing/road_graph.cpp index db72d0bb2c..52597f86b8 100644 --- a/routing/road_graph.cpp +++ b/routing/road_graph.cpp @@ -12,6 +12,7 @@ #include "base/math.hpp" #include "base/stl_helpers.hpp" +#include "std/algorithm.hpp" #include "std/limits.hpp" #include "std/sstream.hpp" @@ -23,15 +24,16 @@ bool OnEdge(Junction const & p, Edge const & ab) { auto const & a = ab.GetStartJunction(); auto const & b = ab.GetEndJunction(); - return m2::IsPointOnSegment(p.GetPoint(), a.GetPoint(), b.GetPoint()); + return m2::IsPointOnSegmentEps(p.GetPoint(), a.GetPoint(), b.GetPoint(), 1e-9); } void SplitEdge(Edge const & ab, Junction const & p, vector<Edge> & edges) { auto const & a = ab.GetStartJunction(); auto const & b = ab.GetEndJunction(); - edges.push_back(Edge::MakeFake(a, p)); - edges.push_back(Edge::MakeFake(p, b)); + bool const partOfReal = ab.IsPartOfReal(); + edges.push_back(Edge::MakeFake(a, p, partOfReal)); + edges.push_back(Edge::MakeFake(p, b, partOfReal)); } } // namespace @@ -51,20 +53,33 @@ string DebugPrint(Junction const & r) // Edge ------------------------------------------------------------------------ -Edge Edge::MakeFake(Junction const & startJunction, Junction const & endJunction) +Edge Edge::MakeFake(Junction const & startJunction, Junction const & endJunction, bool partOfReal) { - return Edge(FeatureID(), true /* forward */, 0 /* segId */, startJunction, endJunction); + Edge edge(FeatureID(), true /* forward */, 0 /* segId */, startJunction, endJunction); + edge.m_partOfReal = partOfReal; + return edge; } -Edge::Edge(FeatureID const & featureId, bool forward, uint32_t segId, Junction const & startJunction, Junction const & endJunction) - : m_featureId(featureId), m_forward(forward), m_segId(segId), m_startJunction(startJunction), m_endJunction(endJunction) +Edge::Edge() : m_forward(true), m_segId(0) { m_partOfReal = !IsFake(); } + +Edge::Edge(FeatureID const & featureId, bool forward, uint32_t segId, + Junction const & startJunction, Junction const & endJunction) + : m_featureId(featureId) + , m_forward(forward) + , m_segId(segId) + , m_startJunction(startJunction) + , m_endJunction(endJunction) { ASSERT_LESS(segId, numeric_limits<uint32_t>::max(), ()); + m_partOfReal = !IsFake(); } Edge Edge::GetReverseEdge() const { - return Edge(m_featureId, !m_forward, m_segId, m_endJunction, m_startJunction); + Edge edge = *this; + edge.m_forward = !edge.m_forward; + swap(edge.m_startJunction, edge.m_endJunction); + return edge; } bool Edge::SameRoadSegmentAndDirection(Edge const & r) const @@ -76,11 +91,9 @@ bool Edge::SameRoadSegmentAndDirection(Edge const & r) const bool Edge::operator==(Edge const & r) const { - return m_featureId == r.m_featureId && - m_forward == r.m_forward && - m_segId == r.m_segId && - m_startJunction == r.m_startJunction && - m_endJunction == r.m_endJunction; + return m_featureId == r.m_featureId && m_forward == r.m_forward && + m_partOfReal == r.m_partOfReal && m_segId == r.m_segId && + m_startJunction == r.m_startJunction && m_endJunction == r.m_endJunction; } bool Edge::operator<(Edge const & r) const @@ -89,6 +102,8 @@ bool Edge::operator<(Edge const & r) const return m_featureId < r.m_featureId; if (m_forward != r.m_forward) return (m_forward == false); + if (m_partOfReal != r.m_partOfReal) + return (m_partOfReal == false); if (m_segId != r.m_segId) return m_segId < r.m_segId; if (!(m_startJunction == r.m_startJunction)) @@ -102,7 +117,8 @@ string DebugPrint(Edge const & r) { ostringstream ss; ss << "Edge{featureId: " << DebugPrint(r.GetFeatureId()) << ", isForward:" << r.IsForward() - << ", segId:" << r.m_segId << ", startJunction:" << DebugPrint(r.m_startJunction) + << ", partOfReal:" << r.IsPartOfReal() << ", segId:" << r.m_segId + << ", startJunction:" << DebugPrint(r.m_startJunction) << ", endJunction:" << DebugPrint(r.m_endJunction) << "}"; return ss.str(); } @@ -198,8 +214,9 @@ void IRoadGraph::AddFakeEdges(Junction const & junction, vector<Edge> edges; SplitEdge(ab, p, edges); - edges.push_back(Edge::MakeFake(junction, p)); - edges.push_back(Edge::MakeFake(p, junction)); + + edges.push_back(Edge::MakeFake(junction, p, false /* partOfReal */)); + edges.push_back(Edge::MakeFake(p, junction, false /* partOfReal */)); ForEachFakeEdge([&](Edge const & uv) { diff --git a/routing/road_graph.hpp b/routing/road_graph.hpp index 1d0f1118cf..6fcc21a6c9 100644 --- a/routing/road_graph.hpp +++ b/routing/road_graph.hpp @@ -25,6 +25,7 @@ public: Junction & operator=(Junction const &) = default; inline bool operator==(Junction const & r) const { return m_point == r.m_point; } + inline bool operator!=(Junction const & r) const { return !(*this == r); } inline bool operator<(Junction const & r) const { return m_point < r.m_point; } inline m2::PointD const & GetPoint() const { return m_point; } @@ -52,10 +53,12 @@ inline bool AlmostEqualAbs(Junction const & lhs, Junction const & rhs) class Edge { public: - static Edge MakeFake(Junction const & startJunction, Junction const & endJunction); + static Edge MakeFake(Junction const & startJunction, Junction const & endJunction, + bool partOfReal); - Edge() : m_forward(true), m_segId(0) {} - Edge(FeatureID const & featureId, bool forward, uint32_t segId, Junction const & startJunction, Junction const & endJunction); + Edge(); + Edge(FeatureID const & featureId, bool forward, uint32_t segId, Junction const & startJunction, + Junction const & endJunction); Edge(Edge const &) = default; Edge & operator=(Edge const &) = default; @@ -65,6 +68,7 @@ public: inline Junction const & GetStartJunction() const { return m_startJunction; } inline Junction const & GetEndJunction() const { return m_endJunction; } inline bool IsFake() const { return !m_featureId.IsValid(); } + inline bool IsPartOfReal() const { return m_partOfReal; } Edge GetReverseEdge() const; @@ -82,6 +86,9 @@ private: // Is the feature along the road. bool m_forward; + // This flag is set for edges that are parts of some real edges. + bool m_partOfReal; + // Ordinal number of the segment on the road. uint32_t m_segId; @@ -261,7 +268,6 @@ public: /// Clear all temporary buffers. virtual void ClearState() {} -private: /// \brief Finds all outgoing regular (non-fake) edges for junction. void GetRegularOutgoingEdges(Junction const & junction, TEdgeVector & edges) const; /// \brief Finds all ingoing regular (non-fake) edges for junction. @@ -271,6 +277,7 @@ private: /// \brief Finds all ingoing fake edges for junction. void GetFakeIngoingEdges(Junction const & junction, TEdgeVector & edges) const; +private: template <typename Fn> void ForEachFakeEdge(Fn && fn) { diff --git a/routing/router.cpp b/routing/router.cpp index eb3dc93e79..bd6e5af5ff 100644 --- a/routing/router.cpp +++ b/routing/router.cpp @@ -3,7 +3,7 @@ namespace routing { -string ToString(RouterType type) +std::string ToString(RouterType type) { switch(type) { @@ -16,7 +16,7 @@ string ToString(RouterType type) return "Error"; } -RouterType FromString(string const & str) +RouterType FromString(std::string const & str) { if (str == "vehicle") return RouterType::Vehicle; diff --git a/routing/router.hpp b/routing/router.hpp index 1e8e0da7d9..31fe361ad1 100644 --- a/routing/router.hpp +++ b/routing/router.hpp @@ -6,13 +6,13 @@ #include "base/cancellable.hpp" -#include "std/function.hpp" -#include "std/string.hpp" +#include <functional> +#include <string> namespace routing { -using TCountryFileFn = function<string(m2::PointD const &)>; +using TCountryFileFn = std::function<std::string(m2::PointD const &)>; class Route; @@ -26,8 +26,8 @@ enum class RouterType Taxi, /// For taxi route calculation Vehicle routing is used. }; -string ToString(RouterType type); -RouterType FromString(string const & str); +std::string ToString(RouterType type); +RouterType FromString(std::string const & str); class IRouter { @@ -55,7 +55,7 @@ public: virtual ~IRouter() {} /// Return unique name of a router implementation. - virtual string GetName() const = 0; + virtual std::string GetName() const = 0; /// Clear all temporary buffers. virtual void ClearState() {} diff --git a/std/functional.hpp b/std/functional.hpp index 7f66ef70d4..6236824d72 100644 --- a/std/functional.hpp +++ b/std/functional.hpp @@ -5,12 +5,13 @@ #endif #include <functional> -using std::less; -using std::less_equal; -using std::greater; using std::equal_to; -using std::hash; using std::function; +using std::greater; +using std::hash; +using std::less; +using std::less_equal; +using std::mem_fn; using std::ref; #ifdef DEBUG_NEW |