diff options
author | Добрый Ээх <bukharaev@gmail.com> | 2017-05-16 11:55:58 +0300 |
---|---|---|
committer | Yuri Gorshenin <mipt.vi002@gmail.com> | 2017-08-11 17:46:36 +0300 |
commit | 993debefd3a717769da5859963ddee8fd66180c5 (patch) | |
tree | 4cc7768c06029a6ec3fffdf089ba85447806d906 /track_analyzing | |
parent | fe2fbc1511e6dd5d5c68b1aa6991e4908c227782 (diff) |
[routing] track analyzer
Diffstat (limited to 'track_analyzing')
-rw-r--r-- | track_analyzing/CMakeLists.txt | 17 | ||||
-rw-r--r-- | track_analyzing/exceptions.hpp | 8 | ||||
-rw-r--r-- | track_analyzing/log_parser.cpp | 168 | ||||
-rw-r--r-- | track_analyzing/log_parser.hpp | 32 | ||||
-rw-r--r-- | track_analyzing/serialization.hpp | 173 | ||||
-rw-r--r-- | track_analyzing/track.hpp | 73 | ||||
-rw-r--r-- | track_analyzing/track_analyzer/CMakeLists.txt | 48 | ||||
-rw-r--r-- | track_analyzing/track_analyzer/cmd_cpp_track.cpp | 31 | ||||
-rw-r--r-- | track_analyzing/track_analyzer/cmd_match.cpp | 112 | ||||
-rw-r--r-- | track_analyzing/track_analyzer/cmd_table.cpp | 290 | ||||
-rw-r--r-- | track_analyzing/track_analyzer/cmd_track.cpp | 77 | ||||
-rw-r--r-- | track_analyzing/track_analyzer/cmd_tracks.cpp | 233 | ||||
-rw-r--r-- | track_analyzing/track_analyzer/track_analyzer.cpp | 118 | ||||
-rw-r--r-- | track_analyzing/track_matcher.cpp | 240 | ||||
-rw-r--r-- | track_analyzing/track_matcher.hpp | 87 | ||||
-rw-r--r-- | track_analyzing/utils.cpp | 92 | ||||
-rw-r--r-- | track_analyzing/utils.hpp | 86 |
17 files changed, 1885 insertions, 0 deletions
diff --git a/track_analyzing/CMakeLists.txt b/track_analyzing/CMakeLists.txt new file mode 100644 index 0000000000..6008a3ea25 --- /dev/null +++ b/track_analyzing/CMakeLists.txt @@ -0,0 +1,17 @@ +project(track_analyzing) + +set( + SRC + exceptions.hpp + log_parser.cpp + log_parser.hpp + serialization.hpp + track.hpp + track_matcher.cpp + track_matcher.hpp + utils.cpp + utils.hpp +) + +add_library(${PROJECT_NAME} ${SRC}) +add_subdirectory(track_analyzer) diff --git a/track_analyzing/exceptions.hpp b/track_analyzing/exceptions.hpp new file mode 100644 index 0000000000..a76337f841 --- /dev/null +++ b/track_analyzing/exceptions.hpp @@ -0,0 +1,8 @@ +#pragma once + +#include "base/exception.hpp" + +namespace tracking +{ +DECLARE_EXCEPTION(MessageException, RootException); +} // namespace tracking diff --git a/track_analyzing/log_parser.cpp b/track_analyzing/log_parser.cpp new file mode 100644 index 0000000000..c1dd61c7a6 --- /dev/null +++ b/track_analyzing/log_parser.cpp @@ -0,0 +1,168 @@ +#include <generator/borders_generator.hpp> +#include <coding/file_name_utils.hpp> +#include <generator/borders_loader.hpp> +#include <regex> +#include <fstream> +#include <unordered_set> +#include <platform/platform.hpp> +#include <base/timer.hpp> +#include <coding/hex.hpp> +#include "track_analyzing/log_parser.hpp" +#include <cstdint> +#include <geometry/mercator.hpp> + +using namespace std; +using namespace tracking; + +namespace +{ +vector<DataPoint> ReadDataPoints(string const & data) +{ + string const decoded = FromHex(data); + vector<uint8_t> buffer; + for (auto c : decoded) + buffer.push_back(static_cast<uint8_t>(c)); + + vector<DataPoint> points; + MemReader memReader(buffer.data(), buffer.size()); + ReaderSource<MemReader> src(memReader); + coding::TrafficGPSEncoder::DeserializeDataPoints(1 /* version */, src, points); + return points; +} + +class PointToMwmId final +{ +public: + PointToMwmId(shared_ptr<m4::Tree<routing::NumMwmId>> mwmTree, + routing::NumMwmIds const & numMwmIds, string const & dataDir) + : m_mwmTree(mwmTree) + { + numMwmIds.ForEachId([&](routing::NumMwmId numMwmId) { + string const & mwmName = numMwmIds.GetFile(numMwmId).GetName(); + string const polyFile = my::JoinPath(dataDir, BORDERS_DIR, mwmName + BORDERS_EXTENSION); + osm::LoadBorders(polyFile, m_borders[numMwmId]); + }); + } + + routing::NumMwmId FindMwmId(m2::PointD const & point, routing::NumMwmId expectedId) const + { + if (expectedId != routing::kFakeNumMwmId && m2::RegionsContain(GetBorders(expectedId), point)) + return expectedId; + + routing::NumMwmId result = routing::kFakeNumMwmId; + m2::RectD const rect = MercatorBounds::RectByCenterXYAndSizeInMeters(point, 1); + m_mwmTree->ForEachInRect(rect, [&](routing::NumMwmId numMwmId) { + if (m2::RegionsContain(GetBorders(numMwmId), point)) + { + result = numMwmId; + return; + } + }); + + return result; + } + +private: + vector<m2::RegionD> const & GetBorders(routing::NumMwmId numMwmId) const + { + auto it = m_borders.find(numMwmId); + CHECK(it != m_borders.cend(), ()); + return it->second; + } + + shared_ptr<m4::Tree<routing::NumMwmId>> m_mwmTree; + unordered_map<routing::NumMwmId, vector<m2::RegionD>> m_borders; +}; +} // namespace + +namespace tracking +{ +LogParser::LogParser(shared_ptr<routing::NumMwmIds> numMwmIds, + unique_ptr<m4::Tree<routing::NumMwmId>> mwmTree, string const & dataDir) + : m_numMwmIds(move(numMwmIds)), m_mwmTree(move(mwmTree)), m_dataDir(dataDir) +{ + CHECK(m_numMwmIds, ()); + CHECK(m_mwmTree, ()); +} + +void LogParser::Parse(string const & logFile, MwmToTracks & mwmToTracks) const +{ + UserToTrack userToTrack; + ParseUserTracks(logFile, userToTrack); + SplitIntoMwms(userToTrack, mwmToTracks); +} + +void LogParser::ParseUserTracks(string const & logFile, UserToTrack & userToTrack) const +{ + my::Timer timer; + + std::ifstream stream(logFile); + CHECK(stream.is_open(), ("Can't open file", logFile)); + + std::regex const base_regex( + ".*(DataV0|CurrentData)\\s+aloha_id\\s*:\\s*(\\S+)\\s+.*\\|(\\w+)\\|"); + std::unordered_set<string> usersWithOldVersion; + size_t linesCount = 0; + size_t pointsCount = 0; + + for (string line; getline(stream, line);) + { + std::smatch base_match; + if (!std::regex_match(line, base_match, base_regex)) + continue; + + CHECK_EQUAL(base_match.size(), 4, ()); + + string const version = base_match[1].str(); + string const userId = base_match[2].str(); + string const data = base_match[3].str(); + if (version != "CurrentData") + { + CHECK_EQUAL(version, "DataV0", ()); + usersWithOldVersion.insert(userId); + continue; + } + + auto const packet = ReadDataPoints(data); + if (!packet.empty()) + { + Track & track = userToTrack[userId]; + track.insert(track.end(), packet.begin(), packet.end()); + } + + ++linesCount; + pointsCount += packet.size(); + }; + + LOG(LINFO, ("Tracks parsing finished, elapsed:", timer.ElapsedSeconds(), "seconds, lines:", + linesCount, ", points", pointsCount)); + LOG(LINFO, ("Users with current version:", userToTrack.size(), ", old version:", + usersWithOldVersion.size())); +} + +void LogParser::SplitIntoMwms(UserToTrack const & userToTrack, MwmToTracks & mwmToTracks) const +{ + my::Timer timer; + + PointToMwmId const pointToMwmId(m_mwmTree, *m_numMwmIds, m_dataDir); + + for (auto & it : userToTrack) + { + string const & user = it.first; + Track const & track = it.second; + + routing::NumMwmId mwmId = routing::kFakeNumMwmId; + for (DataPoint const & point : track) + { + mwmId = pointToMwmId.FindMwmId(MercatorBounds::FromLatLon(point.m_latLon), mwmId); + if (mwmId != routing::kFakeNumMwmId) + mwmToTracks[mwmId][user].push_back(point); + else + LOG(LERROR, ("Can't match mwm region for", point.m_latLon, ", user:", user)); + } + } + + LOG(LINFO, ("Data was splitted into", mwmToTracks.size(), "mwms, elapsed:", + timer.ElapsedSeconds(), "seconds")); +} +} // namespace tracking diff --git a/track_analyzing/log_parser.hpp b/track_analyzing/log_parser.hpp new file mode 100644 index 0000000000..63df4fda87 --- /dev/null +++ b/track_analyzing/log_parser.hpp @@ -0,0 +1,32 @@ +#pragma once + +#include "track_analyzing/track.hpp" + +#include "routing/num_mwm_id.hpp" + +#include "geometry/tree4d.hpp" + +#include <memory> +#include <string> +#include <unordered_map> +#include <vector> + +namespace tracking +{ +class LogParser final +{ +public: + LogParser(std::shared_ptr<routing::NumMwmIds> numMwmIds, + std::unique_ptr<m4::Tree<routing::NumMwmId>> mwmTree, std::string const & dataDir); + + void Parse(std::string const & logFile, MwmToTracks & mwmToTracks) const; + +private: + void ParseUserTracks(std::string const & logFile, UserToTrack & userToTrack) const; + void SplitIntoMwms(UserToTrack const & userToTrack, MwmToTracks & mwmToTracks) const; + + std::shared_ptr<routing::NumMwmIds> m_numMwmIds; + std::shared_ptr<m4::Tree<routing::NumMwmId>> m_mwmTree; + std::string const m_dataDir; +}; +} // namespace tracking diff --git a/track_analyzing/serialization.hpp b/track_analyzing/serialization.hpp new file mode 100644 index 0000000000..f0d0b87865 --- /dev/null +++ b/track_analyzing/serialization.hpp @@ -0,0 +1,173 @@ +#pragma once + +#include "track_analyzing/track.hpp" + +#include "routing/num_mwm_id.hpp" +#include "routing/segment.hpp" + +#include "platform/country_file.hpp" + +#include "coding/read_write_utils.hpp" +#include "coding/reader.hpp" +#include "coding/traffic.hpp" +#include "coding/varint.hpp" +#include "coding/write_to_sink.hpp" +#include "coding/writer.hpp" + +#include "base/assert.hpp" +#include "base/checked_cast.hpp" + +#include <cstdint> +#include <memory> +#include <vector> + +namespace tracking +{ +class MwmToMatchedTracksSerializer final +{ +public: + MwmToMatchedTracksSerializer(std::shared_ptr<routing::NumMwmIds> numMwmIds) + : m_numMwmIds(numMwmIds) + { + } + + template <class Sink> + void Serialize(MwmToMatchedTracks const & mwmToMatchedTracks, Sink & sink) + { + WriteSize(sink, mwmToMatchedTracks.size()); + + for (auto const & mwmIt : mwmToMatchedTracks) + { + rw::Write(sink, m_numMwmIds->GetFile(mwmIt.first).GetName()); + + UserToMatchedTracks const & userToMatchedTracks = mwmIt.second; + CHECK(!userToMatchedTracks.empty(), ()); + WriteSize(sink, userToMatchedTracks.size()); + + for (auto const & userIt : userToMatchedTracks) + { + rw::Write(sink, userIt.first); + + std::vector<MatchedTrack> const & tracks = userIt.second; + CHECK(!tracks.empty(), ()); + WriteSize(sink, tracks.size()); + + for (MatchedTrack const & track : tracks) + { + CHECK(!track.empty(), ()); + WriteSize(sink, track.size()); + + for (MatchedTrackPoint const & point : track) + Serialize(point.GetSegment(), sink); + + std::vector<DataPoint> dataPoints; + for (MatchedTrackPoint const & point : track) + dataPoints.push_back(point.GetDataPoint()); + + std::vector<uint8_t> buffer; + MemWriter<decltype(buffer)> memWriter(buffer); + coding::TrafficGPSEncoder::SerializeDataPoints(coding::TrafficGPSEncoder::kLatestVersion, + memWriter, dataPoints); + + WriteSize(sink, buffer.size()); + sink.Write(buffer.data(), buffer.size()); + } + } + } + } + + template <class Source> + void Deserialize(MwmToMatchedTracks & mwmToMatchedTracks, Source & src) + { + mwmToMatchedTracks.clear(); + + auto const numMmws = ReadSize(src); + for (size_t iMwm = 0; iMwm < numMmws; ++iMwm) + { + std::string mwmName; + rw::Read(src, mwmName); + + auto const mwmId = m_numMwmIds->GetId(platform::CountryFile(mwmName)); + UserToMatchedTracks & userToMatchedTracks = mwmToMatchedTracks[mwmId]; + + auto const numUsers = ReadSize(src); + CHECK_NOT_EQUAL(numUsers, 0, ()); + for (size_t iUser = 0; iUser < numUsers; ++iUser) + { + std::string user; + rw::Read(src, user); + + std::vector<MatchedTrack> & tracks = userToMatchedTracks[user]; + auto const numTracks = ReadSize(src); + CHECK_NOT_EQUAL(numTracks, 0, ()); + tracks.resize(numTracks); + + for (size_t iTrack = 0; iTrack < numTracks; ++iTrack) + { + auto const numSegments = ReadSize(src); + CHECK_NOT_EQUAL(numSegments, 0, ()); + std::vector<routing::Segment> segments; + segments.resize(numSegments); + + for (size_t iSeg = 0; iSeg < numSegments; ++iSeg) + Deserialize(mwmId, segments[iSeg], src); + + std::vector<uint8_t> buffer; + auto const bufferSize = ReadSize(src); + buffer.resize(bufferSize); + src.Read(buffer.data(), bufferSize); + + MemReader memReader(buffer.data(), bufferSize); + ReaderSource<MemReader> memSrc(memReader); + + std::vector<DataPoint> dataPoints; + coding::TrafficGPSEncoder::DeserializeDataPoints( + coding::TrafficGPSEncoder::kLatestVersion, memSrc, dataPoints); + CHECK_EQUAL(numSegments, dataPoints.size(), ("mwm:", mwmName, "user:", user)); + + MatchedTrack & track = tracks[iTrack]; + + for (size_t iPoint = 0; iPoint < numSegments; ++iPoint) + track.emplace_back(dataPoints[iPoint], segments[iPoint]); + } + } + } + } + +private: + static constexpr uint8_t kForward = 0; + static constexpr uint8_t kBackward = 1; + + template <class Sink> + static void WriteSize(Sink & sink, size_t size) + { + WriteVarUint(sink, base::checked_cast<uint64_t>(size)); + } + + template <class Source> + static size_t ReadSize(Source & src) + { + return base::checked_cast<size_t>(ReadVarUint<uint64_t>(src)); + } + + template <class Sink> + static void Serialize(routing::Segment const & segment, Sink & sink) + { + WriteToSink(sink, segment.GetFeatureId()); + WriteToSink(sink, segment.GetSegmentIdx()); + auto const direction = segment.IsForward() ? kForward : kBackward; + WriteToSink(sink, direction); + } + + template <class Source> + void Deserialize(routing::NumMwmId numMwmId, routing::Segment & segment, Source & src) + { + auto const featureId = ReadPrimitiveFromSource<uint32_t>(src); + auto const segmentIdx = ReadPrimitiveFromSource<uint32_t>(src); + auto const direction = ReadPrimitiveFromSource<uint8_t>(src); + segment = {numMwmId, featureId, segmentIdx, direction == kForward}; + } + + std::shared_ptr<routing::NumMwmIds> m_numMwmIds; +}; +} // namespace tracking diff --git a/track_analyzing/track.hpp b/track_analyzing/track.hpp new file mode 100644 index 0000000000..cf9acd9b89 --- /dev/null +++ b/track_analyzing/track.hpp @@ -0,0 +1,73 @@ +#pragma once + +#include "routing/num_mwm_id.hpp" +#include "routing/segment.hpp" + +#include "coding/traffic.hpp" + +#include <string> +#include <unordered_map> +#include <vector> + +namespace tracking +{ +using DataPoint = coding::TrafficGPSEncoder::DataPoint; +using Track = std::vector<DataPoint>; +using UserToTrack = std::unordered_map<std::string, Track>; +using MwmToTracks = std::unordered_map<routing::NumMwmId, UserToTrack>; + +class MatchedTrackPoint final +{ +public: + MatchedTrackPoint(DataPoint const & dataPoint, routing::Segment const & segment) + : m_dataPoint(dataPoint), m_segment(segment) + { + } + + DataPoint const & GetDataPoint() const { return m_dataPoint; } + routing::Segment const & GetSegment() const { return m_segment; } + +private: + DataPoint m_dataPoint; + routing::Segment m_segment; +}; + +using MatchedTrack = std::vector<MatchedTrackPoint>; +using UserToMatchedTracks = std::unordered_map<std::string, std::vector<MatchedTrack>>; +using MwmToMatchedTracks = std::unordered_map<routing::NumMwmId, UserToMatchedTracks>; + +class TrackFilter final +{ +public: + TrackFilter(uint64_t minDuration, double minLength, double minSpeed, double maxSpeed, + bool ignoreTraffic) + : m_minDuration(minDuration) + , m_minLength(minLength) + , m_minSpeed(minSpeed) + , m_maxSpeed(maxSpeed) + , m_ignoreTraffic(ignoreTraffic) + { + } + + bool Passes(uint64_t duration, double length, double speed, bool hasTrafficPoints) const + { + if (duration < m_minDuration) + return false; + + if (length < m_minLength) + return false; + + if (speed < m_minSpeed || speed > m_maxSpeed) + return false; + + return !(m_ignoreTraffic && hasTrafficPoints); + } + +private: + uint64_t const m_minDuration; + double const m_minLength; + double const m_minSpeed; + double const m_maxSpeed; + bool m_ignoreTraffic; +}; +} // namespace tracking diff --git a/track_analyzing/track_analyzer/CMakeLists.txt b/track_analyzing/track_analyzer/CMakeLists.txt new file mode 100644 index 0000000000..83c6e0235d --- /dev/null +++ b/track_analyzing/track_analyzer/CMakeLists.txt @@ -0,0 +1,48 @@ +project(track_analyzer) + +include_directories(${OMIM_ROOT}/3party/gflags/src) + +set( + SRC + cmd_cpp_track.cpp + cmd_match.cpp + cmd_table.cpp + cmd_track.cpp + cmd_tracks.cpp + track_analyzer.cpp +) + +omim_add_executable(${PROJECT_NAME} ${SRC}) + +omim_link_libraries( + ${PROJECT_NAME} + track_analyzing + generator + map + routing + traffic + routing_common + storage + indexer + editor + platform + geometry + coding + base + opening_hours + icu + jansson + protobuf + osrm + stats_client + succinct + pugixml + gflags + oauthcpp + ${LIBZ} +) + +find_package(Boost COMPONENTS filesystem REQUIRED) +target_link_libraries(${PROJECT_NAME} ${Boost_LIBRARIES}) + +link_qt5_core(${PROJECT_NAME}) diff --git a/track_analyzing/track_analyzer/cmd_cpp_track.cpp b/track_analyzing/track_analyzer/cmd_cpp_track.cpp new file mode 100644 index 0000000000..a072e2cebf --- /dev/null +++ b/track_analyzing/track_analyzer/cmd_cpp_track.cpp @@ -0,0 +1,31 @@ +#include "track_analyzing/track.hpp" +#include "track_analyzing/utils.hpp" + +#include "map/routing_helpers.hpp" + +#include "storage/storage.hpp" + +using namespace routing; +using namespace std; + +namespace tracking +{ +void CmdCppTrack(string const & trackFile, string const & mwmName, string const & user, + size_t trackIdx) +{ + storage::Storage storage; + auto const numMwmIds = CreateNumMwmIds(storage); + MwmToMatchedTracks mwmToMatchedTracks; + ReadTracks(numMwmIds, trackFile, mwmToMatchedTracks); + + MatchedTrack const & track = + GetMatchedTrack(mwmToMatchedTracks, *numMwmIds, mwmName, user, trackIdx); + + cout.precision(numeric_limits<double>::max_digits10); + for (MatchedTrackPoint const & point : track) + { + cout << " {" << point.GetDataPoint().m_latLon.lat << ", " << point.GetDataPoint().m_latLon.lon + << "}," << endl; + } +} +} // namespace tracking diff --git a/track_analyzing/track_analyzer/cmd_match.cpp b/track_analyzing/track_analyzer/cmd_match.cpp new file mode 100644 index 0000000000..f196f6c422 --- /dev/null +++ b/track_analyzing/track_analyzer/cmd_match.cpp @@ -0,0 +1,112 @@ +#include "track_analyzing/log_parser.hpp" +#include "track_analyzing/serialization.hpp" +#include "track_analyzing/track.hpp" +#include "track_analyzing/track_matcher.hpp" +#include "track_analyzing/utils.hpp" + +#include "map/routing_helpers.hpp" + +#include "routing/num_mwm_id.hpp" + +#include "storage/country_info_getter.hpp" +#include "storage/storage.hpp" + +#include "platform/platform.hpp" + +#include "geometry/tree4d.hpp" + +#include "base/logging.hpp" +#include "base/timer.hpp" + +#include <memory> +#include <string> + +using namespace routing; +using namespace std; +using namespace tracking; + +namespace +{ +void MatchTracks(MwmToTracks const & mwmToTracks, storage::Storage const & storage, + NumMwmIds const & numMwmIds, MwmToMatchedTracks & mwmToMatchedTracks) +{ + my::Timer timer; + + size_t tracksCount = 0; + size_t shortTracksCount = 0; + size_t pointsCount = 0; + size_t shortTrackPointsCount = 0; + size_t nonMatchedPointsCount = 0; + + ForTracksSortedByMwmName( + [&](string const & mwmName, UserToTrack const & userToTrack) { + auto const countryFile = platform::CountryFile(mwmName); + auto const mwmId = numMwmIds.GetId(countryFile); + TrackMatcher matcher(storage, mwmId, countryFile); + + auto & userToMatchedTracks = mwmToMatchedTracks[mwmId]; + + for (auto const & it : userToTrack) + { + auto & matchedTracks = userToMatchedTracks[it.first]; + matcher.MatchTrack(it.second, matchedTracks); + + if (matchedTracks.empty()) + userToMatchedTracks.erase(it.first); + } + + if (userToMatchedTracks.empty()) + mwmToMatchedTracks.erase(mwmId); + + tracksCount += matcher.GetTracksCount(); + shortTracksCount += matcher.GetShortTracksCount(); + pointsCount += matcher.GetPointsCount(); + shortTrackPointsCount += matcher.GetShortTrackPointsCount(); + nonMatchedPointsCount += matcher.GetNonMatchedPointsCount(); + + LOG(LINFO, (numMwmIds.GetFile(mwmId).GetName(), ", users:", userToTrack.size(), ", tracks:", + matcher.GetTracksCount(), ", short tracks:", matcher.GetShortTracksCount(), + ", points:", matcher.GetPointsCount(), ", short track points", + matcher.GetShortTrackPointsCount(), ", non matched points:", + matcher.GetNonMatchedPointsCount())); + }, + mwmToTracks, numMwmIds); + + LOG(LINFO, + ("Matching finished, elapsed:", timer.ElapsedSeconds(), "seconds, tracks:", tracksCount, + ", short tracks:", shortTracksCount, ", points:", pointsCount, ", short track points", + shortTrackPointsCount, ", non matched points:", nonMatchedPointsCount)); +} + +} // namespace + +namespace tracking +{ +void CmdMatch(string const & logFile, string const & trackFile) +{ + LOG(LINFO, ("Matching", logFile)); + + storage::Storage storage; + storage.RegisterAllLocalMaps(); + shared_ptr<NumMwmIds> numMwmIds = CreateNumMwmIds(storage); + + Platform const & platform = GetPlatform(); + string const dataDir = platform.WritableDir(); + + unique_ptr<storage::CountryInfoGetter> countryInfoGetter = + storage::CountryInfoReader::CreateCountryInfoReader(platform); + unique_ptr<m4::Tree<NumMwmId>> mwmTree = MakeNumMwmTree(*numMwmIds, *countryInfoGetter); + + tracking::LogParser parser(numMwmIds, move(mwmTree), dataDir); + MwmToTracks mwmToTracks; + parser.Parse(logFile, mwmToTracks); + + MwmToMatchedTracks mwmToMatchedTracks; + MatchTracks(mwmToTracks, storage, *numMwmIds, mwmToMatchedTracks); + + FileWriter writer(trackFile, FileWriter::OP_WRITE_TRUNCATE); + MwmToMatchedTracksSerializer serializer(numMwmIds); + serializer.Serialize(mwmToMatchedTracks, writer); + LOG(LINFO, ("Matched track was saved to", trackFile)); +} +} // namespace tracking diff --git a/track_analyzing/track_analyzer/cmd_table.cpp b/track_analyzing/track_analyzer/cmd_table.cpp new file mode 100644 index 0000000000..fa8acddb1f --- /dev/null +++ b/track_analyzing/track_analyzer/cmd_table.cpp @@ -0,0 +1,290 @@ +#include "track_analyzing/track.hpp" +#include "track_analyzing/utils.hpp" + +#include "map/routing_helpers.hpp" + +#include "routing/geometry.hpp" + +#include "routing_common/car_model.hpp" +#include "routing_common/vehicle_model.hpp" + +#include "traffic/speed_groups.hpp" + +#include "indexer/classificator.hpp" + +#include "storage/storage.hpp" + +#include "coding/file_name_utils.hpp" + +#include <iostream> + +using namespace routing; +using namespace std; +using namespace tracking; + +namespace +{ +string RoadTypeToString(uint32_t type) +{ + if (type == 0) + return "unknown-type"; + + return classif().GetReadableObjectName(type); +} + +bool FeatureHasType(FeatureType const & feature, uint32_t type) +{ + bool result = false; + + feature.ForEachType([&](uint32_t featureType) { + if (featureType == type) + { + result = true; + return; + } + }); + + return result; +} + +class CarModelTypes final +{ +public: + CarModelTypes() + { + for (auto const & additionalTag : CarModel::GetAdditionalTags()) + m_tags.push_back(classif().GetTypeByPath(additionalTag.m_hwtag)); + + for (auto const & speedForType : CarModel::GetLimits()) + { + vector<string> path; + for (char const * type : speedForType.m_types) + path.push_back(string(type)); + + m_tags.push_back(classif().GetTypeByPath(path)); + } + } + + uint32_t GetType(FeatureType const & feature) const + { + for (uint32_t type : m_tags) + { + if (FeatureHasType(feature, type)) + return type; + } + + return 0; + } + +private: + vector<uint32_t> m_tags; +}; + +class MoveType final +{ +public: + MoveType() = default; + + MoveType(uint32_t roadType, traffic::SpeedGroup speedGroup) + : m_roadType(roadType), m_speedGroup(speedGroup) + { + } + + bool operator==(MoveType const & rhs) const + { + return m_roadType == rhs.m_roadType && m_speedGroup == rhs.m_speedGroup; + } + + bool operator<(MoveType const & rhs) const + { + if (m_roadType != rhs.m_roadType) + return m_roadType < rhs.m_roadType; + + return m_speedGroup < rhs.m_speedGroup; + } + + string ToString() const + { + ostringstream out; + out << RoadTypeToString(m_roadType) << "*" << traffic::DebugPrint(m_speedGroup); + return out.str(); + } + +private: + uint32_t m_roadType = 0; + traffic::SpeedGroup m_speedGroup = traffic::SpeedGroup::Unknown; +}; + +class MoveInfo final +{ +public: + void Add(double distance, uint64_t time) + { + m_totalDistance += distance; + m_totalTime += time; + } + + void Add(MoveInfo const & rhs) { Add(rhs.m_totalDistance, rhs.m_totalTime); } + + double GetDistance() const { return m_totalDistance; } + uint64_t GetTime() const { return m_totalTime; } + +private: + double m_totalDistance = 0.0; + uint64_t m_totalTime = 0; +}; + +class MoveTypeAggregator final +{ +public: + void Add(MoveType const moveType, MatchedTrack const & track, size_t begin, size_t end, + Geometry & geometry) + { + CHECK_LESS_OR_EQUAL(end, track.size(), ()); + + if (begin + 1 >= end) + return; + + uint64_t const time = + track[end - 1].GetDataPoint().m_timestamp - track[begin].GetDataPoint().m_timestamp; + double const length = CalcSubtrackLength(track, begin, end, geometry); + m_moveInfos[moveType].Add(length, time); + } + + void Add(MoveTypeAggregator const & rhs) + { + for (auto it : rhs.m_moveInfos) + m_moveInfos[it.first].Add(it.second); + } + + string GetSummary() const + { + ostringstream out; + out << std::fixed << std::setprecision(1); + + bool firstIteration = true; + for (auto it : m_moveInfos) + { + MoveInfo const & speedInfo = it.second; + if (firstIteration) + { + firstIteration = false; + } + else + { + out << " "; + } + + out << it.first.ToString() << ": " << speedInfo.GetDistance() << " / " << speedInfo.GetTime(); + } + + return out.str(); + } + +private: + map<MoveType, MoveInfo> m_moveInfos; +}; + +class MatchedTrackPointToMoveType final +{ +public: + MatchedTrackPointToMoveType(string const & mwmFile) + : m_featuresVector(FilesContainerR(make_unique<FileReader>(mwmFile))) + { + } + + MoveType GetMoveType(MatchedTrackPoint const & point) + { + return MoveType(GetRoadType(point.GetSegment().GetFeatureId()), + static_cast<traffic::SpeedGroup>(point.GetDataPoint().m_traffic)); + } + +private: + uint32_t GetRoadType(uint32_t featureId) + { + if (featureId == m_prevFeatureId) + return m_prevRoadType; + + FeatureType feature; + m_featuresVector.GetVector().GetByIndex(featureId, feature); + feature.ParseTypes(); + + m_prevFeatureId = featureId; + m_prevRoadType = m_carModelTypes.GetType(feature); + return m_prevRoadType; + } + + CarModelTypes const m_carModelTypes; + FeaturesVectorTest m_featuresVector; + uint32_t m_prevFeatureId = numeric_limits<uint32_t>::max(); + uint32_t m_prevRoadType = numeric_limits<uint32_t>::max(); +}; +} // namespace + +namespace tracking +{ +void CmdTagsTable(string const & filepath, string const & trackExtension, string const & mwmFilter, + string const & userFilter) +{ + cout << "mwm user track_idx start length time speed ... type: meters / seconds" << endl; + + storage::Storage storage; + auto numMwmIds = CreateNumMwmIds(storage); + + auto processMwm = [&](string const & mwmName, UserToMatchedTracks const & userToMatchedTracks) { + if (IsFiltered(mwmFilter, mwmName)) + return; + + shared_ptr<IVehicleModel> vehicleModel = CarModelFactory().GetVehicleModelForCountry(mwmName); + string const mwmFile = + my::JoinPath(GetPlatform().WritableDir(), to_string(storage.GetCurrentDataVersion()), + mwmName + DATA_FILE_EXTENSION); + MatchedTrackPointToMoveType pointToMoveType(mwmFile); + Geometry geometry(GeometryLoader::CreateFromFile(mwmFile, vehicleModel)); + + for (auto uIt : userToMatchedTracks) + { + string const & user = uIt.first; + if (IsFiltered(userFilter, user)) + continue; + + for (size_t trackIdx = 0; trackIdx < uIt.second.size(); ++trackIdx) + { + MatchedTrack const & track = uIt.second[trackIdx]; + uint64_t const start = track.front().GetDataPoint().m_timestamp; + uint64_t const timeElapsed = track.back().GetDataPoint().m_timestamp - start; + double const length = CalcTrackLength(track, geometry); + double const speed = CalcSpeedKMpH(length, timeElapsed); + + MoveTypeAggregator aggregator; + + MoveType currentType(numeric_limits<uint32_t>::max(), traffic::SpeedGroup::Count); + size_t subTrackBegin = 0; + + for (size_t i = 0; i < track.size(); ++i) + { + MoveType const type = pointToMoveType.GetMoveType(track[i]); + if (type == currentType) + continue; + + aggregator.Add(currentType, track, subTrackBegin, i, geometry); + currentType = type; + subTrackBegin = i; + } + aggregator.Add(currentType, track, subTrackBegin, track.size(), geometry); + + cout << mwmName << " " << user << " " << trackIdx << " " + << my::SecondsSinceEpochToString(start) << " " << length << " " << timeElapsed << " " + << speed << " " << aggregator.GetSummary() << endl; + } + } + }; + + auto processTrack = [&](string const & filename, MwmToMatchedTracks const & mwmToMatchedTracks) { + LOG(LINFO, ("Processing", filename)); + ForTracksSortedByMwmName(processMwm, mwmToMatchedTracks, *numMwmIds); + }; + + ForEachTrackFile(processTrack, filepath, trackExtension, numMwmIds); +} +} // namespace tracking diff --git a/track_analyzing/track_analyzer/cmd_track.cpp b/track_analyzing/track_analyzer/cmd_track.cpp new file mode 100644 index 0000000000..48df1303ae --- /dev/null +++ b/track_analyzing/track_analyzer/cmd_track.cpp @@ -0,0 +1,77 @@ +#include "track_analyzing/track.hpp" +#include "track_analyzing/utils.hpp" + +#include "map/routing_helpers.hpp" + +#include "routing/geometry.hpp" + +#include "routing_common/car_model.hpp" +#include "routing_common/vehicle_model.hpp" + +#include "indexer/feature.hpp" +#include "indexer/features_vector.hpp" + +#include "storage/storage.hpp" + +#include "coding/file_name_utils.hpp" + +#include "geometry/mercator.hpp" + +using namespace routing; +using namespace std; + +namespace tracking +{ +void CmdTrack(string const & trackFile, string const & mwmName, string const & user, + size_t trackIdx) +{ + storage::Storage storage; + auto const numMwmIds = CreateNumMwmIds(storage); + MwmToMatchedTracks mwmToMatchedTracks; + ReadTracks(numMwmIds, trackFile, mwmToMatchedTracks); + + MatchedTrack const & track = + GetMatchedTrack(mwmToMatchedTracks, *numMwmIds, mwmName, user, trackIdx); + + string const mwmFile = + my::JoinPath(GetPlatform().WritableDir(), to_string(storage.GetCurrentDataVersion()), + mwmName + DATA_FILE_EXTENSION); + shared_ptr<IVehicleModel> vehicleModel = CarModelFactory().GetVehicleModelForCountry(mwmName); + FeaturesVectorTest featuresVector(FilesContainerR(make_unique<FileReader>(mwmFile))); + Geometry geometry(GeometryLoader::CreateFromFile(mwmFile, vehicleModel)); + + uint64_t const duration = + track.back().GetDataPoint().m_timestamp - track.front().GetDataPoint().m_timestamp; + double const length = CalcTrackLength(track, geometry); + double const averageSpeed = CalcSpeedKMpH(length, duration); + LOG(LINFO, ("Mwm:", mwmName, ", user:", user, ", points:", track.size(), "duration:", duration, + "length:", length, ", speed:", averageSpeed, "km/h")); + + for (size_t i = 0; i < track.size(); ++i) + { + MatchedTrackPoint const & point = track[i]; + FeatureType feature; + featuresVector.GetVector().GetByIndex(point.GetSegment().GetFeatureId(), feature); + + double speed = 0.0; + uint64_t elapsed = 0; + double distance = 0.0; + if (i > 0) + { + MatchedTrackPoint const & prevPoint = track[i - 1]; + elapsed = point.GetDataPoint().m_timestamp - prevPoint.GetDataPoint().m_timestamp; + distance = MercatorBounds::DistanceOnEarth( + MercatorBounds::FromLatLon(prevPoint.GetDataPoint().m_latLon), + MercatorBounds::FromLatLon(point.GetDataPoint().m_latLon)); + } + + if (elapsed != 0) + speed = CalcSpeedKMpH(distance, elapsed); + + LOG(LINFO, (my::SecondsSinceEpochToString(point.GetDataPoint().m_timestamp), + point.GetDataPoint().m_latLon, point.GetSegment(), ", traffic:", + point.GetDataPoint().m_traffic, ", distance:", distance, ", elapsed:", elapsed, + ", speed:", speed)); + } +} +} // namespace tracking diff --git a/track_analyzing/track_analyzer/cmd_tracks.cpp b/track_analyzing/track_analyzer/cmd_tracks.cpp new file mode 100644 index 0000000000..57e3da6f32 --- /dev/null +++ b/track_analyzing/track_analyzer/cmd_tracks.cpp @@ -0,0 +1,233 @@ +#include "track_analyzing/track.hpp" +#include "track_analyzing/utils.hpp" + +#include "map/routing_helpers.hpp" + +#include "routing_common/car_model.hpp" +#include "routing_common/vehicle_model.hpp" + +#include "routing/edge_estimator.hpp" +#include "routing/geometry.hpp" + +#include "storage/storage.hpp" + +#include "platform/platform.hpp" + +#include "coding/file_name_utils.hpp" + +#include "base/logging.hpp" +#include "base/timer.hpp" + +#include <algorithm> +#include <iostream> + +using namespace routing; +using namespace std; +using namespace tracking; + +namespace +{ +class TrackStats final +{ +public: + void AddUsers(size_t numUsers) { m_numUsers += numUsers; } + void AddTracks(size_t numTracks) { m_numTracks += numTracks; } + void AddPoints(size_t numPoints) { m_numPoints += numPoints; } + + void Add(TrackStats const & rhs) + { + m_numUsers += rhs.m_numUsers; + m_numTracks += rhs.m_numTracks; + m_numPoints += rhs.m_numPoints; + } + + string GetSummary() const + { + ostringstream out; + out << "users: " << m_numUsers << ", tracks: " << m_numTracks << ", points: " << m_numPoints; + return out.str(); + } + + bool IsEmpty() const { return m_numPoints == 0; } + +private: + size_t m_numUsers = 0; + size_t m_numTracks = 0; + size_t m_numPoints = 0; +}; + +class ErrorStat final +{ +public: + void Add(double value) + { + m_count += 1.0; + m_squares += value * value; + m_min = min(m_min, value); + m_max = max(m_max, value); + } + + double GetDeviation() const + { + CHECK_GREATER(m_count, 0.0, ()); + return std::sqrt(m_squares / m_count); + } + + double GetMin() const { return m_min; } + double GetMax() const { return m_max; } + +private: + double m_count = 0.0; + double m_squares = 0.0; + double m_min = numeric_limits<double>::max(); + double m_max = numeric_limits<double>::min(); +}; + +bool TrackHasTrafficPoints(MatchedTrack const & track) +{ + for (MatchedTrackPoint const & point : track) + { + size_t const index = static_cast<size_t>(point.GetDataPoint().m_traffic); + CHECK_LESS(index, static_cast<size_t>(traffic::SpeedGroup::Count), ()); + if (traffic::kSpeedGroupThresholdPercentage[index] != 100) + return true; + } + + return false; +} + +double EstimateDuration(MatchedTrack const & track, shared_ptr<EdgeEstimator> estimator, + Geometry & geometry) +{ + double result = 0.0; + Segment segment; + + for (MatchedTrackPoint const & point : track) + { + if (point.GetSegment() == segment) + continue; + + segment = point.GetSegment(); + result += estimator->CalcSegmentWeight(segment, geometry.GetRoad(segment.GetFeatureId())); + } + + return result; +} +} // namespace + +namespace tracking +{ +void CmdTracks(string const & filepath, string const & trackExtension, string const & mwmFilter, + string const & userFilter, TrackFilter const & filter, bool noTrackLogs, + bool noMwmLogs, bool noWorldLogs) +{ + storage::Storage storage; + auto numMwmIds = CreateNumMwmIds(storage); + + if (!mwmFilter.empty() && !numMwmIds->ContainsFile(platform::CountryFile(mwmFilter))) + MYTHROW(MessageException, ("Mwm", mwmFilter, "does not exist")); + + map<string, TrackStats> mwmToStats; + ErrorStat absoluteError; + ErrorStat relativeError; + + auto processMwm = [&](string const & mwmName, UserToMatchedTracks const & userToMatchedTracks) { + if (IsFiltered(mwmFilter, mwmName)) + return; + + TrackStats & mwmStats = mwmToStats[mwmName]; + + shared_ptr<IVehicleModel> vehicleModel = CarModelFactory().GetVehicleModelForCountry(mwmName); + + Geometry geometry(GeometryLoader::CreateFromFile( + my::JoinPath(GetPlatform().WritableDir(), to_string(storage.GetCurrentDataVersion()), + mwmName + DATA_FILE_EXTENSION), + vehicleModel)); + + shared_ptr<EdgeEstimator> estimator = + EdgeEstimator::CreateForCar(nullptr, vehicleModel->GetMaxSpeed()); + + for (auto it : userToMatchedTracks) + { + string const & user = it.first; + if (IsFiltered(userFilter, user)) + continue; + + vector<MatchedTrack> const & tracks = it.second; + if (!noTrackLogs) + cout << mwmName << ", user: " << user << endl; + + bool thereAreUnfilteredTracks = false; + for (MatchedTrack const & track : tracks) + { + DataPoint const & start = track.front().GetDataPoint(); + DataPoint const & finish = track.back().GetDataPoint(); + + double const length = CalcTrackLength(track, geometry); + uint64_t const duration = finish.m_timestamp - start.m_timestamp; + double const speed = CalcSpeedKMpH(length, duration); + bool const hasTrafficPoints = TrackHasTrafficPoints(track); + + if (!filter.Passes(duration, length, speed, hasTrafficPoints)) + continue; + + double const estimatedDuration = EstimateDuration(track, estimator, geometry); + double const timeError = estimatedDuration - static_cast<double>(duration); + + if (!noTrackLogs) + { + cout << fixed << setprecision(1) << " points: " << track.size() << ", length: " << length + << ", duration: " << duration << ", estimated duration: " << estimatedDuration + << ", speed: " << speed << ", traffic: " << hasTrafficPoints + << ", departure: " << my::SecondsSinceEpochToString(start.m_timestamp) + << ", arrival: " << my::SecondsSinceEpochToString(finish.m_timestamp) + << setprecision(numeric_limits<double>::max_digits10) + << ", start: " << start.m_latLon.lat << ", " << start.m_latLon.lon + << ", finish: " << finish.m_latLon.lat << ", " << finish.m_latLon.lon << endl; + } + + mwmStats.AddTracks(1); + mwmStats.AddPoints(track.size()); + absoluteError.Add(timeError); + relativeError.Add(timeError / static_cast<double>(duration)); + thereAreUnfilteredTracks = true; + } + + if (thereAreUnfilteredTracks) + mwmStats.AddUsers(1); + } + }; + + auto processFile = [&](string const & filename, MwmToMatchedTracks const & mwmToMatchedTracks) { + LOG(LINFO, ("Processing", filename)); + ForTracksSortedByMwmName(processMwm, mwmToMatchedTracks, *numMwmIds); + }; + + ForEachTrackFile(processFile, filepath, trackExtension, numMwmIds); + + if (!noMwmLogs) + { + cout << endl; + for (auto it : mwmToStats) + { + if (!it.second.IsEmpty()) + cout << it.first << ": " << it.second.GetSummary() << endl; + } + } + + if (!noWorldLogs) + { + TrackStats worldStats; + for (auto it : mwmToStats) + worldStats.Add(it.second); + + cout << endl << "World: " << worldStats.GetSummary() << endl; + cout << fixed << setprecision(1) + << "Absolute error: deviation: " << absoluteError.GetDeviation() + << ", min: " << absoluteError.GetMin() << ", max: " << absoluteError.GetMax() << endl; + cout << fixed << setprecision(3) + << "Relative error: deviation: " << relativeError.GetDeviation() + << ", min: " << relativeError.GetMin() << ", max: " << relativeError.GetMax() << endl; + } +} +} // namespace tracking diff --git a/track_analyzing/track_analyzer/track_analyzer.cpp b/track_analyzing/track_analyzer/track_analyzer.cpp new file mode 100644 index 0000000000..c73c0d8246 --- /dev/null +++ b/track_analyzing/track_analyzer/track_analyzer.cpp @@ -0,0 +1,118 @@ +#include "track_analyzing/exceptions.hpp" +#include "track_analyzing/track.hpp" + +#include "indexer/classificator.hpp" +#include "indexer/classificator_loader.hpp" + +#include "3party/gflags/src/gflags/gflags.h" + +using namespace std; +using namespace tracking; + +namespace +{ +#define DEFINE_string_ext(name, value, description) \ + DEFINE_string(name, value, description); \ + \ + string const & Demand_##name() \ + { \ + if (FLAGS_##name.empty()) \ + MYTHROW(MessageException, (string("Specify the argument --") + #name)); \ + \ + return FLAGS_##name; \ + } + +DEFINE_string_ext(cmd, "", "command: match, info, cpptrack"); +DEFINE_string_ext(in, "", "input log file name"); +DEFINE_string(out, "", "output track file name"); +DEFINE_string_ext(mwm, "", "short mwm name"); +DEFINE_string_ext(user, "", "user id"); +DEFINE_int32(track, -1, "track index"); + +DEFINE_string(track_extension, ".track", "track files extension"); +DEFINE_bool(no_world_logs, false, "don't print world summary logs"); +DEFINE_bool(no_mwm_logs, false, "don't print logs per mwm"); +DEFINE_bool(no_track_logs, false, "don't print logs per track"); + +DEFINE_uint64(min_duration, 5 * 60, "minimal track duration in seconds"); +DEFINE_double(min_length, 1000.0, "minimal track length in meters"); +DEFINE_double(min_speed, 15.0, "minimal track average speed in km/hour"); +DEFINE_double(max_speed, 110.0, "maximum track average speed in km/hour"); +DEFINE_bool(ignore_traffic, true, "ignore tracks with traffic data"); + +size_t Demand_track() +{ + if (FLAGS_track < 0) + MYTHROW(MessageException, ("Specify the --track key")); + + return static_cast<size_t>(FLAGS_track); +} +} // namespace + +namespace tracking +{ +void CmdCppTrack(string const & trackFile, string const & mwmName, string const & user, + size_t trackIdx); +void CmdMatch(string const & logFile, string const & trackFile); +void CmdTagsTable(string const & filepath, string const & trackExtension, string const & mwmFilter, + string const & userFilter); +void CmdTrack(string const & trackFile, string const & mwmName, string const & user, + size_t trackIdx); +void CmdTracks(string const & filepath, string const & trackExtension, string const & mwmFilter, + string const & userFilter, TrackFilter const & filter, bool noTrackLogs, + bool noMwmLogs, bool noWorldLogs); +} // namespace tracking + +int main(int argc, char ** argv) +{ + google::ParseCommandLineFlags(&argc, &argv, true); + string const & cmd = Demand_cmd(); + + classificator::Load(); + classif().SortClassificator(); + + try + { + if (cmd == "match") + { + string const & logFile = Demand_in(); + CmdMatch(logFile, FLAGS_out.empty() ? logFile + ".track" : FLAGS_out); + } + else if (cmd == "tracks") + { + TrackFilter const filter(FLAGS_min_duration, FLAGS_min_length, FLAGS_min_speed, + FLAGS_max_speed, FLAGS_ignore_traffic); + CmdTracks(Demand_in(), FLAGS_track_extension, FLAGS_mwm, FLAGS_user, filter, + FLAGS_no_track_logs, FLAGS_no_mwm_logs, FLAGS_no_world_logs); + } + else if (cmd == "track") + { + CmdTrack(Demand_in(), Demand_mwm(), Demand_user(), Demand_track()); + } + else if (cmd == "cpptrack") + { + CmdCppTrack(Demand_in(), Demand_mwm(), Demand_user(), Demand_track()); + } + else if (cmd == "table") + { + CmdTagsTable(Demand_in(), FLAGS_track_extension, FLAGS_mwm, FLAGS_user); + } + else + { + LOG(LWARNING, ("Unknown command", FLAGS_cmd)); + return 1; + } + } + catch (MessageException const & e) + { + LOG(LWARNING, (e.Msg())); + return 1; + } + catch (RootException const & e) + { + LOG(LERROR, (e.what())); + return 1; + } + + return 0; +} diff --git a/track_analyzing/track_matcher.cpp b/track_analyzing/track_matcher.cpp new file mode 100644 index 0000000000..068a2485e4 --- /dev/null +++ b/track_analyzing/track_matcher.cpp @@ -0,0 +1,240 @@ +#include "track_analyzing/track_matcher.hpp" + +#include <routing/index_graph_loader.hpp> + +#include <routing_common/car_model.hpp> + +#include <indexer/scales.hpp> + +#include <geometry/distance.hpp> + +using namespace tracking; +using namespace std; + +namespace +{ +double constexpr kMatchingRange = 20.0; +uint64_t constexpr kShortTrackDuration = 60; + +double DistanceToSegment(m2::PointD const & segmentBegin, m2::PointD const & segmentEnd, + m2::PointD const & point) +{ + m2::ProjectionToSection<m2::PointD> projection; + projection.SetBounds(segmentBegin, segmentEnd); + m2::PointD const projectionPoint = projection(point); + return MercatorBounds::DistanceOnEarth(point, projectionPoint); +} + +double DistanceToSegment(routing::Segment const & segment, m2::PointD const & point, + routing::IndexGraph & indexGraph) +{ + return DistanceToSegment(indexGraph.GetGeometry().GetPoint(segment.GetRoadPoint(false)), + indexGraph.GetGeometry().GetPoint(segment.GetRoadPoint(true)), point); +} + +bool EdgesContain(vector<routing::SegmentEdge> const & edges, routing::Segment const & segment) +{ + for (auto const & edge : edges) + { + if (edge.GetTarget() == segment) + return true; + } + + return false; +} +} // namespace + +namespace tracking +{ +// TrackMatcher ------------------------------------------------------------------------------------ +TrackMatcher::TrackMatcher(storage::Storage const & storage, routing::NumMwmId mwmId, + platform::CountryFile const & countryFile) + : m_mwmId(mwmId) + , m_vehicleModel(routing::CarModelFactory().GetVehicleModelForCountry(countryFile.GetName())) +{ + auto localCountryFile = storage.GetLatestLocalFile(countryFile); + CHECK(localCountryFile, ("Can't find latest country file for", countryFile.GetName())); + auto registerResult = m_index.Register(*localCountryFile); + CHECK_EQUAL(registerResult.second, MwmSet::RegResult::Success, + ("Can't register mwm", countryFile.GetName())); + + m_graph = make_unique<routing::IndexGraph>( + routing::GeometryLoader::Create(m_index, registerResult.first, m_vehicleModel), + routing::EdgeEstimator::CreateForCar(nullptr /* trafficStash */, + m_vehicleModel->GetMaxSpeed())); + + MwmSet::MwmHandle const handle = m_index.GetMwmHandleByCountryFile(countryFile); + routing::DeserializeIndexGraph(*handle.GetValue<MwmValue>(), *m_graph); +} + +void TrackMatcher::MatchTrack(vector<DataPoint> const & track, vector<MatchedTrack> & matchedTracks) +{ + m_pointsCount += track.size(); + + vector<Step> steps; + for (auto const & routePoint : track) + steps.emplace_back(routePoint); + + for (size_t trackBegin = 0; trackBegin < steps.size();) + { + for (; trackBegin < steps.size(); ++trackBegin) + { + steps[trackBegin].FillCandidatesWithNearbySegments(m_index, *m_vehicleModel, m_mwmId); + if (steps[trackBegin].HasCandidates()) + break; + + ++m_nonMatchedPointsCount; + } + + if (trackBegin >= steps.size()) + break; + + size_t trackEnd = trackBegin; + for (; trackEnd < steps.size() - 1; ++trackEnd) + { + Step & nextStep = steps[trackEnd + 1]; + nextStep.FillCandidates(steps[trackEnd], *m_graph); + if (!nextStep.HasCandidates()) + break; + } + + steps[trackEnd].ChooseNearestSegment(); + + for (size_t i = trackEnd; i > trackBegin; --i) + steps[i - 1].ChooseSegment(steps[i], *m_graph); + + ++m_tracksCount; + + uint64_t const trackTime = + steps[trackEnd].GetDataPoint().m_timestamp - steps[trackBegin].GetDataPoint().m_timestamp; + if (trackTime < kShortTrackDuration) + { + ++m_shortTracksCount; + m_shortTrackPointsCount += trackEnd + 1 - trackBegin; + } + else + { + matchedTracks.push_back({}); + MatchedTrack & matchedTrack = matchedTracks.back(); + for (size_t i = trackBegin; i <= trackEnd; ++i) + { + Step const & step = steps[i]; + matchedTrack.emplace_back(step.GetDataPoint(), step.GetSegment()); + } + } + + trackBegin = trackEnd + 1; + } +} + +// TrackMatcher::Step ------------------------------------------------------------------------------ +TrackMatcher::Step::Step(DataPoint const & dataPoint) + : m_dataPoint(dataPoint), m_point(MercatorBounds::FromLatLon(dataPoint.m_latLon)) +{ +} + +void TrackMatcher::Step::FillCandidatesWithNearbySegments( + Index const & index, routing::IVehicleModel const & vehicleModel, routing::NumMwmId mwmId) +{ + index.ForEachInRect( + [&](FeatureType const & ft) { + if (!ft.GetID().IsValid()) + return; + + if (ft.GetID().m_mwmId.GetInfo()->GetType() != MwmInfo::COUNTRY) + return; + + if (!vehicleModel.IsRoad(ft)) + return; + + ft.ParseGeometry(FeatureType::BEST_GEOMETRY); + + for (size_t segIdx = 0; segIdx + 1 < ft.GetPointsCount(); ++segIdx) + { + double const distance = + DistanceToSegment(ft.GetPoint(segIdx), ft.GetPoint(segIdx + 1), m_point); + if (distance < kMatchingRange) + { + m_candidates.emplace_back( + routing::Segment(mwmId, ft.GetID().m_index, static_cast<uint32_t>(segIdx), true), + distance); + + if (!vehicleModel.IsOneWay(ft)) + m_candidates.emplace_back( + routing::Segment(mwmId, ft.GetID().m_index, static_cast<uint32_t>(segIdx), false), + distance); + } + } + }, + MercatorBounds::RectByCenterXYAndSizeInMeters(m_point, kMatchingRange), + scales::GetUpperScale()); +} + +void TrackMatcher::Step::FillCandidates(Step const & previousStep, routing::IndexGraph & graph) +{ + vector<routing::SegmentEdge> edges; + + for (Candidate const & candidate : previousStep.m_candidates) + { + routing::Segment const & segment = candidate.GetSegment(); + m_candidates.emplace_back(segment, DistanceToSegment(segment, m_point, graph)); + + edges.clear(); + graph.GetEdgeList(segment, true, edges); + + for (routing::SegmentEdge const & edge : edges) + { + routing::Segment const & target = edge.GetTarget(); + if (!segment.IsInverse(target)) + m_candidates.emplace_back(target, DistanceToSegment(target, m_point, graph)); + } + } + + my::SortUnique(m_candidates); + + m_candidates.erase(remove_if(m_candidates.begin(), m_candidates.end(), + [&](Candidate const & candidate) { + return candidate.GetDistance() > kMatchingRange; + }), + m_candidates.end()); +} + +void TrackMatcher::Step::ChooseSegment(Step const & nextStep, routing::IndexGraph & indexGraph) +{ + CHECK(!m_candidates.empty(), ()); + + double minDistance = numeric_limits<double>::max(); + + vector<routing::SegmentEdge> edges; + indexGraph.GetEdgeList(nextStep.m_segment, false, edges); + edges.emplace_back(nextStep.m_segment, 0.0 /* weight */); + + for (Candidate const & candidate : m_candidates) + { + if (candidate.GetDistance() < minDistance && EdgesContain(edges, candidate.GetSegment())) + { + minDistance = candidate.GetDistance(); + m_segment = candidate.GetSegment(); + } + } + + CHECK_LESS(minDistance, numeric_limits<double>::max(), + ("Can't find previous segment for", nextStep.m_segment)); +} + +void TrackMatcher::Step::ChooseNearestSegment() +{ + CHECK(!m_candidates.empty(), ()); + + double minDistance = numeric_limits<double>::max(); + + for (Candidate const & candidate : m_candidates) + { + if (candidate.GetDistance() < minDistance) + { + minDistance = candidate.GetDistance(); + m_segment = candidate.GetSegment(); + } + } +} +} // namespace tracking diff --git a/track_analyzing/track_matcher.hpp b/track_analyzing/track_matcher.hpp new file mode 100644 index 0000000000..376f8abd1b --- /dev/null +++ b/track_analyzing/track_matcher.hpp @@ -0,0 +1,87 @@ +#pragma once + +#include "track_analyzing/track.hpp" + +#include "routing/index_graph.hpp" +#include "routing/num_mwm_id.hpp" +#include "routing/segment.hpp" + +#include "indexer/index.hpp" + +#include <storage/storage.hpp> + +#include "geometry/point2d.hpp" + +#include <memory> +#include <string> +#include <vector> + +namespace tracking +{ +class TrackMatcher final +{ +public: + TrackMatcher(storage::Storage const & storage, routing::NumMwmId mwmId, + platform::CountryFile const & countryFile); + + void MatchTrack(std::vector<DataPoint> const & track, std::vector<MatchedTrack> & matchedTracks); + + size_t GetTracksCount() const { return m_tracksCount; } + size_t GetShortTracksCount() const { return m_shortTracksCount; } + size_t GetPointsCount() const { return m_pointsCount; } + size_t GetShortTrackPointsCount() const { return m_shortTrackPointsCount; } + size_t GetNonMatchedPointsCount() const { return m_nonMatchedPointsCount; } + +private: + class Candidate final + { + public: + Candidate(routing::Segment segment, double distance) : m_segment(segment), m_distance(distance) + { + } + + routing::Segment const & GetSegment() const { return m_segment; } + double GetDistance() const { return m_distance; } + bool operator==(Candidate const & candidate) const { return m_segment == candidate.m_segment; } + bool operator<(Candidate const & candidate) const { return m_segment < candidate.m_segment; } + + private: + routing::Segment m_segment; + double m_distance; + }; + + class Step final + { + public: + explicit Step(DataPoint const & dataPoint); + + DataPoint const & GetDataPoint() const { return m_dataPoint; } + routing::Segment const & GetSegment() const { return m_segment; } + + bool HasCandidates() const { return !m_candidates.empty(); } + + void FillCandidatesWithNearbySegments(Index const & index, + routing::IVehicleModel const & vehicleModel, + routing::NumMwmId mwmId); + void FillCandidates(Step const & previousStep, routing::IndexGraph & graph); + void ChooseSegment(Step const & nextStep, routing::IndexGraph & indexGraph); + void ChooseNearestSegment(); + + private: + DataPoint m_dataPoint; + m2::PointD m_point; + routing::Segment m_segment; + std::vector<Candidate> m_candidates; + }; + + routing::NumMwmId const m_mwmId; + Index m_index; + std::shared_ptr<routing::IVehicleModel> m_vehicleModel; + std::unique_ptr<routing::IndexGraph> m_graph; + size_t m_tracksCount = 0; + size_t m_shortTracksCount = 0; + size_t m_pointsCount = 0; + size_t m_shortTrackPointsCount = 0; + size_t m_nonMatchedPointsCount = 0; +}; +} // namespace tracking diff --git a/track_analyzing/utils.cpp b/track_analyzing/utils.cpp new file mode 100644 index 0000000000..c19d397c8e --- /dev/null +++ b/track_analyzing/utils.cpp @@ -0,0 +1,92 @@ +#include "track_analyzing/utils.hpp" + +#include "track_analyzing/serialization.hpp" + +#include "routing/segment.hpp" + +#include <cstdint> + +using namespace routing; +using namespace std; + +namespace tracking +{ +double CalcSubtrackLength(MatchedTrack const & track, size_t begin, size_t end, Geometry & geometry) +{ + CHECK_LESS_OR_EQUAL(end, track.size(), ()); + + double length = 0.0; + + Segment prevSegment; + for (size_t i = begin; i < end; ++i) + { + MatchedTrackPoint const & point = track[i]; + Segment const & segment = point.GetSegment(); + if (segment != prevSegment) + { + length += MercatorBounds::DistanceOnEarth(geometry.GetPoint(segment.GetRoadPoint(false)), + geometry.GetPoint(segment.GetRoadPoint(true))); + prevSegment = segment; + } + } + + return length; +} + +double CalcTrackLength(MatchedTrack const & track, Geometry & geometry) +{ + return CalcSubtrackLength(track, 0, track.size(), geometry); +} + +double CalcSpeedKMpH(double meters, uint64_t secondsElapsed) +{ + CHECK_GREATER(secondsElapsed, 0, ()); + double constexpr kMPS2KMPH = 60.0 * 60.0 / 1000.0; + return kMPS2KMPH * meters / static_cast<double>(secondsElapsed); +} + +bool IsFiltered(string const & argument, string const & variable) +{ + return !argument.empty() && variable != argument; +} + +void ReadTracks(shared_ptr<NumMwmIds> numMwmIds, string const & filename, + MwmToMatchedTracks & mwmToMatchedTracks) +{ + FileReader reader(filename); + ReaderSource<FileReader> src(reader); + MwmToMatchedTracksSerializer serializer(numMwmIds); + serializer.Deserialize(mwmToMatchedTracks, src); +} + +MatchedTrack const & GetMatchedTrack(MwmToMatchedTracks const & mwmToMatchedTracks, + NumMwmIds const & numMwmIds, string const & mwmName, + string const & user, size_t trackIdx) +{ + auto const countryFile = platform::CountryFile(mwmName); + if (!numMwmIds.ContainsFile(countryFile)) + MYTHROW(MessageException, ("Invalid mwm name", mwmName)); + + NumMwmId const numMwmId = numMwmIds.GetId(countryFile); + + auto mIt = mwmToMatchedTracks.find(numMwmId); + if (mIt == mwmToMatchedTracks.cend()) + MYTHROW(MessageException, ("There is no tracks for mwm", mwmName)); + + UserToMatchedTracks const & userToMatchedTracks = mIt->second; + + auto uIt = userToMatchedTracks.find(user); + if (uIt == userToMatchedTracks.end()) + MYTHROW(MessageException, ("There is no user", user)); + + vector<MatchedTrack> const & tracks = uIt->second; + + if (trackIdx >= tracks.size()) + { + MYTHROW(MessageException, ("There is no track", trackIdx, "for user", user, ", she has", + tracks.size(), "tracks only")); + } + + return tracks[trackIdx]; +} +} // namespace tracking
\ No newline at end of file diff --git a/track_analyzing/utils.hpp b/track_analyzing/utils.hpp new file mode 100644 index 0000000000..b10f180d81 --- /dev/null +++ b/track_analyzing/utils.hpp @@ -0,0 +1,86 @@ +#pragma once + +#include "track_analyzing/exceptions.hpp" +#include "track_analyzing/track.hpp" + +#include "routing/geometry.hpp" +#include "routing/num_mwm_id.hpp" + +#include <boost/filesystem.hpp> + +#include <cstdint> +#include <memory> +#include <string> +#include <vector> + +namespace tracking +{ +double CalcSubtrackLength(MatchedTrack const & track, size_t begin, size_t end, + routing::Geometry & geometry); +double CalcTrackLength(MatchedTrack const & track, routing::Geometry & geometry); +double CalcSpeedKMpH(double meters, uint64_t secondsElapsed); +bool IsFiltered(std::string const & argument, std::string const & variable); +void ReadTracks(std::shared_ptr<routing::NumMwmIds> numMwmIds, std::string const & filename, + MwmToMatchedTracks & mwmToMatchedTracks); +MatchedTrack const & GetMatchedTrack(MwmToMatchedTracks const & mwmToMatchedTracks, + routing::NumMwmIds const & numMwmIds, + std::string const & mwmName, std::string const & user, + size_t trackIdx); + +template <typename MwmToTracks, typename ToDo> +void ForTracksSortedByMwmName(ToDo && toDo, MwmToTracks const & mwmToTracks, + routing::NumMwmIds const & numMwmIds) +{ + std::vector<std::string> mwmNames; + mwmNames.reserve(mwmToTracks.size()); + for (auto const & it : mwmToTracks) + mwmNames.push_back(numMwmIds.GetFile(it.first).GetName()); + sort(mwmNames.begin(), mwmNames.end()); + + for (auto const & mwmName : mwmNames) + { + auto const mwmId = numMwmIds.GetId(platform::CountryFile(mwmName)); + auto mwmIt = mwmToTracks.find(mwmId); + CHECK(mwmIt != mwmToTracks.cend(), ()); + toDo(mwmName, mwmIt->second); + } +} + +template <typename ToDo> +void ForEachTrackFile(ToDo && toDo, std::string const & filepath, std::string const & extension, + shared_ptr<routing::NumMwmIds> numMwmIds) +{ + if (!boost::filesystem::exists(filepath.c_str())) + MYTHROW(MessageException, ("File doesn't exist", filepath)); + + if (boost::filesystem::is_regular(filepath)) + { + MwmToMatchedTracks mwmToMatchedTracks; + ReadTracks(numMwmIds, filepath, mwmToMatchedTracks); + toDo(filepath, mwmToMatchedTracks); + return; + } + + if (boost::filesystem::is_directory(filepath)) + { + for (boost::filesystem::recursive_directory_iterator it(filepath.c_str()), end; it != end; ++it) + { + boost::filesystem::path const & path = it->path(); + if (!boost::filesystem::is_regular(path)) + continue; + + if (path.extension() != extension) + continue; + + MwmToMatchedTracks mwmToMatchedTracks; + string const & filename = path.string(); + ReadTracks(numMwmIds, filename, mwmToMatchedTracks); + toDo(filename, mwmToMatchedTracks); + } + + return; + } + + MYTHROW(MessageException, (filepath, "is neither a regular file nor a directory't exist")); +} +} // namespace tracking |