diff options
author | vvvv <vvvv@ydb.tech> | 2023-07-31 18:21:04 +0300 |
---|---|---|
committer | vvvv <vvvv@ydb.tech> | 2023-07-31 18:21:04 +0300 |
commit | dec41c40e51aa407edef81a3c566a5a15780fc49 (patch) | |
tree | 4f197b596b32f35eca368121f0dff913419da9af /library/cpp/geo | |
parent | 3ca8b54c96e09eb2b65be7f09675623438d559c7 (diff) | |
download | ydb-dec41c40e51aa407edef81a3c566a5a15780fc49.tar.gz |
YQL-16239 Move purecalc to public
Diffstat (limited to 'library/cpp/geo')
30 files changed, 2490 insertions, 0 deletions
diff --git a/library/cpp/geo/CMakeLists.darwin-x86_64.txt b/library/cpp/geo/CMakeLists.darwin-x86_64.txt new file mode 100644 index 0000000000..87e48b4a71 --- /dev/null +++ b/library/cpp/geo/CMakeLists.darwin-x86_64.txt @@ -0,0 +1,24 @@ + +# This file was generated by the build system used internally in the Yandex monorepo. +# Only simple modifications are allowed (adding source-files to targets, adding simple properties +# like target_include_directories). These modifications will be ported to original +# ya.make files by maintainers. Any complex modifications which can't be ported back to the +# original buildsystem will not be accepted. + + + +add_library(library-cpp-geo) +target_link_libraries(library-cpp-geo PUBLIC + contrib-libs-cxxsupp + yutil +) +target_sources(library-cpp-geo PRIVATE + ${CMAKE_SOURCE_DIR}/library/cpp/geo/bbox.cpp + ${CMAKE_SOURCE_DIR}/library/cpp/geo/geo.cpp + ${CMAKE_SOURCE_DIR}/library/cpp/geo/point.cpp + ${CMAKE_SOURCE_DIR}/library/cpp/geo/polygon.cpp + ${CMAKE_SOURCE_DIR}/library/cpp/geo/load_save_helper.cpp + ${CMAKE_SOURCE_DIR}/library/cpp/geo/size.cpp + ${CMAKE_SOURCE_DIR}/library/cpp/geo/util.cpp + ${CMAKE_SOURCE_DIR}/library/cpp/geo/window.cpp +) diff --git a/library/cpp/geo/CMakeLists.linux-aarch64.txt b/library/cpp/geo/CMakeLists.linux-aarch64.txt new file mode 100644 index 0000000000..cdad35989a --- /dev/null +++ b/library/cpp/geo/CMakeLists.linux-aarch64.txt @@ -0,0 +1,25 @@ + +# This file was generated by the build system used internally in the Yandex monorepo. +# Only simple modifications are allowed (adding source-files to targets, adding simple properties +# like target_include_directories). These modifications will be ported to original +# ya.make files by maintainers. Any complex modifications which can't be ported back to the +# original buildsystem will not be accepted. + + + +add_library(library-cpp-geo) +target_link_libraries(library-cpp-geo PUBLIC + contrib-libs-linux-headers + contrib-libs-cxxsupp + yutil +) +target_sources(library-cpp-geo PRIVATE + ${CMAKE_SOURCE_DIR}/library/cpp/geo/bbox.cpp + ${CMAKE_SOURCE_DIR}/library/cpp/geo/geo.cpp + ${CMAKE_SOURCE_DIR}/library/cpp/geo/point.cpp + ${CMAKE_SOURCE_DIR}/library/cpp/geo/polygon.cpp + ${CMAKE_SOURCE_DIR}/library/cpp/geo/load_save_helper.cpp + ${CMAKE_SOURCE_DIR}/library/cpp/geo/size.cpp + ${CMAKE_SOURCE_DIR}/library/cpp/geo/util.cpp + ${CMAKE_SOURCE_DIR}/library/cpp/geo/window.cpp +) diff --git a/library/cpp/geo/CMakeLists.linux-x86_64.txt b/library/cpp/geo/CMakeLists.linux-x86_64.txt new file mode 100644 index 0000000000..cdad35989a --- /dev/null +++ b/library/cpp/geo/CMakeLists.linux-x86_64.txt @@ -0,0 +1,25 @@ + +# This file was generated by the build system used internally in the Yandex monorepo. +# Only simple modifications are allowed (adding source-files to targets, adding simple properties +# like target_include_directories). These modifications will be ported to original +# ya.make files by maintainers. Any complex modifications which can't be ported back to the +# original buildsystem will not be accepted. + + + +add_library(library-cpp-geo) +target_link_libraries(library-cpp-geo PUBLIC + contrib-libs-linux-headers + contrib-libs-cxxsupp + yutil +) +target_sources(library-cpp-geo PRIVATE + ${CMAKE_SOURCE_DIR}/library/cpp/geo/bbox.cpp + ${CMAKE_SOURCE_DIR}/library/cpp/geo/geo.cpp + ${CMAKE_SOURCE_DIR}/library/cpp/geo/point.cpp + ${CMAKE_SOURCE_DIR}/library/cpp/geo/polygon.cpp + ${CMAKE_SOURCE_DIR}/library/cpp/geo/load_save_helper.cpp + ${CMAKE_SOURCE_DIR}/library/cpp/geo/size.cpp + ${CMAKE_SOURCE_DIR}/library/cpp/geo/util.cpp + ${CMAKE_SOURCE_DIR}/library/cpp/geo/window.cpp +) diff --git a/library/cpp/geo/CMakeLists.txt b/library/cpp/geo/CMakeLists.txt new file mode 100644 index 0000000000..f8b31df0c1 --- /dev/null +++ b/library/cpp/geo/CMakeLists.txt @@ -0,0 +1,17 @@ + +# This file was generated by the build system used internally in the Yandex monorepo. +# Only simple modifications are allowed (adding source-files to targets, adding simple properties +# like target_include_directories). These modifications will be ported to original +# ya.make files by maintainers. Any complex modifications which can't be ported back to the +# original buildsystem will not be accepted. + + +if (CMAKE_SYSTEM_NAME STREQUAL "Linux" AND CMAKE_SYSTEM_PROCESSOR STREQUAL "aarch64" AND NOT HAVE_CUDA) + include(CMakeLists.linux-aarch64.txt) +elseif (CMAKE_SYSTEM_NAME STREQUAL "Darwin" AND CMAKE_SYSTEM_PROCESSOR STREQUAL "x86_64") + include(CMakeLists.darwin-x86_64.txt) +elseif (WIN32 AND CMAKE_SYSTEM_PROCESSOR STREQUAL "AMD64" AND NOT HAVE_CUDA) + include(CMakeLists.windows-x86_64.txt) +elseif (CMAKE_SYSTEM_NAME STREQUAL "Linux" AND CMAKE_SYSTEM_PROCESSOR STREQUAL "x86_64" AND NOT HAVE_CUDA) + include(CMakeLists.linux-x86_64.txt) +endif() diff --git a/library/cpp/geo/CMakeLists.windows-x86_64.txt b/library/cpp/geo/CMakeLists.windows-x86_64.txt new file mode 100644 index 0000000000..87e48b4a71 --- /dev/null +++ b/library/cpp/geo/CMakeLists.windows-x86_64.txt @@ -0,0 +1,24 @@ + +# This file was generated by the build system used internally in the Yandex monorepo. +# Only simple modifications are allowed (adding source-files to targets, adding simple properties +# like target_include_directories). These modifications will be ported to original +# ya.make files by maintainers. Any complex modifications which can't be ported back to the +# original buildsystem will not be accepted. + + + +add_library(library-cpp-geo) +target_link_libraries(library-cpp-geo PUBLIC + contrib-libs-cxxsupp + yutil +) +target_sources(library-cpp-geo PRIVATE + ${CMAKE_SOURCE_DIR}/library/cpp/geo/bbox.cpp + ${CMAKE_SOURCE_DIR}/library/cpp/geo/geo.cpp + ${CMAKE_SOURCE_DIR}/library/cpp/geo/point.cpp + ${CMAKE_SOURCE_DIR}/library/cpp/geo/polygon.cpp + ${CMAKE_SOURCE_DIR}/library/cpp/geo/load_save_helper.cpp + ${CMAKE_SOURCE_DIR}/library/cpp/geo/size.cpp + ${CMAKE_SOURCE_DIR}/library/cpp/geo/util.cpp + ${CMAKE_SOURCE_DIR}/library/cpp/geo/window.cpp +) diff --git a/library/cpp/geo/bbox.cpp b/library/cpp/geo/bbox.cpp new file mode 100644 index 0000000000..aa4258ac22 --- /dev/null +++ b/library/cpp/geo/bbox.cpp @@ -0,0 +1 @@ +#include "bbox.h" diff --git a/library/cpp/geo/bbox.h b/library/cpp/geo/bbox.h new file mode 100644 index 0000000000..7ec7e6f7d6 --- /dev/null +++ b/library/cpp/geo/bbox.h @@ -0,0 +1,59 @@ +#pragma once + +#include <util/generic/utility.h> + +#include "point.h" + +namespace NGeo { + + class TGeoBoundingBox { + public: + TGeoBoundingBox() + + = default; + + TGeoBoundingBox(const TGeoPoint& p1, const TGeoPoint& p2) { + MinX_ = Min(p1.Lon(), p2.Lon()); + MaxX_ = Max(p1.Lon(), p2.Lon()); + MinY_ = Min(p1.Lat(), p2.Lat()); + MaxY_ = Max(p1.Lat(), p2.Lat()); + } + + const double& GetMinX() const { + return MinX_; + } + + const double& GetMaxX() const { + return MaxX_; + } + + const double& GetMinY() const { + return MinY_; + } + + const double& GetMaxY() const { + return MaxY_; + } + + double Width() const { + return MaxX_ - MinX_; + } + + double Height() const { + return MaxY_ - MinY_; + } + + private: + double MinX_{std::numeric_limits<double>::quiet_NaN()}; + double MaxX_{std::numeric_limits<double>::quiet_NaN()}; + double MinY_{std::numeric_limits<double>::quiet_NaN()}; + double MaxY_{std::numeric_limits<double>::quiet_NaN()}; + }; + + inline bool operator==(const TGeoBoundingBox& a, const TGeoBoundingBox& b) { + return a.GetMinX() == b.GetMinX() && + a.GetMinY() == b.GetMinY() && + a.GetMaxX() == b.GetMaxX() && + a.GetMaxY() == b.GetMaxY(); + } +} // namespace NGeo diff --git a/library/cpp/geo/geo.cpp b/library/cpp/geo/geo.cpp new file mode 100644 index 0000000000..37adc5c62c --- /dev/null +++ b/library/cpp/geo/geo.cpp @@ -0,0 +1 @@ +#include "geo.h" diff --git a/library/cpp/geo/geo.h b/library/cpp/geo/geo.h new file mode 100644 index 0000000000..1aebacab5c --- /dev/null +++ b/library/cpp/geo/geo.h @@ -0,0 +1,8 @@ +#pragma once + +#include "bbox.h" +#include "point.h" +#include "polygon.h" +#include "size.h" +#include "util.h" +#include "window.h" diff --git a/library/cpp/geo/load_save_helper.cpp b/library/cpp/geo/load_save_helper.cpp new file mode 100644 index 0000000000..13fa7ac6df --- /dev/null +++ b/library/cpp/geo/load_save_helper.cpp @@ -0,0 +1,49 @@ +#include "load_save_helper.h" +#include <util/stream/input.h> + +void TSerializer<NGeo::TGeoPoint>::Save(IOutputStream* out, const NGeo::TGeoPoint& point) { + double lon = static_cast<double>(point.Lon()); + double lat = static_cast<double>(point.Lat()); + ::Save(out, lon); + ::Save(out, lat); +} + +void TSerializer<NGeo::TGeoPoint>::Load(IInputStream* in, NGeo::TGeoPoint& point) { + double lon = std::numeric_limits<double>::quiet_NaN(); + double lat = std::numeric_limits<double>::quiet_NaN(); + ::Load(in, lon); + ::Load(in, lat); + point = {lon, lat}; +} + +void TSerializer<NGeo::TGeoWindow>::Save(IOutputStream* out, const NGeo::TGeoWindow& window) { + const auto& center = window.GetCenter(); + const auto& size = window.GetSize(); + ::Save(out, center); + ::Save(out, size); +} + +void TSerializer<NGeo::TGeoWindow>::Load(IInputStream* in, NGeo::TGeoWindow& window) { + NGeo::TSize size{}; + NGeo::TGeoPoint center{}; + + ::Load(in, center); + ::Load(in, size); + + window = {center, size}; +} + +void TSerializer<NGeo::TSize>::Save(IOutputStream* out, const NGeo::TSize& size) { + double width = static_cast<double>(size.GetWidth()); + double height = static_cast<double>(size.GetHeight()); + ::Save(out, width); + ::Save(out, height); +} + +void TSerializer<NGeo::TSize>::Load(IInputStream* in, NGeo::TSize& size) { + double width = std::numeric_limits<double>::quiet_NaN(); + double height = std::numeric_limits<double>::quiet_NaN(); + ::Load(in, width); + ::Load(in, height); + size = {width, height}; +} diff --git a/library/cpp/geo/load_save_helper.h b/library/cpp/geo/load_save_helper.h new file mode 100644 index 0000000000..4a5fceea18 --- /dev/null +++ b/library/cpp/geo/load_save_helper.h @@ -0,0 +1,23 @@ +#pragma once + +#include <library/cpp/geo/window.h> +#include <util/stream/input.h> +#include <util/ysaveload.h> + +template <> +struct TSerializer<NGeo::TGeoPoint> { + static void Save(IOutputStream*, const NGeo::TGeoPoint&); + static void Load(IInputStream*, NGeo::TGeoPoint&); +}; + +template <> +struct TSerializer<NGeo::TGeoWindow> { + static void Save(IOutputStream*, const NGeo::TGeoWindow&); + static void Load(IInputStream*, NGeo::TGeoWindow&); +}; + +template <> +struct TSerializer<NGeo::TSize> { + static void Save(IOutputStream*, const NGeo::TSize&); + static void Load(IInputStream*, NGeo::TSize&); +}; diff --git a/library/cpp/geo/point.cpp b/library/cpp/geo/point.cpp new file mode 100644 index 0000000000..1d227c967f --- /dev/null +++ b/library/cpp/geo/point.cpp @@ -0,0 +1,146 @@ +#include "point.h" +#include "util.h" + +#include <util/generic/ylimits.h> +#include <util/generic/ymath.h> + +#include <cstdlib> +#include <utility> + +namespace NGeo { + namespace { + bool IsNonDegeneratePoint(double lon, double lat) { + return (MIN_LONGITUDE - WORLD_WIDTH < lon && lon < MAX_LONGITUDE + WORLD_WIDTH) && + (MIN_LATITUDE < lat && lat < MAX_LATITUDE); + } + } // namespace + + float TGeoPoint::Distance(const TGeoPoint& p) const noexcept { + auto dp = p - (*this); + return sqrtf(Sqr(GetWidthAtEquator(dp.GetWidth(), (Lat_ + p.Lat()) * 0.5)) + Sqr(dp.GetHeight())); + } + + bool TGeoPoint::IsPole() const noexcept { + return Lat_ <= MIN_LATITUDE || MAX_LATITUDE <= Lat_; + } + + bool TGeoPoint::IsVisibleOnMap() const noexcept { + return -VISIBLE_LATITUDE_BOUND <= Lat_ && Lat_ <= VISIBLE_LATITUDE_BOUND; + } + + TGeoPoint TGeoPoint::Parse(TStringBuf s, TStringBuf delimiter) { + const auto& [lon, lat] = PairFromString(s, delimiter); + Y_ENSURE_EX(IsNonDegeneratePoint(lon, lat), TBadCastException() << "Invalid point: (" << lon << ", " << lat << ")"); + return {lon, lat}; + } + + TMaybe<TGeoPoint> TGeoPoint::TryParse(TStringBuf s, TStringBuf delimiter) { + std::pair<double, double> lonLat; + if (!TryPairFromString(lonLat, s, delimiter)) { + return {}; + } + if (!IsNonDegeneratePoint(lonLat.first, lonLat.second)) { + return {}; + } + return TGeoPoint(lonLat.first, lonLat.second); + } + + TSize operator-(const TGeoPoint& p1, const TGeoPoint& p2) { + return {p1.Lon() - p2.Lon(), p1.Lat() - p2.Lat()}; + } + + /* + Conversion code was imported from http://wiki.yandex-team.ru/YandexMobile/maps/Algorithm/mapengine/coordtransforms + */ + namespace WGS84 { + /* Isometric to geodetic latitude parameters, default to WGS 84 */ + const double ab = 0.00335655146887969400; + const double bb = 0.00000657187271079536; + const double cb = 0.00000001764564338702; + const double db = 0.00000000005328478445; + + const double _a = R; + const double _f = 1.0 / 298.257223563; + const double _b = _a - _f * _a; + const double _e = sqrt(1 - pow(_b / _a, 2)); + const double _e2 = _e * _e; + const double _g = sqrt(1.0 - _e2); + const double _gR2 = _g * R * 2.0; + } // namespace WGS84 + + TGeoPoint MercatorToLL(TMercatorPoint pt) { + using namespace WGS84; + + // Y_ENSURE(pt.IsDefined(), "Point is not defined"); + + /* Isometric latitude*/ + const double xphi = PI / 2.0 - 2.0 * atan(exp(-pt.Y_ / R)); + + double latitude = xphi + ab * sin(2.0 * xphi) + bb * sin(4.0 * xphi) + cb * sin(6.0 * xphi) + db * sin(8.0 * xphi); + double longitude = pt.X_ / R; + + return TGeoPoint{Rad2deg(longitude), Rad2deg(latitude)}; + } + + double GetMercatorY(const TGeoPoint& ll) { + if (Y_UNLIKELY(ll.Lat() == 0.)) { + // shortcut for common case, avoiding floating point errors + return 0.; + } + if (Y_UNLIKELY(ll.Lat() == MIN_LATITUDE)) { + return -std::numeric_limits<double>::infinity(); + } + if (Y_UNLIKELY(ll.Lat() == MAX_LATITUDE)) { + return +std::numeric_limits<double>::infinity(); + } + double lat = Deg2rad(ll.Lat()); + double esinLat = WGS84::_e * sin(lat); + + double tan_temp = tan(PI / 4.e0 + lat / 2.e0); + double pow_temp = pow(tan(PI / 4.e0 + asin(esinLat) / 2), WGS84::_e); + double U = tan_temp / pow_temp; + return WGS84::R * log(U); + } + + TMercatorPoint LLToMercator(TGeoPoint ll) { + // Y_ENSURE(ll.IsValid(), "Point is not defined"); + + // Y_ENSURE(-90. <= ll.Lat() && ll.Lat() <= +90., "Latitude is out of range [-90, 90]"); + + double lon = Deg2rad(ll.Lon()); + double x = WGS84::R * lon; + double y = GetMercatorY(ll); + + return TMercatorPoint{x, y}; + } + + double GeodeticDistance(TGeoPoint p1, TGeoPoint p2) { + using namespace WGS84; + + constexpr double deg2HalfRad = PI / 360.0; + + const double lon1Half = p1.Lon() * deg2HalfRad; + const double lon2Half = p2.Lon() * deg2HalfRad; + + const double lat1Half = p1.Lat() * deg2HalfRad; + const double lat2Half = p2.Lat() * deg2HalfRad; + + const double diffLatHalf = fabs(lat1Half - lat2Half); + const double diffLonHalf = fabs(lon1Half - lon2Half); + + if (diffLatHalf < 0.5e-8 && diffLonHalf < 0.5e-8) { + return 0; + } + + double s = sin(lat1Half + lat2Half); + double s2 = s * s; + double m = _gR2 / (1.0 - _e2 * s2); + + const double w = sin(diffLatHalf); + const double w2 = w * w; + const double cc = Max(1.0 - s2 - w2, 0.0); // cos(lat1Half * 2) * cos(lat2Half * 2) + const double z = sin(diffLonHalf); + + return m * asin(sqrt(w2 + cc * z * z)); + } +} // namespace NGeo diff --git a/library/cpp/geo/point.h b/library/cpp/geo/point.h new file mode 100644 index 0000000000..70c91ab2dd --- /dev/null +++ b/library/cpp/geo/point.h @@ -0,0 +1,198 @@ +#pragma once + +#include <util/generic/string.h> +#include <util/stream/output.h> +#include <util/string/cast.h> +#include <util/generic/maybe.h> + +#include <algorithm> +#include <cmath> + +namespace NGeo { + class TSize; + + class TGeoPoint { + public: + TGeoPoint(double lon, double lat) noexcept + : Lon_(lon) + , Lat_(lat) + { + } + + TGeoPoint() noexcept + : Lon_(BadX) + , Lat_(BadY) + { + } + + double Lon() const noexcept { + return Lon_; + } + + double Lat() const noexcept { + return Lat_; + } + + float Distance(const TGeoPoint& p) const noexcept; + + void swap(TGeoPoint& p) noexcept { + std::swap(Lon_, p.Lon_); + std::swap(Lat_, p.Lat_); + } + + bool IsValid() const { + return (Lon_ != BadX) && (Lat_ != BadY); + } + + /// Returns true if the point represents either North or South Pole + bool IsPole() const noexcept; + + /// Returns true if the point may be shown on the Yandex Map (fits into the valid range of latitudes) + bool IsVisibleOnMap() const noexcept; + + bool operator!() const { + return !IsValid(); + } + + TString ToCgiStr() const { + return ToString(); + } + + TString ToString(const char* delimiter = ",") const { + return TString::Join(::ToString(Lon_), delimiter, ::ToString(Lat_)); + } + + /** + * \note Parsing functions work is safe way. They discard invalid points: + * 1) on the Poles and 'beyond' the Poles; + * 2) not belonging to the 'main' world and +/-1 world to the left or to the right. + * If you need such cases, construct the TGeoPoint manually. + */ + + /// Throws TBadCastException on error + static TGeoPoint Parse(TStringBuf s, TStringBuf delimiter = TStringBuf(",")); + + /// Returns Nothing() on error + static TMaybe<TGeoPoint> TryParse(TStringBuf s, TStringBuf delimiter = TStringBuf(",")); + + private: + double Lon_; + double Lat_; + + static constexpr double BadX{361.}; + static constexpr double BadY{181.}; + }; + + double GeodeticDistance(TGeoPoint p1, TGeoPoint p2); + + /** + * \class TMercatorPoint + * + * Represents a point in EPSG:3395 projection + * (WGS 84 / World Mercator) + */ + class TMercatorPoint { + public: + friend class TMercatorWindow; + friend TGeoPoint MercatorToLL(TMercatorPoint); + + /** + * Constructs a point with the given coordinates. + */ + constexpr TMercatorPoint(double x, double y) noexcept + : X_{x} + , Y_{y} + { + } + + /** + * Constructs a point with two NaN coordinates. + * + * Should not be called directly. + * If your `point` variable might be undefined, + * declare it explicitly as TMaybe<TMercatorPoint>. + */ + constexpr TMercatorPoint() noexcept + : X_{std::numeric_limits<double>::quiet_NaN()} + , Y_{std::numeric_limits<double>::quiet_NaN()} + { + } + + /** + * Returns the X_ coordinate. + * + * The line X_ == 0 corresponds to the Prime meridian. + */ + constexpr double X() const noexcept { + return X_; + } + + /** + * Returns the Y_ coordinate. + * + * The line Y_ == 0 corresponds to the Equator. + */ + constexpr double Y() const noexcept { + return Y_; + } + + private: + bool IsDefined() const noexcept { + return !std::isnan(X_) && !std::isnan(Y_); + } + + private: + double X_; + double Y_; + }; + + /** + * Operators + */ + + inline bool operator==(const TGeoPoint& p1, const TGeoPoint& p2) { + return p1.Lon() == p2.Lon() && p1.Lat() == p2.Lat(); + } + + inline bool operator==(const TMercatorPoint& p1, const TMercatorPoint& p2) { + return p1.X() == p2.X() && p1.Y() == p2.Y(); + } + + inline bool operator<(const TGeoPoint& p1, const TGeoPoint& p2) { + if (p1.Lon() != p2.Lon()) { + return p1.Lon() < p2.Lon(); + } + return p1.Lat() < p2.Lat(); + } + + /** + * Conversion + */ + + namespace WGS84 { + /* Radius of reference ellipsoid, default to WGS 84 */ + const double R = 6378137.0; + } // namespace WGS84 + + using TPointLL = TGeoPoint; + using TPointXY = TMercatorPoint; + + TGeoPoint MercatorToLL(TMercatorPoint); + TMercatorPoint LLToMercator(TGeoPoint); + + /** + * Input/output + */ + + TSize operator-(const TGeoPoint& p1, const TGeoPoint& p2); +} // namespace NGeo + +template <> +inline void Out<NGeo::TGeoPoint>(IOutputStream& o, const NGeo::TGeoPoint& p) { + o << '[' << p.Lon() << ", " << p.Lat() << ']'; +} + +template <> +inline void Out<NGeo::TMercatorPoint>(IOutputStream& o, const NGeo::TMercatorPoint& p) { + o << '[' << p.X() << ", " << p.Y() << ']'; +} diff --git a/library/cpp/geo/polygon.cpp b/library/cpp/geo/polygon.cpp new file mode 100644 index 0000000000..44e5c38b5f --- /dev/null +++ b/library/cpp/geo/polygon.cpp @@ -0,0 +1,28 @@ +#include "polygon.h" +namespace NGeo { + TMaybe<TGeoPolygon> TGeoPolygon::TryParse(TStringBuf s, TStringBuf llDelimiter, TStringBuf pointsDelimiter) { + TVector<TGeoPoint> points; + + for (const auto& pointString : StringSplitter(s).SplitByString(pointsDelimiter).SkipEmpty()) { + auto curPoint = TGeoPoint::TryParse(pointString.Token(), llDelimiter); + if (!curPoint) { + return {}; + } + points.push_back(*curPoint); + } + + if (points.size() < 3) { + return {}; + } + + return TGeoPolygon(points); + } + + TGeoPolygon TGeoPolygon::Parse(TStringBuf s, TStringBuf llDelimiter, TStringBuf pointsDelimiter) { + auto res = TGeoPolygon::TryParse(s, llDelimiter, pointsDelimiter); + if (!res) { + ythrow yexception() << "Can't parse polygon from input string: " << s; + } + return *res; + } +} // namespace NGeo diff --git a/library/cpp/geo/polygon.h b/library/cpp/geo/polygon.h new file mode 100644 index 0000000000..1528345fec --- /dev/null +++ b/library/cpp/geo/polygon.h @@ -0,0 +1,90 @@ +#pragma once + +#include "point.h" +#include "window.h" + +#include <util/ysaveload.h> +#include <util/generic/algorithm.h> +#include <util/generic/string.h> +#include <util/generic/vector.h> +#include <util/generic/yexception.h> +#include <util/stream/output.h> +#include <util/string/cast.h> +#include <util/string/join.h> +#include <util/string/split.h> + +#include <algorithm> +#include <functional> + +namespace NGeo { + class TGeoPolygon { + private: + TVector<TGeoPoint> Points_; + TGeoWindow Window_; + + public: + TGeoPolygon() = default; + + explicit TGeoPolygon(const TVector<TGeoPoint>& points) + : Points_(points) + { + CalcWindow(); + } + + const TVector<TGeoPoint>& GetPoints() const { + return Points_; + } + + const TGeoWindow& GetWindow() const { + return Window_; + } + + void swap(TGeoPolygon& o) noexcept { + Points_.swap(o.Points_); + Window_.swap(o.Window_); + } + + bool IsValid() const noexcept { + return !Points_.empty() && Window_.IsValid(); + } + + bool operator!() const { + return !IsValid(); + } + + /** + * try to parse TGeoPolygon from string which stores points + * coords are separated by llDelimiter, points are separated by pointsDelimiter + * return parsed TGeoPolygon on success, otherwise throw exception + */ + static TGeoPolygon Parse(TStringBuf s, TStringBuf llDelimiter = ",", TStringBuf pointsDelimiter = TStringBuf(" ")); + + /** + * try to parse TGeoPolygon from string which stores points + * coords are separated by llDelimiter, points are separated by pointsDelimiter + * return TMaybe of parsed TGeoPolygon on success, otherwise return empty TMaybe + */ + static TMaybe<TGeoPolygon> TryParse(TStringBuf s, TStringBuf llDelimiter = ",", TStringBuf pointsDelimiter = TStringBuf(" ")); + + private: + void CalcWindow() { + auto getLon = std::mem_fn(&TGeoPoint::Lon); + double lowerX = MinElementBy(Points_.begin(), Points_.end(), getLon)->Lon(); + double upperX = MaxElementBy(Points_.begin(), Points_.end(), getLon)->Lon(); + + auto getLat = std::mem_fn(&TGeoPoint::Lat); + double lowerY = MinElementBy(Points_.begin(), Points_.end(), getLat)->Lat(); + double upperY = MaxElementBy(Points_.begin(), Points_.end(), getLat)->Lat(); + + Window_ = TGeoWindow{TGeoPoint{lowerX, lowerY}, TGeoPoint{upperX, upperY}}; + } + }; + + inline bool operator==(const TGeoPolygon& p1, const TGeoPolygon& p2) { + return p1.GetPoints() == p2.GetPoints(); + } + + inline bool operator!=(const TGeoPolygon& p1, const TGeoPolygon& p2) { + return !(p1 == p2); + } +} // namespace NGeo diff --git a/library/cpp/geo/size.cpp b/library/cpp/geo/size.cpp new file mode 100644 index 0000000000..f1bd8ab763 --- /dev/null +++ b/library/cpp/geo/size.cpp @@ -0,0 +1,31 @@ +#include "size.h" + +#include "util.h" + +namespace NGeo { + const double TSize::BadWidth = -1.; + const double TSize::BadHeight = -1.; + + namespace { + bool IsNonNegativeSize(double width, double height) { + return width >= 0. && height >= 0.; + } + } // namespace + + TSize TSize::Parse(TStringBuf s, TStringBuf delimiter) { + const auto& [width, height] = PairFromString(s, delimiter); + Y_ENSURE_EX(IsNonNegativeSize(width, height), TBadCastException() << "Negative window size"); + return {width, height}; + } + + TMaybe<TSize> TSize::TryParse(TStringBuf s, TStringBuf delimiter) { + std::pair<double, double> lonLat; + if (!TryPairFromString(lonLat, s, delimiter)) { + return {}; + } + if (!IsNonNegativeSize(lonLat.first, lonLat.second)) { + return {}; + } + return TSize{lonLat.first, lonLat.second}; + } +} // namespace NGeo diff --git a/library/cpp/geo/size.h b/library/cpp/geo/size.h new file mode 100644 index 0000000000..b619c6d899 --- /dev/null +++ b/library/cpp/geo/size.h @@ -0,0 +1,93 @@ +#pragma once + +#include <util/generic/string.h> +#include <util/stream/output.h> +#include <util/string/cast.h> + +namespace NGeo { + class TSize { + public: + TSize(double width, double height) noexcept + : Width_(width) + , Height_(height) + { + } + + explicit TSize(double size) noexcept + : Width_(size) + , Height_(size) + { + } + + TSize() noexcept + : Width_(BadWidth) + , Height_(BadHeight) + { + } + + double GetWidth() const noexcept { + return Width_; + } + + double GetHeight() const noexcept { + return Height_; + } + + void swap(TSize& s) noexcept { + std::swap(Width_, s.Width_); + std::swap(Height_, s.Height_); + } + + bool IsValid() const { + return (Width_ != BadWidth) && (Height_ != BadHeight); + } + + void Stretch(double multiplier) { + Width_ *= multiplier; + Height_ *= multiplier; + } + + void Inflate(double additionX, double additionY) { + Width_ += additionX; + Height_ += additionY; + } + + bool operator!() const { + return !IsValid(); + } + + TString ToCgiStr() const { + TString s = ToString(Width_); + s.append(','); + s.append(ToString(Height_)); + return s; + } + + /** + * try to parse TSize + * return parsed TSize on success, otherwise throw exception + */ + static TSize Parse(TStringBuf s, TStringBuf delimiter = TStringBuf(",")); + + /** + * try to parse TSize + * return TMaybe of parsed TSize on success, otherwise return empty TMaybe + */ + static TMaybe<TSize> TryParse(TStringBuf s, TStringBuf delimiter = TStringBuf(",")); + + private: + double Width_; + double Height_; + static const double BadWidth; + static const double BadHeight; + }; + + inline bool operator==(const TSize& p1, const TSize& p2) { + return p1.GetHeight() == p2.GetHeight() && p1.GetWidth() == p2.GetWidth(); + } +} // namespace NGeo + +template <> +inline void Out<NGeo::TSize>(IOutputStream& o, const NGeo::TSize& s) { + o << '<' << s.GetWidth() << ", " << s.GetHeight() << '>'; +} diff --git a/library/cpp/geo/style/ya.make b/library/cpp/geo/style/ya.make new file mode 100644 index 0000000000..f72d50f27e --- /dev/null +++ b/library/cpp/geo/style/ya.make @@ -0,0 +1,8 @@ +CPP_STYLE_TEST_14() + +STYLE( + library/cpp/geo/**/*.cpp + library/cpp/geo/**/*.h +) + +END() diff --git a/library/cpp/geo/ut/load_save_helper_ut.cpp b/library/cpp/geo/ut/load_save_helper_ut.cpp new file mode 100644 index 0000000000..f251f56630 --- /dev/null +++ b/library/cpp/geo/ut/load_save_helper_ut.cpp @@ -0,0 +1,90 @@ +#include "load_save_helper.h" +#include "point.h" + +#include <library/cpp/testing/unittest/registar.h> +#include <util/stream/str.h> +#include <util/ysaveload.h> + +namespace { + void CheckSave(const NGeo::TGeoPoint& point) { + TStringStream output; + ::Save(&output, point); + TStringStream answer; + ::Save(&answer, static_cast<double>(point.Lon())); + ::Save(&answer, static_cast<double>(point.Lat())); + UNIT_ASSERT_EQUAL(output.Str(), answer.Str()); + } + + void CheckLoad(const double x, const double y) { + TStringStream input; + ::Save(&input, x); + ::Save(&input, y); + NGeo::TGeoPoint output; + ::Load(&input, output); + + const double eps = 1.E-8; + UNIT_ASSERT_DOUBLES_EQUAL(static_cast<double>(output.Lon()), x, eps); + UNIT_ASSERT_DOUBLES_EQUAL(static_cast<double>(output.Lat()), y, eps); + } + + void CheckLoadAfterSavePointLL(double x, double y) { + NGeo::TGeoPoint answer = {x, y}; + TStringStream iostream; + ::Save(&iostream, answer); + NGeo::TGeoPoint output; + ::Load(&iostream, output); + + const double eps = 1.E-8; + UNIT_ASSERT_DOUBLES_EQUAL(static_cast<double>(output.Lon()), x, eps); + UNIT_ASSERT_DOUBLES_EQUAL(static_cast<double>(output.Lat()), y, eps); + } + + void CheckLoadAfterSaveWindowLL(NGeo::TGeoPoint center, NGeo::TSize size) { + NGeo::TGeoWindow answer = {center, size}; + TStringStream iostream; + ::Save(&iostream, answer); + NGeo::TGeoWindow output; + ::Load(&iostream, output); + UNIT_ASSERT_EQUAL(output.GetCenter(), answer.GetCenter()); + UNIT_ASSERT_EQUAL(output.GetSize(), answer.GetSize()); + } +} // namespace + +Y_UNIT_TEST_SUITE(TSaveLoadForPointLL) { + Y_UNIT_TEST(TestSave) { + // {27.561481, 53.902496} Minsk Lon and Lat + CheckSave({27.561481, 53.902496}); + CheckSave({-27.561481, 53.902496}); + CheckSave({27.561481, -53.902496}); + CheckSave({-27.561481, -53.902496}); + } + + Y_UNIT_TEST(TestLoad) { + CheckLoad(27.561481, 53.902496); + CheckLoad(-27.561481, 53.902496); + CheckLoad(27.561481, -53.902496); + CheckLoad(-27.561481, -53.902496); + } + + Y_UNIT_TEST(TestSaveLoad) { + CheckLoadAfterSavePointLL(27.561481, 53.902496); + CheckLoadAfterSavePointLL(-27.561481, 53.902496); + CheckLoadAfterSavePointLL(27.561481, -53.902496); + CheckLoadAfterSavePointLL(-27.561481, -53.902496); + CheckLoadAfterSavePointLL(0, 0); + } +} + +Y_UNIT_TEST_SUITE(TSaveLoadForWindowLL) { + Y_UNIT_TEST(TestSave) { + CheckLoadAfterSaveWindowLL({27.561481, 53.902496}, {1, 2}); + CheckLoadAfterSaveWindowLL({27.561481, 53.902496}, {2, 1}); + CheckLoadAfterSaveWindowLL({-27.561481, 53.902496}, {1, 2}); + CheckLoadAfterSaveWindowLL({-27.561481, 53.902496}, {2, 1}); + CheckLoadAfterSaveWindowLL({27.561481, -53.902496}, {1, 2}); + CheckLoadAfterSaveWindowLL({27.561481, -53.902496}, {2, 1}); + CheckLoadAfterSaveWindowLL({-27.561481, -53.902496}, {1, 2}); + CheckLoadAfterSaveWindowLL({-27.561481, -53.902496}, {2, 1}); + CheckLoadAfterSaveWindowLL({0, 0}, {0, 0}); + } +} diff --git a/library/cpp/geo/ut/point_ut.cpp b/library/cpp/geo/ut/point_ut.cpp new file mode 100644 index 0000000000..bbf8f32cea --- /dev/null +++ b/library/cpp/geo/ut/point_ut.cpp @@ -0,0 +1,171 @@ +#include "point.h" + +#include <library/cpp/testing/unittest/registar.h> + +using namespace NGeo; + +namespace { + void CheckMercator(TGeoPoint input, TMercatorPoint answer, double eps = 1.e-8) { + auto output = LLToMercator(input); + UNIT_ASSERT_DOUBLES_EQUAL(output.X(), answer.X(), eps); + UNIT_ASSERT_DOUBLES_EQUAL(output.Y(), answer.Y(), eps); + } + + void CheckGeo(TMercatorPoint input, TGeoPoint answer, double eps = 1.e-8) { + auto output = MercatorToLL(input); + UNIT_ASSERT_DOUBLES_EQUAL(output.Lon(), answer.Lon(), eps); + UNIT_ASSERT_DOUBLES_EQUAL(output.Lat(), answer.Lat(), eps); + } +} // namespace + +Y_UNIT_TEST_SUITE(TPointTest) { + Y_UNIT_TEST(TestGeoPointFromString) { + UNIT_ASSERT_EQUAL(TGeoPoint::Parse("0.15,0.67"), + TGeoPoint(0.15, 0.67)); + UNIT_ASSERT_EQUAL(TGeoPoint::Parse("-52.,-27."), + TGeoPoint(-52., -27.)); + UNIT_ASSERT_EQUAL(TGeoPoint::Parse("0.15 0.67", " "), + TGeoPoint(0.15, 0.67)); + UNIT_ASSERT_EQUAL(TGeoPoint::Parse("-27. -52", " "), + TGeoPoint(-27., -52.)); + UNIT_ASSERT_EQUAL(TGeoPoint::Parse("182,55"), + TGeoPoint(182., 55.)); + + // current behavior + UNIT_ASSERT(TGeoPoint::TryParse(TString{}).Empty()); + UNIT_ASSERT_EXCEPTION(TGeoPoint::Parse("Hello,world"), TBadCastException); + UNIT_ASSERT_EXCEPTION(TGeoPoint::Parse("640 17", " "), TBadCastException); + UNIT_ASSERT_EXCEPTION(TGeoPoint::Parse("50.,100"), TBadCastException); + UNIT_ASSERT_EQUAL(TGeoPoint::Parse(" 0.01, 0.01"), TGeoPoint(0.01, 0.01)); + UNIT_ASSERT_EXCEPTION(TGeoPoint::Parse("0.01 , 0.01"), TBadCastException); + UNIT_ASSERT_EXCEPTION(TGeoPoint::Parse("0.01, 0.01 "), TBadCastException); + } +} + +Y_UNIT_TEST_SUITE(TConversionTest) { + Y_UNIT_TEST(TestConversionGeoToMercator) { + // test data is obtained using PostGIS: + // SELECT ST_AsText(ST_Transform(ST_SetSRID(ST_MakePoint(lon, lat), 4326), 3395)) + + CheckMercator({27.547028, 53.893962}, {3066521.12982805, 7115552.47353991}); + CheckMercator({-70.862782, -53.002613}, {-7888408.80843475, -6949331.55685883}); + CheckMercator({37.588536, 55.734004}, {4184336.68718463, 7470303.90973406}); + CheckMercator({0., 0.}, {0, 0}); + } + + Y_UNIT_TEST(TestConversionMercatorToGeo) { + // test data is obtained using PostGIS: + // SELECT ST_AsText(ST_Transform(ST_SetSRID(ST_MakePoint(X, Y), 3395), 4326)) + + CheckGeo({3066521, 7115552}, {27.5470268337348, 53.8939594873943}); + CheckGeo({-7888409, -6949332}, {-70.8627837208599, -53.0026154014032}); + CheckGeo({4184336, 7470304}, {37.5885298269154, 55.734004457522}); + CheckGeo({0, 0}, {0., 0.}); + } + + Y_UNIT_TEST(TestExactConversion) { + // Zero maps to zero with no epsilons + UNIT_ASSERT_VALUES_EQUAL(LLToMercator({0., 0.}).X(), 0.); + UNIT_ASSERT_VALUES_EQUAL(LLToMercator({0., 0.}).Y(), 0.); + UNIT_ASSERT_VALUES_EQUAL(MercatorToLL({0., 0.}).Lon(), 0.); + UNIT_ASSERT_VALUES_EQUAL(MercatorToLL({0., 0.}).Lat(), 0.); + } + + Y_UNIT_TEST(TestPoles) { + UNIT_ASSERT_VALUES_EQUAL(LLToMercator({0, 90}).Y(), std::numeric_limits<double>::infinity()); + UNIT_ASSERT_VALUES_EQUAL(LLToMercator({0, -90}).Y(), -std::numeric_limits<double>::infinity()); + + UNIT_ASSERT_VALUES_EQUAL(MercatorToLL({0, std::numeric_limits<double>::infinity()}).Lat(), 90.); + UNIT_ASSERT_VALUES_EQUAL(MercatorToLL({0, -std::numeric_limits<double>::infinity()}).Lat(), -90.); + } + + Y_UNIT_TEST(TestNearPoles) { + // Reference values were obtained using mpmath library (floating-point arithmetic with arbitrary precision) + CheckMercator({0., 89.9}, {0., 44884542.157175040}, 1.e-6); + CheckMercator({0., 89.99}, {0., 59570746.872518855}, 1.e-5); + CheckMercator({0., 89.999}, {0., 74256950.065173316}, 1.e-4); + CheckMercator({0., 89.9999}, {0., 88943153.242600886}, 1.e-3); + CheckMercator({0., 89.99999}, {0., 103629356.41987618}, 1.e-1); + CheckMercator({0., 89.999999}, {0., 118315559.59714996}, 1.e-1); + CheckMercator({0., 89.9999999}, {0., 133001762.77442373}, 1.e-0); + CheckMercator({0., 89.99999999}, {0., 147687965.95169749}, 1.e+1); + CheckMercator({0., 89.9999999999999857891452847979962825775146484375}, {0., 233563773.75716050}, 1.e+7); + + CheckGeo({0., 233563773.75716050}, {0., 89.9999999999999857891452847979962825775146484375}, 1.e-15); + CheckGeo({0., 147687965.95169749}, {0., 89.99999999}, 1.e-13); + CheckGeo({0., 133001762.77442373}, {0., 89.9999999}, 1.e-13); + CheckGeo({0., 118315559.59714996}, {0., 89.999999}, 1.e-13); + CheckGeo({0., 103629356.41987618}, {0., 89.99999}, 1.e-13); + CheckGeo({0., 88943153.242600886}, {0., 89.9999}, 1.e-13); + CheckGeo({0., 74256950.065173316}, {0., 89.999}, 1.e-13); + CheckGeo({0., 59570746.872518855}, {0., 89.99}, 1.e-13); + CheckGeo({0., 44884542.157175040}, {0., 89.9}, 1.e-13); + } + + Y_UNIT_TEST(TestVisibleRange) { + UNIT_ASSERT(TGeoPoint(37., 55.).IsVisibleOnMap()); + UNIT_ASSERT(!TGeoPoint(37., 86.).IsVisibleOnMap()); + UNIT_ASSERT(TGeoPoint(37., -85.).IsVisibleOnMap()); + UNIT_ASSERT(!TGeoPoint(37., -90.).IsVisibleOnMap()); + } + + Y_UNIT_TEST(TestRoundTripGeoMercatorGeo) { + auto check = [](double longitude, double latitude) { + auto pt = MercatorToLL(LLToMercator(TGeoPoint{longitude, latitude})); + UNIT_ASSERT_DOUBLES_EQUAL_C(longitude, pt.Lon(), 1.e-12, "longitude for point (" << longitude << ", " << latitude << ")"); + UNIT_ASSERT_DOUBLES_EQUAL_C(latitude, pt.Lat(), 1.e-8, "latitude for point (" << longitude << ", " << latitude << ")"); + }; + + check(37., 55.); + check(0.1, 0.1); + check(0.2, 89.9); + check(181., -42.); + check(362., -43.); + check(-183., -87.); + check(1000., -77.); + } + + Y_UNIT_TEST(TestRoundTripMercatorGeoMercator) { + auto check = [](double x, double y) { + auto pt = LLToMercator(MercatorToLL(TMercatorPoint{x, y})); + UNIT_ASSERT_DOUBLES_EQUAL_C(x, pt.X(), 1.e-4, "x for point (" << x << ", " << y << ")"); + UNIT_ASSERT_DOUBLES_EQUAL_C(y, pt.Y(), 1.e-4, "y for point (" << x << ", " << y << ")"); + }; + + check(100., 200.); + check(-123456., 654321.); + check(5.e7, 1.23456789); + check(1.e8, -2.e7); + } +} + +Y_UNIT_TEST_SUITE(TestDistance) { + Y_UNIT_TEST(TestGeodeticDistance) { + const TGeoPoint minsk(27.55, 53.916667); + const TGeoPoint moscow(37.617778, 55.755833); + const TGeoPoint newYork(-73.994167, 40.728333); + const TGeoPoint sydney(151.208333, -33.869444); + + const double eps = 1.E-6; // absolute error + + UNIT_ASSERT_DOUBLES_EQUAL(GeodeticDistance(minsk, minsk), 0.0, eps); + UNIT_ASSERT_DOUBLES_EQUAL(GeodeticDistance(minsk, moscow), 677190.08871321136, eps); + UNIT_ASSERT_DOUBLES_EQUAL(GeodeticDistance(minsk, newYork), 7129091.7536358498, eps); + UNIT_ASSERT_DOUBLES_EQUAL(GeodeticDistance(minsk, sydney), 15110861.267782301, eps); + + UNIT_ASSERT_DOUBLES_EQUAL(GeodeticDistance(moscow, minsk), 677190.08871321136, eps); + UNIT_ASSERT_DOUBLES_EQUAL(GeodeticDistance(moscow, moscow), 0.0, eps); + UNIT_ASSERT_DOUBLES_EQUAL(GeodeticDistance(moscow, newYork), 7519517.2469277605, eps); + UNIT_ASSERT_DOUBLES_EQUAL(GeodeticDistance(moscow, sydney), 14467193.188083574, eps); + + UNIT_ASSERT_DOUBLES_EQUAL(GeodeticDistance(newYork, minsk), 7129091.7536358498, eps); + UNIT_ASSERT_DOUBLES_EQUAL(GeodeticDistance(newYork, moscow), 7519517.2469277605, eps); + UNIT_ASSERT_DOUBLES_EQUAL(GeodeticDistance(newYork, newYork), 0.0, eps); + UNIT_ASSERT_DOUBLES_EQUAL(GeodeticDistance(newYork, sydney), 15954603.669226252, eps); + + UNIT_ASSERT_DOUBLES_EQUAL(GeodeticDistance(sydney, minsk), 15110861.267782301, eps); + UNIT_ASSERT_DOUBLES_EQUAL(GeodeticDistance(sydney, moscow), 14467193.188083574, eps); + UNIT_ASSERT_DOUBLES_EQUAL(GeodeticDistance(sydney, newYork), 15954603.669226252, eps); + UNIT_ASSERT_DOUBLES_EQUAL(GeodeticDistance(sydney, sydney), 0.0, eps); + } +} diff --git a/library/cpp/geo/ut/polygon_ut.cpp b/library/cpp/geo/ut/polygon_ut.cpp new file mode 100644 index 0000000000..cd9dee9759 --- /dev/null +++ b/library/cpp/geo/ut/polygon_ut.cpp @@ -0,0 +1,34 @@ +#include "polygon.h" + +#include <library/cpp/testing/unittest/registar.h> + +using namespace NGeo; + +Y_UNIT_TEST_SUITE(TGeoPolygonTest) { + Y_UNIT_TEST(TestEmptyPolygon) { + TGeoPolygon empty; + UNIT_ASSERT(!empty); + UNIT_ASSERT(!empty.IsValid()); + } + + Y_UNIT_TEST(TestPolygon) { + TGeoPolygon polygon({{1., 2.}, {2., 1.}, {2., 4.}, {1., 3.}}); + UNIT_ASSERT(polygon.IsValid()); + UNIT_ASSERT_EQUAL(polygon.GetWindow(), + TGeoWindow(TGeoPoint(1., 1.), TGeoPoint(2., 4.))); + } + + Y_UNIT_TEST(TestParse) { + UNIT_ASSERT_EQUAL(TGeoPolygon::Parse(TString{"1.23,5.67 7.89,10.11 11.10,9.87"}), + NGeo::TGeoPolygon({{1.23, 5.67}, {7.89, 10.11}, {11.10, 9.87}})); + UNIT_ASSERT_EQUAL(TGeoPolygon::Parse(TString{"1.23,5.67 7.89,10.11 11.10,9.87 6.54,3.21"}), + NGeo::TGeoPolygon({{1.23, 5.67}, {7.89, 10.11}, {11.10, 9.87}, {6.54, 3.21}})); + + UNIT_ASSERT(TGeoPolygon::TryParse(TString{"1.23,5.67 7.89,10.11"}).Empty()); + UNIT_ASSERT_EQUAL(TGeoPolygon::Parse(TString{"1.23+5.67~7.89+10.11~11.10+9.87"}, "+", "~"), + NGeo::TGeoPolygon({{1.23, 5.67}, {7.89, 10.11}, {11.10, 9.87}})); + + UNIT_ASSERT_EQUAL(TGeoPolygon::Parse(TString{"1.23+5.67+~7.89+10.11+~11.10+9.87"}, "+", "+~"), + NGeo::TGeoPolygon({{1.23, 5.67}, {7.89, 10.11}, {11.10, 9.87}})); + } +} diff --git a/library/cpp/geo/ut/size_ut.cpp b/library/cpp/geo/ut/size_ut.cpp new file mode 100644 index 0000000000..41b4a2c257 --- /dev/null +++ b/library/cpp/geo/ut/size_ut.cpp @@ -0,0 +1,29 @@ +#include "size.h" + +#include <library/cpp/testing/unittest/registar.h> +#include <util/generic/maybe.h> + +using namespace NGeo; + +Y_UNIT_TEST_SUITE(TSizeTest) { + Y_UNIT_TEST(TestFromString) { + UNIT_ASSERT_EQUAL(TSize::Parse("0.15,0.67"), TSize(0.15, 0.67)); + UNIT_ASSERT_EQUAL(TSize::Parse("0.15 0.67", " "), TSize(0.15, 0.67)); + + UNIT_ASSERT_EXCEPTION(TSize::Parse(""), TBadCastException); + UNIT_ASSERT_EXCEPTION(TSize::Parse("Hello,world"), TBadCastException); + UNIT_ASSERT_EXCEPTION(TSize::Parse("-1,-1"), TBadCastException); + + UNIT_ASSERT_EQUAL(TSize::Parse("424242 50", " "), TSize(424242., 50.)); + UNIT_ASSERT_EQUAL(TSize::Parse("50.,424242"), TSize(50., 424242.)); + UNIT_ASSERT_EQUAL(TSize::Parse(" 0.01, 0.01"), TSize(0.01, 0.01)); + UNIT_ASSERT_EXCEPTION(TSize::Parse("0.01 ,0.01"), TBadCastException); + UNIT_ASSERT_EXCEPTION(TSize::Parse("0.01,0.01 "), TBadCastException); + } + + Y_UNIT_TEST(TestTryFromString) { + UNIT_ASSERT(TSize::TryParse("1,2")); + UNIT_ASSERT(!TSize::TryParse("-1,-2")); + UNIT_ASSERT(!TSize::TryParse("1,2a")); + } +} diff --git a/library/cpp/geo/ut/util_ut.cpp b/library/cpp/geo/ut/util_ut.cpp new file mode 100644 index 0000000000..ebd86cfbd8 --- /dev/null +++ b/library/cpp/geo/ut/util_ut.cpp @@ -0,0 +1,36 @@ +#include <library/cpp/geo/util.h> + +#include <library/cpp/testing/unittest/registar.h> + +using namespace NGeo; + +Y_UNIT_TEST_SUITE(TGeoUtilTest) { + Y_UNIT_TEST(TestPointFromString) { + UNIT_ASSERT_EQUAL(PairFromString("27.56,53.90"), (std::pair<double, double>(27.56, 53.90))); + UNIT_ASSERT_EQUAL(PairFromString("27.56 53.90", " "), (std::pair<double, double>(27.56, 53.90))); + UNIT_ASSERT_EQUAL(PairFromString("27.56@@53.90", "@@"), (std::pair<double, double>(27.56, 53.90))); + UNIT_ASSERT_EXCEPTION(PairFromString("27.56@@53.90", "@"), TBadCastException); + UNIT_ASSERT_EXCEPTION(PairFromString(""), TBadCastException); + } + + Y_UNIT_TEST(TestTryPointFromString) { + std::pair<double, double> point; + + UNIT_ASSERT(TryPairFromString(point, "27.56,53.90")); + UNIT_ASSERT_EQUAL(point, (std::pair<double, double>(27.56, 53.90))); + + UNIT_ASSERT(TryPairFromString(point, "27.56 53.90", " ")); + UNIT_ASSERT_EQUAL(point, (std::pair<double, double>(27.56, 53.90))); + + UNIT_ASSERT(TryPairFromString(point, "27.56@@53.90", "@@")); + UNIT_ASSERT_EQUAL(point, (std::pair<double, double>(27.56, 53.90))); + + UNIT_ASSERT(!TryPairFromString(point, "27.56@@53.90", "@")); + UNIT_ASSERT(!TryPairFromString(point, "")); + } + + Y_UNIT_TEST(TestVisibleMapBound) { + const double expectedLat = MercatorToLL(TMercatorPoint(0., LLToMercator(TGeoPoint(180., 0.)).X())).Lat(); + UNIT_ASSERT_DOUBLES_EQUAL(VISIBLE_LATITUDE_BOUND, expectedLat, 1.e-14); + } +} diff --git a/library/cpp/geo/ut/window_ut.cpp b/library/cpp/geo/ut/window_ut.cpp new file mode 100644 index 0000000000..194fb4e735 --- /dev/null +++ b/library/cpp/geo/ut/window_ut.cpp @@ -0,0 +1,547 @@ +#include "window.h" +#include <library/cpp/testing/unittest/registar.h> +#include <util/generic/ymath.h> + +using namespace NGeo; + +namespace { + constexpr double DEFAULT_EPS = 1.E-5; + + bool CheckGeoPointEqual(const TGeoPoint& found, const TGeoPoint& expected, const double eps = DEFAULT_EPS) { + if (std::isnan(found.Lon()) || std::isnan(found.Lat())) { + Cerr << "NaNs found: (" << found.Lon() << ", " << found.Lat() << ")" << Endl; + return false; + } + if (Abs(found.Lon() - expected.Lon()) > eps) { + Cerr << "longitude differs: " << found.Lon() << " found, " << expected.Lon() << " expected" << Endl; + return false; + } + if (Abs(found.Lat() - expected.Lat()) > eps) { + Cerr << "latitude differs: " << found.Lat() << " found, " << expected.Lat() << " expected" << Endl; + return false; + } + return true; + } + + bool CheckSizeEqual(const TSize& found, const TSize& expected, const double eps = DEFAULT_EPS) { + if (std::isnan(found.GetWidth()) || std::isnan(found.GetHeight())) { + Cerr << "NaNs found: (" << found.GetWidth() << ", " << found.GetHeight() << ")" << Endl; + return false; + } + if (Abs(found.GetWidth() - expected.GetWidth()) > eps) { + Cerr << "width differs: " << found.GetWidth() << " found, " << expected.GetWidth() << " expected" << Endl; + return false; + } + if (Abs(found.GetHeight() - expected.GetHeight()) > eps) { + Cerr << "height differs: " << found.GetHeight() << " found, " << expected.GetHeight() << " expected" << Endl; + return false; + } + return true; + } + + bool CheckGeoWindowEqual(const TGeoWindow& lhs, const TGeoWindow& rhs, const double eps = DEFAULT_EPS) { + return CheckGeoPointEqual(lhs.GetCenter(), rhs.GetCenter(), eps) && CheckSizeEqual(lhs.GetSize(), rhs.GetSize(), eps); + } +} // namespace + +/** + * TGeoWindow + */ +Y_UNIT_TEST_SUITE(TGeoWindowTest) { + Y_UNIT_TEST(TestParser) { + UNIT_ASSERT_EQUAL(TGeoWindow::ParseFromCornersPoints("1.23,5.67", "7.65,3.21"), + TGeoWindow(TGeoPoint(1.23, 3.21), TGeoPoint(7.65, 5.67))); + UNIT_ASSERT_EQUAL(TGeoWindow::ParseFromCornersPoints("1.23~5.67", "7.65~3.21", "~"), + TGeoWindow(TGeoPoint(1.23, 3.21), TGeoPoint(7.65, 5.67))); + UNIT_ASSERT_EXCEPTION(TGeoWindow::ParseFromCornersPoints("1.23~5.67", "7.65~3.21"), TBadCastException); + + UNIT_ASSERT(TGeoWindow::TryParseFromCornersPoints("1.23~5.67", "7.65~3.21").Empty()); + UNIT_ASSERT(TGeoWindow::TryParseFromCornersPoints("1.23,5.67", "7.65,3.21").Defined()); + UNIT_ASSERT_EQUAL(TGeoWindow::TryParseFromCornersPoints("1.23,5.67", "7.65,3.21").GetRef(), + TGeoWindow(TGeoPoint(1.23, 3.21), TGeoPoint(7.65, 5.67))); + UNIT_ASSERT(TGeoWindow::TryParseFromCornersPoints("1.23+++5.67+", "7.65+++3.21+", "+++").Empty()); + + UNIT_ASSERT_EQUAL(TGeoWindow::ParseFromLlAndSpn("1.23,5.67", "0.1,0.2"), + TGeoWindow(TGeoPoint(1.23, 5.67), TSize(0.1, 0.2))); + UNIT_ASSERT_EQUAL(TGeoWindow::ParseFromLlAndSpn("1.23~5.67", "0.1~0.2", "~"), + TGeoWindow(TGeoPoint(1.23, 5.67), TSize(0.1, 0.2))); + UNIT_ASSERT_EXCEPTION(TGeoWindow::ParseFromLlAndSpn("1.23~5.67", "0.1~0.2"), TBadCastException); + UNIT_ASSERT(TGeoWindow::TryParseFromLlAndSpn("1.23~5.67", "0.1~0.2").Empty()); + UNIT_ASSERT(TGeoWindow::TryParseFromLlAndSpn("1.23~5.67", "0.1~0.2", "~").Defined()); + UNIT_ASSERT_EQUAL(TGeoWindow::TryParseFromLlAndSpn("1.23~5.67", "0.1~0.2", "~").GetRef(), + TGeoWindow(TGeoPoint(1.23, 5.67), TSize(0.1, 0.2))); + } + + Y_UNIT_TEST(TestConstructor) { + TGeoPoint center{55.50, 82.50}; + TSize size{5.00, 3.00}; + TGeoWindow window(center, size); + + UNIT_ASSERT_EQUAL(window.GetCenter(), center); + UNIT_ASSERT_EQUAL(window.GetSize(), size); + } + + Y_UNIT_TEST(TestPoles) { + { + TGeoWindow northPole{TGeoPoint{180., 90.}, TSize{1.5, 1.5}}; + UNIT_ASSERT(CheckGeoPointEqual(northPole.GetCenter(), TGeoPoint{180., 90.})); + UNIT_ASSERT(CheckGeoPointEqual(northPole.GetLowerLeftCorner(), TGeoPoint{179.25, 88.5})); + UNIT_ASSERT(CheckGeoPointEqual(northPole.GetUpperRightCorner(), TGeoPoint{180.75, 90.0})); + } + { + TGeoWindow tallWindow{TGeoPoint{37., 55.}, TSize{10., 180.}}; + UNIT_ASSERT(CheckGeoPointEqual(tallWindow.GetCenter(), TGeoPoint{37., 55.})); + UNIT_ASSERT(CheckGeoPointEqual(tallWindow.GetLowerLeftCorner(), TGeoPoint{32., -90.})); + UNIT_ASSERT(CheckGeoPointEqual(tallWindow.GetUpperRightCorner(), TGeoPoint{42., 90.})); + } + { + TGeoWindow world{TGeoPoint{0., 0.}, TSize{360., 180.}}; + UNIT_ASSERT(CheckGeoPointEqual(world.GetCenter(), TGeoPoint{0., 0.})); + UNIT_ASSERT(CheckGeoPointEqual(world.GetLowerLeftCorner(), TGeoPoint{-180., -90.})); + UNIT_ASSERT(CheckGeoPointEqual(world.GetUpperRightCorner(), TGeoPoint{180., 90.})); + } + { + TGeoWindow world{TGeoPoint{0., 0.}, TSize{360., 360.}}; + UNIT_ASSERT(CheckGeoPointEqual(world.GetCenter(), TGeoPoint{0., 0.})); + UNIT_ASSERT(CheckGeoPointEqual(world.GetLowerLeftCorner(), TGeoPoint{-180., -90.})); + UNIT_ASSERT(CheckGeoPointEqual(world.GetUpperRightCorner(), TGeoPoint{180., 90.})); + } + } + + Y_UNIT_TEST(TestBigSize) { + { + TGeoWindow w{TGeoPoint{37., 55.}, TSize{100., 179.}}; + UNIT_ASSERT(CheckGeoPointEqual(w.GetCenter(), TGeoPoint{37., 55.})); + UNIT_ASSERT(CheckGeoPointEqual(w.GetLowerLeftCorner(), TGeoPoint{-13., -89.09540675})); + UNIT_ASSERT(CheckGeoPointEqual(w.GetUpperRightCorner(), TGeoPoint{87., 89.90907637})); + } + } + + Y_UNIT_TEST(TestCenterWhenInitWithCorners) { + UNIT_ASSERT(CheckGeoPointEqual(TGeoWindow(TGeoPoint{5.00, 40.00}, TGeoPoint{25.00, 80.00}).GetCenter(), TGeoPoint{15.00, 67.17797})); + UNIT_ASSERT(CheckGeoPointEqual(TGeoWindow(TGeoPoint{-5.00, -40.00}, TGeoPoint{-25.00, -80.00}).GetCenter(), TGeoPoint{-15.00, -67.17797})); + } + + Y_UNIT_TEST(TestCornersWhenInitWithCenter) { + // check lat calc + UNIT_ASSERT_DOUBLES_EQUAL(TGeoWindow(TGeoPoint{25.00, 50.00}, TSize{10.00, 10.00}).GetLowerLeftCorner().Lat(), 44.73927, DEFAULT_EPS); + + // lat equals to 90 + UNIT_ASSERT_DOUBLES_EQUAL(TGeoWindow(TGeoPoint{25.00, 50.00}, TSize{10.00, 179.99999}).GetUpperRightCorner().Lat(), 90, DEFAULT_EPS); + + // lat equals to -90 + UNIT_ASSERT_DOUBLES_EQUAL(TGeoWindow(TGeoPoint{25.00, -50.00}, TSize{10.00, -179.99999}).GetUpperRightCorner().Lat(), -90, DEFAULT_EPS); + + // check naive lon calc + UNIT_ASSERT_DOUBLES_EQUAL(TGeoWindow(TGeoPoint{10, 10}, TSize{10, 5}).GetLowerLeftCorner().Lon(), 5, DEFAULT_EPS); + + // check lon equals to 190 (no wrapping) + UNIT_ASSERT_DOUBLES_EQUAL(TGeoWindow(TGeoPoint{20, 0}, TSize{340, 5}).GetUpperRightCorner().Lon(), 190, DEFAULT_EPS); + + UNIT_ASSERT_DOUBLES_EQUAL(TGeoWindow(TGeoPoint{-40, 0}, TSize{-280, 5}).GetUpperRightCorner().Lon(), -180, DEFAULT_EPS); + + // naive calculating when point is (0, 0) + UNIT_ASSERT(CheckGeoPointEqual(TGeoWindow(TGeoPoint{0, 0}, TSize{160, 160}).GetLowerLeftCorner(), TGeoPoint{-80, -80}, DEFAULT_EPS)); + UNIT_ASSERT(CheckGeoPointEqual(TGeoWindow(TGeoPoint{0, 0}, TSize{160, 160}).GetUpperRightCorner(), TGeoPoint{80, 80}, DEFAULT_EPS)); + } + + Y_UNIT_TEST(TestCenterSetter) { + TGeoPoint center{27.56, 53.90}; + TGeoWindow window{}; + window.SetCenter(center); + UNIT_ASSERT_EQUAL(window.GetCenter(), center); + } + + Y_UNIT_TEST(TestEqualOperator) { + TGeoWindow window{TGeoPoint{27.56, 53.90}, TGeoPoint{30.35, 56.89}}; + UNIT_ASSERT(window == window); + + TGeoWindow anotherWindow{TGeoPoint{60.10, 57.90}, TGeoPoint{60.70, 58.25}}; + UNIT_ASSERT(!(window == anotherWindow)); + } + + Y_UNIT_TEST(TestAssignmentOperator) { + TGeoWindow lhs{TGeoPoint{27.56, 53.90}, TGeoPoint{30.35, 53.89}}; + TGeoWindow rhs{}; + rhs = lhs; + UNIT_ASSERT_EQUAL(lhs, rhs); + } + + Y_UNIT_TEST(TestContainsMethod) { + // you could see cases here https://tech.yandex.ru/maps/jsbox/2.1/rectangle + // (pay attention that the first coord is lat and the second one is lon) + TGeoWindow window{TGeoPoint{27.45, 53.82}, TGeoPoint{27.65, 53.97}}; + + // point is inside the window + UNIT_ASSERT(window.Contains(TGeoPoint{27.55, 53.90})); + + // point is to the right of the window + UNIT_ASSERT(!window.Contains(TGeoPoint{27.66, 53.95})); + + // point is to the left of the window + UNIT_ASSERT(!window.Contains(TGeoPoint{27.44, 53.95})); + + // point is under the window + UNIT_ASSERT(!window.Contains(TGeoPoint{27.50, 53.81})); + + // point is above the window + UNIT_ASSERT(!window.Contains(TGeoPoint{27.50, 53.98})); + + // point is on border + UNIT_ASSERT(window.Contains(TGeoPoint{27.45, 53.86})); + UNIT_ASSERT(window.Contains(TGeoPoint{27.65, 53.86})); + UNIT_ASSERT(window.Contains(TGeoPoint{27.55, 53.82})); + UNIT_ASSERT(window.Contains(TGeoPoint{27.55, 53.97})); + + // negate coord + UNIT_ASSERT(TGeoWindow(TGeoPoint{-72.17, -38.82}, TGeoPoint{-68.95, -36.70}).Contains(TGeoPoint{-70.40, -37.75})); + + // special cases + UNIT_ASSERT(!TGeoWindow{}.Contains(TGeoPoint{60.09, 57.90})); + + UNIT_ASSERT(TGeoWindow(TGeoPoint{}, TGeoPoint{27.55, 53.90}).Contains(TGeoPoint{27.55, 53.90})); + UNIT_ASSERT(TGeoWindow(TGeoPoint{27.55, 53.90}, TGeoPoint{}).Contains(TGeoPoint{27.55, 53.90})); + } + + Y_UNIT_TEST(TestIntersectsMethod) { + // intersect only by lat + UNIT_ASSERT( + !Intersects( + TGeoWindow{TGeoPoint{27.60, 53.90}, TGeoPoint{27.80, 53.95}}, + TGeoWindow{TGeoPoint{27.30, 53.88}, TGeoPoint{27.50, 53.98}})); + + // intersect only by lon + UNIT_ASSERT( + !Intersects( + TGeoWindow{TGeoPoint{27.35, 54}, TGeoPoint{27.45, 54.10}}, + TGeoWindow{TGeoPoint{27.30, 53.88}, TGeoPoint{27.50, 53.98}})); + + // one inside another + UNIT_ASSERT( + Intersects( + TGeoWindow{TGeoPoint{27.35, 53.90}, TGeoPoint{27.45, 53.95}}, + TGeoWindow{TGeoPoint{27.30, 53.88}, TGeoPoint{27.50, 53.98}})); + + // intersection is point + UNIT_ASSERT( + !Intersects( + TGeoWindow{TGeoPoint{27.50, 53.98}, TGeoPoint{27.70, 54.00}}, + TGeoWindow{TGeoPoint{27.30, 53.88}, TGeoPoint{27.50, 53.98}})); + + // intersection is segment + UNIT_ASSERT( + !Intersects( + TGeoWindow{TGeoPoint{27.40, 53.98}, TGeoPoint{27.70, 54.00}}, + TGeoWindow{TGeoPoint{27.30, 53.88}, TGeoPoint{27.50, 53.98}})); + + // intersection is area + UNIT_ASSERT( + Intersects( + TGeoWindow{TGeoPoint{27.40, 53.90}, TGeoPoint{27.70, 54.00}}, + TGeoWindow{TGeoPoint{27.30, 53.88}, TGeoPoint{27.50, 53.98}})); + + // equal windows + TGeoWindow window{TGeoPoint{27.60, 53.88}, TGeoPoint{27.80, 53.98}}; + UNIT_ASSERT(Intersects(window, window)); + } + + Y_UNIT_TEST(TestIntersectionMethod) { + // non-intersecting window + UNIT_ASSERT( + !(Intersection( + TGeoWindow{TGeoPoint{37.66, 55.66}, TGeoPoint{37.53, 55.64}}, + TGeoWindow{TGeoPoint{37.67, 55.66}, TGeoPoint{37.69, 55.71}}))); + + // one inside another + UNIT_ASSERT(CheckGeoWindowEqual( + Intersection( + TGeoWindow{TGeoPoint{37.00, 55.00}, TSize{10.00, 10.00}}, + TGeoWindow{TGeoPoint{37.00, 55.00}, TSize{2.00, 2.00}}) + .GetRef(), + (TGeoWindow{TGeoPoint{37.00, 55.00}, TSize{2.00, 2.00}}))); + + // cross + UNIT_ASSERT(CheckGeoWindowEqual( + Intersection( + TGeoWindow{TGeoPoint{37.00, 55.00}, TSize{10.00, 2.00}}, + TGeoWindow{TGeoPoint{37.00, 55.00}, TSize{2.00, 10.00}}) + .GetRef(), + (TGeoWindow{TGeoPoint{37.00, 55.00}, TSize{2.00, 2.00}}))); + + // intersection is a point + UNIT_ASSERT(CheckGeoWindowEqual( + Intersection( + TGeoWindow{TGeoPoint{27.50, 53.98}, TGeoPoint{27.70, 54.00}}, + TGeoWindow{TGeoPoint{27.30, 53.88}, TGeoPoint{27.50, 53.98}}) + .GetRef(), + (TGeoWindow{TGeoPoint{27.50, 53.98}, TSize{0, 0}}))); + + // intersection is a segment + UNIT_ASSERT(CheckGeoWindowEqual( + Intersection( + TGeoWindow{TGeoPoint{27.40, 53.98}, TGeoPoint{27.70, 54.00}}, + TGeoWindow{TGeoPoint{27.30, 53.88}, TGeoPoint{27.50, 53.98}}) + .GetRef(), + (TGeoWindow{TGeoPoint{27.45, 53.98}, TSize{0.10, 0}}))); + + // intersection is area + UNIT_ASSERT(CheckGeoWindowEqual( + Intersection( + TGeoWindow{TGeoPoint{27.40, 53.90}, TGeoPoint{27.70, 54.00}}, + TGeoWindow{TGeoPoint{27.30, 53.88}, TGeoPoint{27.50, 53.98}}) + .GetRef(), + (TGeoWindow{TGeoPoint{27.40, 53.90}, TGeoPoint{27.50, 53.98}}))); + + // special cases + UNIT_ASSERT( + !(Intersection( + TGeoWindow{TGeoPoint{27.30, 53.88}, TGeoPoint{27.50, 53.98}}, + TGeoWindow{}))); + } + + Y_UNIT_TEST(TestDistanceMethod) { + // one window inside another + UNIT_ASSERT_DOUBLES_EQUAL( + (TGeoWindow{TGeoPoint{27.50, 53.98}, TGeoPoint{27.80, 54.10}}) + .Distance(TGeoWindow{TGeoPoint{27.55, 54.00}, TGeoPoint{27.70, 54.07}}), + 0, + 1.E-5); + + // gap only by lon + UNIT_ASSERT_DOUBLES_EQUAL( + (TGeoWindow{TGeoPoint{27.50, 53.98}, TGeoPoint{27.60, 54.10}}) + .Distance(TGeoWindow{TGeoPoint{27.69, 54.10}, TGeoPoint{27.90, 54.20}}), + 0.052773, + 1.E-5); + + // gap only by lat + UNIT_ASSERT_DOUBLES_EQUAL( + (TGeoWindow{TGeoPoint{27.50, 53.98}, TGeoPoint{27.60, 54.10}}) + .Distance(TGeoWindow{TGeoPoint{27.50, 54.20}, TGeoPoint{27.70, 54.30}}), + 0.1, + 1.E-5); + + // gap by lot and lat, you can calculate answer using two previous tests + UNIT_ASSERT_DOUBLES_EQUAL( + (TGeoWindow{TGeoPoint{27.50, 53.98}, TGeoPoint{27.60, 54.10}} + .Distance(TGeoWindow{TGeoPoint{27.69, 54.20}, TGeoPoint{27.70, 54.30}})), + 0.11304, + 1.E-5); + + // negate coord + UNIT_ASSERT_DOUBLES_EQUAL( + (TGeoWindow{TGeoPoint{-27.50, -53.98}, TGeoPoint{-27.60, -54.10}} + .Distance(TGeoWindow{TGeoPoint{-27.69, -54.20}, TGeoPoint{-27.70, -54.30}})), + 0.11304, + 1.E-5); + } + + Y_UNIT_TEST(TestApproxDistanceMethod) { + // point inside + UNIT_ASSERT_DOUBLES_EQUAL( + (TGeoWindow{TGeoPoint{27.50, 53.98}, TGeoPoint{27.80, 54.10}}) + .GetApproxDistance(TGeoPoint{27.60, 54.05}), + 0, + 1.E-5); + + // gap only by lon + UNIT_ASSERT_DOUBLES_EQUAL( + (TGeoWindow{TGeoPoint{27.50, 54.00}, TGeoPoint{27.60, 54.10}}) + .GetApproxDistance(TGeoPoint{27.70, 54.05}), + 6535.3, + 0.1); + + // gap only by lat + UNIT_ASSERT_DOUBLES_EQUAL( + (TGeoWindow{TGeoPoint{27.50, 54.00}, TGeoPoint{27.60, 54.10}}) + .GetApproxDistance(TGeoPoint{27.55, 53.95}), + 5566.0, + 0.1); + + // gap by lot and lat + UNIT_ASSERT_DOUBLES_EQUAL( + (TGeoWindow{TGeoPoint{27.50, 54.00}, TGeoPoint{27.60, 54.10}}) + .GetApproxDistance(TGeoPoint{27.70, 54.20}), + 12900.6, + 0.1); + + // negate coord + UNIT_ASSERT_DOUBLES_EQUAL( + (TGeoWindow{TGeoPoint{-27.50, -54.00}, TGeoPoint{-27.60, -54.10}}) + .GetApproxDistance(TGeoPoint{-27.70, -54.20}), + 12900.6, + 0.1); + } + + Y_UNIT_TEST(TestUnionMethod) { + // one inside another + UNIT_ASSERT(CheckGeoWindowEqual( + Union( + TGeoWindow{TGeoPoint{37.00, 55.00}, TSize{2.00, 3.00}}, + TGeoWindow{TGeoPoint{37.10, 55.20}, TSize{1.50, 1.00}}), + TGeoWindow(TGeoPoint{37.00, 55.00}, TSize{2.00, 3.00}))); + + // non-intersecting windows + UNIT_ASSERT(CheckGeoWindowEqual( + Union( + TGeoWindow{TGeoPoint{37.00, 55.00}, TGeoPoint{37.10, 55.10}}, + TGeoWindow{TGeoPoint{37.20, 55.20}, TGeoPoint{37.30, 55.30}}), + TGeoWindow(TGeoPoint{37.00, 55.00}, TGeoPoint{37.30, 55.30}))); + + // negate coords, one inside another + UNIT_ASSERT(CheckGeoWindowEqual( + Union( + TGeoWindow{TGeoPoint{-57.62, -20.64}, TSize{2.00, 4.00}}, + TGeoWindow{TGeoPoint{-57.62, -20.64}, TSize{12.00, 10.00}}), + TGeoWindow(TGeoPoint{-57.62, -20.64}, TSize{12.00, 10.00}), 1.E-2)); + + // cross + UNIT_ASSERT(CheckGeoWindowEqual( + Union( + TGeoWindow{TGeoPoint{-3.82, 5.52}, TGeoPoint{0.10, 6.50}}, + TGeoWindow{TGeoPoint{-1.5, 4.20}, TGeoPoint{-0.5, 7.13}}), + TGeoWindow(TGeoPoint{-3.82, 4.20}, TGeoPoint{0.10, 7.13}))); + + // special cases + UNIT_ASSERT(CheckGeoWindowEqual( + Union( + TGeoWindow{TGeoPoint{-3.82, 5.52}, TGeoPoint{0.10, 6.50}}, + TGeoWindow{}), + TGeoWindow(TGeoPoint{-3.82, 5.52}, TGeoPoint{361., 181.}))); + + UNIT_ASSERT(CheckGeoWindowEqual( + Union( + TGeoWindow{}, + TGeoWindow{TGeoPoint{-3.82, 5.52}, TGeoPoint{0.10, 6.50}}), + TGeoWindow(TGeoPoint{-3.82, 5.52}, TGeoPoint{361., 181.}))); + } + + Y_UNIT_TEST(TestStretchMethod) { + TSize size{0.5, 1}; + TGeoPoint center{27.40, 53.90}; + TGeoWindow window{}; + double multiplier = 0; + + // multiplier is less than 1. + window = {center, size}; + multiplier = 0.5; + + UNIT_ASSERT(CheckGeoPointEqual(window.GetLowerLeftCorner(), TGeoPoint{27.14999, 53.39699})); + UNIT_ASSERT(CheckGeoPointEqual(window.GetUpperRightCorner(), TGeoPoint{27.65000, 54.39699})); + + window.Stretch(multiplier); + UNIT_ASSERT(CheckGeoWindowEqual(window, TGeoWindow{center, TSize{0.25, 0.5}})); + UNIT_ASSERT(CheckGeoPointEqual(window.GetLowerLeftCorner(), TGeoPoint{27.27499, 53.64925})); + UNIT_ASSERT(CheckGeoPointEqual(window.GetUpperRightCorner(), TGeoPoint{27.52500, 54.14924})); + + // multiplier is greater than 1. + window = {center, size}; + multiplier = 2.2; + + window.Stretch(multiplier); + UNIT_ASSERT(CheckGeoWindowEqual(window, TGeoWindow{center, TSize{1.1, 2.2}})); + UNIT_ASSERT(CheckGeoPointEqual(window.GetLowerLeftCorner(), TGeoPoint{26.84999, 52.78545})); + UNIT_ASSERT(CheckGeoPointEqual(window.GetUpperRightCorner(), TGeoPoint{27.95000, 54.98545})); + + // invalid multiplier + window = {center, size}; + multiplier = 100.; + + window.Stretch(multiplier); + UNIT_ASSERT(CheckGeoWindowEqual(window, TGeoWindow{center, TSize{50, 100}})); + UNIT_ASSERT(CheckGeoPointEqual(window.GetLowerLeftCorner(), TGeoPoint{2.40000, -18.88352})); + UNIT_ASSERT(CheckGeoPointEqual(window.GetUpperRightCorner(), TGeoPoint{52.39999, 81.26212})); + + // invalid multiplier + window = {center, size}; + multiplier = 0; + + window.Stretch(multiplier); + UNIT_ASSERT(CheckGeoWindowEqual(window, TGeoWindow{center, TSize{0, 0}})); + UNIT_ASSERT(CheckGeoPointEqual(window.GetLowerLeftCorner(), TGeoPoint{27.39999, 53.90000})); + UNIT_ASSERT(CheckGeoPointEqual(window.GetUpperRightCorner(), TGeoPoint{27.39999, 53.90000})); + + // invalid multiplier + window = {center, size}; + multiplier = -5.; + + window.Stretch(multiplier); + UNIT_ASSERT(CheckGeoWindowEqual(window, TGeoWindow{center, TSize{-2.5, -5}})); + UNIT_ASSERT(CheckGeoPointEqual(window.GetLowerLeftCorner(), TGeoPoint{28.64999, 56.32495})); + UNIT_ASSERT(CheckGeoPointEqual(window.GetUpperRightCorner(), TGeoPoint{26.15000, 51.32491})); + } +} + +/** + * TMercatorWindow + */ +Y_UNIT_TEST_SUITE(TMercatorWindowTest) { + Y_UNIT_TEST(TestConstructor) { + // init with two corners + TMercatorPoint lowerLeft{5, 3}; + TMercatorPoint upperRight{10, 20}; + TMercatorWindow window{lowerLeft, upperRight}; + + UNIT_ASSERT_EQUAL(window.GetWidth(), 5.); + UNIT_ASSERT_EQUAL(window.GetHeight(), 17.); + UNIT_ASSERT_EQUAL(window.GetCenter(), (TMercatorPoint{7.5, 11.5})); + + TMercatorPoint center{8, 12}; + TSize size{5, 17}; + window = {center, size}; + UNIT_ASSERT_EQUAL(window.GetUpperRightCorner().X(), 10.5); + UNIT_ASSERT_EQUAL(window.GetUpperRightCorner().Y(), 20.5); + UNIT_ASSERT_EQUAL(window.GetLowerLeftCorner().X(), 5.5); + UNIT_ASSERT_EQUAL(window.GetLowerLeftCorner().Y(), 3.5); + } + + Y_UNIT_TEST(TestInflateMethod) { + TSize size{200, 500}; + TMercatorPoint center{441, 688}; + TMercatorWindow window{}; + int add = 10; + + window = {center, size}; + UNIT_ASSERT_EQUAL(window.GetLowerLeftCorner(), TMercatorPoint(341, 438)); + UNIT_ASSERT_EQUAL(window.GetUpperRightCorner(), TMercatorPoint(541, 938)); + window.Inflate(add); + UNIT_ASSERT_EQUAL(window, TMercatorWindow(center, TSize{220, 520})); + UNIT_ASSERT_EQUAL(window.GetLowerLeftCorner(), TMercatorPoint(331, 428)); + UNIT_ASSERT_EQUAL(window.GetUpperRightCorner(), TMercatorPoint(551, 948)); + + // negate coords + center = {-441, -688}; + window = {center, size}; + UNIT_ASSERT_EQUAL(window.GetLowerLeftCorner(), TMercatorPoint(-541, -938)); + UNIT_ASSERT_EQUAL(window.GetUpperRightCorner(), TMercatorPoint(-341, -438)); + window.Inflate(add); + UNIT_ASSERT_EQUAL(window, TMercatorWindow(center, TSize{220, 520})); + UNIT_ASSERT_EQUAL(window.GetLowerLeftCorner(), TMercatorPoint(-551, -948)); + UNIT_ASSERT_EQUAL(window.GetUpperRightCorner(), TMercatorPoint(-331, -428)); + + // size becomes negate + size = {6, 12}; + center = {0, 0}; + window = {center, size}; + UNIT_ASSERT_EQUAL(window.GetLowerLeftCorner(), TMercatorPoint(-3, -6)); + UNIT_ASSERT_EQUAL(window.GetUpperRightCorner(), TMercatorPoint(3, 6)); + + add = -20; + window.Inflate(add); + UNIT_ASSERT_EQUAL(window, TMercatorWindow(center, TSize{-34, -28})); + UNIT_ASSERT_EQUAL(window.GetLowerLeftCorner(), TMercatorPoint(17, 14)); + UNIT_ASSERT_EQUAL(window.GetUpperRightCorner(), TMercatorPoint(-17, -14)); + UNIT_ASSERT_EQUAL(window.GetSize(), TSize(-34, -28)); + + // big add param + size = {10, 15}; + center = {5, 10}; + window = {center, size}; + + add = static_cast<int>(1E5); + window.Inflate(add); + UNIT_ASSERT_EQUAL(window, TMercatorWindow(center, TSize{200'010, 200'015})); + UNIT_ASSERT_EQUAL(window.GetLowerLeftCorner(), TMercatorPoint(-100'000, -99'997.5)); + UNIT_ASSERT_EQUAL(window.GetUpperRightCorner(), TMercatorPoint(100'010, 100'017.5)); + } +} diff --git a/library/cpp/geo/ut/ya.make b/library/cpp/geo/ut/ya.make new file mode 100644 index 0000000000..5bd891db1f --- /dev/null +++ b/library/cpp/geo/ut/ya.make @@ -0,0 +1,12 @@ +UNITTEST_FOR(library/cpp/geo) + +SRCS( + load_save_helper_ut.cpp + polygon_ut.cpp + point_ut.cpp + size_ut.cpp + util_ut.cpp + window_ut.cpp +) + +END() diff --git a/library/cpp/geo/util.cpp b/library/cpp/geo/util.cpp new file mode 100644 index 0000000000..e8d0fc378e --- /dev/null +++ b/library/cpp/geo/util.cpp @@ -0,0 +1,34 @@ +#include "util.h" + +#include <math.h> +#include <util/generic/cast.h> +#include <util/generic/string.h> +#include <util/string/cast.h> +#include <utility> + +namespace NGeo { + bool TryPairFromString(std::pair<double, double>& res, TStringBuf inputStr, TStringBuf delimiter) { + TStringBuf lhsStr; + TStringBuf rhsStr; + + double lhs = NAN; + double rhs = NAN; + if ( + !inputStr.TrySplit(delimiter, lhsStr, rhsStr) || + !TryFromString<double>(lhsStr, lhs) || + !TryFromString<double>(rhsStr, rhs)) { + return false; + } + + res = {lhs, rhs}; + return true; + } + + std::pair<double, double> PairFromString(TStringBuf inputStr, TStringBuf delimiter) { + std::pair<double, double> res; + if (!TryPairFromString(res, inputStr, delimiter)) { + ythrow TBadCastException() << "Wrong point string: " << inputStr; + } + return res; + } +} // namespace NGeo diff --git a/library/cpp/geo/util.h b/library/cpp/geo/util.h new file mode 100644 index 0000000000..18b411e6a4 --- /dev/null +++ b/library/cpp/geo/util.h @@ -0,0 +1,107 @@ +#pragma once + +#include "point.h" +#include "size.h" +#include "window.h" + +#include <util/generic/ymath.h> + +namespace NGeo { + constexpr double MIN_LATITUDE = -90.; + constexpr double MAX_LATITUDE = +90.; + constexpr double MIN_LONGITUDE = -180.; + constexpr double MAX_LONGITUDE = +180.; + constexpr double WORLD_WIDTH = MAX_LONGITUDE - MIN_LONGITUDE; + constexpr double WORLD_HEIGHT = MAX_LATITUDE - MIN_LATITUDE; + + // The Mercator projection is truncated at certain latitude so that the visible world forms a square. The poles are not shown. + constexpr double VISIBLE_LATITUDE_BOUND = 85.084059050109785; + + inline double Deg2rad(double d) { + return d * PI / 180; + } + + inline double Rad2deg(double d) { + return d * 180 / PI; + } + + inline double GetLongitudeFromMetersAtEquator(double meters) { + return Rad2deg(meters * (1. / WGS84::R)); + } + + inline double GetMetersFromDeg(double angle) { + return Deg2rad(angle) * NGeo::WGS84::R; + } + + inline double GetLatCos(double latDegree) { + return cos(Deg2rad(latDegree)); + } + + /** + * Get Inversed cosinus of latitude + * It is more precise, than division of two big doubles + * It is safe for lattitue at 90 degrees + */ + inline double GetInversedLatCosSafe(double latDegree) { + return 1. / Max(0.001, cos(Deg2rad(latDegree))); + } + + /** + * Gets Lontitude width for given width at equator and latitude + */ + inline double GetWidthAtLatitude(double widthEquator, double latDegree) { + return widthEquator * GetInversedLatCosSafe(latDegree); + } + + inline double GetWidthAtLatitude(double widthEquator, const TGeoPoint& p) { + return GetWidthAtLatitude(widthEquator, p.Lat()); + } + + /* + * Returns Normalised width at equator for specified width at latitude and latitude + */ + + inline double GetWidthAtEquator(double widthAtLatitude, double latDegree) { + return widthAtLatitude * GetLatCos(latDegree); + } + + inline double GetWidthAtEquator(double widthAtLatitude, const TGeoPoint& p) { + return GetWidthAtEquator(widthAtLatitude, p.Lat()); + } + + /* + * Same for size + */ + + inline TSize GetSizeAtLatitude(const TSize& sizeAtEquator, const TGeoPoint& at) { + return TSize(GetWidthAtLatitude(sizeAtEquator.GetWidth(), at), sizeAtEquator.GetHeight()); + } + + inline TSize GetSizeAtEquator(const TSize& sizeAtLatitude, const TGeoPoint& at) { + return TSize(GetWidthAtEquator(sizeAtLatitude.GetWidth(), at), sizeAtLatitude.GetHeight()); + } + + inline TGeoWindow ConstructWindowFromEquatorSize(const TGeoPoint& center, const TSize& sizeAtEquator) { + return TGeoWindow(center, GetSizeAtLatitude(sizeAtEquator, center)); + } + + inline double SquaredDiagonal(const NGeo::TSize& size, double latitude) { + return Sqr(NGeo::GetWidthAtEquator(size.GetWidth(), latitude)) + Sqr(size.GetHeight()); + } + + inline double Diagonal(const NGeo::TSize& size, double latitude) { + return sqrt(SquaredDiagonal(size, latitude)); + } + + /** + * try to parse two coords from string + * return pair of coords on success, otherwise throw exception + */ + std::pair<double, double> PairFromString(TStringBuf inputStr, TStringBuf delimiter = TStringBuf(",")); + + /** + * try to parse two coords from string + * write result to first param and return true on success, otherwise return false + */ + bool TryPairFromString(std::pair<double, double>& res, TStringBuf inputStr, TStringBuf delimiter = TStringBuf(",")); +} // namespace NGeo diff --git a/library/cpp/geo/window.cpp b/library/cpp/geo/window.cpp new file mode 100644 index 0000000000..2ad2b61b71 --- /dev/null +++ b/library/cpp/geo/window.cpp @@ -0,0 +1,297 @@ +#include "window.h" + +#include "util.h" + +#include <util/generic/ylimits.h> +#include <util/generic/ymath.h> +#include <util/generic/maybe.h> + +#include <cstdlib> +#include <utility> + +namespace NGeo { + namespace { + TMercatorPoint GetMiddlePoint(const TMercatorPoint& p1, const TMercatorPoint& p2) { + return TMercatorPoint{(p1.X() + p2.X()) / 2, (p1.Y() + p2.Y()) / 2}; + } + + struct TLatBounds { + double LatMin; + double LatMax; + }; + } // namespace + + bool TrySpan2LatitudeDegenerateCases(double ll, double lspan, TLatBounds& result) { + // TODO(sobols@): Compare with eps? + if (Y_UNLIKELY(lspan >= 180.)) { + result.LatMin = -90.; + result.LatMax = +90.; + return true; + } + if (Y_UNLIKELY(ll == +90.)) { + result.LatMin = ll - lspan; + result.LatMax = ll; + return true; + } + if (Y_UNLIKELY(ll == -90.)) { + result.LatMin = ll; + result.LatMax = ll + lspan; + return true; + } + return false; + } + + /** + * Finds such latitudes lmin, lmax that: + * 1) lmin <= ll <= lmax, + * 2) lmax - lmin == lspan, + * 3) MercatorY(ll) - MercatorY(lmin) == MercatorY(lmax) - MercatorY(ll) + * (the ll parallel is a center between lmin and lmax parallels in Mercator projection) + * + * \returns a pair (lmin, lmax) + */ + TLatBounds Span2Latitude(double ll, double lspan) { + TLatBounds result{}; + if (TrySpan2LatitudeDegenerateCases(ll, lspan, result)) { + return result; + } + + const double lc = Deg2rad(ll); + const double h = Deg2rad(lspan); + + // Spherical (Pseudo) Mercator: + // MercatorY(lc) = R * ln(tan(lc / 2 + PI / 4)). + // Note that + // ln(a) - ln(b) = ln(a / b) + // That'a why + // MercatorY(lc) - MercatorY(lmin) == MercatorY(lmin + h) - MercatorY(lc) <=> + // <=> tan(lc / 2 + PI / 4) / tan(lmin / 2 + PI / 4) == + // == tan(lmin / 2 + h / 2 + PI / 4) / tan(lc / 2 + PI / 4). + // Also note that + // tan(x + y) == (tan(x) + tan(y)) / (1 - tan(x) * tan(y)), + // so + // tan(lmin / 2 + h / 2 + PI / 4) == + // == (tan(lmin / 2 + PI / 4) + tan(h / 2)) / (1 - tan(lmin / 2 + PI / 4) * tan(h / 2)) + + const double yx = tan(lc / 2 + PI / 4); + + // Let x be tan(lmin / 2 + PI / 4), + // then + // yx / x == (x + tan(h / 2)) / ((1 - x * tan(h / 2)) * yx), + // or + // yx^2 * (1 - x * tan(h / 2)) == (x + tan(h / 2)) * x. + // Now we solve a quadratic equation: + // x^2 + bx + c == 0 + + const double C = yx * yx; + + const double b = (C + 1) * tan(h / 2), c = -C; + const double D = b * b - 4 * c; + const double root = (-b + sqrt(D)) / 2; + + result.LatMin = Rad2deg((atan(root) - PI / 4) * 2); + result.LatMax = result.LatMin + lspan; + return result; + } + + void TGeoWindow::CalcCorners() { + if (!IsValid()) { + return; + } + const TLatBounds latBounds = Span2Latitude(Center_.Lat(), Size_.GetHeight()); + + if (-90. < latBounds.LatMin && latBounds.LatMax < +90.) { + TMercatorPoint lowerLeftCornerM = LLToMercator(TGeoPoint(Center_.Lon() - (Size_.GetWidth() / 2), latBounds.LatMin)); + TMercatorPoint upperRightCornerM = LLToMercator(TGeoPoint(Center_.Lon() + (Size_.GetWidth() / 2), latBounds.LatMax)); + TMercatorPoint centerM = LLToMercator(Center_); + + double w = upperRightCornerM.X() - lowerLeftCornerM.X(); + double h = upperRightCornerM.Y() - lowerLeftCornerM.Y(); + + LowerLeftCorner_ = MercatorToLL(TMercatorPoint(centerM.X() - w / 2, centerM.Y() - h / 2)); + UpperRightCorner_ = MercatorToLL(TMercatorPoint(centerM.X() + w / 2, centerM.Y() + h / 2)); + } else { + LowerLeftCorner_ = TGeoPoint(Center_.Lon() - (Size_.GetWidth() / 2), latBounds.LatMin); + UpperRightCorner_ = TGeoPoint(Center_.Lon() + (Size_.GetWidth() / 2), latBounds.LatMax); + } + } + + void TGeoWindow::CalcCenterAndSpan() { + if (!LowerLeftCorner_ || !UpperRightCorner_) { + return; + } + + TMercatorPoint lower = LLToMercator(LowerLeftCorner_); + TMercatorPoint upper = LLToMercator(UpperRightCorner_); + TMercatorPoint center = GetMiddlePoint(lower, upper); + Center_ = MercatorToLL(center); + + Size_ = TSize(UpperRightCorner_.Lon() - LowerLeftCorner_.Lon(), + UpperRightCorner_.Lat() - LowerLeftCorner_.Lat()); + } + + bool TGeoWindow::Contains(const TGeoPoint& p) const { + return LowerLeftCorner_.Lon() <= p.Lon() && p.Lon() <= UpperRightCorner_.Lon() && + LowerLeftCorner_.Lat() <= p.Lat() && p.Lat() <= UpperRightCorner_.Lat(); + } + + double TGeoWindow::Diameter() const { + return Diagonal(Size_, Center_.Lat()); + } + + double TGeoWindow::Distance(const TGeoWindow& w) const { + const double minX = Max(GetLowerLeftCorner().Lon(), w.GetLowerLeftCorner().Lon()); + const double maxX = Min(GetUpperRightCorner().Lon(), w.GetUpperRightCorner().Lon()); + const double minY = Max(GetLowerLeftCorner().Lat(), w.GetLowerLeftCorner().Lat()); + const double maxY = Min(GetUpperRightCorner().Lat(), w.GetUpperRightCorner().Lat()); + double xGap = minX > maxX ? (minX - maxX) : 0.; + double yGap = minY > maxY ? (minY - maxY) : 0.; + return sqrtf(Sqr(xGap * cos((minY + maxY) * 0.5 * PI / 180)) + Sqr(yGap)); + } + + double TWindowLL::GetApproxDistance(const TPointLL& point) const { + const double metresInDegree = WGS84::R * PI / 180; + return Distance(TWindowLL{point, point}) * metresInDegree; + } + + TGeoWindow TGeoWindow::ParseFromCornersPoints(TStringBuf leftCornerStr, TStringBuf rightCornerStr, TStringBuf delimiter) { + auto leftCorner = TGeoPoint::Parse(leftCornerStr, delimiter); + auto rightCorner = TGeoPoint::Parse(rightCornerStr, delimiter); + + return {leftCorner, rightCorner}; + } + + TMaybe<TGeoWindow> TGeoWindow::TryParseFromCornersPoints(TStringBuf leftCornerStr, TStringBuf rightCornerStr, TStringBuf delimiter) { + auto leftCorner = TGeoPoint::TryParse(leftCornerStr, delimiter); + auto rightCorner = TGeoPoint::TryParse(rightCornerStr, delimiter); + if (!leftCorner || !rightCorner) { + return {}; + } + + return TGeoWindow{*leftCorner, *rightCorner}; + } + + TGeoWindow TGeoWindow::ParseFromLlAndSpn(TStringBuf llStr, TStringBuf spnStr, TStringBuf delimiter) { + TGeoPoint ll = TGeoPoint::Parse(llStr, delimiter); + TSize spn = TSize::Parse(spnStr, delimiter); + + return {ll, spn}; + } + + TMaybe<TGeoWindow> TGeoWindow::TryParseFromLlAndSpn(TStringBuf llStr, TStringBuf spnStr, TStringBuf delimiter) { + auto ll = TGeoPoint::TryParse(llStr, delimiter); + auto spn = TSize::TryParse(spnStr, delimiter); + + if (!ll || !spn) { + return {}; + } + + return TGeoWindow{*ll, *spn}; + } + /** + * TMercatorWindow + */ + + TMercatorWindow::TMercatorWindow() noexcept + : HalfWidth_{std::numeric_limits<double>::quiet_NaN()} + , HalfHeight_{std::numeric_limits<double>::quiet_NaN()} + { + } + + TMercatorWindow::TMercatorWindow(const TMercatorPoint& center, const TSize& size) noexcept + : Center_{center} + , HalfWidth_{size.GetWidth() / 2} + , HalfHeight_{size.GetHeight() / 2} + { + } + + TMercatorWindow::TMercatorWindow(const TMercatorPoint& firstPoint, const TMercatorPoint& secondPoint) noexcept + : Center_{GetMiddlePoint(firstPoint, secondPoint)} + , HalfWidth_{Abs(secondPoint.X() - firstPoint.X()) / 2} + , HalfHeight_{Abs(secondPoint.Y() - firstPoint.Y()) / 2} + { + } + + bool TMercatorWindow::Contains(const TMercatorPoint& pt) const noexcept { + return (Center_.X() - HalfWidth_ <= pt.X()) && + (pt.X() <= Center_.X() + HalfWidth_) && + (Center_.Y() - HalfHeight_ <= pt.Y()) && + (pt.Y() <= Center_.Y() + HalfHeight_); + } + + /** + * Conversion + */ + + TMercatorWindow LLToMercator(const TGeoWindow& window) { + return TMercatorWindow{LLToMercator(window.GetLowerLeftCorner()), LLToMercator(window.GetUpperRightCorner())}; + } + + TGeoWindow MercatorToLL(const TMercatorWindow& window) { + return TGeoWindow{MercatorToLL(window.GetLowerLeftCorner()), MercatorToLL(window.GetUpperRightCorner())}; + } + + /** + * Operators + */ + + TMaybe<TGeoWindow> Intersection(const TGeoWindow& lhs, const TGeoWindow& rhs) { + const double minX = Max(lhs.GetLowerLeftCorner().Lon(), rhs.GetLowerLeftCorner().Lon()); + const double maxX = Min(lhs.GetUpperRightCorner().Lon(), rhs.GetUpperRightCorner().Lon()); + const double minY = Max(lhs.GetLowerLeftCorner().Lat(), rhs.GetLowerLeftCorner().Lat()); + const double maxY = Min(lhs.GetUpperRightCorner().Lat(), rhs.GetUpperRightCorner().Lat()); + if (minX > maxX || minY > maxY) { + return {}; + } + return TGeoWindow(TGeoPoint(minX, minY), TGeoPoint(maxX, maxY)); + } + + TMaybe<TGeoWindow> Intersection(const TMaybe<TGeoWindow>& lhs, const TMaybe<TGeoWindow>& rhs) { + if (!lhs || !rhs) { + return {}; + } + return Intersection(*lhs, *rhs); + } + + TGeoWindow Union(const TGeoWindow& lhs, const TGeoWindow& rhs) { + const double minX = Min(lhs.GetLowerLeftCorner().Lon(), rhs.GetLowerLeftCorner().Lon()); + const double maxX = Max(lhs.GetUpperRightCorner().Lon(), rhs.GetUpperRightCorner().Lon()); + const double minY = Min(lhs.GetLowerLeftCorner().Lat(), rhs.GetLowerLeftCorner().Lat()); + const double maxY = Max(lhs.GetUpperRightCorner().Lat(), rhs.GetUpperRightCorner().Lat()); + return TGeoWindow{TGeoPoint{minX, minY}, TGeoPoint{maxX, maxY}}; + } + + TMaybe<TGeoWindow> Union(const TMaybe<TGeoWindow>& lhs, const TMaybe<TGeoWindow>& rhs) { + if (!lhs) { + return rhs; + } + if (!rhs) { + return lhs; + } + return Union(*lhs, *rhs); + } + + bool Contains(const TMaybe<TGeoWindow>& window, const TGeoPoint& point) { + if (!window) { + return false; + } + return window.GetRef().Contains(point); + } + + bool Intersects(const TGeoWindow& lhs, const TGeoWindow& rhs) { + bool haveHorizIntersection = + !(lhs.GetUpperRightCorner().Lon() <= rhs.GetLowerLeftCorner().Lon() || + rhs.GetUpperRightCorner().Lon() <= lhs.GetLowerLeftCorner().Lon()); + bool haveVertIntersection = + !(lhs.GetUpperRightCorner().Lat() <= rhs.GetLowerLeftCorner().Lat() || + rhs.GetUpperRightCorner().Lat() <= lhs.GetLowerLeftCorner().Lat()); + return haveHorizIntersection && haveVertIntersection; + } + + bool Intersects(const TMaybe<TGeoWindow>& lhs, const TMaybe<TGeoWindow>& rhs) { + if (!lhs || !rhs) { + return false; + } + return Intersects(*lhs, *rhs); + } +} // namespace NGeo diff --git a/library/cpp/geo/window.h b/library/cpp/geo/window.h new file mode 100644 index 0000000000..1205d8351b --- /dev/null +++ b/library/cpp/geo/window.h @@ -0,0 +1,264 @@ +#pragma once + +#include "point.h" +#include "size.h" +#include <util/generic/string.h> +#include <util/generic/yexception.h> +#include <util/string/cast.h> +#include <util/generic/maybe.h> + +#include <algorithm> + +namespace NGeo { + class TGeoWindow { + public: + TGeoWindow() noexcept + + = default; + + TGeoWindow(const TGeoPoint& center, const TSize& size) noexcept + : Center_(center) + , Size_(size) + { + CalcCorners(); + } + + TGeoWindow(const TGeoPoint& firstPoint, const TGeoPoint& secondPoint) noexcept + : LowerLeftCorner_{std::min(firstPoint.Lon(), secondPoint.Lon()), + std::min(firstPoint.Lat(), secondPoint.Lat())} + , UpperRightCorner_{std::max(firstPoint.Lon(), secondPoint.Lon()), + std::max(firstPoint.Lat(), secondPoint.Lat())} + { + CalcCenterAndSpan(); + } + + const TGeoPoint& GetCenter() const noexcept { + return Center_; + } + + void SetCenter(const TGeoPoint& newCenter) { + Center_ = newCenter; + CalcCorners(); + } + + const TSize& GetSize() const noexcept { + return Size_; + } + + void SetSize(const TSize& newSize) { + Size_ = newSize; + CalcCorners(); + } + + const TGeoPoint& GetLowerLeftCorner() const noexcept { + return LowerLeftCorner_; + } + + const TGeoPoint& GetUpperRightCorner() const noexcept { + return UpperRightCorner_; + } + + void swap(TGeoWindow& o) noexcept { + Center_.swap(o.Center_); + Size_.swap(o.Size_); + LowerLeftCorner_.swap(o.LowerLeftCorner_); + UpperRightCorner_.swap(o.UpperRightCorner_); + } + + bool IsValid() const noexcept { + return Center_.IsValid() && Size_.IsValid(); + } + + bool Contains(const TGeoPoint&) const; + + bool Contains(const TGeoWindow& w) const { + return Contains(w.LowerLeftCorner_) && Contains(w.UpperRightCorner_); + } + + void Stretch(double multiplier) { + Size_.Stretch(multiplier); + CalcCorners(); + } + + void Inflate(double additionX, double additionY) { + Size_.Inflate(additionX * 2, additionY * 2); + CalcCorners(); + } + + void Inflate(double addition) { + Inflate(addition, addition); + } + + bool operator!() const { + return !IsValid(); + } + + double Diameter() const; + + double Area() const { + return Size_.GetHeight() * Size_.GetWidth(); + } + + double Distance(const TGeoWindow&) const; + + double GetApproxDistance(const TPointLL& point) const; + + /** + * try to parse TGeoWindow from center and span + * return parsed TGeoWindow on success, otherwise throw exception + */ + static TGeoWindow ParseFromLlAndSpn(TStringBuf llStr, TStringBuf spnStr, TStringBuf delimiter = TStringBuf(",")); + + /** + * try to parse TGeoWindow from two corners + * return parsed TGeoWindow on success, otherwise throw exception + */ + static TGeoWindow ParseFromCornersPoints(TStringBuf leftCornerStr, TStringBuf rightCornerStr, TStringBuf delimiter = TStringBuf(",")); + + /** + * try to parse TGeoWindow from center and span + * return TMaybe of parsed TGeoWindow on success, otherwise return empty TMaybe + */ + static TMaybe<TGeoWindow> TryParseFromLlAndSpn(TStringBuf llStr, TStringBuf spnStr, TStringBuf delimiter = TStringBuf(",")); + + /** + * try to parse TGeoWindow from two corners + * return TMaybe of parsed TGeoWindow on success, otherwise return empty TMaybe + */ + static TMaybe<TGeoWindow> TryParseFromCornersPoints(TStringBuf leftCornerStr, TStringBuf rightCornerStr, TStringBuf delimiter = TStringBuf(",")); + + private: + TGeoPoint Center_; + TSize Size_; + TGeoPoint LowerLeftCorner_; + TGeoPoint UpperRightCorner_; + + void CalcCorners(); + void CalcCenterAndSpan(); + }; + + inline bool operator==(const TGeoWindow& lhs, const TGeoWindow& rhs) { + return lhs.GetCenter() == rhs.GetCenter() && lhs.GetSize() == rhs.GetSize(); + } + + inline bool operator!=(const TGeoWindow& p1, const TGeoWindow& p2) { + return !(p1 == p2); + } + + /** + * \class TMercatorWindow + * + * Represents a window in EPSG:3395 projection + * (WGS 84 / World Mercator) + */ + class TMercatorWindow { + public: + TMercatorWindow() noexcept; + TMercatorWindow(const TMercatorPoint& center, const TSize& size) noexcept; + TMercatorWindow(const TMercatorPoint& firstPoint, const TMercatorPoint& secondPoint) noexcept; + + const TMercatorPoint& GetCenter() const noexcept { + return Center_; + } + + TSize GetHalfSize() const noexcept { + return {HalfWidth_, HalfHeight_}; + } + + TSize GetSize() const noexcept { + return {GetWidth(), GetHeight()}; + } + + double GetWidth() const noexcept { + return HalfWidth_ * 2; + } + + double GetHeight() const noexcept { + return HalfHeight_ * 2; + } + + TMercatorPoint GetLowerLeftCorner() const noexcept { + return TMercatorPoint{Center_.X() - HalfWidth_, Center_.Y() - HalfHeight_}; + } + + TMercatorPoint GetUpperRightCorner() const noexcept { + return TMercatorPoint{Center_.X() + HalfWidth_, Center_.Y() + HalfHeight_}; + } + + bool Contains(const TMercatorPoint& pt) const noexcept; + + bool Contains(const TMercatorWindow& w) const { + return Contains(w.GetLowerLeftCorner()) && Contains(w.GetUpperRightCorner()); + } + + void Stretch(double multiplier) { + HalfWidth_ *= multiplier; + HalfHeight_ *= multiplier; + } + + void Inflate(double additionX, double additionY) { + HalfWidth_ += additionX; + HalfHeight_ += additionY; + } + + void Inflate(double addition) { + Inflate(addition, addition); + } + + double Area() const { + return GetHeight() * GetWidth(); + } + + private: + bool IsDefined() const { + return Center_.IsDefined() && !std::isnan(HalfWidth_) && !std::isnan(HalfHeight_); + } + + private: + TMercatorPoint Center_; + double HalfWidth_; + double HalfHeight_; + }; + + inline bool operator==(const TMercatorWindow& lhs, const TMercatorWindow& rhs) { + return lhs.GetCenter() == rhs.GetCenter() && lhs.GetHalfSize() == rhs.GetHalfSize(); + } + + inline bool operator!=(const TMercatorWindow& p1, const TMercatorWindow& p2) { + return !(p1 == p2); + } + + /** + * Typedefs + * TODO(sobols@): remove + */ + + using TWindowLL = TGeoWindow; + + /** + * Conversion + */ + + TMercatorWindow LLToMercator(const TGeoWindow&); + TGeoWindow MercatorToLL(const TMercatorWindow&); + + /** + * Utility functions + */ + + bool Contains(const TMaybe<TGeoWindow>& window, const TGeoPoint& point); + + TMaybe<TGeoWindow> Union(const TMaybe<TGeoWindow>& lhs, const TMaybe<TGeoWindow>& rhs); + TGeoWindow Union(const TGeoWindow& lhs, const TGeoWindow& rhs); + + TMaybe<TGeoWindow> Intersection(const TMaybe<TGeoWindow>& lhs, const TMaybe<TGeoWindow>& rhs); + TMaybe<TGeoWindow> Intersection(const TGeoWindow& lhs, const TGeoWindow& rhs); + + bool Intersects(const TGeoWindow& lhs, const TGeoWindow& rhs); + bool Intersects(const TMaybe<TGeoWindow>& lhs, const TMaybe<TGeoWindow>& rhs); +} // namespace NGeo + +template <> +inline void Out<NGeo::TGeoWindow>(IOutputStream& o, const NGeo::TGeoWindow& obj) { + o << '{' << obj.GetCenter() << ", " << obj.GetSize() << ", " << obj.GetLowerLeftCorner() << ", " << obj.GetUpperRightCorner() << "}"; +} diff --git a/library/cpp/geo/ya.make b/library/cpp/geo/ya.make new file mode 100644 index 0000000000..1d36003c5c --- /dev/null +++ b/library/cpp/geo/ya.make @@ -0,0 +1,19 @@ +LIBRARY() + +SRCS( + bbox.cpp + geo.cpp + point.cpp + polygon.cpp + load_save_helper.cpp + size.cpp + util.cpp + window.cpp +) + +END() + +RECURSE_FOR_TESTS( + ut + style + ) |