diff options
| author | Maxim Pimenov <m@maps.me> | 2018-07-23 19:29:00 +0300 |
|---|---|---|
| committer | Vlad Mihaylenko <vxmihaylenko@gmail.com> | 2018-07-25 18:49:59 +0300 |
| commit | 845af4ae26f41e86d2db9399420c19ec04b43d05 (patch) | |
| tree | 6b7c4d696579d9f5b9d304dd7ed7246767244925 /geometry | |
| parent | 4e146ec1ed8f8aed0d07ab6f0fe49d067b4c9901 (diff) | |
[geometry] Coding style fixes.
Diffstat (limited to 'geometry')
32 files changed, 2197 insertions, 2428 deletions
diff --git a/geometry/algorithm.cpp b/geometry/algorithm.cpp index c8c34ce000..751476f7d5 100644 --- a/geometry/algorithm.cpp +++ b/geometry/algorithm.cpp @@ -3,9 +3,12 @@ #include "base/logging.hpp" +using namespace std; + namespace m2 { -// CalculatePolyLineCenter ----------------------------------------------------------------------------- +// CalculatePolyLineCenter +// ----------------------------------------------------------------------------- void CalculatePolyLineCenter::operator()(m2::PointD const & pt) { diff --git a/geometry/angles.cpp b/geometry/angles.cpp index 7abf02c77a..c911abf0b3 100644 --- a/geometry/angles.cpp +++ b/geometry/angles.cpp @@ -1,16 +1,14 @@ #include "geometry/angles.hpp" - namespace ang { - double AngleIn2PI(double ang) { double const period = 2.0 * math::pi; ang = fmod(ang, period); if (ang < 0.0) ang += period; - + if (my::AlmostEqualULPs(period, ang)) return 0.0; @@ -29,7 +27,7 @@ double GetShortestDistance(double rad1, double rad2) if (res < 0.0) res = period + res; else - res = - period + res; + res = -period + res; } return res; } @@ -44,9 +42,7 @@ double GetMiddleAngle(double a1, double a2) ang -= math::pi; else ang += math::pi; - } return ang; } - -} +} // namespace ang diff --git a/geometry/angles.hpp b/geometry/angles.hpp index 0371fe0dbc..ce16c60b78 100644 --- a/geometry/angles.hpp +++ b/geometry/angles.hpp @@ -4,130 +4,116 @@ #include "base/matrix.hpp" -#include "std/cmath.hpp" -#include "std/string.hpp" - +#include <cmath> +#include <string> namespace ang { - template <typename T> - class Angle - { - T m_val; - T m_sin; - T m_cos; - - public: - Angle() : m_val(0), m_sin(0), m_cos(1) {} - Angle(T const & val) : m_val(val), m_sin(::sin(val)), m_cos(::cos(val)) {} - Angle(T const & sin, T const & cos) : m_val(::atan2(sin, cos)), m_sin(sin), m_cos(cos) {} - - T const & val() const - { - return m_val; - } - - T const & sin() const - { - return m_sin; - } - - T const & cos() const - { - return m_cos; - } - - Angle<T> const & operator*=(math::Matrix<T, 3, 3> const & m) - { - m2::Point<T> pt0(0, 0); - m2::Point<T> pt1(m_cos, m_sin); - - pt1 *= m; - pt0 *= m; - - m_val = atan2(pt1.y - pt0.y, pt1.x - pt0.x); - m_sin = ::sin(m_val); - m_cos = ::cos(m_val); - - return *this; - } - - friend string DebugPrint(Angle<T> const & ang) - { - return DebugPrint(ang.m_val); - } - }; - - typedef Angle<double> AngleD; - typedef Angle<float> AngleF; - - template <typename T> - Angle<T> const operator*(Angle<T> const & a, math::Matrix<T, 3, 3> const & m) - { - Angle<T> ret(a); - ret *= m; - return ret; - } +template <typename T> +class Angle +{ +public: + Angle() : m_val(0), m_sin(0), m_cos(1) {} + Angle(T const & val) : m_val(val), m_sin(::sin(val)), m_cos(::cos(val)) {} + Angle(T const & sin, T const & cos) : m_val(::atan2(sin, cos)), m_sin(sin), m_cos(cos) {} - /// Returns an angle of vector [p1, p2] from x-axis directed to y-axis. - /// Angle is in range [-pi, pi]. - template <typename T> - inline T AngleTo(m2::Point<T> const & p1, m2::Point<T> const & p2) - { - return atan2(p2.y - p1.y, p2.x - p1.x); - } + T const & val() const { return m_val; } + + T const & sin() const { return m_sin; } - /// Returns an angle from vector [p, p1] to vector [p, p2]. A counterclockwise rotation. - /// Angle is in range [0, 2 * pi] - template <typename T> - inline T TwoVectorsAngle(m2::Point<T> const & p, m2::Point<T> const & p1, m2::Point<T> const & p2) + T const & cos() const { return m_cos; } + + Angle<T> const & operator*=(math::Matrix<T, 3, 3> const & m) { - T a = ang::AngleTo(p, p2) - ang::AngleTo(p, p1); - while (a < 0) - a += math::twicePi; - return a; + m2::Point<T> pt0(0, 0); + m2::Point<T> pt1(m_cos, m_sin); + + pt1 *= m; + pt0 *= m; + + m_val = atan2(pt1.y - pt0.y, pt1.x - pt0.x); + m_sin = ::sin(m_val); + m_cos = ::cos(m_val); + + return *this; } - double AngleIn2PI(double ang); + friend std::string DebugPrint(Angle<T> const & ang) { return DebugPrint(ang.m_val); } + +private: + T m_val; + T m_sin; + T m_cos; +}; + +using AngleD = Angle<double>; +using AngleF = Angle<float>; + +template <typename T> +Angle<T> const operator*(Angle<T> const & a, math::Matrix<T, 3, 3> const & m) +{ + Angle<T> ret(a); + ret *= m; + return ret; +} + +/// Returns an angle of vector [p1, p2] from x-axis directed to y-axis. +/// Angle is in range [-pi, pi]. +template <typename T> +T AngleTo(m2::Point<T> const & p1, m2::Point<T> const & p2) +{ + return atan2(p2.y - p1.y, p2.x - p1.x); +} + +/// Returns an angle from vector [p, p1] to vector [p, p2]. A counterclockwise rotation. +/// Angle is in range [0, 2 * pi] +template <typename T> +T TwoVectorsAngle(m2::Point<T> const & p, m2::Point<T> const & p1, m2::Point<T> const & p2) +{ + T a = ang::AngleTo(p, p2) - ang::AngleTo(p, p1); + while (a < 0) + a += math::twicePi; + return a; +} + +double AngleIn2PI(double ang); - /// @return Oriented angle (<= PI) from rad1 to rad2. - /// >0 - clockwise, <0 - counterclockwise - double GetShortestDistance(double rad1, double rad2); +/// @return Oriented angle (<= PI) from rad1 to rad2. +/// >0 - clockwise, <0 - counterclockwise +double GetShortestDistance(double rad1, double rad2); - double GetMiddleAngle(double a1, double a2); +double GetMiddleAngle(double a1, double a2); - /// @return If north is zero - azimuth between geographic north and [p1, p2] vector is returned. - /// If north is not zero - it is treated as azimuth of some custom direction(eg magnetic north or some other direction), - /// and azimuth between that direction and [p1, p2] is returned. - /// Azimuth is in range [0, 2 * pi] - template <typename T> - inline T Azimuth(m2::Point<T> const & p1, m2::Point<T> const & p2, T north = 0) +/// @return If north is zero - azimuth between geographic north and [p1, p2] vector is returned. +/// If north is not zero - it is treated as azimuth of some custom direction(eg magnetic north or +/// some other direction), and azimuth between that direction and [p1, p2] is returned. Azimuth is +/// in range [0, 2 * pi] +template <typename T> +T Azimuth(m2::Point<T> const & p1, m2::Point<T> const & p2, T north = 0) +{ + T azimuth = math::pi2 - (AngleTo(p1, p2) + north); + if (azimuth < 0) + azimuth += math::twicePi; + return azimuth; +} + +/// Average angle calcker. Can't find any suitable solution, so decided to do like this: +/// Avg(i) = Avg(Avg(i-1), Ai); +class AverageCalc +{ +public: + AverageCalc() : m_ang(0.0), m_isEmpty(true) {} + + void Add(double a) { - T azimuth = math::pi2 - (AngleTo(p1, p2) + north); - if (azimuth < 0) - azimuth += math::twicePi; - return azimuth; + m_ang = (m_isEmpty ? a : GetMiddleAngle(m_ang, a)); + m_isEmpty = false; } - /// Average angle calcker. Can't find any suitable solution, so decided to do like this: - /// Avg(i) = Avg(Avg(i-1), Ai); - class AverageCalc - { - double m_ang; - bool m_isEmpty; - - public: - AverageCalc() : m_ang(0.0), m_isEmpty(true) {} - - void Add(double a) - { - m_ang = (m_isEmpty ? a : GetMiddleAngle(m_ang, a)); - m_isEmpty = false; - } - - double GetAverage() const - { - return m_ang; - } - }; -} + double GetAverage() const { return m_ang; } + +private: + double m_ang; + bool m_isEmpty; +}; +} // namespace ang diff --git a/geometry/any_rect2d.hpp b/geometry/any_rect2d.hpp index b538f5f99e..0a507c719f 100644 --- a/geometry/any_rect2d.hpp +++ b/geometry/any_rect2d.hpp @@ -1,279 +1,242 @@ #pragma once +#include "geometry/angles.hpp" #include "geometry/point2d.hpp" #include "geometry/rect2d.hpp" #include "geometry/rect_intersect.hpp" -#include "geometry/angles.hpp" #include "base/math.hpp" +#include <string> namespace m2 { - /// axis aligned rect - template <typename T> - class AnyRect - { - ang::Angle<T> m_angle; - - Point<T> m_zero; - Rect<T> m_rect; - - static Point<T> const Convert(Point<T> const & p, - Point<T> const & fromI, Point<T> const & fromJ, - Point<T> const & toI, Point<T> const & toJ) - { - Point<T> res; - - res.x = p.x * DotProduct(fromI, toI) + p.y * DotProduct(fromJ, toI); - res.y = p.x * DotProduct(fromI, toJ) + p.y * DotProduct(fromJ, toJ); - - return res; - } - - public: - AnyRect() : m_zero(0, 0), m_rect() {} +/// axis aligned rect +template <typename T> +class AnyRect +{ +public: + AnyRect() : m_zero(0, 0), m_rect() {} - /// creating from regular rect - explicit AnyRect(Rect<T> const & r) + /// creating from regular rect + explicit AnyRect(Rect<T> const & r) + { + if (r.IsValid()) { - if (r.IsValid()) - { - m_zero = Point<T>(r.minX(), r.minY()); - m_rect = Rect<T>(0, 0, r.SizeX(), r.SizeY()); - } - else - { - m_zero = Point<T>(0, 0); - m_rect = r; - } + m_zero = Point<T>(r.minX(), r.minY()); + m_rect = Rect<T>(0, 0, r.SizeX(), r.SizeY()); } - - AnyRect(Point<T> const & zero, ang::Angle<T> const & angle, Rect<T> const & r) - : m_angle(angle), m_rect(r) + else { - m_zero = Convert(zero, Point<T>(1, 0), Point<T>(0, 1), i(), j()); + m_zero = Point<T>(0, 0); + m_rect = r; } + } - Point<T> const & LocalZero() const - { - return m_zero; - } + AnyRect(Point<T> const & zero, ang::Angle<T> const & angle, Rect<T> const & r) + : m_angle(angle), m_rect(r) + { + m_zero = Convert(zero, Point<T>(1, 0), Point<T>(0, 1), i(), j()); + } - Point<T> const GlobalZero() const - { - return Convert(m_zero, i(), j(), m2::Point<T>(1, 0), m2::Point<T>(0, 1)); - } + Point<T> const & LocalZero() const { return m_zero; } - Point<T> const i() const - { - return Point<T>(m_angle.cos(), m_angle.sin()); - } + Point<T> const GlobalZero() const + { + return Convert(m_zero, i(), j(), m2::Point<T>(1, 0), m2::Point<T>(0, 1)); + } - Point<T> const j() const - { - return Point<T>(-m_angle.sin(), m_angle.cos()); - } + Point<T> const i() const { return Point<T>(m_angle.cos(), m_angle.sin()); } - void SetAngle(ang::Angle<T> const & a) - { - m2::Point<T> glbZero = GlobalZero(); + Point<T> const j() const { return Point<T>(-m_angle.sin(), m_angle.cos()); } - m_angle = a; - m_zero = Convert(glbZero, Point<T>(1, 0), Point<T>(0, 1), i(), j()); - } + void SetAngle(ang::Angle<T> const & a) + { + m2::Point<T> glbZero = GlobalZero(); - ang::Angle<T> const & Angle() const - { - return m_angle; - } + m_angle = a; + m_zero = Convert(glbZero, Point<T>(1, 0), Point<T>(0, 1), i(), j()); + } - Point<T> const GlobalCenter() const - { - return ConvertFrom(m_rect.Center()); - } + ang::Angle<T> const & Angle() const { return m_angle; } - Point<T> const LocalCenter() const - { - return m_rect.Center(); - } + Point<T> const GlobalCenter() const { return ConvertFrom(m_rect.Center()); } - T GetMaxSize() const { return max(m_rect.SizeX(), m_rect.SizeY()); } + Point<T> const LocalCenter() const { return m_rect.Center(); } - bool EqualDxDy(AnyRect<T> const & r, T eps) const - { - m2::Point<T> arr1[4]; - GetGlobalPoints(arr1); - sort(arr1, arr1 + 4); + T GetMaxSize() const { return max(m_rect.SizeX(), m_rect.SizeY()); } - m2::Point<T> arr2[4]; - r.GetGlobalPoints(arr2); - sort(arr2, arr2 + 4); + bool EqualDxDy(AnyRect<T> const & r, T eps) const + { + m2::Point<T> arr1[4]; + GetGlobalPoints(arr1); + sort(arr1, arr1 + 4); - for (size_t i = 0; i < 4; ++i) - if (!arr1[i].EqualDxDy(arr2[i], eps)) - return false; + m2::Point<T> arr2[4]; + r.GetGlobalPoints(arr2); + sort(arr2, arr2 + 4); - return true; - } + for (size_t i = 0; i < 4; ++i) + if (!arr1[i].EqualDxDy(arr2[i], eps)) + return false; - bool IsPointInside(Point<T> const & pt) const - { - return m_rect.IsPointInside(ConvertTo(pt)); - } + return true; + } - bool IsRectInside(AnyRect<T> const & r) const - { - m2::Point<T> pts[4]; - r.GetGlobalPoints(pts); - ConvertTo(pts, 4); - return m_rect.IsPointInside(pts[0]) - && m_rect.IsPointInside(pts[1]) - && m_rect.IsPointInside(pts[2]) - && m_rect.IsPointInside(pts[3]); - } + bool IsPointInside(Point<T> const & pt) const { return m_rect.IsPointInside(ConvertTo(pt)); } - bool IsIntersect(AnyRect<T> const & r) const - { - m2::Point<T> pts[4]; - if (r.GetLocalRect() == Rect<T>()) - return false; - r.GetGlobalPoints(pts); - ConvertTo(pts, 4); + bool IsRectInside(AnyRect<T> const & r) const + { + m2::Point<T> pts[4]; + r.GetGlobalPoints(pts); + ConvertTo(pts, 4); + return m_rect.IsPointInside(pts[0]) && m_rect.IsPointInside(pts[1]) && + m_rect.IsPointInside(pts[2]) && m_rect.IsPointInside(pts[3]); + } - m2::Rect<T> r1(pts[0], pts[0]); - r1.Add(pts[1]); - r1.Add(pts[2]); - r1.Add(pts[3]); + bool IsIntersect(AnyRect<T> const & r) const + { + m2::Point<T> pts[4]; + if (r.GetLocalRect() == Rect<T>()) + return false; + r.GetGlobalPoints(pts); + ConvertTo(pts, 4); - if (!GetLocalRect().IsIntersect(r1)) - return false; + m2::Rect<T> r1(pts[0], pts[0]); + r1.Add(pts[1]); + r1.Add(pts[2]); + r1.Add(pts[3]); - if (r.IsRectInside(*this)) - return true; + if (!GetLocalRect().IsIntersect(r1)) + return false; - if (IsRectInside(r)) - return true; + if (r.IsRectInside(*this)) + return true; - return Intersect(GetLocalRect(), pts[0], pts[1]) - || Intersect(GetLocalRect(), pts[1], pts[2]) - || Intersect(GetLocalRect(), pts[2], pts[3]) - || Intersect(GetLocalRect(), pts[3], pts[0]); - } + if (IsRectInside(r)) + return true; - /// Convert into coordinate system of this AnyRect - Point<T> const ConvertTo(Point<T> const & p) const - { - m2::Point<T> i1(1, 0); - m2::Point<T> j1(0, 1); - return Convert(p - Convert(m_zero, i(), j(), i1, j1), i1, j1, i(), j()); - } + return Intersect(GetLocalRect(), pts[0], pts[1]) || Intersect(GetLocalRect(), pts[1], pts[2]) || + Intersect(GetLocalRect(), pts[2], pts[3]) || Intersect(GetLocalRect(), pts[3], pts[0]); + } - void ConvertTo(Point<T> * pts, size_t count) const - { - for (size_t i = 0; i < count; ++i) - pts[i] = ConvertTo(pts[i]); - } + /// Convert into coordinate system of this AnyRect + Point<T> const ConvertTo(Point<T> const & p) const + { + m2::Point<T> i1(1, 0); + m2::Point<T> j1(0, 1); + return Convert(p - Convert(m_zero, i(), j(), i1, j1), i1, j1, i(), j()); + } - /// Convert into global coordinates from the local coordinates of this AnyRect - Point<T> const ConvertFrom(Point<T> const & p) const - { - return Convert(p + m_zero, i(), j(), m2::Point<T>(1, 0), m2::Point<T>(0, 1)); - } + void ConvertTo(Point<T> * pts, size_t count) const + { + for (size_t i = 0; i < count; ++i) + pts[i] = ConvertTo(pts[i]); + } - void ConvertFrom(Point<T> * pts, size_t count) const - { - for (size_t i = 0; i < count; ++i) - pts[i] = ConvertFrom(pts[i]); - } + /// Convert into global coordinates from the local coordinates of this AnyRect + Point<T> const ConvertFrom(Point<T> const & p) const + { + return Convert(p + m_zero, i(), j(), m2::Point<T>(1, 0), m2::Point<T>(0, 1)); + } - Rect<T> const & GetLocalRect() const - { - return m_rect; - } + void ConvertFrom(Point<T> * pts, size_t count) const + { + for (size_t i = 0; i < count; ++i) + pts[i] = ConvertFrom(pts[i]); + } - Rect<T> const GetGlobalRect() const - { - Point<T> pts[4]; - GetGlobalPoints(pts); + Rect<T> const & GetLocalRect() const { return m_rect; } - Rect<T> res(pts[0], pts[1]); - res.Add(pts[2]); - res.Add(pts[3]); + Rect<T> const GetGlobalRect() const + { + Point<T> pts[4]; + GetGlobalPoints(pts); - return res; - } + Rect<T> res(pts[0], pts[1]); + res.Add(pts[2]); + res.Add(pts[3]); - void GetGlobalPoints(Point<T> * pts) const - { - pts[0] = Point<T>(ConvertFrom(Point<T>(m_rect.minX(), m_rect.minY()))); - pts[1] = Point<T>(ConvertFrom(Point<T>(m_rect.minX(), m_rect.maxY()))); - pts[2] = Point<T>(ConvertFrom(Point<T>(m_rect.maxX(), m_rect.maxY()))); - pts[3] = Point<T>(ConvertFrom(Point<T>(m_rect.maxX(), m_rect.minY()))); - } + return res; + } - template <typename U> - void Inflate(U const & dx, U const & dy) - { - m_rect.Inflate(dx, dy); - } + void GetGlobalPoints(Point<T> * pts) const + { + pts[0] = Point<T>(ConvertFrom(Point<T>(m_rect.minX(), m_rect.minY()))); + pts[1] = Point<T>(ConvertFrom(Point<T>(m_rect.minX(), m_rect.maxY()))); + pts[2] = Point<T>(ConvertFrom(Point<T>(m_rect.maxX(), m_rect.maxY()))); + pts[3] = Point<T>(ConvertFrom(Point<T>(m_rect.maxX(), m_rect.minY()))); + } - void Add(AnyRect<T> const & r) - { - Point<T> pts[4]; - r.GetGlobalPoints(pts); - ConvertTo(pts, 4); - m_rect.Add(pts[0]); - m_rect.Add(pts[1]); - m_rect.Add(pts[2]); - m_rect.Add(pts[3]); - } + template <typename U> + void Inflate(U const & dx, U const & dy) + { + m_rect.Inflate(dx, dy); + } - void Offset(Point<T> const & p) - { - m_zero = ConvertTo(ConvertFrom(m_zero) + p); - } + void Add(AnyRect<T> const & r) + { + Point<T> pts[4]; + r.GetGlobalPoints(pts); + ConvertTo(pts, 4); + m_rect.Add(pts[0]); + m_rect.Add(pts[1]); + m_rect.Add(pts[2]); + m_rect.Add(pts[3]); + } - Point<T> const Center() const - { - return ConvertFrom(m_rect.Center()); - } + void Offset(Point<T> const & p) { m_zero = ConvertTo(ConvertFrom(m_zero) + p); } - void SetSizesToIncludePoint(Point<T> const & p) - { - m_rect.SetSizesToIncludePoint(ConvertTo(p)); - } + Point<T> const Center() const { return ConvertFrom(m_rect.Center()); } - friend string DebugPrint(m2::AnyRect<T> const & r) - { - return "{ Zero = " + DebugPrint(r.m_zero) + - ", Rect = " + DebugPrint(r.m_rect) + - ", Ang = " + DebugPrint(r.m_angle) + " }"; - } - }; + void SetSizesToIncludePoint(Point<T> const & p) { m_rect.SetSizesToIncludePoint(ConvertTo(p)); } - template <typename T> - AnyRect<T> const Offset(AnyRect<T> const & r, Point<T> const & pt) + friend std::string DebugPrint(m2::AnyRect<T> const & r) { - AnyRect<T> res(r); - res.Offset(pt); - return res; + return "{ Zero = " + DebugPrint(r.m_zero) + ", Rect = " + DebugPrint(r.m_rect) + + ", Ang = " + DebugPrint(r.m_angle) + " }"; } - template <typename T, typename U> - AnyRect<T> const Inflate(AnyRect<T> const & r, U const & dx, U const & dy) +private: + static Point<T> const Convert(Point<T> const & p, Point<T> const & fromI, Point<T> const & fromJ, + Point<T> const & toI, Point<T> const & toJ) { - AnyRect<T> res = r; - res.Inflate(dx, dy); + Point<T> res; + + res.x = p.x * DotProduct(fromI, toI) + p.y * DotProduct(fromJ, toI); + res.y = p.x * DotProduct(fromI, toJ) + p.y * DotProduct(fromJ, toJ); + return res; } - template <typename T, typename U> - AnyRect<T> const Inflate(AnyRect<T> const & r, Point<U> const & pt) - { - return Inflate(r, pt.x, pt.y); - } + ang::Angle<T> m_angle; + + Point<T> m_zero; + Rect<T> m_rect; +}; + +using AnyRectD = AnyRect<double>; +using AnyRectF = AnyRect<float>; - typedef AnyRect<double> AnyRectD; - typedef AnyRect<float> AnyRectF; +template <typename T> +AnyRect<T> const Offset(AnyRect<T> const & r, Point<T> const & pt) +{ + AnyRect<T> res(r); + res.Offset(pt); + return res; +} + +template <typename T, typename U> +AnyRect<T> const Inflate(AnyRect<T> const & r, U const & dx, U const & dy) +{ + AnyRect<T> res = r; + res.Inflate(dx, dy); + return res; +} + +template <typename T, typename U> +AnyRect<T> const Inflate(AnyRect<T> const & r, Point<U> const & pt) +{ + return Inflate(r, pt.x, pt.y); } +} // namespace m2 diff --git a/geometry/avg_vector.hpp b/geometry/avg_vector.hpp index 2841f47509..06eefbaa0e 100644 --- a/geometry/avg_vector.hpp +++ b/geometry/avg_vector.hpp @@ -1,7 +1,7 @@ #pragma once -#include "base/math.hpp" #include "base/assert.hpp" +#include "base/math.hpp" #include <array> #include <cmath> @@ -12,105 +12,104 @@ namespace math { - template <class T, size_t Dim> class AvgVector - { - typedef std::deque<std::array<T, Dim>> ContT; - typedef typename ContT::value_type ValueT; +template <class T, size_t Dim> +class AvgVector +{ + typedef std::deque<std::array<T, Dim>> ContT; + typedef typename ContT::value_type ValueT; - ContT m_vectors; - size_t m_count; + ContT m_vectors; + size_t m_count; - static T Distance(ValueT const & a1, ValueT const & a2) - { - T res = 0; - for (size_t i = 0; i < Dim; ++i) - res += std::pow(a1[i] - a2[i], 2); + static T Distance(ValueT const & a1, ValueT const & a2) + { + T res = 0; + for (size_t i = 0; i < Dim; ++i) + res += std::pow(a1[i] - a2[i], 2); - return sqrt(res); - } + return sqrt(res); + } - static void Average(ValueT const & a1, ValueT const & a2, T * res) - { - for (size_t i = 0; i < Dim; ++i) - res[i] = (a1[i] + a2[i]) / 2.0; - } + static void Average(ValueT const & a1, ValueT const & a2, T * res) + { + for (size_t i = 0; i < Dim; ++i) + res[i] = (a1[i] + a2[i]) / 2.0; + } - void CalcAverage(T * res) const - { - T minD = std::numeric_limits<T>::max(); - size_t I = 0, J = 1; + void CalcAverage(T * res) const + { + T minD = std::numeric_limits<T>::max(); + size_t I = 0, J = 1; - size_t const count = m_vectors.size(); - ASSERT_GREATER ( count, 1, () ); - for (size_t i = 0; i < count - 1; ++i) - for (size_t j = i+1; j < count; ++j) + size_t const count = m_vectors.size(); + ASSERT_GREATER(count, 1, ()); + for (size_t i = 0; i < count - 1; ++i) + for (size_t j = i + 1; j < count; ++j) + { + T const d = Distance(m_vectors[i], m_vectors[j]); + if (d < minD) { - T const d = Distance(m_vectors[i], m_vectors[j]); - if (d < minD) - { - I = i; - J = j; - minD = d; - } + I = i; + J = j; + minD = d; } + } - Average(m_vectors[I], m_vectors[J], res); - } - - public: - AvgVector(size_t count = 1) : m_count(count) - { - static_assert(std::is_floating_point<T>::value, ""); - } - - void SetCount(size_t count) { m_count = count; } + Average(m_vectors[I], m_vectors[J], res); + } - /// @param[in] Next measurement. - /// @param[out] Average value. - void Next(T * arr) - { - if (m_vectors.size() == m_count) - m_vectors.pop_front(); +public: + AvgVector(size_t count = 1) : m_count(count) + { + static_assert(std::is_floating_point<T>::value, ""); + } - m_vectors.push_back(ValueT()); - std::memcpy(m_vectors.back().data(), arr, Dim * sizeof(T)); + void SetCount(size_t count) { m_count = count; } - if (m_vectors.size() > 1) - CalcAverage(arr); - } - }; - - // Compass smoothing parameters - // We're using technique described in - // http://windowsteamblog.com/windows_phone/b/wpdev/archive/2010/09/08/using-the-accelerometer-on-windows-phone-7.aspx - // In short it's a combination of low-pass filter to smooth the - // small orientation changes and a threshold filter to get big changes fast. - // k in the following formula: O(n) = O(n-1) + k * (I - O(n - 1)); - // smoothed heading angle. doesn't always correspond to the m_headingAngle - // as we change the heading angle only if the delta between - // smoothedHeadingRad and new heading value is bigger than smoothingThreshold. - template <class T, size_t Dim> class LowPassVector + /// @param[in] Next measurement. + /// @param[out] Average value. + void Next(T * arr) { - typedef std::array<T, Dim> ArrayT; - ArrayT m_val; - T m_factor; + if (m_vectors.size() == m_count) + m_vectors.pop_front(); + + m_vectors.push_back(ValueT()); + std::memcpy(m_vectors.back().data(), arr, Dim * sizeof(T)); + + if (m_vectors.size() > 1) + CalcAverage(arr); + } +}; + +// Compass smoothing parameters +// We're using technique described in +// http://windowsteamblog.com/windows_phone/b/wpdev/archive/2010/09/08/using-the-accelerometer-on-windows-phone-7.aspx +// In short it's a combination of low-pass filter to smooth the +// small orientation changes and a threshold filter to get big changes fast. +// k in the following formula: O(n) = O(n-1) + k * (I - O(n - 1)); +// smoothed heading angle. doesn't always correspond to the m_headingAngle +// as we change the heading angle only if the delta between +// smoothedHeadingRad and new heading value is bigger than smoothingThreshold. +template <class T, size_t Dim> +class LowPassVector +{ + typedef std::array<T, Dim> ArrayT; + ArrayT m_val; + T m_factor; - public: - LowPassVector() : m_factor(0.15) - { - m_val.fill(T()); - } - void SetFactor(T t) { m_factor = t; } +public: + LowPassVector() : m_factor(0.15) { m_val.fill(T()); } + void SetFactor(T t) { m_factor = t; } - /// @param[in] Next measurement. - /// @param[out] Average value. - void Next(T * arr) + /// @param[in] Next measurement. + /// @param[out] Average value. + void Next(T * arr) + { + for (size_t i = 0; i < Dim; ++i) { - for (size_t i = 0; i < Dim; ++i) - { - m_val[i] = m_val[i] + m_factor * (arr[i] - m_val[i]); - arr[i] = m_val[i]; - } + m_val[i] = m_val[i] + m_factor * (arr[i] - m_val[i]); + arr[i] = m_val[i]; } - }; -} + } +}; +} // namespace math diff --git a/geometry/clipping.cpp b/geometry/clipping.cpp index db0de607cd..c08083589a 100644 --- a/geometry/clipping.cpp +++ b/geometry/clipping.cpp @@ -1,12 +1,14 @@ -#include "clipping.hpp" -#include "rect_intersect.hpp" +#include "geometry/clipping.hpp" -#include "std/vector.hpp" +#include "geometry/rect_intersect.hpp" + +#include <algorithm> + +using namespace std; namespace m2 { - -using AddPoligonPoint = function<void(m2::PointD const &)>; +using AddPolygonPoint = function<void(m2::PointD const &)>; int GetRectSideIndex(int code) { @@ -19,9 +21,9 @@ int GetRectSideIndex(int code) return 3; } -void InsertCorners(vector<m2::PointD> const & corners, - m2::PointD const & p1, m2::PointD const & p2, m2::PointD const & p3, - AddPoligonPoint const & addPoligonPoint, int code1, int code2) +void InsertCorners(vector<m2::PointD> const & corners, m2::PointD const & p1, m2::PointD const & p2, + m2::PointD const & p3, AddPolygonPoint const & addPolygonPoint, int code1, + int code2) { int cornerInd = GetRectSideIndex(code1); int endCornerInd = GetRectSideIndex(code2); @@ -35,15 +37,15 @@ void InsertCorners(vector<m2::PointD> const & corners, while (cornerInd != endCornerInd) { - addPoligonPoint(corners[cornerInd]); + addPolygonPoint(corners[cornerInd]); cornerInd = (cornerInd + 1) % 4; } } bool IntersectEdge(m2::RectD const & rect, vector<m2::PointD> const & corners, m2::PointD const & pp1, m2::PointD const & pp2, m2::PointD const & pp3, - AddPoligonPoint const & addPoligonPoint, - int prevClipCode, int nextClipCode, int & firstClipCode, int & lastClipCode) + AddPolygonPoint const & addPolygonPoint, int prevClipCode, int nextClipCode, + int & firstClipCode, int & lastClipCode) { m2::PointD p1 = pp1; m2::PointD p2 = pp2; @@ -51,27 +53,26 @@ bool IntersectEdge(m2::RectD const & rect, vector<m2::PointD> const & corners, if (m2::Intersect(rect, p1, p2, firstClipCode, lastClipCode)) { if (firstClipCode != 0 && prevClipCode != 0 && ((firstClipCode & prevClipCode) == 0)) - InsertCorners(corners, pp1, pp2, pp3, addPoligonPoint, prevClipCode, firstClipCode); + InsertCorners(corners, pp1, pp2, pp3, addPolygonPoint, prevClipCode, firstClipCode); - addPoligonPoint(p1); - addPoligonPoint(p2); + addPolygonPoint(p1); + addPolygonPoint(p2); if (lastClipCode != 0 && nextClipCode != 0 && ((lastClipCode & nextClipCode) == 0) && firstClipCode != lastClipCode && prevClipCode != nextClipCode) - InsertCorners(corners, pp1, pp2, pp3, addPoligonPoint, lastClipCode, nextClipCode); + InsertCorners(corners, pp1, pp2, pp3, addPolygonPoint, lastClipCode, nextClipCode); return true; } else if (prevClipCode != 0 && nextClipCode != 0) { - InsertCorners(corners, pp1, pp2, pp3, addPoligonPoint, prevClipCode, nextClipCode); + InsertCorners(corners, pp1, pp2, pp3, addPolygonPoint, prevClipCode, nextClipCode); } return false; } -void ClipTriangleByRect(m2::RectD const & rect, m2::PointD const & p1, - m2::PointD const & p2, m2::PointD const & p3, - ClipTriangleByRectResultIt const & resultIterator) +void ClipTriangleByRect(m2::RectD const & rect, m2::PointD const & p1, m2::PointD const & p2, + m2::PointD const & p3, ClipTriangleByRectResultIt const & resultIterator) { if (resultIterator == nullptr) return; @@ -84,25 +85,25 @@ void ClipTriangleByRect(m2::RectD const & rect, m2::PointD const & p1, const double kEps = 1e-8; vector<m2::PointD> poligon; - auto const addPoligonPoint = [&poligon, kEps](m2::PointD const & pt) - { + auto const addPolygonPoint = [&poligon, kEps](m2::PointD const & pt) { if (poligon.empty() || !poligon.back().EqualDxDy(pt, kEps)) poligon.push_back(pt); }; - vector<m2::PointD> const corners = { rect.LeftTop(), rect.RightTop(), rect.RightBottom(), rect.LeftBottom() }; + vector<m2::PointD> const corners = {rect.LeftTop(), rect.RightTop(), rect.RightBottom(), + rect.LeftBottom()}; int firstClipCode[3]; int lastClipCode[3]; bool intersected[3]; - intersected[0] = IntersectEdge(rect, corners, p1, p2, p3, addPoligonPoint, - 0, 0, firstClipCode[0], lastClipCode[0]); + intersected[0] = IntersectEdge(rect, corners, p1, p2, p3, addPolygonPoint, 0, 0, firstClipCode[0], + lastClipCode[0]); - intersected[1] = IntersectEdge(rect, corners, p2, p3, p1, addPoligonPoint, - lastClipCode[0], 0, firstClipCode[1], lastClipCode[1]); + intersected[1] = IntersectEdge(rect, corners, p2, p3, p1, addPolygonPoint, lastClipCode[0], 0, + firstClipCode[1], lastClipCode[1]); - intersected[2] = IntersectEdge(rect, corners, p3, p1, p2, addPoligonPoint, + intersected[2] = IntersectEdge(rect, corners, p3, p1, p2, addPolygonPoint, lastClipCode[1] != 0 ? lastClipCode[1] : lastClipCode[0], firstClipCode[0] != 0 ? firstClipCode[0] : firstClipCode[1], firstClipCode[2], lastClipCode[2]); @@ -119,7 +120,7 @@ void ClipTriangleByRect(m2::RectD const & rect, m2::PointD const & p1, } if (intersectCount == 1 && intersected[2]) - InsertCorners(corners, p1, p2, p3, addPoligonPoint, lastClipCode[2], firstClipCode[2]); + InsertCorners(corners, p1, p2, p3, addPolygonPoint, lastClipCode[2], firstClipCode[2]); if (!poligon.empty() && poligon.back().EqualDxDy(poligon[0], kEps)) poligon.pop_back(); @@ -190,5 +191,4 @@ vector<m2::SharedSpline> ClipSplineByRect(m2::RectD const & rect, m2::SharedSpli } return result; } - -} // namespace m2; +} // namespace m2; diff --git a/geometry/clipping.hpp b/geometry/clipping.hpp index 58b7691d44..27a2e25d64 100644 --- a/geometry/clipping.hpp +++ b/geometry/clipping.hpp @@ -1,20 +1,21 @@ #pragma once -#include "rect2d.hpp" -#include "spline.hpp" -#include "triangle2d.hpp" +#include "geometry/point2d.hpp" +#include "geometry/rect2d.hpp" +#include "geometry/spline.hpp" +#include "geometry/triangle2d.hpp" -#include "std/function.hpp" +#include <functional> +#include <vector> namespace m2 { +using ClipTriangleByRectResultIt = + std::function<void(m2::PointD const &, m2::PointD const &, m2::PointD const &)>; -using ClipTriangleByRectResultIt = function<void(m2::PointD const &, m2::PointD const &, m2::PointD const &)>; +void ClipTriangleByRect(m2::RectD const & rect, m2::PointD const & p1, m2::PointD const & p2, + m2::PointD const & p3, ClipTriangleByRectResultIt const & resultIterator); -void ClipTriangleByRect(m2::RectD const & rect, m2::PointD const & p1, - m2::PointD const & p2, m2::PointD const & p3, - ClipTriangleByRectResultIt const & resultIterator); - -vector<m2::SharedSpline> ClipSplineByRect(m2::RectD const & rect, m2::SharedSpline const & spline); - -} // namespace m2 +std::vector<m2::SharedSpline> ClipSplineByRect(m2::RectD const & rect, + m2::SharedSpline const & spline); +} // namespace m2 diff --git a/geometry/covering.hpp b/geometry/covering.hpp index eff30cb0ba..5ffeb9a937 100644 --- a/geometry/covering.hpp +++ b/geometry/covering.hpp @@ -1,11 +1,14 @@ #pragma once + #include "geometry/covering_utils.hpp" #include "geometry/point2d.hpp" + #include "base/assert.hpp" #include "base/base.hpp" #include "base/logging.hpp" #include "base/set_operations.hpp" #include "base/stl_add.hpp" + #include "std/algorithm.hpp" #include "std/array.hpp" #include "std/functional.hpp" @@ -17,7 +20,6 @@ namespace covering { - template <class CellIdT> class Covering { @@ -27,10 +29,7 @@ public: Covering() : m_Size(0) {} - explicit Covering(CellId cell) : m_Size(1) - { - m_Covering[cell.Level()].push_back(cell); - } + explicit Covering(CellId cell) : m_Size(1) { m_Covering[cell.Level()].push_back(cell); } explicit Covering(vector<CellId> const & v) { @@ -78,7 +77,7 @@ public: void OutputToVector(vector<CellId> & result) const { for (int level = 0; level < CellId::DEPTH_LEVELS; ++level) - result.insert(result.end(), m_Covering[level].begin(), m_Covering[level].end()); + result.insert(result.end(), m_Covering[level].begin(), m_Covering[level].end()); } void OutputToVector(vector<int64_t> & result, int cellDepth) const @@ -110,13 +109,12 @@ public: } private: - void SimplifyLevel(int level) { map<CellId, uint32_t, LessLevelOrder> parentCellCounts; typedef typename vector<CellId>::const_iterator ConstIteartor; for (ConstIteartor it = m_Covering[level].begin(); it != m_Covering[level].end(); ++it) - ++parentCellCounts[it->Parent()]; + ++parentCellCounts[it->Parent()]; vector<CellId> parentCells, childCells; for (ConstIteartor it = m_Covering[level].begin(); it != m_Covering[level].end(); ++it) @@ -147,7 +145,7 @@ private: { explicit CompareCellsAtLevel(int level) : m_Level(level) {} - bool operator() (CellId id1, CellId id2) const + bool operator()(CellId id1, CellId id2) const { return m_Comp(id1.AncestorAtLevel(m_Level), id2.AncestorAtLevel(m_Level)); } @@ -229,9 +227,8 @@ private: if (i + 3 < a.size()) { CellId const parent = a[i].Parent(); - if (parent == a[i+1].Parent() && - parent == a[i+2].Parent() && - parent == a[i+3].Parent()) + if (parent == a[i + 1].Parent() && parent == a[i + 2].Parent() && + parent == a[i + 3].Parent()) { parents.push_back(parent); i += 3; @@ -280,10 +277,7 @@ private: CoverTriangleImpl(info, cell.Child(child)); } - - array<vector<CellId>, CellId::DEPTH_LEVELS> m_Covering; // Covering by level. + array<vector<CellId>, CellId::DEPTH_LEVELS> m_Covering; // Covering by level. size_t m_Size; }; - - } diff --git a/geometry/covering_utils.hpp b/geometry/covering_utils.hpp index 9ca35d7969..6ef89e377f 100644 --- a/geometry/covering_utils.hpp +++ b/geometry/covering_utils.hpp @@ -1,7 +1,8 @@ #pragma once -#include "point2d.hpp" -#include "robust_orientation.hpp" -#include "triangle2d.hpp" + +#include "geometry/point2d.hpp" +#include "geometry/robust_orientation.hpp" +#include "geometry/triangle2d.hpp" #include "base/assert.hpp" #include "base/base.hpp" @@ -13,7 +14,6 @@ namespace covering { - // Result of an intersection between object and cell. enum CellObjectIntersection { @@ -25,19 +25,14 @@ enum CellObjectIntersection }; template <class CellIdT> -inline CellObjectIntersection IntersectCellWithLine(CellIdT const cell, - m2::PointD const & a, - m2::PointD const & b) +CellObjectIntersection IntersectCellWithLine(CellIdT const cell, m2::PointD const & a, + m2::PointD const & b) { std::pair<uint32_t, uint32_t> const xy = cell.XY(); uint32_t const r = cell.Radius(); - m2::PointD const cellCorners[4] = - { - m2::PointD(xy.first - r, xy.second - r), - m2::PointD(xy.first - r, xy.second + r), - m2::PointD(xy.first + r, xy.second + r), - m2::PointD(xy.first + r, xy.second - r) - }; + m2::PointD const cellCorners[4] = { + m2::PointD(xy.first - r, xy.second - r), m2::PointD(xy.first - r, xy.second + r), + m2::PointD(xy.first + r, xy.second + r), m2::PointD(xy.first + r, xy.second - r)}; for (int i = 0; i < 4; ++i) if (m2::robust::SegmentsIntersect(a, b, cellCorners[i], cellCorners[i == 0 ? 3 : i - 1])) return CELL_OBJECT_INTERSECT; @@ -47,8 +42,8 @@ inline CellObjectIntersection IntersectCellWithLine(CellIdT const cell, } template <class CellIdT> -CellObjectIntersection IntersectCellWithTriangle( - CellIdT const cell, m2::PointD const & a, m2::PointD const & b, m2::PointD const & c) +CellObjectIntersection IntersectCellWithTriangle(CellIdT const cell, m2::PointD const & a, + m2::PointD const & b, m2::PointD const & c) { CellObjectIntersection const i1 = IntersectCellWithLine(cell, a, b); if (i1 == CELL_OBJECT_INTERSECT) @@ -117,4 +112,4 @@ void CoverObject(IntersectF const & intersect, uint64_t cellPenaltyArea, CellIdC } } -} // namespace covering +} // namespace covering diff --git a/geometry/distance.hpp b/geometry/distance.hpp index 8cc6da0538..219a57b824 100644 --- a/geometry/distance.hpp +++ b/geometry/distance.hpp @@ -1,4 +1,5 @@ #pragma once + #include "geometry/point2d.hpp" #include "base/math.hpp" @@ -8,107 +9,92 @@ namespace m2 { - namespace impl { - -template <typename PointT> class CalculatedSection +template <typename Point> +class CalculatedSection { -private: - static_assert(std::numeric_limits<typename PointT::value_type>::is_signed, - "We do not support unsigned points!!!"); - public: - void SetBounds(PointT const & p0, PointT const & p1) + void SetBounds(Point const & p0, Point const & p1) { - m_P0 = p0; - m_P1 = p1; - m_D = m_P1 - m_P0; - m_D2 = Length(m_D); + m_p0 = p0; + m_p1 = p1; + m_d = m_p1 - m_p0; + m_length = sqrt(SquaredLength(m_d)); - if (my::AlmostEqualULPs(m_D2, 0.0)) + if (my::AlmostEqualULPs(m_length, 0.0)) { - // make zero vector - then all DotProduct will be equal to zero - m_D = m2::PointD::Zero(); + // Make zero vector and all DotProduct will be equal to zero. + m_d = m2::PointD::Zero(); } else { - // normalize vector - m_D = m_D / m_D2; + // Normalize vector. + m_d = m_d / m_length; } } - inline double GetLength() const { return m_D2; } - inline PointT const & P0() const { return m_P0; } - inline PointT const & P1() const { return m_P1; } + double GetLength() const { return m_length; } + Point const & P0() const { return m_p0; } + Point const & P1() const { return m_p1; } protected: - template <class VectorT> static double SquaredLength(VectorT const & v) + template <typename Vector> + static double SquaredLength(Vector const & v) { return DotProduct(v, v); } - template <class VectorT> static double Length(VectorT const & v) - { - return sqrt(SquaredLength(v)); - } - double Distance(PointD const & v) const - { - return CrossProduct(v, m_D); - } - PointT m_P0, m_P1; - m2::PointD m_D; - double m_D2; -}; + double Distance(PointD const & v) const { return CrossProduct(v, m_d); } + + Point m_p0; + Point m_p1; + m2::PointD m_d; + double m_length; +private: + static_assert(std::numeric_limits<typename Point::value_type>::is_signed, + "Unsigned points are not supported"); +}; } // namespace impl -template <typename PointT> class DistanceToLineSquare : public impl::CalculatedSection<PointT> +template <typename Point> +class DistanceToLineSquare : public impl::CalculatedSection<Point> { public: - double operator() (PointT const & Y) const + double operator()(Point const & p) const { - PointT const diff = Y - this->m_P0; - m2::PointD const YmP0(diff); - double const t = DotProduct(this->m_D, YmP0); + Point const diff = p - this->m_p0; + m2::PointD const diffD(diff); + double const t = DotProduct(this->m_d, diffD); if (t <= 0) - { - // Y is closest to P0. - return this->SquaredLength(YmP0); - } - if (t >= this->m_D2) - { - // Y is closest to P1. - return this->SquaredLength(Y - this->m_P1); - } + return this->SquaredLength(diffD); + + if (t >= this->m_length) + return this->SquaredLength(p - this->m_p1); - // Closest point is interior to segment. - return std::pow(this->Distance(YmP0), 2); + // Closest point is between |m_p0| and |m_p1|. + return std::pow(this->Distance(diffD), 2.0); } }; -template <typename PointT> class ProjectionToSection : public impl::CalculatedSection<PointT> +template <typename Point> +class ProjectionToSection : public impl::CalculatedSection<Point> { public: - m2::PointD operator() (PointT const & Y) const + m2::PointD operator()(Point const & p) const { - m2::PointD const YmP0 = Y - this->m_P0; - double const t = DotProduct(this->m_D, YmP0); + m2::PointD const diffD = p - this->m_p0; + double const t = DotProduct(this->m_d, diffD); if (t <= 0) - { - // Y is closest to P0. - return this->m_P0; - } - if (t >= this->m_D2) - { - // Y is closest to P1. - return this->m_P1; - } + return this->m_p0; + + if (t >= this->m_length) + return this->m_p1; - return this->m_D*t + this->m_P0; + return this->m_p0 + this->m_d * t; } }; - -} +} // namespace m2 diff --git a/geometry/distance_on_sphere.cpp b/geometry/distance_on_sphere.cpp index 3365b9a69d..7aadd2b876 100644 --- a/geometry/distance_on_sphere.cpp +++ b/geometry/distance_on_sphere.cpp @@ -1,8 +1,14 @@ #include "geometry/distance_on_sphere.hpp" + #include "base/math.hpp" -#include "std/algorithm.hpp" -double ms::DistanceOnSphere(double lat1Deg, double lon1Deg, double lat2Deg, double lon2Deg) +#include <algorithm> + +using namespace std; + +namespace ms +{ +double DistanceOnSphere(double lat1Deg, double lon1Deg, double lat2Deg, double lon2Deg) { double const lat1 = my::DegToRad(lat1Deg); double const lat2 = my::DegToRad(lat2Deg); @@ -12,9 +18,12 @@ double ms::DistanceOnSphere(double lat1Deg, double lon1Deg, double lat2Deg, doub return 2.0 * atan2(sqrt(y), sqrt(max(0.0, 1.0 - y))); } -double ms::AreaOnSphere(ms::LatLon const & ll1, ms::LatLon const & ll2, ms::LatLon const & ll3) +double AreaOnSphere(ms::LatLon const & ll1, ms::LatLon const & ll2, ms::LatLon const & ll3) { // Todo: proper area on sphere (not needed for now) double const avgLat = my::DegToRad((ll1.lat + ll2.lat + ll3.lat) / 3); - return cos(avgLat) * 0.5 * fabs((ll2.lon - ll1.lon)*(ll3.lat - ll1.lat) - (ll3.lon - ll1.lon)*(ll2.lat - ll1.lat)); + return cos(avgLat) * 0.5 * + fabs((ll2.lon - ll1.lon) * (ll3.lat - ll1.lat) - + (ll3.lon - ll1.lon) * (ll2.lat - ll1.lat)); } +} // namespace ms diff --git a/geometry/distance_on_sphere.hpp b/geometry/distance_on_sphere.hpp index efba329e3d..e8c6181e2f 100644 --- a/geometry/distance_on_sphere.hpp +++ b/geometry/distance_on_sphere.hpp @@ -1,11 +1,12 @@ #pragma once -#include "base/base.hpp" + #include "geometry/latlon.hpp" +#include "base/base.hpp" + // namespace ms - "math on sphere", similar to the namespaces m2 and mn. namespace ms { - // Earth radius in meters. inline double EarthRadiusMeters() { return 6378000; } // Length of one degree square at the equator in meters. @@ -32,7 +33,7 @@ inline double DistanceOnEarth(LatLon const & ll1, LatLon const & ll2) inline double AreaOnEarth(LatLon const & ll1, LatLon const & ll2, LatLon const & ll3) { - return OneDegreeEquatorLengthMeters() * OneDegreeEquatorLengthMeters() * AreaOnSphere(ll1, ll2, ll3); + return OneDegreeEquatorLengthMeters() * OneDegreeEquatorLengthMeters() * + AreaOnSphere(ll1, ll2, ll3); } - } // namespace ms diff --git a/geometry/geometry_tests/point_test.cpp b/geometry/geometry_tests/point_test.cpp index 0c15ef621b..3152f923a9 100644 --- a/geometry/geometry_tests/point_test.cpp +++ b/geometry/geometry_tests/point_test.cpp @@ -4,6 +4,9 @@ #include "geometry/point2d.hpp" #include "geometry/triangle2d.hpp" +#include <array> + +using namespace std; UNIT_TEST(Point_Rotate) { @@ -78,9 +81,19 @@ UNIT_TEST(GetArrowPoints) UNIT_TEST(PointAtSegment) { - TEST(m2::AlmostEqualULPs(m2::PointAtSegment(m2::PointF(0, 0), m2::PointF(1, 0), 0.5f), m2::PointF(0.5f, 0.f)), ()); - TEST(m2::AlmostEqualULPs(m2::PointAtSegment(m2::PointF(0, 0), m2::PointF(0, 1), 0.3f), m2::PointF(0.f, 0.3f)), ()); - TEST(m2::AlmostEqualULPs(m2::PointAtSegment(m2::PointD(0., 0.), m2::PointD(30., 40.), 5.), m2::PointD(3., 4.)), ()); - TEST(m2::AlmostEqualULPs(m2::PointAtSegment(m2::PointF(-3, -4), m2::PointF(-30, -40), 5.f), m2::PointF(-6.f, -8.f)), ()); - TEST(m2::AlmostEqualULPs(m2::PointAtSegment(m2::PointD(14., -48.), m2::PointD(70., -240.), 25.), m2::PointD(21., -72.)), ()); + TEST(m2::AlmostEqualULPs(m2::PointAtSegment(m2::PointF(0, 0), m2::PointF(1, 0), 0.5f), + m2::PointF(0.5f, 0.f)), + ()); + TEST(m2::AlmostEqualULPs(m2::PointAtSegment(m2::PointF(0, 0), m2::PointF(0, 1), 0.3f), + m2::PointF(0.f, 0.3f)), + ()); + TEST(m2::AlmostEqualULPs(m2::PointAtSegment(m2::PointD(0., 0.), m2::PointD(30., 40.), 5.), + m2::PointD(3., 4.)), + ()); + TEST(m2::AlmostEqualULPs(m2::PointAtSegment(m2::PointF(-3, -4), m2::PointF(-30, -40), 5.f), + m2::PointF(-6.f, -8.f)), + ()); + TEST(m2::AlmostEqualULPs(m2::PointAtSegment(m2::PointD(14., -48.), m2::PointD(70., -240.), 25.), + m2::PointD(21., -72.)), + ()); } diff --git a/geometry/geometry_tests/polygon_test.cpp b/geometry/geometry_tests/polygon_test.cpp index 3ebb69a686..0dfa606382 100644 --- a/geometry/geometry_tests/polygon_test.cpp +++ b/geometry/geometry_tests/polygon_test.cpp @@ -6,47 +6,51 @@ #include "base/macros.hpp" -#include "std/algorithm.hpp" +#include <algorithm> +using namespace std; -namespace { typedef m2::PointD P; } +namespace +{ +using P = m2::PointD; +} // namespace using namespace m2::robust; UNIT_TEST(IsSegmentInCone) { - TEST(IsSegmentInCone(P(0,0), P( 0, 3), P(-1,-1), P(1,-1)), ()); - TEST(IsSegmentInCone(P(0,0), P( 2, 3), P(-1,-1), P(1,-1)), ()); - TEST(IsSegmentInCone(P(0,0), P(-3, 3), P(-1,-1), P(1,-1)), ()); - TEST(IsSegmentInCone(P(0,0), P(-3, 0), P(-1,-1), P(1,-1)), ()); - TEST(IsSegmentInCone(P(0,0), P( 3, 0), P(-1,-1), P(1,-1)), ()); - TEST(!IsSegmentInCone(P(0,0), P( 0,-1), P(-1,-1), P(1,-1)), ()); - TEST(!IsSegmentInCone(P(0,0), P( 1,-3), P(-1,-1), P(1,-1)), ()); - TEST(!IsSegmentInCone(P(0,0), P(-1,-3), P(-1,-1), P(1,-1)), ()); - - TEST(IsSegmentInCone(P(0,0), P( 0, 3), P(-1,1), P(1,1)), ()); - TEST(IsSegmentInCone(P(0,0), P( 2, 3), P(-1,1), P(1,1)), ()); - TEST(!IsSegmentInCone(P(0,0), P(-3, 3), P(-1,1), P(1,1)), ()); - TEST(!IsSegmentInCone(P(0,0), P(-3, 0), P(-1,1), P(1,1)), ()); - TEST(!IsSegmentInCone(P(0,0), P( 3, 0), P(-1,1), P(1,1)), ()); - TEST(!IsSegmentInCone(P(0,0), P( 0,-1), P(-1,1), P(1,1)), ()); - TEST(!IsSegmentInCone(P(0,0), P( 1,-3), P(-1,1), P(1,1)), ()); - TEST(!IsSegmentInCone(P(0,0), P(-1,-3), P(-1,1), P(1,1)), ()); + TEST(IsSegmentInCone(P(0, 0), P(0, 3), P(-1, -1), P(1, -1)), ()); + TEST(IsSegmentInCone(P(0, 0), P(2, 3), P(-1, -1), P(1, -1)), ()); + TEST(IsSegmentInCone(P(0, 0), P(-3, 3), P(-1, -1), P(1, -1)), ()); + TEST(IsSegmentInCone(P(0, 0), P(-3, 0), P(-1, -1), P(1, -1)), ()); + TEST(IsSegmentInCone(P(0, 0), P(3, 0), P(-1, -1), P(1, -1)), ()); + TEST(!IsSegmentInCone(P(0, 0), P(0, -1), P(-1, -1), P(1, -1)), ()); + TEST(!IsSegmentInCone(P(0, 0), P(1, -3), P(-1, -1), P(1, -1)), ()); + TEST(!IsSegmentInCone(P(0, 0), P(-1, -3), P(-1, -1), P(1, -1)), ()); + + TEST(IsSegmentInCone(P(0, 0), P(0, 3), P(-1, 1), P(1, 1)), ()); + TEST(IsSegmentInCone(P(0, 0), P(2, 3), P(-1, 1), P(1, 1)), ()); + TEST(!IsSegmentInCone(P(0, 0), P(-3, 3), P(-1, 1), P(1, 1)), ()); + TEST(!IsSegmentInCone(P(0, 0), P(-3, 0), P(-1, 1), P(1, 1)), ()); + TEST(!IsSegmentInCone(P(0, 0), P(3, 0), P(-1, 1), P(1, 1)), ()); + TEST(!IsSegmentInCone(P(0, 0), P(0, -1), P(-1, 1), P(1, 1)), ()); + TEST(!IsSegmentInCone(P(0, 0), P(1, -3), P(-1, 1), P(1, 1)), ()); + TEST(!IsSegmentInCone(P(0, 0), P(-1, -3), P(-1, 1), P(1, 1)), ()); } namespace { - template <typename IterT> - void TestDiagonalVisible(IterT beg, IterT end, IterT i0, IterT i1, bool res) - { - TEST_EQUAL ( IsDiagonalVisible(beg, end, i0, i1), res, () ); - TEST_EQUAL ( IsDiagonalVisible(beg, end, i1, i0), res, () ); - } +template <typename IterT> +void TestDiagonalVisible(IterT beg, IterT end, IterT i0, IterT i1, bool res) +{ + TEST_EQUAL(IsDiagonalVisible(beg, end, i0, i1), res, ()); + TEST_EQUAL(IsDiagonalVisible(beg, end, i1, i0), res, ()); +} } UNIT_TEST(IsDiagonalVisible) { - P poly [] = { P(0, 0), P(3, 0), P(3, 2), P(2, 2), P(2, 1), P(0, 1) }; + P poly[] = {P(0, 0), P(3, 0), P(3, 2), P(2, 2), P(2, 1), P(0, 1)}; P const * b = poly; P const * e = poly + ARRAY_SIZE(poly); @@ -63,59 +67,53 @@ UNIT_TEST(IsDiagonalVisible) namespace { - void TestFindStrip(P const * beg, size_t n) - { - size_t const i = FindSingleStrip(n, IsDiagonalVisibleFunctor<P const *>(beg, beg + n)); - TEST_LESS ( i, n, () ); +void TestFindStrip(P const * beg, size_t n) +{ + size_t const i = FindSingleStrip(n, IsDiagonalVisibleFunctor<P const *>(beg, beg + n)); + TEST_LESS(i, n, ()); - vector<size_t> test; - MakeSingleStripFromIndex(i, n, MakeBackInsertFunctor(test)); + vector<size_t> test; + MakeSingleStripFromIndex(i, n, MakeBackInsertFunctor(test)); - sort(test.begin(), test.end()); - unique(test.begin(), test.end()); + sort(test.begin(), test.end()); + unique(test.begin(), test.end()); - TEST_EQUAL ( test.size(), n, () ); - } + TEST_EQUAL(test.size(), n, ()); +} - void TestFindStripMulti(P const * beg, size_t n) - { - for (size_t i = 3; i <= n; ++i) - TestFindStrip(beg, i); - } +void TestFindStripMulti(P const * beg, size_t n) +{ + for (size_t i = 3; i <= n; ++i) + TestFindStrip(beg, i); +} } UNIT_TEST(FindSingleStrip) { { - P poly[] = { P(0, 0), P(3, 0), P(3, 2), P(2, 2), P(2, 1), P(0, 1) }; + P poly[] = {P(0, 0), P(3, 0), P(3, 2), P(2, 2), P(2, 1), P(0, 1)}; TestFindStripMulti(poly, ARRAY_SIZE(poly)); } { - P poly[] = { P(0, 0), P(2, 0), P(2, -1), P(3, -1), P(3, 2), P(2, 2), P(2, 1), P(0, 1) }; + P poly[] = {P(0, 0), P(2, 0), P(2, -1), P(3, -1), P(3, 2), P(2, 2), P(2, 1), P(0, 1)}; size_t const n = ARRAY_SIZE(poly); - TEST_EQUAL ( FindSingleStrip(n, IsDiagonalVisibleFunctor<P const *>(poly, poly + n)), n, () ); + TEST_EQUAL(FindSingleStrip(n, IsDiagonalVisibleFunctor<P const *>(poly, poly + n)), n, ()); } { // Minsk, Bobryiskaya str., 7 - P poly[] = { - P(53.8926922, 27.5460021), - P(53.8926539, 27.5461821), - P(53.8926164, 27.5461591), - P(53.8925455, 27.5464921), - P(53.8925817, 27.5465143), - P(53.8925441, 27.5466909), - P(53.8923762, 27.5465881), - P(53.8925229, 27.5458984) - }; + P poly[] = {P(53.8926922, 27.5460021), P(53.8926539, 27.5461821), P(53.8926164, 27.5461591), + P(53.8925455, 27.5464921), P(53.8925817, 27.5465143), P(53.8925441, 27.5466909), + P(53.8923762, 27.5465881), P(53.8925229, 27.5458984)}; TestFindStrip(poly, ARRAY_SIZE(poly)); } } namespace { -template <typename IterT> void TestPolygonCCW(IterT beg, IterT end) +template <typename IterT> +void TestPolygonCCW(IterT beg, IterT end) { TEST_EQUAL(m2::robust::CheckPolygonSelfIntersections(beg, end), false, ()); @@ -124,7 +122,8 @@ template <typename IterT> void TestPolygonCCW(IterT beg, IterT end) TEST(!IsPolygonCCW(ReverseIterT(end), ReverseIterT(beg)), ()); } -template <typename IterT> void TestPolygonOrReverseCCW(IterT beg, IterT end) +template <typename IterT> +void TestPolygonOrReverseCCW(IterT beg, IterT end) { TEST_EQUAL(m2::robust::CheckPolygonSelfIntersections(beg, end), false, ()); @@ -137,24 +136,24 @@ template <typename IterT> void TestPolygonOrReverseCCW(IterT beg, IterT end) UNIT_TEST(IsPolygonCCW_Smoke) { - P arr1[] = { P(1, 1), P(2, 0), P(3, 2) }; + P arr1[] = {P(1, 1), P(2, 0), P(3, 2)}; TestPolygonCCW(arr1, arr1 + ARRAY_SIZE(arr1)); - P arr2[] = { P(0, 0), P(1, 0), P(0, 1) }; + P arr2[] = {P(0, 0), P(1, 0), P(0, 1)}; TestPolygonCCW(arr2, arr2 + ARRAY_SIZE(arr2)); - P arr3[] = { P(0, 1), P(1, 1), P(1, 0), P(2, 0), P(2, 1), P(1, 1), P(1, 2), P(0, 2) }; + P arr3[] = {P(0, 1), P(1, 1), P(1, 0), P(2, 0), P(2, 1), P(1, 1), P(1, 2), P(0, 2)}; TestPolygonCCW(arr3, arr3 + ARRAY_SIZE(arr3)); } UNIT_TEST(IsPolygonCCW_DataSet) { - P arr[] = { P(27.3018836975098, 61.7740631103516), P(27.2981071472168, 61.7816162109375), - P(27.2962188720703, 61.7831611633301), P(27.293815612793, 61.7814445495605), - P(27.2926139831543, 61.783332824707), P(27.2919273376465, 61.787109375), - P(27.2948455810547, 61.7865943908691), P(27.2958755493164, 61.7883110046387), - P(27.3001670837402, 61.779899597168), P(27.3036003112793, 61.7771530151367), - P(27.3015403747559, 61.7747497558594) }; + P arr[] = {P(27.3018836975098, 61.7740631103516), P(27.2981071472168, 61.7816162109375), + P(27.2962188720703, 61.7831611633301), P(27.293815612793, 61.7814445495605), + P(27.2926139831543, 61.783332824707), P(27.2919273376465, 61.787109375), + P(27.2948455810547, 61.7865943908691), P(27.2958755493164, 61.7883110046387), + P(27.3001670837402, 61.779899597168), P(27.3036003112793, 61.7771530151367), + P(27.3015403747559, 61.7747497558594)}; TestPolygonOrReverseCCW(arr, arr + ARRAY_SIZE(arr)); } @@ -162,16 +161,16 @@ UNIT_TEST(IsPolygonCCW_DataSet) UNIT_TEST(PolygonArea_Smoke) { { - P arr[] = { P (-1, 0), P(0, 1), P(1, -1) }; + P arr[] = {P(-1, 0), P(0, 1), P(1, -1)}; TEST_ALMOST_EQUAL_ULPS(m2::GetTriangleArea(arr[0], arr[1], arr[2]), GetPolygonArea(arr, arr + ARRAY_SIZE(arr)), ()); } { - P arr[] = { P (-5, -7), P(-3.5, 10), P(7.2, 5), P(14, -6.4) }; - TEST_ALMOST_EQUAL_ULPS(m2::GetTriangleArea(arr[0], arr[1], arr[2]) + - m2::GetTriangleArea(arr[2], arr[3], arr[0]), - GetPolygonArea(arr, arr + ARRAY_SIZE(arr)), ()); + P arr[] = {P(-5, -7), P(-3.5, 10), P(7.2, 5), P(14, -6.4)}; + TEST_ALMOST_EQUAL_ULPS( + m2::GetTriangleArea(arr[0], arr[1], arr[2]) + m2::GetTriangleArea(arr[2], arr[3], arr[0]), + GetPolygonArea(arr, arr + ARRAY_SIZE(arr)), ()); } } @@ -205,10 +204,10 @@ UNIT_TEST(IsPolygonCCW_DataSet3) /* UNIT_TEST(IsPolygonCCW_DataSet4) { - P arr[] = { P(37.368060441099174795, 67.293103344080122952), P(37.368017525754879671, 67.292797572252140981), - P(37.367990703664702323, 67.292969568905391498), P(37.368060441099174795, 67.293103344080122952), - P(37.368017525754879671, 67.292797572252140981), P(37.368097992025411713, 67.292830094036474975), - P(37.368216009222180674, 67.292969568905391498) }; + P arr[] = { P(37.368060441099174795, 67.293103344080122952), +P(37.368017525754879671, 67.292797572252140981), P(37.367990703664702323, 67.292969568905391498), +P(37.368060441099174795, 67.293103344080122952), P(37.368017525754879671, 67.292797572252140981), +P(37.368097992025411713, 67.292830094036474975), P(37.368216009222180674, 67.292969568905391498) }; TestPolygonOrReverseCCW(arr, arr + ARRAY_SIZE(arr)); } */ diff --git a/geometry/geometry_tests/tree_test.cpp b/geometry/geometry_tests/tree_test.cpp index 31b4844ba5..1495663049 100644 --- a/geometry/geometry_tests/tree_test.cpp +++ b/geometry/geometry_tests/tree_test.cpp @@ -2,27 +2,39 @@ #include "geometry/tree4d.hpp" +#include <functional> + +using namespace std; namespace { - typedef m2::RectD R; +using R = m2::RectD; + +struct traits_t +{ + m2::RectD LimitRect(m2::RectD const & r) const { return r; } +}; + +using Tree = m4::Tree<R, traits_t>; - struct traits_t { m2::RectD LimitRect(m2::RectD const & r) const { return r; }}; - typedef m4::Tree<R, traits_t> TTree; +template <typename T> +bool RTrue(T const &, T const &) +{ + return true; +} - template <class T> bool RTrue(T const &, T const &) { return true; } - template <class T> bool RFalse(T const &, T const &) { return false; } +template <typename T> +bool RFalse(T const &, T const &) +{ + return false; } +} // namespace UNIT_TEST(Tree4D_Smoke) { - TTree theTree; + Tree theTree; - R arr[] = { - R(0, 0, 1, 1), - R(1, 1, 2, 2), - R(2, 2, 3, 3) - }; + R arr[] = {R(0, 0, 1, 1), R(1, 1, 2, 2), R(2, 2, 3, 3)}; for (size_t i = 0; i < ARRAY_SIZE(arr); ++i) theTree.ReplaceAllInRect(arr[i], &RTrue<R>); @@ -52,31 +64,23 @@ UNIT_TEST(Tree4D_Smoke) UNIT_TEST(Tree4D_ReplaceAllInRect) { - TTree theTree; - - R arr[] = { - R(8, 13, 554, 32), R(555, 13, 700, 32), - R(8, 33, 554, 52), R(555, 33, 700, 52), - R(8, 54, 554, 73), R(555, 54, 700, 73), - R(8, 76, 554, 95), R(555, 76, 700, 95) - }; - - R arr1[] = { - R(3, 23, 257, 42), R(600, 23, 800, 42), - R(3, 43, 257, 62), R(600, 43, 800, 62), - R(3, 65, 257, 84), R(600, 65, 800, 84), - R(3, 87, 257, 106), R(600, 87, 800, 106) - }; + Tree theTree; + + R arr[] = {R(8, 13, 554, 32), R(555, 13, 700, 32), R(8, 33, 554, 52), R(555, 33, 700, 52), + R(8, 54, 554, 73), R(555, 54, 700, 73), R(8, 76, 554, 95), R(555, 76, 700, 95)}; + + R arr1[] = {R(3, 23, 257, 42), R(600, 23, 800, 42), R(3, 43, 257, 62), R(600, 43, 800, 62), + R(3, 65, 257, 84), R(600, 65, 800, 84), R(3, 87, 257, 106), R(600, 87, 800, 106)}; for (size_t i = 0; i < ARRAY_SIZE(arr); ++i) { size_t const count = theTree.GetSize(); theTree.ReplaceAllInRect(arr[i], &RFalse<R>); - TEST_EQUAL ( theTree.GetSize(), count + 1, () ); + TEST_EQUAL(theTree.GetSize(), count + 1, ()); theTree.ReplaceAllInRect(arr1[i], &RFalse<R>); - TEST_EQUAL ( theTree.GetSize(), count + 1, () ); + TEST_EQUAL(theTree.GetSize(), count + 1, ()); } vector<R> test; @@ -87,28 +91,25 @@ UNIT_TEST(Tree4D_ReplaceAllInRect) TEST_EQUAL(test[i], arr[i], ()); } -namespace +namespace { - void CheckInRect(R const * arr, size_t count, R const & searchR, size_t expected) - { - TTree theTree; +void CheckInRect(R const * arr, size_t count, R const & searchR, size_t expected) +{ + Tree theTree; - for (size_t i = 0; i < count; ++i) - theTree.Add(arr[i], arr[i]); + for (size_t i = 0; i < count; ++i) + theTree.Add(arr[i], arr[i]); - vector<R> test; - theTree.ForEachInRect(searchR, MakeBackInsertFunctor(test)); + vector<R> test; + theTree.ForEachInRect(searchR, MakeBackInsertFunctor(test)); - TEST_EQUAL(test.size(), expected, ()); - } + TEST_EQUAL(test.size(), expected, ()); +} } UNIT_TEST(Tree4D_ForEachInRect) { - R arr[] = - { - R(0, 0, 1, 1), R(5, 5, 10, 10), R(-1, -1, 0, 0), R(-10, -10, -5, -5) - }; + R arr[] = {R(0, 0, 1, 1), R(5, 5, 10, 10), R(-1, -1, 0, 0), R(-10, -10, -5, -5)}; CheckInRect(arr, ARRAY_SIZE(arr), R(1, 1, 5, 5), 0); CheckInRect(arr, ARRAY_SIZE(arr), R(-5, -5, -1, -1), 0); CheckInRect(arr, ARRAY_SIZE(arr), R(3, 3, 3, 3), 0); @@ -125,7 +126,6 @@ UNIT_TEST(Tree4D_ForEachInRect) namespace { - struct TestObj : public m2::RectD { int m_id; @@ -137,7 +137,6 @@ struct TestObj : public m2::RectD bool operator==(TestObj const & r) const { return m_id == r.m_id; } }; - } UNIT_TEST(Tree4D_ReplaceEqual) @@ -145,11 +144,7 @@ UNIT_TEST(Tree4D_ReplaceEqual) typedef TestObj T; m4::Tree<T, traits_t> theTree; - T arr[] = { - T(0, 0, 1, 1, 1), - T(1, 1, 2, 2, 2), - T(2, 2, 3, 3, 3) - }; + T arr[] = {T(0, 0, 1, 1, 1), T(1, 1, 2, 2, 2), T(2, 2, 3, 3, 3)}; // 1. for (size_t i = 0; i < ARRAY_SIZE(arr); ++i) diff --git a/geometry/latlon.cpp b/geometry/latlon.cpp index 636a91c054..fa0521a2c3 100644 --- a/geometry/latlon.cpp +++ b/geometry/latlon.cpp @@ -1,6 +1,8 @@ #include "latlon.hpp" -#include "std/sstream.hpp" +#include <sstream> + +using namespace std; namespace ms { @@ -18,10 +20,7 @@ string DebugPrint(LatLon const & t) return out.str(); } -bool LatLon::operator == (ms::LatLon const & p) const -{ - return lat == p.lat && lon == p.lon; -} +bool LatLon::operator==(ms::LatLon const & p) const { return lat == p.lat && lon == p.lon; } bool LatLon::EqualDxDy(LatLon const & p, double eps) const { diff --git a/geometry/latlon.hpp b/geometry/latlon.hpp index 3204eec693..ceff8cbe31 100644 --- a/geometry/latlon.hpp +++ b/geometry/latlon.hpp @@ -2,11 +2,10 @@ #include "base/math.hpp" -#include "std/string.hpp" +#include <string> namespace ms { - /// \brief Class for representing WGS point. class LatLon { @@ -24,19 +23,15 @@ public: static LatLon Zero() { return LatLon(0., 0.); } - bool operator == (ms::LatLon const & p) const; + bool operator==(ms::LatLon const & p) const; bool EqualDxDy(LatLon const & p, double eps) const; struct Hash { - size_t operator()(ms::LatLon const & p) const - { - return my::Hash(p.lat, p.lon); - } + size_t operator()(ms::LatLon const & p) const { return my::Hash(p.lat, p.lon); } }; }; -string DebugPrint(LatLon const & t); - +std::string DebugPrint(LatLon const & t); } // namespace ms diff --git a/geometry/line2d.hpp b/geometry/line2d.hpp index cfce8d0858..fc7b544e1b 100644 --- a/geometry/line2d.hpp +++ b/geometry/line2d.hpp @@ -15,17 +15,12 @@ struct Line2D explicit Line2D(Segment2D const & segment) : m_point(segment.m_u), m_direction(segment.Dir()) {} - Line2D(PointD const & point, PointD const & direction) - : m_point(point), m_direction(direction) - { - } + Line2D(PointD const & point, PointD const & direction) : m_point(point), m_direction(direction) {} PointD m_point; PointD m_direction; }; -std::string DebugPrint(Line2D const & line); - struct LineIntersector { struct Result @@ -47,6 +42,7 @@ struct LineIntersector static Result Intersect(Line2D const & lhs, Line2D const & rhs, double eps); }; +std::string DebugPrint(Line2D const & line); std::string DebugPrint(LineIntersector::Result::Type type); std::string DebugPrint(LineIntersector::Result const & result); } // namespace m2 diff --git a/geometry/mercator.cpp b/geometry/mercator.cpp index df93104f85..9f46e5585a 100644 --- a/geometry/mercator.cpp +++ b/geometry/mercator.cpp @@ -2,24 +2,28 @@ #include "geometry/distance_on_sphere.hpp" +#include <algorithm> +#include <cmath> + +using namespace std; + double MercatorBounds::minX = -180; double MercatorBounds::maxX = 180; double MercatorBounds::minY = -180; double MercatorBounds::maxY = 180; -m2::RectD MercatorBounds::MetresToXY(double lon, double lat, - double lonMetresR, double latMetresR) +m2::RectD MercatorBounds::MetresToXY(double lon, double lat, double lonMetresR, double latMetresR) { double const latDegreeOffset = latMetresR * degreeInMetres; double const minLat = max(-90.0, lat - latDegreeOffset); - double const maxLat = min( 90.0, lat + latDegreeOffset); + double const maxLat = min(90.0, lat + latDegreeOffset); double const cosL = max(cos(my::DegToRad(max(fabs(minLat), fabs(maxLat)))), 0.00001); - ASSERT_GREATER ( cosL, 0.0, () ); + ASSERT_GREATER(cosL, 0.0, ()); double const lonDegreeOffset = lonMetresR * degreeInMetres / cosL; double const minLon = max(-180.0, lon - lonDegreeOffset); - double const maxLon = min( 180.0, lon + lonDegreeOffset); + double const maxLon = min(180.0, lon + lonDegreeOffset); return m2::RectD(FromLatLon(minLat, minLon), FromLatLon(maxLat, maxLon)); } @@ -33,7 +37,7 @@ m2::PointD MercatorBounds::GetSmPoint(m2::PointD const & pt, double lonMetresR, double const newLat = min(90.0, max(-90.0, lat + latDegreeOffset)); double const cosL = max(cos(my::DegToRad(newLat)), 0.00001); - ASSERT_GREATER ( cosL, 0.0, () ); + ASSERT_GREATER(cosL, 0.0, ()); double const lonDegreeOffset = lonMetresR * degreeInMetres / cosL; double const newLon = min(180.0, max(-180.0, lon + lonDegreeOffset)); @@ -46,7 +50,8 @@ double MercatorBounds::DistanceOnEarth(m2::PointD const & p1, m2::PointD const & return ms::DistanceOnEarth(ToLatLon(p1), ToLatLon(p2)); } -double MercatorBounds::AreaOnEarth(m2::PointD const & p1, m2::PointD const & p2, m2::PointD const & p3) +double MercatorBounds::AreaOnEarth(m2::PointD const & p1, m2::PointD const & p2, + m2::PointD const & p3) { return ms::AreaOnEarth(ToLatLon(p1), ToLatLon(p2), ToLatLon(p3)); } diff --git a/geometry/mercator.hpp b/geometry/mercator.hpp index acabe3123a..cee5cff05f 100644 --- a/geometry/mercator.hpp +++ b/geometry/mercator.hpp @@ -1,4 +1,5 @@ #pragma once + #include "geometry/latlon.hpp" #include "geometry/point2d.hpp" #include "geometry/rect2d.hpp" @@ -12,73 +13,45 @@ struct MercatorBounds static double minY; static double maxY; - inline static m2::RectD FullRect() { return m2::RectD(minX, minY, maxX, maxY); } + static m2::RectD FullRect() { return m2::RectD(minX, minY, maxX, maxY); } - inline static bool ValidLon(double d) - { - return my::between_s(-180.0, 180.0, d); - } - inline static bool ValidLat(double d) - { - return my::between_s(-90.0, 90.0, d); - } + static bool ValidLon(double d) { return my::between_s(-180.0, 180.0, d); } + static bool ValidLat(double d) { return my::between_s(-90.0, 90.0, d); } - inline static bool ValidX(double d) - { - return my::between_s(minX, maxX, d); - } - inline static bool ValidY(double d) - { - return my::between_s(minY, maxY, d); - } + static bool ValidX(double d) { return my::between_s(minX, maxX, d); } + static bool ValidY(double d) { return my::between_s(minY, maxY, d); } - inline static double ClampX(double d) - { - return my::clamp(d, minX, maxX); - } - inline static double ClampY(double d) - { - return my::clamp(d, minY, maxY); - } + static double ClampX(double d) { return my::clamp(d, minX, maxX); } + static double ClampY(double d) { return my::clamp(d, minY, maxY); } - inline static double YToLat(double y) - { - return my::RadToDeg(2.0 * atan(tanh(0.5 * my::DegToRad(y)))); - } + static double YToLat(double y) { return my::RadToDeg(2.0 * atan(tanh(0.5 * my::DegToRad(y)))); } - inline static double LatToY(double lat) + static double LatToY(double lat) { double const sinx = sin(my::DegToRad(my::clamp(lat, -86.0, 86.0))); double const res = my::RadToDeg(0.5 * log((1.0 + sinx) / (1.0 - sinx))); return ClampY(res); } - inline static double XToLon(double x) - { - return x; - } + static double XToLon(double x) { return x; } - inline static double LonToX(double lon) - { - return lon; - } + static double LonToX(double lon) { return lon; } static double constexpr degreeInMetres = 360.0 / 40008245; /// @name Get rect for center point (lon, lat) and dimensions in metres. //@{ /// @return mercator rect. - static m2::RectD MetresToXY(double lon, double lat, - double lonMetresR, double latMetresR); + static m2::RectD MetresToXY(double lon, double lat, double lonMetresR, double latMetresR); - inline static m2::RectD MetresToXY(double lon, double lat, double metresR) + static m2::RectD MetresToXY(double lon, double lat, double metresR) { return MetresToXY(lon, lat, metresR, metresR); } //@} - inline static m2::RectD RectByCenterXYAndSizeInMeters(double centerX, double centerY, - double sizeX, double sizeY) + static m2::RectD RectByCenterXYAndSizeInMeters(double centerX, double centerY, double sizeX, + double sizeY) { ASSERT_GREATER_OR_EQUAL(sizeX, 0, ()); ASSERT_GREATER_OR_EQUAL(sizeY, 0, ()); @@ -86,7 +59,7 @@ struct MercatorBounds return MetresToXY(XToLon(centerX), YToLat(centerY), sizeX, sizeY); } - inline static m2::RectD RectByCenterXYAndSizeInMeters(m2::PointD const & center, double size) + static m2::RectD RectByCenterXYAndSizeInMeters(m2::PointD const & center, double size) { return RectByCenterXYAndSizeInMeters(center.x, center.y, size, size); } @@ -95,34 +68,34 @@ struct MercatorBounds static double constexpr GetCellID2PointAbsEpsilon() { return 1.0E-4; } - inline static m2::PointD FromLatLon(double lat, double lon) + static m2::PointD FromLatLon(double lat, double lon) { return m2::PointD(LonToX(lon), LatToY(lat)); } - inline static m2::PointD FromLatLon(ms::LatLon const & point) + static m2::PointD FromLatLon(ms::LatLon const & point) { return FromLatLon(point.lat, point.lon); } - inline static m2::RectD RectByCenterLatLonAndSizeInMeters(double lat, double lon, double size) + static m2::RectD RectByCenterLatLonAndSizeInMeters(double lat, double lon, double size) { return RectByCenterXYAndSizeInMeters(FromLatLon(lat, lon), size); } - inline static ms::LatLon ToLatLon(m2::PointD const & point) + static ms::LatLon ToLatLon(m2::PointD const & point) { return {YToLat(point.y), XToLon(point.x)}; } /// Converts lat lon rect to mercator one - inline static m2::RectD FromLatLonRect(m2::RectD const & latLonRect) + static m2::RectD FromLatLonRect(m2::RectD const & latLonRect) { return m2::RectD(FromLatLon(latLonRect.minY(), latLonRect.minX()), FromLatLon(latLonRect.maxY(), latLonRect.maxX())); } - inline static m2::RectD ToLatLonRect(m2::RectD const & mercatorRect) + static m2::RectD ToLatLonRect(m2::RectD const & mercatorRect) { return m2::RectD(YToLat(mercatorRect.minY()), XToLon(mercatorRect.minX()), YToLat(mercatorRect.maxY()), XToLon(mercatorRect.maxX())); diff --git a/geometry/packer.cpp b/geometry/packer.cpp index 183af8d4e8..6b56b86966 100644 --- a/geometry/packer.cpp +++ b/geometry/packer.cpp @@ -3,106 +3,122 @@ #include "base/assert.hpp" #include "base/logging.hpp" +using namespace std; + namespace m2 { - Packer::Packer() - : m_currentX(0), - m_currentY(0), - m_yStep(0), - m_width(0), - m_height(0), - m_currentHandle(0), - m_maxHandle(0), - m_invalidHandle(0x00FFFFFF) - {} - - Packer::Packer(unsigned width, unsigned height, uint32_t maxHandle) - : m_currentX(0), - m_currentY(0), - m_yStep(0), - m_width(width), - m_height(height), - m_currentHandle(0), - m_maxHandle(maxHandle), - m_invalidHandle(0x00FFFFFF) - { - } - - uint32_t Packer::invalidHandle() const - { - return m_invalidHandle; - } - - Packer::handle_t Packer::pack(unsigned width, unsigned height) - { - ASSERT(width <= m_width, ()); - ASSERT(height <= m_height, ()); +Packer::Packer() + : m_currentX(0) + , m_currentY(0) + , m_yStep(0) + , m_width(0) + , m_height(0) + , m_currentHandle(0) + , m_maxHandle(0) + , m_invalidHandle(0x00FFFFFF) +{ +} - if ((width > m_width) || (height > m_height)) - return m_invalidHandle; +Packer::Packer(unsigned width, unsigned height, uint32_t maxHandle) + : m_currentX(0) + , m_currentY(0) + , m_yStep(0) + , m_width(width) + , m_height(height) + , m_currentHandle(0) + , m_maxHandle(maxHandle) + , m_invalidHandle(0x00FFFFFF) +{ +} - /// checking whether there is enough space on X axis +uint32_t Packer::invalidHandle() const { return m_invalidHandle; } - if (m_currentX + width > m_width) - { - m_currentY += m_yStep; - m_currentX = 0; - m_yStep = 0; - } +Packer::handle_t Packer::pack(unsigned width, unsigned height) +{ + ASSERT(width <= m_width, ()); + ASSERT(height <= m_height, ()); - /// checking whether there is enough space on Y axis - if (m_currentY + height > m_height) - { - /// texture overflow detected. all packed rects should be forgotten. - callOverflowFns(); - reset(); - } - /// check handleOverflow - if (m_currentHandle == m_maxHandle) - { - /// handles overflow detected. all packed rects should be forgotten. - callOverflowFns(); - reset(); - m_currentHandle = 0; - } + if ((width > m_width) || (height > m_height)) + return m_invalidHandle; - /// can pack - m_yStep = max(height, m_yStep); - handle_t curHandle = m_currentHandle++; - m_rects[curHandle] = m2::RectU(m_currentX, m_currentY, m_currentX + width, m_currentY + height); - m_currentX += width; + /// checking whether there is enough space on X axis - return curHandle; + if (m_currentX + width > m_width) + { + m_currentY += m_yStep; + m_currentX = 0; + m_yStep = 0; } - Packer::handle_t Packer::freeHandle() + /// checking whether there is enough space on Y axis + if (m_currentY + height > m_height) { - if (m_currentHandle == m_maxHandle) - { - callOverflowFns(); - reset(); - m_currentHandle = 0; - } - - return m_currentHandle++; + /// texture overflow detected. all packed rects should be forgotten. + callOverflowFns(); + reset(); + } + /// check handleOverflow + if (m_currentHandle == m_maxHandle) + { + /// handles overflow detected. all packed rects should be forgotten. + callOverflowFns(); + reset(); + m_currentHandle = 0; } - bool Packer::hasRoom(unsigned width, unsigned height) const + /// can pack + m_yStep = max(height, m_yStep); + handle_t curHandle = m_currentHandle++; + m_rects[curHandle] = m2::RectU(m_currentX, m_currentY, m_currentX + width, m_currentY + height); + m_currentX += width; + + return curHandle; +} + +Packer::handle_t Packer::freeHandle() +{ + if (m_currentHandle == m_maxHandle) { - return ((m_width >= width) && (m_height - m_currentY - m_yStep >= height)) - || ((m_width - m_currentX >= width ) && (m_height - m_currentY >= height)); + callOverflowFns(); + reset(); + m_currentHandle = 0; } - bool Packer::hasRoom(m2::PointU const * sizes, size_t cnt) const + return m_currentHandle++; +} + +bool Packer::hasRoom(unsigned width, unsigned height) const +{ + return ((m_width >= width) && (m_height - m_currentY - m_yStep >= height)) || + ((m_width - m_currentX >= width) && (m_height - m_currentY >= height)); +} + +bool Packer::hasRoom(m2::PointU const * sizes, size_t cnt) const +{ + unsigned currentX = m_currentX; + unsigned currentY = m_currentY; + unsigned yStep = m_yStep; + + for (unsigned i = 0; i < cnt; ++i) { - unsigned currentX = m_currentX; - unsigned currentY = m_currentY; - unsigned yStep = m_yStep; + unsigned width = sizes[i].x; + unsigned height = sizes[i].y; - for (unsigned i = 0; i < cnt; ++i) + if (width <= m_width - currentX) + { + if (height <= m_height - currentY) + { + yStep = max(height, yStep); + currentX += width; + } + else + return false; + } + else { - unsigned width = sizes[i].x; - unsigned height = sizes[i].y; + currentX = 0; + currentY += yStep; + yStep = 0; if (width <= m_width - currentX) { @@ -114,70 +130,48 @@ namespace m2 else return false; } - else - { - currentX = 0; - currentY += yStep; - yStep = 0; - - if (width <= m_width - currentX) - { - if (height <= m_height - currentY) - { - yStep = max(height, yStep); - currentX += width; - } - else - return false; - } - } } - - return true; } - bool Packer::isPacked(handle_t handle) - { - return m_rects.find(handle) != m_rects.end(); - } + return true; +} - Packer::find_result_t Packer::find(handle_t handle) const - { - rects_t::const_iterator it = m_rects.find(handle); - std::pair<bool, m2::RectU> res; - res.first = (it != m_rects.end()); - if (res.first) - res.second = it->second; - return res; - } +bool Packer::isPacked(handle_t handle) { return m_rects.find(handle) != m_rects.end(); } - void Packer::remove(handle_t handle) - { - m_rects.erase(handle); - } +Packer::find_result_t Packer::find(handle_t handle) const +{ + rects_t::const_iterator it = m_rects.find(handle); + std::pair<bool, m2::RectU> res; + res.first = (it != m_rects.end()); + if (res.first) + res.second = it->second; + return res; +} - void Packer::reset() - { - m_rects.clear(); - m_currentX = 0; - m_currentY = 0; - m_yStep = 0; - m_currentHandle = 0; - } +void Packer::remove(handle_t handle) { m_rects.erase(handle); } - void Packer::addOverflowFn(overflowFn fn, int priority) - { - m_overflowFns.push(std::pair<size_t, overflowFn>(priority, fn)); - } +void Packer::reset() +{ + m_rects.clear(); + m_currentX = 0; + m_currentY = 0; + m_yStep = 0; + m_currentHandle = 0; +} - void Packer::callOverflowFns() +void Packer::addOverflowFn(overflowFn fn, int priority) +{ + m_overflowFns.push(std::pair<size_t, overflowFn>(priority, fn)); +} + +void Packer::callOverflowFns() +{ + LOG(LDEBUG, ("Texture|Handles Overflow")); + overflowFns handlersCopy = m_overflowFns; + while (!handlersCopy.empty()) { - LOG(LDEBUG, ("Texture|Handles Overflow")); - overflowFns handlersCopy = m_overflowFns; - while (!handlersCopy.empty()) - { - handlersCopy.top().second(); - handlersCopy.pop(); - } + handlersCopy.top().second(); + handlersCopy.pop(); } } +} // namespace m2 diff --git a/geometry/packer.hpp b/geometry/packer.hpp index 3efe051abf..4944fdd3cc 100644 --- a/geometry/packer.hpp +++ b/geometry/packer.hpp @@ -2,99 +2,97 @@ #include "geometry/rect2d.hpp" -#include "std/list.hpp" -#include "std/map.hpp" -#include "std/function.hpp" -#include "std/queue.hpp" -#include "std/utility.hpp" -#include "std/vector.hpp" - +#include <cstdint> +#include <functional> +#include <list> +#include <map> +#include <queue> +#include <utility> +#include <vector> namespace m2 { - template <typename pair_t> - struct first_less - { - bool operator()(pair_t const & first, pair_t const & second) - { - return first.first < second.first; - } - }; - - /// The simplest row-by-row packer. - /// When there is no free room all the packing - /// rect is cleared and the process is started again. - class Packer +template <typename pair_t> +struct first_less +{ + bool operator()(pair_t const & first, pair_t const & second) { - public: - - typedef function<void()> overflowFn; - - typedef priority_queue<pair<size_t, overflowFn>, vector<pair<size_t, overflowFn> >, first_less<pair<size_t, overflowFn> > > overflowFns; - - typedef uint32_t handle_t; - typedef std::pair<bool, m2::RectU> find_result_t; + return first.first < second.first; + } +}; + +/// The simplest row-by-row packer. +/// When there is no free room all the packing +/// rect is cleared and the process is started again. +class Packer +{ +public: + using overflowFn = std::function<void()>; - private: + using overflowFns = + std::priority_queue<std::pair<size_t, overflowFn>, std::vector<std::pair<size_t, overflowFn>>, + first_less<std::pair<size_t, overflowFn>>>; - unsigned m_currentX; - unsigned m_currentY; - unsigned m_yStep; + using handle_t = uint32_t; + using find_result_t = std::pair<bool, m2::RectU>; - unsigned m_width; - unsigned m_height; + Packer(); - overflowFns m_overflowFns; + /// create a packer on a rectangular area of (0, 0, width, height) dimensions + Packer(unsigned width, unsigned height, uint32_t maxHandle = 0xFFFF - 1); - handle_t m_currentHandle; + /// reset the state of the packer + void reset(); - typedef map<handle_t, m2::RectU> rects_t; + /// add overflow handler. + /// @param priority handlers with higher priority value are called first. + void addOverflowFn(overflowFn fn, int priority); - rects_t m_rects; + /// pack the rect with dimensions width X height on a free area. + /// when there is no free area - find it somehow(depending on a packer implementation, + /// the simplest one will just clear the whole rect and start the packing process again). + handle_t pack(unsigned width, unsigned height); - void callOverflowFns(); + /// return free handle + handle_t freeHandle(); - uint32_t m_maxHandle; - uint32_t m_invalidHandle; + /// Does we have room to pack another rectangle? + bool hasRoom(unsigned width, unsigned height) const; - public: + /// Does we have room to pack a sequence of rectangles? + bool hasRoom(m2::PointU const * sizes, size_t cnt) const; - Packer(); + /// is the handle present on the texture. + bool isPacked(handle_t handle); - /// create a packer on a rectangular area of (0, 0, width, height) dimensions - Packer(unsigned width, unsigned height, uint32_t maxHandle = 0xFFFF - 1); + /// find the packed area by the handle. + find_result_t find(handle_t handle) const; - /// reset the state of the packer - void reset(); + /// remove the handle from the list of active handles. + void remove(handle_t handle); - /// add overflow handler. - /// @param priority handlers with higher priority value are called first. - void addOverflowFn(overflowFn fn, int priority); + /// get an invalid handle + uint32_t invalidHandle() const; - /// pack the rect with dimensions width X height on a free area. - /// when there is no free area - find it somehow(depending on a packer implementation, - /// the simplest one will just clear the whole rect and start the packing process again). - handle_t pack(unsigned width, unsigned height); +private: + using rects_t = std::map<handle_t, m2::RectU>; - /// return free handle - handle_t freeHandle(); + void callOverflowFns(); - /// Does we have room to pack another rectangle? - bool hasRoom(unsigned width, unsigned height) const; + unsigned m_currentX; + unsigned m_currentY; + unsigned m_yStep; - /// Does we have room to pack a sequence of rectangles? - bool hasRoom(m2::PointU const * sizes, size_t cnt) const; + unsigned m_width; + unsigned m_height; - /// is the handle present on the texture. - bool isPacked(handle_t handle); + overflowFns m_overflowFns; - /// find the packed area by the handle. - find_result_t find(handle_t handle) const; + handle_t m_currentHandle; - /// remove the handle from the list of active handles. - void remove(handle_t handle); + rects_t m_rects; - /// get an invalid handle - uint32_t invalidHandle() const; - }; -} + uint32_t m_maxHandle; + uint32_t m_invalidHandle; +}; +} // namespace m2 diff --git a/geometry/point2d.hpp b/geometry/point2d.hpp index 7afec7c336..3b46e05150 100644 --- a/geometry/point2d.hpp +++ b/geometry/point2d.hpp @@ -5,331 +5,295 @@ #include "base/math.hpp" #include "base/matrix.hpp" -#include "std/array.hpp" -#include "std/cmath.hpp" -#include "std/functional.hpp" -#include "std/sstream.hpp" -#include "std/typeinfo.hpp" - +#include <array> +#include <cmath> +#include <functional> +#include <sstream> +#include <typeinfo> namespace m2 { - template <typename T> - class Point - { - public: - using value_type = T; - - T x, y; - - Point() : x(T()), y(T()) {} - - Point(T x_, T y_) : x(x_), y(y_) {} - - template <typename U> - explicit Point(Point<U> const & u) : x(u.x), y(u.y) {} - - static Point<T> Zero() { return Point<T>(0, 0); } - - bool EqualDxDy(Point<T> const & p, T eps) const - { - return ((fabs(x - p.x) < eps) && (fabs(y - p.y) < eps)); - } - - T SquaredLength(Point<T> const & p) const { return pow(x - p.x, 2) + pow(y - p.y, 2); } - - T SquaredLength() const { return x * x + y * y; } - - double Length(Point<T> const & p) const - { - return sqrt(SquaredLength(p)); - } - - bool IsAlmostZero() const - { - return AlmostEqualULPs(*this, Point<T>(0,0)); - } - - Point<T> Move(T len, T ang) const - { - return Point<T>(x + len * cos(ang), y + len * sin(ang)); - } - - Point<T> Move(T len, T angSin, T angCos) const - { - return m2::Point<T>(x + len * angCos, y + len * angSin); - } - - Point<T> const & operator-=(Point<T> const & a) - { - x -= a.x; - y -= a.y; - return *this; - } - - Point<T> const & operator+=(Point<T> const & a) - { - x += a.x; - y += a.y; - return *this; - } - - template <typename U> - Point<T> const & operator*=(U const & k) - { - x = static_cast<T>(x * k); - y = static_cast<T>(y * k); - return *this; - } - - template <typename U> - Point<T> const & operator=(Point<U> const & a) - { - x = static_cast<T>(a.x); - y = static_cast<T>(a.y); - return *this; - } - - bool operator==(m2::Point<T> const & p) const - { - return x == p.x && y == p.y; - } - - bool operator!=(m2::Point<T> const & p) const - { - return !(*this == p); - } - - m2::Point<T> operator+(m2::Point<T> const & pt) const - { - return m2::Point<T>(x + pt.x, y + pt.y); - } - - m2::Point<T> operator-(m2::Point<T> const & pt) const - { - return m2::Point<T>(x - pt.x, y - pt.y); - } - - m2::Point<T> operator-() const - { - return m2::Point<T>(-x, -y); - } - - m2::Point<T> operator*(T scale) const - { - return m2::Point<T>(x * scale, y * scale); - } - - m2::Point<T> const operator*(math::Matrix<T, 3, 3> const & m) const - { - m2::Point<T> res; - res.x = x * m(0, 0) + y * m(1, 0) + m(2, 0); - res.y = x * m(0, 1) + y * m(1, 1) + m(2, 1); - return res; - } - - m2::Point<T> operator/(T scale) const - { - return m2::Point<T>(x / scale, y / scale); - } - - m2::Point<T> mid(m2::Point<T> const & p) const - { - return m2::Point<T>((x + p.x) * 0.5, (y + p.y) * 0.5); - } - - /// @name VectorOperationsOnPoint - double Length() const - { - return sqrt(SquaredLength()); - } - - Point<T> Normalize() const - { - ASSERT(!IsAlmostZero(), ()); - double const module = this->Length(); - return Point<T>(x / module, y / module); - } - - std::pair<Point<T>, Point<T> > Normals(T prolongationFactor = 1) const - { - T const prolongatedX = prolongationFactor * x; - T const prolongatedY = prolongationFactor * y; - return std::pair<Point<T>, Point<T> >(Point<T>(static_cast<T>(-prolongatedY), static_cast<T>(prolongatedX)), - Point<T>(static_cast<T>(prolongatedY), static_cast<T>(-prolongatedX))); - } - - m2::Point<T> const & operator *= (math::Matrix<T, 3, 3> const & m) - { - T tempX = x; - x = tempX * m(0, 0) + y * m(1, 0) + m(2, 0); - y = tempX * m(0, 1) + y * m(1, 1) + m(2, 1); - return *this; - } - - void Rotate(double angle) - { - T cosAngle = cos(angle); - T sinAngle = sin(angle); - T oldX = x; - x = cosAngle * oldX - sinAngle * y; - y = sinAngle * oldX + cosAngle * y; - } - - // Returns vector rotated 90 degrees counterclockwise. - Point Ort() const { return Point(-y, x); } - - void Transform(m2::Point<T> const & org, - m2::Point<T> const & dx, m2::Point<T> const & dy) - { - T oldX = x; - x = org.x + oldX * dx.x + y * dy.x; - y = org.y + oldX * dx.y + y * dy.y; - } - - struct Hash - { - size_t operator()(m2::Point<T> const & p) const - { - return my::Hash(p.x, p.y); - } - }; - }; +template <typename T> +class Point +{ +public: + using value_type = T; + + T x, y; - template <typename T> - inline Point<T> const operator- (Point<T> const & a, Point<T> const & b) + Point() : x(T()), y(T()) {} + + Point(T x_, T y_) : x(x_), y(y_) {} + + template <typename U> + explicit Point(Point<U> const & u) : x(u.x), y(u.y) { - return Point<T>(a.x - b.x, a.y - b.y); } - template <typename T> - inline Point<T> const operator+ (Point<T> const & a, Point<T> const & b) + static Point<T> Zero() { return Point<T>(0, 0); } + + bool EqualDxDy(Point<T> const & p, T eps) const { - return Point<T>(a.x + b.x, a.y + b.y); + return ((fabs(x - p.x) < eps) && (fabs(y - p.y) < eps)); } - // Dot product of a and b, equals to |a|*|b|*cos(angle_between_a_and_b). - template <typename T> - T const DotProduct(Point<T> const & a, Point<T> const & b) + T SquaredLength(Point<T> const & p) const { return pow(x - p.x, 2.0) + pow(y - p.y, 2.0); } + + T SquaredLength() const { return x * x + y * y; } + + double Length(Point<T> const & p) const { return sqrt(SquaredLength(p)); } + + bool IsAlmostZero() const { return AlmostEqualULPs(*this, Point<T>(0, 0)); } + + Point<T> Move(T len, T ang) const { return Point<T>(x + len * cos(ang), y + len * sin(ang)); } + + Point<T> Move(T len, T angSin, T angCos) const { - return a.x * b.x + a.y * b.y; + return m2::Point<T>(x + len * angCos, y + len * angSin); } - // Value of cross product of a and b, equals to |a|*|b|*sin(angle_between_a_and_b). - template <typename T> - T const CrossProduct(Point<T> const & a, Point<T> const & b) + Point<T> const & operator-=(Point<T> const & a) { - return a.x * b.y - a.y * b.x; + x -= a.x; + y -= a.y; + return *this; } - template <typename T> - Point<T> const Rotate(Point<T> const & pt, T a) + Point<T> const & operator+=(Point<T> const & a) { - Point<T> res(pt); - res.Rotate(a); - return res; + x += a.x; + y += a.y; + return *this; } - template <typename T, typename U> - Point<T> const Shift(Point<T> const & pt, U const & dx, U const & dy) + template <typename U> + Point<T> const & operator*=(U const & k) { - return Point<T>(pt.x + dx, pt.y + dy); + x = static_cast<T>(x * k); + y = static_cast<T>(y * k); + return *this; } - template <typename T, typename U> - Point<T> const Shift(Point<T> const & pt, Point<U> const & offset) + template <typename U> + Point<T> const & operator=(Point<U> const & a) { - return Shift(pt, offset.x, offset.y); + x = static_cast<T>(a.x); + y = static_cast<T>(a.y); + return *this; } - template <typename T> - Point<T> const Floor(Point<T> const & pt) + bool operator==(m2::Point<T> const & p) const { return x == p.x && y == p.y; } + + bool operator!=(m2::Point<T> const & p) const { return !(*this == p); } + + m2::Point<T> operator+(m2::Point<T> const & pt) const { return m2::Point<T>(x + pt.x, y + pt.y); } + + m2::Point<T> operator-(m2::Point<T> const & pt) const { return m2::Point<T>(x - pt.x, y - pt.y); } + + m2::Point<T> operator-() const { return m2::Point<T>(-x, -y); } + + m2::Point<T> operator*(T scale) const { return m2::Point<T>(x * scale, y * scale); } + + m2::Point<T> const operator*(math::Matrix<T, 3, 3> const & m) const { - Point<T> res; - res.x = floor(pt.x); - res.y = floor(pt.y); + m2::Point<T> res; + res.x = x * m(0, 0) + y * m(1, 0) + m(2, 0); + res.y = x * m(0, 1) + y * m(1, 1) + m(2, 1); return res; } - template <typename T> std::string DebugPrint(m2::Point<T> const & p) - { - ostringstream out; - out.precision(20); - out << "m2::Point<" << typeid(T).name() << ">(" << p.x << ", " << p.y << ")"; - return out.str(); - } + m2::Point<T> operator/(T scale) const { return m2::Point<T>(x / scale, y / scale); } - template <typename T> - bool AlmostEqualAbs(m2::Point<T> const & a, m2::Point<T> const & b, double const eps) + m2::Point<T> mid(m2::Point<T> const & p) const { - return my::AlmostEqualAbs(a.x, b.x, eps) && my::AlmostEqualAbs(a.y, b.y, eps); + return m2::Point<T>((x + p.x) * 0.5, (y + p.y) * 0.5); } - template <typename T> - bool AlmostEqualULPs(m2::Point<T> const & a, m2::Point<T> const & b, unsigned int maxULPs = 256) + /// @name VectorOperationsOnPoint + double Length() const { return sqrt(SquaredLength()); } + + Point<T> Normalize() const { - return my::AlmostEqualULPs(a.x, b.x, maxULPs) && my::AlmostEqualULPs(a.y, b.y, maxULPs); + ASSERT(!IsAlmostZero(), ()); + double const length = this->Length(); + return Point<T>(x / length, y / length); } - /// Calculate three points of a triangle (p1, p2 and p3) which give an arrow that - /// presents an equilateral triangle with the median - /// starting at point b and having direction b,e. - /// The height of the equilateral triangle is l and the base of the triangle is 2 * w - template <typename T, typename TT, typename PointT = Point<T>> - void GetArrowPoints(PointT const & b, PointT const & e, T w, T l, array<Point<TT>, 3> & arrPnts) + std::pair<Point<T>, Point<T>> Normals(T prolongationFactor = 1) const { - ASSERT(!m2::AlmostEqualULPs(b, e), ()); - - PointT const beVec = e - b; - PointT beNormalizedVec = beVec.Normalize(); - std::pair<PointT, PointT > beNormVecs = beNormalizedVec.Normals(w); - - arrPnts[0] = e + beNormVecs.first; - arrPnts[1] = e + beNormalizedVec * l; - arrPnts[2] = e + beNormVecs.second; + T const prolongatedX = prolongationFactor * x; + T const prolongatedY = prolongationFactor * y; + return std::pair<Point<T>, Point<T>>( + Point<T>(static_cast<T>(-prolongatedY), static_cast<T>(prolongatedX)), + Point<T>(static_cast<T>(prolongatedY), static_cast<T>(-prolongatedX))); } - /// Returns a point which is belonged to the segment p1, p2 with respet the indent shiftFromP1 from p1. - /// If shiftFromP1 is more the distance between (p1, p2) it returns p2. - /// If shiftFromP1 is less or equal zero it returns p1. - template <typename T> - Point<T> PointAtSegment(Point<T> const & p1, Point<T> const & p2, T shiftFromP1) + m2::Point<T> const & operator*=(math::Matrix<T, 3, 3> const & m) { - Point<T> p12 = p2 - p1; - shiftFromP1 = my::clamp(shiftFromP1, static_cast<T>(0.0), static_cast<T>(p12.Length())); - return p1 + p12.Normalize() * shiftFromP1; + T tempX = x; + x = tempX * m(0, 0) + y * m(1, 0) + m(2, 0); + y = tempX * m(0, 1) + y * m(1, 1) + m(2, 1); + return *this; } - template <class TArchive, class PointT> - TArchive & operator >> (TArchive & ar, m2::Point<PointT> & pt) + void Rotate(double angle) { - ar >> pt.x; - ar >> pt.y; - return ar; + T cosAngle = cos(angle); + T sinAngle = sin(angle); + T oldX = x; + x = cosAngle * oldX - sinAngle * y; + y = sinAngle * oldX + cosAngle * y; } - template <class TArchive, class PointT> - TArchive & operator<<(TArchive & ar, m2::Point<PointT> const & pt) + // Returns vector rotated 90 degrees counterclockwise. + Point Ort() const { return Point(-y, x); } + + void Transform(m2::Point<T> const & org, m2::Point<T> const & dx, m2::Point<T> const & dy) { - ar << pt.x; - ar << pt.y; - return ar; + T oldX = x; + x = org.x + oldX * dx.x + y * dy.x; + y = org.y + oldX * dx.y + y * dy.y; } - template <typename T> - bool operator<(Point<T> const & l, Point<T> const & r) + struct Hash { - if (l.x != r.x) - return l.x < r.x; - return l.y < r.y; - } + size_t operator()(m2::Point<T> const & p) const { return my::Hash(p.x, p.y); } + }; +}; + +using PointF = Point<float>; +using PointD = Point<double>; +using PointU = Point<uint32_t>; +using PointU64 = Point<uint64_t>; +using PointI = Point<int32_t>; +using PointI64 = Point<int64_t>; + +template <typename T> +Point<T> const operator-(Point<T> const & a, Point<T> const & b) +{ + return Point<T>(a.x - b.x, a.y - b.y); +} + +template <typename T> +Point<T> const operator+(Point<T> const & a, Point<T> const & b) +{ + return Point<T>(a.x + b.x, a.y + b.y); +} + +template <typename T> +T const DotProduct(Point<T> const & a, Point<T> const & b) +{ + return a.x * b.x + a.y * b.y; +} + +template <typename T> +T const CrossProduct(Point<T> const & a, Point<T> const & b) +{ + return a.x * b.y - a.y * b.x; +} + +template <typename T> +Point<T> const Rotate(Point<T> const & pt, T a) +{ + Point<T> res(pt); + res.Rotate(a); + return res; +} + +template <typename T, typename U> +Point<T> const Shift(Point<T> const & pt, U const & dx, U const & dy) +{ + return Point<T>(pt.x + dx, pt.y + dy); +} + +template <typename T, typename U> +Point<T> const Shift(Point<T> const & pt, Point<U> const & offset) +{ + return Shift(pt, offset.x, offset.y); +} + +template <typename T> +Point<T> const Floor(Point<T> const & pt) +{ + Point<T> res; + res.x = floor(pt.x); + res.y = floor(pt.y); + return res; +} + +template <typename T> +std::string DebugPrint(m2::Point<T> const & p) +{ + std::ostringstream out; + out.precision(20); + out << "m2::Point<" << typeid(T).name() << ">(" << p.x << ", " << p.y << ")"; + return out.str(); +} + +template <typename T> +bool AlmostEqualAbs(m2::Point<T> const & a, m2::Point<T> const & b, double const eps) +{ + return my::AlmostEqualAbs(a.x, b.x, eps) && my::AlmostEqualAbs(a.y, b.y, eps); +} - using PointF = Point<float>; - using PointD = Point<double>; - using PointU = Point<uint32_t>; - using PointU64 = Point<uint64_t>; - using PointI = Point<int32_t>; - using PointI64 = Point<int64_t>; +template <typename T> +bool AlmostEqualULPs(m2::Point<T> const & a, m2::Point<T> const & b, unsigned int maxULPs = 256) +{ + return my::AlmostEqualULPs(a.x, b.x, maxULPs) && my::AlmostEqualULPs(a.y, b.y, maxULPs); +} + +/// Calculate three points of a triangle (p1, p2 and p3) which give an arrow that +/// presents an equilateral triangle with the median +/// starting at point b and having direction b,e. +/// The height of the equilateral triangle is l and the base of the triangle is 2 * w +template <typename T, typename TT, typename PointT = Point<T>> +void GetArrowPoints(PointT const & b, PointT const & e, T w, T l, std::array<Point<TT>, 3> & arr) +{ + ASSERT(!m2::AlmostEqualULPs(b, e), ()); + + PointT const beVec = e - b; + PointT beNormalizedVec = beVec.Normalize(); + std::pair<PointT, PointT> beNormVecs = beNormalizedVec.Normals(w); + + arr[0] = e + beNormVecs.first; + arr[1] = e + beNormalizedVec * l; + arr[2] = e + beNormVecs.second; +} + +/// Returns a point which is belonged to the segment p1, p2 with respet the indent shiftFromP1 from +/// p1. If shiftFromP1 is more the distance between (p1, p2) it returns p2. If shiftFromP1 is less +/// or equal zero it returns p1. +template <typename T> +Point<T> PointAtSegment(Point<T> const & p1, Point<T> const & p2, T shiftFromP1) +{ + Point<T> p12 = p2 - p1; + shiftFromP1 = my::clamp(shiftFromP1, static_cast<T>(0.0), static_cast<T>(p12.Length())); + return p1 + p12.Normalize() * shiftFromP1; +} + +template <class TArchive, class PointT> +TArchive & operator>>(TArchive & ar, m2::Point<PointT> & pt) +{ + ar >> pt.x; + ar >> pt.y; + return ar; +} + +template <class TArchive, class PointT> +TArchive & operator<<(TArchive & ar, m2::Point<PointT> const & pt) +{ + ar << pt.x; + ar << pt.y; + return ar; +} + +template <typename T> +bool operator<(Point<T> const & l, Point<T> const & r) +{ + if (l.x != r.x) + return l.x < r.x; + return l.y < r.y; +} } // namespace m2 namespace my diff --git a/geometry/polyline2d.hpp b/geometry/polyline2d.hpp index 2bc82d64b5..00d9588d1f 100644 --- a/geometry/polyline2d.hpp +++ b/geometry/polyline2d.hpp @@ -1,37 +1,40 @@ #pragma once +#include "geometry/distance.hpp" #include "geometry/point2d.hpp" #include "geometry/rect2d.hpp" -#include "geometry/distance.hpp" #include "base/internal/message.hpp" -#include "std/initializer_list.hpp" -#include "std/vector.hpp" +#include <cstddef> +#include <initializer_list> +#include <limits> +#include <string> +#include <vector> namespace m2 { template <typename T> class Polyline { - vector<Point<T> > m_points; + std::vector<Point<T>> m_points; public: - using Container = vector<Point<T>>; + using Container = std::vector<Point<T>>; using Iter = typename Container::const_iterator; Polyline() {} - Polyline(initializer_list<Point<T>> const & points) : m_points(points) + Polyline(std::initializer_list<Point<T>> const & points) : m_points(points) { ASSERT_GREATER(m_points.size(), 1, ()); } - explicit Polyline(vector<Point<T>> const & points) : m_points(points) + explicit Polyline(std::vector<Point<T>> const & points) : m_points(points) { ASSERT_GREATER(m_points.size(), 1, ()); } - explicit Polyline(vector<Point<T>> && points) : m_points(move(points)) + explicit Polyline(std::vector<Point<T>> && points) : m_points(move(points)) { ASSERT_GREATER(m_points.size(), 1, ()); } @@ -47,7 +50,7 @@ public: // @todo add cached value and lazy init double dist = 0; for (size_t i = 1; i < m_points.size(); ++i) - dist += m_points[i-1].Length(m_points[i]); + dist += m_points[i - 1].Length(m_points[i]); return dist; } @@ -61,7 +64,7 @@ public: double CalcMinSquaredDistance(m2::Point<T> const & point) const { - double res = numeric_limits<double>::max(); + double res = std::numeric_limits<double>::max(); m2::DistanceToLineSquare<m2::Point<T>> d; Iter i = Begin(); @@ -136,31 +139,31 @@ public: return m_points.back(); } - vector<Point<T>> ExtractSegment(size_t segmentIndex, bool reversed) const + std::vector<Point<T>> ExtractSegment(size_t segmentIndex, bool reversed) const { if (segmentIndex + 1 >= m_points.size()) - return vector<Point<T>>(); + return std::vector<Point<T>>(); - return reversed ? vector<Point<T>>{m_points[segmentIndex + 1], m_points[segmentIndex]} : - vector<Point<T>>{m_points[segmentIndex], m_points[segmentIndex + 1]}; + return reversed ? std::vector<Point<T>>{m_points[segmentIndex + 1], m_points[segmentIndex]} + : std::vector<Point<T>>{m_points[segmentIndex], m_points[segmentIndex + 1]}; } - vector<Point<T>> ExtractSegment(size_t startPointIndex, size_t endPointIndex) const + std::vector<Point<T>> ExtractSegment(size_t startPointIndex, size_t endPointIndex) const { if (startPointIndex > endPointIndex || startPointIndex >= m_points.size() || endPointIndex >= m_points.size()) { - return vector<Point<T>>(); + return std::vector<Point<T>>(); } - vector<Point<T>> result(endPointIndex - startPointIndex + 1); + std::vector<Point<T>> result(endPointIndex - startPointIndex + 1); for (size_t i = startPointIndex, j = 0; i <= endPointIndex; ++i, ++j) result[j] = m_points[i]; return result; } - vector<Point<T> > const & GetPoints() const { return m_points; } - friend string DebugPrint(Polyline const & p) { return ::DebugPrint(p.m_points); } + std::vector<Point<T>> const & GetPoints() const { return m_points; } + friend std::string DebugPrint(Polyline const & p) { return ::DebugPrint(p.m_points); } }; using PolylineD = Polyline<double>; diff --git a/geometry/rect2d.hpp b/geometry/rect2d.hpp index 44f3e9eafd..e980a7b880 100644 --- a/geometry/rect2d.hpp +++ b/geometry/rect2d.hpp @@ -5,399 +5,367 @@ #include "base/assert.hpp" #include "base/internal/message.hpp" -#include "std/algorithm.hpp" -#include "std/limits.hpp" -#include "std/string.hpp" +#include <algorithm> +#include <limits> +#include <sstream> +#include <string> namespace m2 { - namespace impl - { - template <typename T, bool has_sign> struct min_max_value; - template <typename T> struct min_max_value<T, true> - { - T get_min() { return -get_max(); } - T get_max() { return numeric_limits<T>::max(); } - }; - template <typename T> struct min_max_value<T, false> - { - T get_min() { return numeric_limits<T>::min(); } - T get_max() { return numeric_limits<T>::max(); } - }; - } - - - template <typename T> - class Rect - { - template <class TArchive, class TPoint> - friend TArchive & operator << (TArchive & ar, Rect<TPoint> const & rect); - template <class TArchive, class TPoint> - friend TArchive & operator >> (TArchive & ar, Rect<TPoint> & rect); - - enum { IsSigned = numeric_limits<T>::is_signed }; - - T m_minX, m_minY, m_maxX, m_maxY; +namespace impl +{ +template <typename T, bool has_sign> +struct min_max_value; - public: - typedef T value_type; +template <typename T> +struct min_max_value<T, true> +{ + T get_min() { return -get_max(); } + T get_max() { return std::numeric_limits<T>::max(); } +}; - Rect() { MakeEmpty(); } - Rect(T minX, T minY, T maxX, T maxY) - : m_minX(minX), m_minY(minY), m_maxX(maxX), m_maxY(maxY) - { - ASSERT ( minX <= maxX, (minX, maxX) ); - ASSERT ( minY <= maxY, (minY, maxY) ); - } - Rect(Point<T> const & p1, Point<T> const & p2) - : m_minX(min(p1.x, p2.x)), m_minY(min(p1.y, p2.y)), - m_maxX(max(p1.x, p2.x)), m_maxY(max(p1.y, p2.y)) - { - } +template <typename T> +struct min_max_value<T, false> +{ + T get_min() { return std::numeric_limits<T>::min(); } + T get_max() { return std::numeric_limits<T>::max(); } +}; +} // namespace impl - template <typename U> - explicit Rect(Rect<U> const & src) - : m_minX(src.minX()), m_minY(src.minY()), m_maxX(src.maxX()), m_maxY(src.maxY()) - { - } +template <typename T> +class Rect +{ +public: + using value_type = T; - static Rect GetEmptyRect() { return Rect(); } + Rect() { MakeEmpty(); } - static Rect GetInfiniteRect() - { - Rect r; - r.MakeInfinite(); - return r; - } + Rect(T minX, T minY, T maxX, T maxY) : m_minX(minX), m_minY(minY), m_maxX(maxX), m_maxY(maxY) + { + ASSERT(minX <= maxX, ()); + ASSERT(minY <= maxY, ()); + } - void MakeEmpty() - { - m_minX = m_minY = impl::min_max_value<T, IsSigned>().get_max(); - m_maxX = m_maxY = impl::min_max_value<T, IsSigned>().get_min(); - } + Rect(Point<T> const & p1, Point<T> const & p2) + : m_minX(std::min(p1.x, p2.x)) + , m_minY(std::min(p1.y, p2.y)) + , m_maxX(std::max(p1.x, p2.x)) + , m_maxY(std::max(p1.y, p2.y)) + { + } - void MakeInfinite() - { - m_minX = m_minY = impl::min_max_value<T, IsSigned>().get_min(); - m_maxX = m_maxY = impl::min_max_value<T, IsSigned>().get_max(); - } + template <typename U> + explicit Rect(Rect<U> const & src) + : m_minX(src.minX()), m_minY(src.minY()), m_maxX(src.maxX()), m_maxY(src.maxY()) + { + } - bool IsValid() const - { - return (m_minX <= m_maxX && m_minY <= m_maxY); - } + static Rect GetEmptyRect() { return Rect(); } - bool IsEmptyInterior() const { return m_minX >= m_maxX || m_minY >= m_maxY; } + static Rect GetInfiniteRect() + { + Rect r; + r.MakeInfinite(); + return r; + } - void Add(m2::Point<T> const & p) - { - m_minX = min(p.x, m_minX); - m_minY = min(p.y, m_minY); - m_maxX = max(p.x, m_maxX); - m_maxY = max(p.y, m_maxY); - } + void MakeEmpty() + { + m_minX = m_minY = impl::min_max_value<T, IsSigned>().get_max(); + m_maxX = m_maxY = impl::min_max_value<T, IsSigned>().get_min(); + } - void Add(m2::Rect<T> const & r) - { - m_minX = min(r.m_minX, m_minX); - m_minY = min(r.m_minY, m_minY); - m_maxX = max(r.m_maxX, m_maxX); - m_maxY = max(r.m_maxY, m_maxY); - } + void MakeInfinite() + { + m_minX = m_minY = impl::min_max_value<T, IsSigned>().get_min(); + m_maxX = m_maxY = impl::min_max_value<T, IsSigned>().get_max(); + } - void Offset(m2::Point<T> const & p) - { - m_minX += p.x; - m_minY += p.y; - m_maxX += p.x; - m_maxY += p.y; - } + bool IsValid() const { return (m_minX <= m_maxX && m_minY <= m_maxY); } - void Offset(T const & dx, T const & dy) - { - m_minX += dx; - m_minY += dy; - m_maxX += dx; - m_maxY += dy; - } + bool IsEmptyInterior() const { return m_minX >= m_maxX || m_minY >= m_maxY; } - Point<T> LeftTop() const { return Point<T>(m_minX, m_maxY); } - Point<T> RightTop() const { return Point<T>(m_maxX, m_maxY); } - Point<T> RightBottom() const { return Point<T>(m_maxX, m_minY); } - Point<T> LeftBottom() const { return Point<T>(m_minX, m_minY); } + void Add(m2::Point<T> const & p) + { + m_minX = std::min(p.x, m_minX); + m_minY = std::min(p.y, m_minY); + m_maxX = std::max(p.x, m_maxX); + m_maxY = std::max(p.y, m_maxY); + } - bool IsIntersect(Rect const & r) const - { - return !((m_maxX < r.m_minX) || (m_minX > r.m_maxX) || - (m_maxY < r.m_minY) || (m_minY > r.m_maxY)); - } + void Add(m2::Rect<T> const & r) + { + m_minX = std::min(r.m_minX, m_minX); + m_minY = std::min(r.m_minY, m_minY); + m_maxX = std::max(r.m_maxX, m_maxX); + m_maxY = std::max(r.m_maxY, m_maxY); + } - bool IsPointInside(Point<T> const & pt) const - { - return !(m_minX > pt.x || pt.x > m_maxX || m_minY > pt.y || pt.y > m_maxY); - } + void Offset(m2::Point<T> const & p) + { + m_minX += p.x; + m_minY += p.y; + m_maxX += p.x; + m_maxY += p.y; + } - bool IsRectInside(Rect<T> const & rect) const - { - return (IsPointInside(Point<T>(rect.minX(), rect.minY())) && - IsPointInside(Point<T>(rect.maxX(), rect.maxY()))); - } + void Offset(T const & dx, T const & dy) + { + m_minX += dx; + m_minY += dy; + m_maxX += dx; + m_maxY += dy; + } - Point<T> Center() const { return Point<T>((m_minX + m_maxX) / 2.0, (m_minY + m_maxY) / 2.0); } - T SizeX() const { return max(static_cast<T>(0), m_maxX - m_minX); } - T SizeY() const { return max(static_cast<T>(0), m_maxY - m_minY); } + Point<T> LeftTop() const { return Point<T>(m_minX, m_maxY); } + Point<T> RightTop() const { return Point<T>(m_maxX, m_maxY); } + Point<T> RightBottom() const { return Point<T>(m_maxX, m_minY); } + Point<T> LeftBottom() const { return Point<T>(m_minX, m_minY); } - void DivideByGreaterSize(Rect & r1, Rect & r2) const - { - if (SizeX() > SizeY()) - { - T const pivot = (m_minX + m_maxX) / 2; - r1 = Rect<T>(m_minX, m_minY, pivot, m_maxY); - r2 = Rect<T>(pivot, m_minY, m_maxX, m_maxY); - } - else - { - T const pivot = (m_minY + m_maxY) / 2; - r1 = Rect<T>(m_minX, m_minY, m_maxX, pivot); - r2 = Rect<T>(m_minX, pivot, m_maxX, m_maxY); - } - } + bool IsIntersect(Rect const & r) const + { + return !((m_maxX < r.m_minX) || (m_minX > r.m_maxX) || (m_maxY < r.m_minY) || + (m_minY > r.m_maxY)); + } - void SetSizes(T dx, T dy) - { - ASSERT_GREATER ( dx, 0, () ); - ASSERT_GREATER ( dy, 0, () ); + bool IsPointInside(Point<T> const & pt) const + { + return !(m_minX > pt.x || pt.x > m_maxX || m_minY > pt.y || pt.y > m_maxY); + } - dx /= 2; - dy /= 2; + bool IsRectInside(Rect<T> const & rect) const + { + return (IsPointInside(Point<T>(rect.minX(), rect.minY())) && + IsPointInside(Point<T>(rect.maxX(), rect.maxY()))); + } - Point<T> const c = Center(); - m_minX = c.x - dx; - m_minY = c.y - dy; - m_maxX = c.x + dx; - m_maxY = c.y + dy; - } + Point<T> Center() const { return Point<T>((m_minX + m_maxX) / 2.0, (m_minY + m_maxY) / 2.0); } + T SizeX() const { return std::max(static_cast<T>(0), m_maxX - m_minX); } + T SizeY() const { return std::max(static_cast<T>(0), m_maxY - m_minY); } - void SetSizesToIncludePoint(Point<T> const & pt) + void DivideByGreaterSize(Rect & r1, Rect & r2) const + { + if (SizeX() > SizeY()) { - Point<T> const c = Center(); - T const dx = my::Abs(pt.x - c.x); - T const dy = my::Abs(pt.y - c.y); - - m_minX = c.x - dx; - m_minY = c.y - dy; - m_maxX = c.x + dx; - m_maxY = c.y + dy; + T const pivot = (m_minX + m_maxX) / 2; + r1 = Rect<T>(m_minX, m_minY, pivot, m_maxY); + r2 = Rect<T>(pivot, m_minY, m_maxX, m_maxY); } - - void SetCenter(m2::Point<T> const & p) + else { - Offset(p - Center()); + T const pivot = (m_minY + m_maxY) / 2; + r1 = Rect<T>(m_minX, m_minY, m_maxX, pivot); + r2 = Rect<T>(m_minX, pivot, m_maxX, m_maxY); } + } - T minX() const { return m_minX; } - T minY() const { return m_minY; } - T maxX() const { return m_maxX; } - T maxY() const { return m_maxY; } - - void setMinX(T minX) { m_minX = minX; } - void setMinY(T minY) { m_minY = minY; } - void setMaxX(T maxX) { m_maxX = maxX; } - void setMaxY(T maxY) { m_maxY = maxY; } + void SetSizes(T dx, T dy) + { + ASSERT_GREATER(dx, 0, ()); + ASSERT_GREATER(dy, 0, ()); - void Scale(T scale) - { - scale *= 0.5; - - m2::Point<T> const center = Center(); - T const halfSizeX = SizeX() * scale; - T const halfSizeY = SizeY() * scale; - m_minX = center.x - halfSizeX; - m_minY = center.y - halfSizeY; - m_maxX = center.x + halfSizeX; - m_maxY = center.y + halfSizeY; - } + dx /= 2; + dy /= 2; - void Inflate(T dx, T dy) - { - m_minX -= dx; m_maxX += dx; - m_minY -= dy; m_maxY += dy; - } + Point<T> const c = Center(); + m_minX = c.x - dx; + m_minY = c.y - dy; + m_maxX = c.x + dx; + m_maxY = c.y + dy; + } - bool Intersect(m2::Rect<T> const & r) - { - T newMinX = max(m_minX, r.minX()); - T newMaxX = min(m_maxX, r.maxX()); + void SetSizesToIncludePoint(Point<T> const & pt) + { + Point<T> const c = Center(); + T const dx = my::Abs(pt.x - c.x); + T const dy = my::Abs(pt.y - c.y); + + m_minX = c.x - dx; + m_minY = c.y - dy; + m_maxX = c.x + dx; + m_maxY = c.y + dy; + } - if (newMinX > newMaxX) - return false; + void SetCenter(m2::Point<T> const & p) { Offset(p - Center()); } - T newMinY = max(m_minY, r.minY()); - T newMaxY = min(m_maxY, r.maxY()); + T minX() const { return m_minX; } + T minY() const { return m_minY; } + T maxX() const { return m_maxX; } + T maxY() const { return m_maxY; } - if (newMinY > newMaxY) - return false; + void setMinX(T minX) { m_minX = minX; } + void setMinY(T minY) { m_minY = minY; } + void setMaxX(T maxX) { m_maxX = maxX; } + void setMaxY(T maxY) { m_maxY = maxY; } - m_minX = newMinX; - m_minY = newMinY; - m_maxX = newMaxX; - m_maxY = newMaxY; + void Scale(T scale) + { + scale *= 0.5; + + m2::Point<T> const center = Center(); + T const halfSizeX = SizeX() * scale; + T const halfSizeY = SizeY() * scale; + m_minX = center.x - halfSizeX; + m_minY = center.y - halfSizeY; + m_maxX = center.x + halfSizeX; + m_maxY = center.y + halfSizeY; + } - return true; - } + void Inflate(T dx, T dy) + { + m_minX -= dx; + m_maxX += dx; + m_minY -= dy; + m_maxY += dy; + } - /* - bool operator < (m2::Rect<T> const & r) const - { - if (m_minX != r.m_minX) - return m_minX < r.m_minX; - if (m_minY != r.m_minY) - return m_minY < r.m_minY; - if (m_maxX != r.m_maxX) - return m_maxX < r.m_maxX; - if (m_maxY != r.m_maxY) - return m_maxY < r.m_maxY; + bool Intersect(m2::Rect<T> const & r) + { + T newMinX = std::max(m_minX, r.minX()); + T newMaxX = std::min(m_maxX, r.maxX()); + if (newMinX > newMaxX) return false; - } - */ - bool operator == (m2::Rect<T> const & r) const - { - return m_minX == r.m_minX && m_minY == r.m_minY && m_maxX == r.m_maxX && m_maxY == r.m_maxY; - } + T newMinY = std::max(m_minY, r.minY()); + T newMaxY = std::min(m_maxY, r.maxY()); - bool operator != (m2::Rect<T> const & r) const - { - return !(*this == r); - } - }; - - template <typename T> - inline bool IsEqual(Rect<T> const & r1, Rect<T> const & r2, double epsX, double epsY) - { - Rect<T> r = r1; - r.Inflate(epsX, epsY); - if (!r.IsRectInside(r2)) return false; + if (newMinY > newMaxY) + return false; - r = r2; - r.Inflate(epsX, epsY); - if (!r.IsRectInside(r1)) return false; + m_minX = newMinX; + m_minY = newMinY; + m_maxX = newMaxX; + m_maxY = newMaxY; return true; } - template <typename T> - inline bool IsEqualSize(Rect<T> const & r1, Rect<T> const & r2, double epsX, double epsY) + bool operator==(m2::Rect<T> const & r) const { - return fabs(r1.SizeX() - r2.SizeX()) < epsX && fabs(r1.SizeY() - r2.SizeY()) < epsY; + return m_minX == r.m_minX && m_minY == r.m_minY && m_maxX == r.m_maxX && m_maxY == r.m_maxY; } - template <typename T> - inline m2::Rect<T> const Add(m2::Rect<T> const & r, m2::Point<T> const & p) - { - return m2::Rect<T>( - min(p.x, r.minX()), - min(p.y, r.minY()), - max(p.x, r.maxX()), - max(p.y, r.maxY()) - ); - } + bool operator!=(m2::Rect<T> const & r) const { return !(*this == r); } - template <typename T> - inline m2::Rect<T> const Add(m2::Rect<T> const & r1, m2::Rect<T> const & r2) +private: + enum { - return m2::Rect<T>( - min(r2.minX(), r1.minX()), - min(r2.minY(), r1.minY()), - max(r2.maxX(), r1.maxX()), - max(r2.maxY(), r1.maxY()) - ); - } + IsSigned = std::numeric_limits<T>::is_signed + }; - template <typename T> - inline m2::Rect<T> const Offset(m2::Rect<T> const & r1, m2::Point<T> const & p) - { - return m2::Rect<T>( - r1.minX() + p.x, - r1.minY() + p.y, - r1.maxX() + p.x, - r1.maxY() + p.y - ); - } + template <class TArchive, class TPoint> + friend TArchive & operator<<(TArchive & ar, Rect<TPoint> const & rect); - template <typename T> - inline m2::Rect<T> const Inflate(m2::Rect<T> const & r, T const & dx, T const & dy) - { - return m2::Rect<T>( - r.minX() - dx, - r.minY() - dy, - r.maxX() + dx, - r.maxY() + dy - ); - } + template <class TArchive, class TPoint> + friend TArchive & operator>>(TArchive & ar, Rect<TPoint> & rect); - template <typename T> - inline m2::Rect<T> const Inflate(m2::Rect<T> const & r, m2::Point<T> const & p) - { - return Inflate(r, p.x, p.y); - } + T m_minX, m_minY, m_maxX, m_maxY; +}; - template <typename T> - inline m2::Rect<T> const Offset(m2::Rect<T> const & r1, T const & dx, T const & dy) - { - return m2::Rect<T>( - r1.minX() + dx, - r1.minY() + dy, - r1.maxX() + dx, - r1.maxY() + dy - ); - } +using RectF = Rect<float>; +using RectD = Rect<double>; +using RectU = Rect<unsigned>; +using RectU32 = Rect<uint32_t>; +using RectI = Rect<int>; - template <typename T, typename TCollection> - inline bool HasIntersection(m2::Rect<T> const & rect, TCollection const & geometry) - { - for (auto const & g : geometry) - { - if (rect.IsIntersect(g)) - return true; - } +template <typename T> +bool IsEqual(Rect<T> const & r1, Rect<T> const & r2, double epsX, double epsY) +{ + Rect<T> r = r1; + r.Inflate(epsX, epsY); + if (!r.IsRectInside(r2)) return false; - }; - template <class TArchive, class PointT> - TArchive & operator >> (TArchive & ar, m2::Rect<PointT> & rect) - { - ar >> rect.m_minX; - ar >> rect.m_minY; - ar >> rect.m_maxX; - ar >> rect.m_maxY; - return ar; - } + r = r2; + r.Inflate(epsX, epsY); + if (!r.IsRectInside(r1)) + return false; - template <class TArchive, class PointT> - TArchive & operator << (TArchive & ar, m2::Rect<PointT> const & rect) - { - ar << rect.m_minX; - ar << rect.m_minY; - ar << rect.m_maxX; - ar << rect.m_maxY; - return ar; - } + return true; +} + +template <typename T> +bool IsEqualSize(Rect<T> const & r1, Rect<T> const & r2, double epsX, double epsY) +{ + return fabs(r1.SizeX() - r2.SizeX()) < epsX && fabs(r1.SizeY() - r2.SizeY()) < epsY; +} + +template <typename T> +m2::Rect<T> const Add(m2::Rect<T> const & r, m2::Point<T> const & p) +{ + return m2::Rect<T>(std::min(p.x, r.minX()), std::min(p.y, r.minY()), std::max(p.x, r.maxX()), + std::max(p.y, r.maxY())); +} + +template <typename T> +m2::Rect<T> const Add(m2::Rect<T> const & r1, m2::Rect<T> const & r2) +{ + return m2::Rect<T>(std::min(r2.minX(), r1.minX()), std::min(r2.minY(), r1.minY()), + std::max(r2.maxX(), r1.maxX()), std::max(r2.maxY(), r1.maxY())); +} + +template <typename T> +m2::Rect<T> const Offset(m2::Rect<T> const & r1, m2::Point<T> const & p) +{ + return m2::Rect<T>(r1.minX() + p.x, r1.minY() + p.y, r1.maxX() + p.x, r1.maxY() + p.y); +} + +template <typename T> +m2::Rect<T> const Inflate(m2::Rect<T> const & r, T const & dx, T const & dy) +{ + return m2::Rect<T>(r.minX() - dx, r.minY() - dy, r.maxX() + dx, r.maxY() + dy); +} + +template <typename T> +m2::Rect<T> const Inflate(m2::Rect<T> const & r, m2::Point<T> const & p) +{ + return Inflate(r, p.x, p.y); +} - typedef Rect<float> RectF; - typedef Rect<double> RectD; - typedef Rect<unsigned> RectU; - typedef Rect<uint32_t> RectU32; - typedef Rect<int> RectI; +template <typename T> +m2::Rect<T> const Offset(m2::Rect<T> const & r1, T const & dx, T const & dy) +{ + return m2::Rect<T>(r1.minX() + dx, r1.minY() + dy, r1.maxX() + dx, r1.maxY() + dy); +} - template <typename T> - inline string DebugPrint(m2::Rect<T> const & r) +template <typename T, typename TCollection> +bool HasIntersection(m2::Rect<T> const & rect, TCollection const & geometry) +{ + for (auto const & g : geometry) { - ostringstream out; - out.precision(20); - out << "m2::Rect(" - << r.minX() << ", " << r.minY() << ", " << r.maxX() << ", " << r.maxY() << ")"; - return out.str(); + if (rect.IsIntersect(g)) + return true; } + return false; +}; + +template <class TArchive, class PointT> +TArchive & operator>>(TArchive & ar, m2::Rect<PointT> & rect) +{ + ar >> rect.m_minX; + ar >> rect.m_minY; + ar >> rect.m_maxX; + ar >> rect.m_maxY; + return ar; +} + +template <class TArchive, class PointT> +TArchive & operator<<(TArchive & ar, m2::Rect<PointT> const & rect) +{ + ar << rect.m_minX; + ar << rect.m_minY; + ar << rect.m_maxX; + ar << rect.m_maxY; + return ar; +} + +template <typename T> +std::string DebugPrint(m2::Rect<T> const & r) +{ + std::ostringstream out; + out.precision(20); + out << "m2::Rect(" << r.minX() << ", " << r.minY() << ", " << r.maxX() << ", " << r.maxY() << ")"; + return out.str(); } +} // namespace m2 diff --git a/geometry/region2d.hpp b/geometry/region2d.hpp index e7a5e0f262..5bdb252613 100644 --- a/geometry/region2d.hpp +++ b/geometry/region2d.hpp @@ -6,358 +6,362 @@ #include "base/math.hpp" -#include "std/algorithm.hpp" -#include "std/type_traits.hpp" -#include "std/utility.hpp" -#include "std/vector.hpp" +#include <algorithm> +#include <type_traits> +#include <utility> +#include <vector> namespace m2 { - namespace detail - { - struct DefEqualFloat - { - // 1e-9 is two orders of magnitude more accurate than our OSM source data. - static double constexpr kPrecision = 1e-9; - - template <class TPoint> - bool EqualPoints(TPoint const & p1, TPoint const & p2) const - { - static_assert(std::is_floating_point<typename TPoint::value_type>::value, ""); +namespace detail +{ +struct DefEqualFloat +{ + // 1e-9 is two orders of magnitude more accurate than our OSM source data. + static double constexpr kPrecision = 1e-9; - return my::AlmostEqualAbs(p1.x, p2.x, static_cast<typename TPoint::value_type>(kPrecision)) && - my::AlmostEqualAbs(p1.y, p2.y, static_cast<typename TPoint::value_type>(kPrecision)); - } - template <class TCoord> - bool EqualZeroSquarePrecision(TCoord val) const - { - static_assert(std::is_floating_point<TCoord>::value, ""); + template <typename Point> + bool EqualPoints(Point const & p1, Point const & p2) const + { + static_assert(std::is_floating_point<typename Point::value_type>::value, ""); - return my::AlmostEqualAbs(val, 0.0, kPrecision * kPrecision); - } - // Determines if value of a val lays between a p1 and a p2 values with some precision. - inline bool IsAlmostBetween(double val, double p1, double p2) const - { - return (val >= p1 - kPrecision && val <= p2 + kPrecision) || - (val <= p1 + kPrecision && val >= p2 - kPrecision); - } - }; + return my::AlmostEqualAbs(p1.x, p2.x, static_cast<typename Point::value_type>(kPrecision)) && + my::AlmostEqualAbs(p1.y, p2.y, static_cast<typename Point::value_type>(kPrecision)); + } - struct DefEqualInt - { - template <class TPoint> - bool EqualPoints(TPoint const & p1, TPoint const & p2) const - { - return p1 == p2; - } - template <class TCoord> - bool EqualZeroSquarePrecision(TCoord val) const - { - return val == 0; - } - inline bool IsAlmostBetween(double val, double left, double right) const - { - return (val >= left && val <= right) || - (val <= left && val >= right); - } - }; + template <typename TCoord> + bool EqualZeroSquarePrecision(TCoord val) const + { + static_assert(std::is_floating_point<TCoord>::value, ""); - template <int floating> struct TraitsType; - template <> struct TraitsType<1> - { - typedef DefEqualFloat EqualType; - typedef double BigType; - }; - template <> struct TraitsType<0> - { - typedef DefEqualInt EqualType; - typedef int64_t BigType; - }; + return my::AlmostEqualAbs(val, 0.0, kPrecision * kPrecision); } - - template <class PointT> - class Region + // Determines if value of a val lays between a p1 and a p2 values with some precision. + bool IsAlmostBetween(double val, double p1, double p2) const { - template <class TArchive, class TPoint> - friend TArchive & operator << (TArchive & ar, Region<TPoint> const & region); - template <class TArchive, class TPoint> - friend TArchive & operator >> (TArchive & ar, Region<TPoint> & region); - - public: - typedef PointT ValueT; - typedef typename PointT::value_type CoordT; - - private: - typedef vector<PointT> ContainerT; - typedef detail::TraitsType<is_floating_point<CoordT>::value> TraitsT; - - public: - /// @name Needed for boost region concept. - //@{ - typedef typename ContainerT::const_iterator IteratorT; - IteratorT Begin() const { return m_points.begin(); } - IteratorT End() const { return m_points.end(); } - size_t Size() const { return m_points.size(); } - //@} - - public: - Region() = default; - - template <class Points> - explicit Region(Points && points) : m_points(std::forward<Points>(points)) - { - CalcLimitRect(); - } + return (val >= p1 - kPrecision && val <= p2 + kPrecision) || + (val <= p1 + kPrecision && val >= p2 - kPrecision); + } +}; - template <class IterT> - Region(IterT first, IterT last) : m_points(first, last) - { - CalcLimitRect(); - } +struct DefEqualInt +{ + template <typename Point> + bool EqualPoints(Point const & p1, Point const & p2) const + { + return p1 == p2; + } - template <class IterT> - void Assign(IterT first, IterT last) - { - m_points.assign(first, last); - CalcLimitRect(); - } + template <typename TCoord> + bool EqualZeroSquarePrecision(TCoord val) const + { + return val == 0; + } - template <class IterT, class Fn> - void AssignEx(IterT first, IterT last, Fn fn) - { - m_points.reserve(distance(first, last)); + bool IsAlmostBetween(double val, double left, double right) const + { + return (val >= left && val <= right) || (val <= left && val >= right); + } +}; - while (first != last) - m_points.push_back(fn(*first++)); +template <int floating> +struct TraitsType; - CalcLimitRect(); - } +template <> +struct TraitsType<1> +{ + typedef DefEqualFloat EqualType; + typedef double BigType; +}; - void AddPoint(PointT const & pt) - { - m_points.push_back(pt); - m_rect.Add(pt); - } +template <> +struct TraitsType<0> +{ + typedef DefEqualInt EqualType; + typedef int64_t BigType; +}; +} // namespace detail - template <class TFunctor> - void ForEachPoint(TFunctor toDo) const - { - for_each(m_points.begin(), m_points.end(), toDo); - } +template <typename Point> +class Region +{ +public: + using ValueT = Point; + using CoordT = typename Point::value_type; + using ContainerT = std::vector<Point>; + using TraitsT = detail::TraitsType<std::is_floating_point<CoordT>::value>; + + /// @name Needed for boost region concept. + //@{ + using IteratorT = typename ContainerT::const_iterator; + IteratorT Begin() const { return m_points.begin(); } + IteratorT End() const { return m_points.end(); } + size_t Size() const { return m_points.size(); } + //@} + + Region() = default; + + template <typename Points> + explicit Region(Points && points) : m_points(std::forward<Points>(points)) + { + CalcLimitRect(); + } - inline m2::Rect<CoordT> const & GetRect() const { return m_rect; } - inline size_t GetPointsCount() const { return m_points.size(); } - inline bool IsValid() const { return GetPointsCount() > 2; } + template <typename IterT> + Region(IterT first, IterT last) : m_points(first, last) + { + CalcLimitRect(); + } - void Swap(Region<PointT> & rhs) - { - m_points.swap(rhs.m_points); - std::swap(m_rect, rhs.m_rect); - } + template <typename IterT> + void Assign(IterT first, IterT last) + { + m_points.assign(first, last); + CalcLimitRect(); + } - ContainerT const & Data() const { return m_points; } + template <typename IterT, typename Fn> + void AssignEx(IterT first, IterT last, Fn fn) + { + m_points.reserve(distance(first, last)); - template <class TEqualF> - static inline bool IsIntersect(CoordT const & x11, CoordT const & y11, CoordT const & x12, CoordT const & y12, - CoordT const & x21, CoordT const & y21, CoordT const & x22, CoordT const & y22, - TEqualF equalF, PointT & pt) - { - double const divider = ((y12 - y11) * (x22 - x21) - (x12 - x11) * (y22-y21)); - if (equalF.EqualZeroSquarePrecision(divider)) - return false; - double v = ((x12 - x11) * (y21 - y11) + (y12 - y11) * (x11 - x21)) / divider; - PointT p(x21 + (x22 - x21) * v, y21 + (y22 - y21) * v); - - if (!equalF.IsAlmostBetween(p.x, x11, x12)) - return false; - if (!equalF.IsAlmostBetween(p.x, x21, x22)) - return false; - if (!equalF.IsAlmostBetween(p.y, y11, y12)) - return false; - if (!equalF.IsAlmostBetween(p.y, y21, y22)) - return false; - - pt = p; - return true; - } + while (first != last) + m_points.push_back(fn(*first++)); - static inline bool IsIntersect(PointT const & p1, PointT const & p2, PointT const & p3, PointT const & p4 , PointT & pt) - { - return IsIntersect(p1.x, p1.y, p2.x, p2.y, p3.x, p3.y, p4.x, p4.y, typename TraitsT::EqualType(), pt); - } + CalcLimitRect(); + } - public: + void AddPoint(Point const & pt) + { + m_points.push_back(pt); + m_rect.Add(pt); + } - /// Taken from Computational Geometry in C and modified - template <class TEqualF> - bool Contains(PointT const & pt, TEqualF equalF) const - { - if (!m_rect.IsPointInside(pt)) - return false; + template <typename TFunctor> + void ForEachPoint(TFunctor toDo) const + { + for_each(m_points.begin(), m_points.end(), toDo); + } - int rCross = 0; /* number of right edge/ray crossings */ - int lCross = 0; /* number of left edge/ray crossings */ + m2::Rect<CoordT> const & GetRect() const { return m_rect; } + size_t GetPointsCount() const { return m_points.size(); } + bool IsValid() const { return GetPointsCount() > 2; } - size_t const numPoints = m_points.size(); + void Swap(Region<Point> & rhs) + { + m_points.swap(rhs.m_points); + std::swap(m_rect, rhs.m_rect); + } - typedef typename TraitsT::BigType BigCoordT; - typedef Point<BigCoordT> BigPointT; + ContainerT const & Data() const { return m_points; } - BigPointT prev = BigPointT(m_points[numPoints - 1]) - BigPointT(pt); - for (size_t i = 0; i < numPoints; ++i) - { - if (equalF.EqualPoints(m_points[i], pt)) - return true; + template <typename TEqualF> + static bool IsIntersect(CoordT const & x11, CoordT const & y11, CoordT const & x12, + CoordT const & y12, CoordT const & x21, CoordT const & y21, + CoordT const & x22, CoordT const & y22, TEqualF equalF, Point & pt) + { + double const divider = ((y12 - y11) * (x22 - x21) - (x12 - x11) * (y22 - y21)); + if (equalF.EqualZeroSquarePrecision(divider)) + return false; + double v = ((x12 - x11) * (y21 - y11) + (y12 - y11) * (x11 - x21)) / divider; + Point p(x21 + (x22 - x21) * v, y21 + (y22 - y21) * v); - BigPointT const curr = BigPointT(m_points[i]) - BigPointT(pt); + if (!equalF.IsAlmostBetween(p.x, x11, x12)) + return false; + if (!equalF.IsAlmostBetween(p.x, x21, x22)) + return false; + if (!equalF.IsAlmostBetween(p.y, y11, y12)) + return false; + if (!equalF.IsAlmostBetween(p.y, y21, y22)) + return false; - bool const rCheck = ((curr.y > 0) != (prev.y > 0)); - bool const lCheck = ((curr.y < 0) != (prev.y < 0)); + pt = p; + return true; + } - if (rCheck || lCheck) - { - ASSERT_NOT_EQUAL ( curr.y, prev.y, () ); - - BigCoordT const delta = prev.y - curr.y; - BigCoordT const cp = CrossProduct(curr, prev); - - // Squared precision is needed here because of comparison between cross product of two - // vectors and zero. It's impossible to compare them relatively, so they're compared - // absolutely, and, as cross product is proportional to product of lengths of both - // operands precision must be squared too. - if (!equalF.EqualZeroSquarePrecision(cp)) - { - bool const PrevGreaterCurr = delta > 0.0; - - if (rCheck && ((cp > 0) == PrevGreaterCurr)) ++rCross; - if (lCheck && ((cp > 0) != PrevGreaterCurr)) ++lCross; - } - } + static bool IsIntersect(Point const & p1, Point const & p2, Point const & p3, Point const & p4, + Point & pt) + { + return IsIntersect(p1.x, p1.y, p2.x, p2.y, p3.x, p3.y, p4.x, p4.y, + typename TraitsT::EqualType(), pt); + } - prev = curr; - } + /// Taken from Computational Geometry in C and modified + template <typename TEqualF> + bool Contains(Point const & pt, TEqualF equalF) const + { + if (!m_rect.IsPointInside(pt)) + return false; - /* q on the edge if left and right cross are not the same parity. */ - if ((rCross & 1) != (lCross & 1)) - return true; // on the edge + int rCross = 0; /* number of right edge/ray crossings */ + int lCross = 0; /* number of left edge/ray crossings */ - /* q inside if an odd number of crossings. */ - if (rCross & 1) - return true; // inside - else - return false; // outside - } + size_t const numPoints = m_points.size(); - bool Contains(PointT const & pt) const - { - return Contains(pt, typename TraitsT::EqualType()); - } + using BigCoordT = typename TraitsT::BigType; + using BigPoint = ::m2::Point<BigCoordT>; - /// Finds point of intersection with the section. - bool FindIntersection(PointT const & point1, PointT const & point2, PointT & result) const + BigPoint prev = BigPoint(m_points[numPoints - 1]) - BigPoint(pt); + for (size_t i = 0; i < numPoints; ++i) { - if (m_points.empty()) - return false; - PointT const * prev = &m_points.back(); - for (PointT const & curr : m_points) - { - if (IsIntersect(point1, point2, *prev, curr, result)) - return true; - prev = &curr; - } - return false; - } + if (equalF.EqualPoints(m_points[i], pt)) + return true; - /// Slow check that point lies at the border. - template <class TEqualF> - bool AtBorder(PointT const & pt, double const delta, TEqualF equalF) const - { - if (!m_rect.IsPointInside(pt)) - return false; + BigPoint const curr = BigPoint(m_points[i]) - BigPoint(pt); - const double squareDelta = delta*delta; - size_t const numPoints = m_points.size(); + bool const rCheck = ((curr.y > 0) != (prev.y > 0)); + bool const lCheck = ((curr.y < 0) != (prev.y < 0)); - PointT prev = m_points[numPoints - 1]; - DistanceToLineSquare<PointT> distance; - for (size_t i = 0; i < numPoints; ++i) + if (rCheck || lCheck) { - PointT const curr = m_points[i]; + ASSERT_NOT_EQUAL(curr.y, prev.y, ()); - // Borders often have same points with ways - if (equalF.EqualPoints(m_points[i], pt)) - return true; + BigCoordT const delta = prev.y - curr.y; + BigCoordT const cp = CrossProduct(curr, prev); - distance.SetBounds(prev, curr); - if (distance(pt) < squareDelta) - return true; + // Squared precision is needed here because of comparison between cross product of two + // std::vectors and zero. It's impossible to compare them relatively, so they're compared + // absolutely, and, as cross product is proportional to product of lengths of both + // operands precision must be squared too. + if (!equalF.EqualZeroSquarePrecision(cp)) + { + bool const PrevGreaterCurr = delta > 0.0; - prev = curr; + if (rCheck && ((cp > 0) == PrevGreaterCurr)) + ++rCross; + if (lCheck && ((cp > 0) != PrevGreaterCurr)) + ++lCross; + } } - return false; // Point lies outside the border. + prev = curr; } - bool AtBorder(PointT const & pt, double const delta) const + /* q on the edge if left and right cross are not the same parity. */ + if ((rCross & 1) != (lCross & 1)) + return true; // on the edge + + /* q inside if an odd number of crossings. */ + if (rCross & 1) + return true; // inside + else + return false; // outside + } + + bool Contains(Point const & pt) const { return Contains(pt, typename TraitsT::EqualType()); } + + /// Finds point of intersection with the section. + bool FindIntersection(Point const & point1, Point const & point2, Point & result) const + { + if (m_points.empty()) + return false; + Point const * prev = &m_points.back(); + for (Point const & curr : m_points) { - return AtBorder(pt, delta, typename TraitsT::EqualType()); + if (IsIntersect(point1, point2, *prev, curr, result)) + return true; + prev = &curr; } + return false; + } - private: - void CalcLimitRect() + /// Slow check that point lies at the border. + template <typename TEqualF> + bool AtBorder(Point const & pt, double const delta, TEqualF equalF) const + { + if (!m_rect.IsPointInside(pt)) + return false; + + const double squareDelta = delta * delta; + size_t const numPoints = m_points.size(); + + Point prev = m_points[numPoints - 1]; + DistanceToLineSquare<Point> distance; + for (size_t i = 0; i < numPoints; ++i) { - m_rect.MakeEmpty(); - for (size_t i = 0; i < m_points.size(); ++i) - m_rect.Add(m_points[i]); - } + Point const curr = m_points[i]; - ContainerT m_points; - m2::Rect<CoordT> m_rect; + // Borders often have same points with ways + if (equalF.EqualPoints(m_points[i], pt)) + return true; - template <class T> friend string DebugPrint(Region<T> const &); - }; + distance.SetBounds(prev, curr); + if (distance(pt) < squareDelta) + return true; - template <class PointT> - void swap(Region<PointT> & r1, Region<PointT> & r2) - { - r1.Swap(r2); - } + prev = curr; + } - template <class TArchive, class PointT> - TArchive & operator >> (TArchive & ar, Region<PointT> & region) - { - ar >> region.m_rect; - ar >> region.m_points; - return ar; + return false; // Point lies outside the border. } - template <class TArchive, class PointT> - TArchive & operator << (TArchive & ar, Region<PointT> const & region) + bool AtBorder(Point const & pt, double const delta) const { - ar << region.m_rect; - ar << region.m_points; - return ar; + return AtBorder(pt, delta, typename TraitsT::EqualType()); } - template <class PointT> - inline string DebugPrint(Region<PointT> const & r) +private: + template <typename Archive, typename Pt> + friend Archive & operator<<(Archive & ar, Region<Pt> const & region); + + template <typename Archive, typename Pt> + friend Archive & operator>>(Archive & ar, Region<Pt> & region); + + template <typename T> + friend std::string DebugPrint(Region<T> const &); + + void CalcLimitRect() { - return (DebugPrint(r.m_rect) + ::DebugPrint(r.m_points)); + m_rect.MakeEmpty(); + for (size_t i = 0; i < m_points.size(); ++i) + m_rect.Add(m_points[i]); } - template <class Point> - bool RegionsContain(vector<Region<Point>> const & regions, Point const & point) - { - for (auto const & region : regions) - { - if (region.Contains(point)) - return true; - } + ContainerT m_points; + m2::Rect<CoordT> m_rect; +}; - return false; +template <typename Point> +void swap(Region<Point> & r1, Region<Point> & r2) +{ + r1.Swap(r2); +} + +template <typename Archive, typename Point> +Archive & operator>>(Archive & ar, Region<Point> & region) +{ + ar >> region.m_rect; + ar >> region.m_points; + return ar; +} + +template <typename Archive, typename Point> +Archive & operator<<(Archive & ar, Region<Point> const & region) +{ + ar << region.m_rect; + ar << region.m_points; + return ar; +} + +template <typename Point> +std::string DebugPrint(Region<Point> const & r) +{ + return (DebugPrint(r.m_rect) + ::DebugPrint(r.m_points)); +} + +template <typename Point> +bool RegionsContain(std::vector<Region<Point>> const & regions, Point const & point) +{ + for (auto const & region : regions) + { + if (region.Contains(point)) + return true; } - typedef Region<m2::PointD> RegionD; - typedef Region<m2::PointI> RegionI; - typedef Region<m2::PointU> RegionU; + return false; } + +using RegionD = Region<m2::PointD>; +using RegionI = Region<m2::PointI>; +using RegionU = Region<m2::PointU>; +} // namespace m2 diff --git a/geometry/robust_orientation.cpp b/geometry/robust_orientation.cpp index abf07fc5fc..37eae2e101 100644 --- a/geometry/robust_orientation.cpp +++ b/geometry/robust_orientation.cpp @@ -2,10 +2,9 @@ #include "base/macros.hpp" -#include "std/algorithm.hpp" +#include <algorithm> -extern "C" -{ +extern "C" { #if defined(__clang__) #pragma clang diagnostic push #pragma clang diagnostic ignored "-Wconditional-uninitialized" @@ -16,62 +15,61 @@ extern "C" #endif } +using namespace std; -namespace m2 { namespace robust +namespace m2 { - bool Init() - { - exactinit(); - return true; - } - - double OrientedS(PointD const & p1, PointD const & p2, PointD const & p) - { - static bool res = Init(); - ASSERT_EQUAL ( res, true, () ); - UNUSED_VALUE(res); +namespace robust +{ +bool Init() +{ + exactinit(); + return true; +} - double a[] = { p1.x, p1.y }; - double b[] = { p2.x, p2.y }; - double c[] = { p.x, p.y }; +double OrientedS(PointD const & p1, PointD const & p2, PointD const & p) +{ + static bool res = Init(); + ASSERT_EQUAL(res, true, ()); + UNUSED_VALUE(res); - return orient2d(a, b, c); - } + double a[] = {p1.x, p1.y}; + double b[] = {p2.x, p2.y}; + double c[] = {p.x, p.y}; - bool IsSegmentInCone(PointD const & v, PointD const & v1, - PointD const & vPrev, PointD const & vNext) - { - double const cpLR = OrientedS(vPrev, vNext, v); + return orient2d(a, b, c); +} - if (cpLR == 0.0) - { - // Points vPrev, v, vNext placed on one line; - // use property that polygon has CCW orientation. - return OrientedS(vPrev, vNext, v1) > 0.0; - } +bool IsSegmentInCone(PointD const & v, PointD const & v1, PointD const & vPrev, + PointD const & vNext) +{ + double const cpLR = OrientedS(vPrev, vNext, v); - if (cpLR < 0.0) - { - // vertex is concave - return OrientedS(v, vPrev, v1) < 0.0 && OrientedS(v, vNext, v1) > 0.0; - } - else - { - // vertex is convex - return OrientedS(v, vPrev, v1) < 0.0 || OrientedS(v, vNext, v1) > 0.0; - } + if (cpLR == 0.0) + { + // Points vPrev, v, vNext placed on one line; + // use property that polygon has CCW orientation. + return OrientedS(vPrev, vNext, v1) > 0.0; } - bool SegmentsIntersect(PointD const & a, PointD const & b, - PointD const & c, PointD const & d) + if (cpLR < 0.0) { - return - max(a.x, b.x) >= min(c.x, d.x) && - min(a.x, b.x) <= max(c.x, d.x) && - max(a.y, b.y) >= min(c.y, d.y) && - min(a.y, b.y) <= max(c.y, d.y) && - OrientedS(a, b, c) * OrientedS(a, b, d) <= 0.0 && - OrientedS(c, d, a) * OrientedS(c, d, b) <= 0.0; + // vertex is concave + return OrientedS(v, vPrev, v1) < 0.0 && OrientedS(v, vNext, v1) > 0.0; + } + else + { + // vertex is convex + return OrientedS(v, vPrev, v1) < 0.0 || OrientedS(v, vNext, v1) > 0.0; } } + +bool SegmentsIntersect(PointD const & a, PointD const & b, PointD const & c, PointD const & d) +{ + return max(a.x, b.x) >= min(c.x, d.x) && min(a.x, b.x) <= max(c.x, d.x) && + max(a.y, b.y) >= min(c.y, d.y) && min(a.y, b.y) <= max(c.y, d.y) && + OrientedS(a, b, c) * OrientedS(a, b, d) <= 0.0 && + OrientedS(c, d, a) * OrientedS(c, d, b) <= 0.0; } +} // namespace robust +} // namespace m2 diff --git a/geometry/robust_orientation.hpp b/geometry/robust_orientation.hpp index 5a9a6ee21e..3466ef9a0a 100644 --- a/geometry/robust_orientation.hpp +++ b/geometry/robust_orientation.hpp @@ -4,128 +4,139 @@ #include "base/stl_add.hpp" -#include "std/algorithm.hpp" +#include <algorithm> +#include <iterator> - -namespace m2 { namespace robust +namespace m2 +{ +namespace robust { - bool Init(); +bool Init(); - /// @return > 0, (p1, p2, p) - is CCW (left oriented) - /// < 0, (p1, p2, p) - is CW (right oriented) - /// Same as CrossProduct(p1 - p, p2 - p), but uses robust calculations. - double OrientedS(PointD const & p1, PointD const & p2, PointD const & p); +/// @return > 0, (p1, p2, p) - is CCW (left oriented) +/// < 0, (p1, p2, p) - is CW (right oriented) +/// Same as CrossProduct(p1 - p, p2 - p), but uses robust calculations. +double OrientedS(PointD const & p1, PointD const & p2, PointD const & p); - /// Is segment (v, v1) in cone (vPrev, v, vNext)? - /// @precondition (vPrev, v, vNext) is CCW. - bool IsSegmentInCone(PointD const & v, PointD const & v1, - PointD const & vPrev, PointD const & vNext); +/// Is segment (v, v1) in cone (vPrev, v, vNext)? +/// @precondition (vPrev, v, vNext) is CCW. +bool IsSegmentInCone(PointD const & v, PointD const & v1, PointD const & vPrev, + PointD const & vNext); - bool SegmentsIntersect(PointD const & p1, PointD const & p2, - PointD const & p3, PointD const & p4); +bool SegmentsIntersect(PointD const & p1, PointD const & p2, PointD const & p3, PointD const & p4); - template <typename T> bool Between(T a, T b, T c) - { - return min(a, b) <= c && c <= max(a, b); - } +template <typename T> +bool Between(T a, T b, T c) +{ + return std::min(a, b) <= c && c <= std::max(a, b); +} - template <class PointT> bool IsInSection(PointT const & p1, PointT const & p2, PointT const & p) - { - return Between(p1.x, p2.x, p.x) && Between(p1.y, p2.y, p.y); - } +template <class PointT> +bool IsInSection(PointT const & p1, PointT const & p2, PointT const & p) +{ + return Between(p1.x, p2.x, p.x) && Between(p1.y, p2.y, p.y); +} - template <typename IterT> - bool CheckPolygonSelfIntersections(IterT beg, IterT end) - { - IterT last = end; - --last; +template <typename IterT> +bool CheckPolygonSelfIntersections(IterT beg, IterT end) +{ + IterT last = end; + --last; - for (IterT i = beg; i != last; ++i) - for (IterT j = i; j != end; ++j) + for (IterT i = beg; i != last; ++i) + { + for (IterT j = i; j != end; ++j) + { + // do not check intersection of neibour segments + if (std::distance(i, j) <= 1 || (i == beg && j == last)) + continue; + + IterT ii = NextIterInCycle(i, beg, end); + IterT jj = NextIterInCycle(j, beg, end); + PointD a = *i, b = *ii, c = *j, d = *jj; + + // check for rect intersection + if (std::max(a.x, b.x) < std::min(c.x, d.x) || std::min(a.x, b.x) > std::max(c.x, d.x) || + std::max(a.y, b.y) < std::min(c.y, d.y) || std::min(a.y, b.y) > std::max(c.y, d.y)) { - // do not check intersection of neibour segments - if (distance(i, j) <= 1 || (i == beg && j == last)) - continue; - - IterT ii = NextIterInCycle(i, beg, end); - IterT jj = NextIterInCycle(j, beg, end); - PointD a = *i, b = *ii, c = *j, d = *jj; - - // check for rect intersection - if (max(a.x, b.x) < min(c.x, d.x) || - min(a.x, b.x) > max(c.x, d.x) || - max(a.y, b.y) < min(c.y, d.y) || - min(a.y, b.y) > max(c.y, d.y)) - { - continue; - } - - double const s1 = OrientedS(a, b, c); - double const s2 = OrientedS(a, b, d); - double const s3 = OrientedS(c, d, a); - double const s4 = OrientedS(c, d, b); + continue; + } - // check if sections have any intersection - if (s1 * s2 > 0.0 || s3 * s4 > 0.0) - continue; + double const s1 = OrientedS(a, b, c); + double const s2 = OrientedS(a, b, d); + double const s3 = OrientedS(c, d, a); + double const s4 = OrientedS(c, d, b); - // Common principle if any point lay exactly on section, check 2 variants: - // - касание (><) - don't return as intersection; - // - 'X'-crossing - return as intersection; - // 'X'-crossing defines when points lay in different cones. + // check if sections have any intersection + if (s1 * s2 > 0.0 || s3 * s4 > 0.0) + continue; - if (s1 == 0.0 && IsInSection(a, b, c)) - { - PointD const prev = *PrevIterInCycle(j, beg, end); + // Common principle if any point lay exactly on section, check 2 variants: + // - касание (><) - don't return as intersection; + // - 'X'-crossing - return as intersection; + // 'X'-crossing defines when points lay in different cones. - PointD test[] = { a, b }; - if (a == c) test[0] = *PrevIterInCycle(i, beg, end); - if (b == c) test[1] = *NextIterInCycle(ii, beg, end); + if (s1 == 0.0 && IsInSection(a, b, c)) + { + PointD const prev = *PrevIterInCycle(j, beg, end); - if (IsSegmentInCone(c, test[0], prev, d) == IsSegmentInCone(c, test[1], prev, d)) - continue; - } + PointD test[] = {a, b}; + if (a == c) + test[0] = *PrevIterInCycle(i, beg, end); + if (b == c) + test[1] = *NextIterInCycle(ii, beg, end); - if (s2 == 0.0 && IsInSection(a, b, d)) - { - PointD const next = *NextIterInCycle(jj, beg, end); + if (IsSegmentInCone(c, test[0], prev, d) == IsSegmentInCone(c, test[1], prev, d)) + continue; + } - PointD test[] = { a, b }; - if (a == d) test[0] = *PrevIterInCycle(i, beg, end); - if (b == d) test[1] = *NextIterInCycle(ii, beg, end); + if (s2 == 0.0 && IsInSection(a, b, d)) + { + PointD const next = *NextIterInCycle(jj, beg, end); - if (IsSegmentInCone(d, test[0], c, next) == IsSegmentInCone(d, test[1], c, next)) - continue; - } + PointD test[] = {a, b}; + if (a == d) + test[0] = *PrevIterInCycle(i, beg, end); + if (b == d) + test[1] = *NextIterInCycle(ii, beg, end); - if (s3 == 0.0 && IsInSection(c, d, a)) - { - PointD const prev = *PrevIterInCycle(i, beg, end); + if (IsSegmentInCone(d, test[0], c, next) == IsSegmentInCone(d, test[1], c, next)) + continue; + } - PointD test[] = { c, d }; - if (c == a) test[0] = *PrevIterInCycle(j, beg, end); - if (d == a) test[1] = *NextIterInCycle(jj, beg, end); + if (s3 == 0.0 && IsInSection(c, d, a)) + { + PointD const prev = *PrevIterInCycle(i, beg, end); - if (IsSegmentInCone(a, test[0], prev, b) == IsSegmentInCone(a, test[1], prev, b)) - continue; - } + PointD test[] = {c, d}; + if (c == a) + test[0] = *PrevIterInCycle(j, beg, end); + if (d == a) + test[1] = *NextIterInCycle(jj, beg, end); - if (s4 == 0.0 && IsInSection(c, d, b)) - { - PointD const next = *NextIterInCycle(ii, beg, end); + if (IsSegmentInCone(a, test[0], prev, b) == IsSegmentInCone(a, test[1], prev, b)) + continue; + } - PointD test[] = { c, d }; - if (c == b) test[0] = *PrevIterInCycle(j, beg, end); - if (d == b) test[1] = *NextIterInCycle(jj, beg, end); + if (s4 == 0.0 && IsInSection(c, d, b)) + { + PointD const next = *NextIterInCycle(ii, beg, end); - if (IsSegmentInCone(b, test[0], a, next) == IsSegmentInCone(b, test[1], a, next)) - continue; - } + PointD test[] = {c, d}; + if (c == b) + test[0] = *PrevIterInCycle(j, beg, end); + if (d == b) + test[1] = *NextIterInCycle(jj, beg, end); - return true; + if (IsSegmentInCone(b, test[0], a, next) == IsSegmentInCone(b, test[1], a, next)) + continue; } - return false; + return true; + } } + + return false; } -} +} // namespace robust +} // namespace m2 diff --git a/geometry/screenbase.cpp b/geometry/screenbase.cpp index 4d27415a2e..fabf1d5b56 100644 --- a/geometry/screenbase.cpp +++ b/geometry/screenbase.cpp @@ -1,11 +1,13 @@ #include "geometry/screenbase.hpp" -#include "geometry/transformations.hpp" #include "geometry/angles.hpp" +#include "geometry/transformations.hpp" #include "base/assert.hpp" #include "base/logging.hpp" -#include "std/cmath.hpp" +#include <cmath> + +using namespace std; double constexpr kPerspectiveAngleFOV = math::pi / 3.0; double constexpr kMaxPerspectiveAngle1 = math::pi4; @@ -15,22 +17,22 @@ double constexpr kStartPerspectiveScale1 = 1.7e-5; double constexpr kEndPerspectiveScale1 = 0.3e-5; double constexpr kEndPerspectiveScale2 = 0.13e-5; -ScreenBase::ScreenBase() : - m_ViewportRect(0, 0, 640, 480), - m_PixelRect(m_ViewportRect), - m_Scale(0.1), - m_Angle(0.0), - m_Org(320, 240), - m_3dFOV(kPerspectiveAngleFOV), - m_3dNearZ(0.001), - m_3dFarZ(0.0), - m_3dAngleX(0.0), - m_3dMaxAngleX(0.0), - m_3dScale(1.0), - m_isPerspective(false), - m_isAutoPerspective(false), - m_GlobalRect(m_Org, ang::AngleD(0), m2::RectD(-320, -240, 320, 240)), - m_ClipRect(m2::RectD(0, 0, 640, 480)) +ScreenBase::ScreenBase() + : m_ViewportRect(0, 0, 640, 480) + , m_PixelRect(m_ViewportRect) + , m_Scale(0.1) + , m_Angle(0.0) + , m_Org(320, 240) + , m_3dFOV(kPerspectiveAngleFOV) + , m_3dNearZ(0.001) + , m_3dFarZ(0.0) + , m_3dAngleX(0.0) + , m_3dMaxAngleX(0.0) + , m_3dScale(1.0) + , m_isPerspective(false) + , m_GlobalRect(m_Org, ang::AngleD(0), m2::RectD(-320, -240, 320, 240)) + , m_ClipRect(m2::RectD(0, 0, 640, 480)) + , m_isAutoPerspective(false) { m_GtoP = math::Identity<double, 3>(); m_PtoG = math::Identity<double, 3>(); @@ -42,10 +44,8 @@ ScreenBase::ScreenBase(m2::RectI const & pxRect, m2::AnyRectD const & glbRect) SetFromRect(glbRect); } -ScreenBase::ScreenBase(ScreenBase const & s, - m2::PointD const & org, double scale, double angle) - : m_ViewportRect(s.m_ViewportRect), - m_Scale(scale), m_Angle(angle), m_Org(org) +ScreenBase::ScreenBase(ScreenBase const & s, m2::PointD const & org, double scale, double angle) + : m_ViewportRect(s.m_ViewportRect), m_Scale(scale), m_Angle(angle), m_Org(org) { UpdateDependentParameters(); } @@ -54,25 +54,17 @@ void ScreenBase::UpdateDependentParameters() { m_PixelRect = CalculatePixelRect(m_Scale); - m_PtoG = math::Shift( /// 5. shifting on (E0, N0) - math::Rotate( /// 4. rotating on the screen angle - math::Scale( /// 3. scaling to translate pixel sizes to global - math::Scale( /// 2. swapping the Y axis??? why??? supposed to be a rotation on -pi / 2 here. - math::Shift( /// 1. shifting for the pixel center to become (0, 0) - math::Identity<double, 3>(), - - m_PixelRect.Center() - ), - 1, - -1 - ), - m_Scale, - m_Scale - ), - m_Angle.cos(), - m_Angle.sin() - ), - m_Org - ); + m_PtoG = math::Shift( /// 5. shifting on (E0, N0) + math::Rotate( /// 4. rotating on the screen angle + math::Scale( /// 3. scaling to translate pixel sizes to global + math::Scale( /// 2. swapping the Y axis??? why??? supposed to be a rotation on -pi / + /// 2 here. + math::Shift( /// 1. shifting for the pixel center to become (0, 0) + math::Identity<double, 3>(), -m_PixelRect.Center()), + 1, -1), + m_Scale, m_Scale), + m_Angle.cos(), m_Angle.sin()), + m_Org); m_GtoP = math::Inverse(m_PtoG); @@ -102,13 +94,15 @@ double ScreenBase::CalculateAutoPerspectiveAngle(double scale) if (scale > kEndPerspectiveScale1) { - double const k = (kStartPerspectiveScale1 - scale) / (kStartPerspectiveScale1 - kEndPerspectiveScale1); + double const k = + (kStartPerspectiveScale1 - scale) / (kStartPerspectiveScale1 - kEndPerspectiveScale1); return kMaxPerspectiveAngle1 * k; } if (scale > kEndPerspectiveScale2) { - double const k = (kEndPerspectiveScale1 - scale) / (kEndPerspectiveScale1 - kEndPerspectiveScale2); + double const k = + (kEndPerspectiveScale1 - scale) / (kEndPerspectiveScale1 - kEndPerspectiveScale2); return kMaxPerspectiveAngle1 + (kMaxPerspectiveAngle2 - kMaxPerspectiveAngle1) * k; } @@ -116,10 +110,7 @@ double ScreenBase::CalculateAutoPerspectiveAngle(double scale) } // static -double ScreenBase::GetStartPerspectiveScale() -{ - return kStartPerspectiveScale1; -} +double ScreenBase::GetStartPerspectiveScale() { return kStartPerspectiveScale1; } double ScreenBase::CalculatePerspectiveAngle(double scale) const { @@ -147,10 +138,7 @@ void ScreenBase::SetFromRects(m2::AnyRectD const & glbRect, m2::RectD const & px UpdateDependentParameters(); } -void ScreenBase::SetFromRect(m2::AnyRectD const & glbRect) -{ - SetFromRects(glbRect, m_PixelRect); -} +void ScreenBase::SetFromRect(m2::AnyRectD const & glbRect) { SetFromRects(glbRect, m_PixelRect); } void ScreenBase::SetFromParams(m2::PointD const & org, double angle, double scale) { @@ -166,7 +154,7 @@ void ScreenBase::MatchGandP(m2::PointD const & g, m2::PointD const & p) SetOrg(m_Org - g_current + g); } -void ScreenBase::MatchGandP3d(m2::PointD const & g, m2::PointD const &p3d) +void ScreenBase::MatchGandP3d(m2::PointD const & g, m2::PointD const & p3d) { m2::PointD g_current = PtoG(P3dtoP(p3d)); SetOrg(m_Org - g_current + g); @@ -208,10 +196,7 @@ void ScreenBase::OnSize(m2::RectI const & r) UpdateDependentParameters(); } -void ScreenBase::OnSize(int x0, int y0, int w, int h) -{ - OnSize(m2::RectI(x0, y0, x0 + w, y0 + h)); -} +void ScreenBase::OnSize(int x0, int y0, int w, int h) { OnSize(m2::RectI(x0, y0, x0 + w, y0 + h)); } void ScreenBase::SetScale(double scale) { @@ -225,38 +210,22 @@ void ScreenBase::SetAngle(double angle) UpdateDependentParameters(); } -int ScreenBase::GetWidth() const -{ - return my::rounds(m_PixelRect.SizeX()); -} +int ScreenBase::GetWidth() const { return my::rounds(m_PixelRect.SizeX()); } -int ScreenBase::GetHeight() const -{ - return my::rounds(m_PixelRect.SizeY()); -} +int ScreenBase::GetHeight() const { return my::rounds(m_PixelRect.SizeY()); } -ScreenBase::MatrixT const -ScreenBase::CalcTransform(m2::PointD const & oldPt1, m2::PointD const & oldPt2, - m2::PointD const & newPt1, m2::PointD const & newPt2, - bool allowRotate) +ScreenBase::MatrixT const ScreenBase::CalcTransform(m2::PointD const & oldPt1, + m2::PointD const & oldPt2, + m2::PointD const & newPt1, + m2::PointD const & newPt2, bool allowRotate) { double const s = newPt1.Length(newPt2) / oldPt1.Length(oldPt2); double const a = allowRotate ? ang::AngleTo(newPt1, newPt2) - ang::AngleTo(oldPt1, oldPt2) : 0.0; - MatrixT m = - math::Shift( - math::Scale( - math::Rotate( - math::Shift( - math::Identity<double, 3>(), - -oldPt1.x, -oldPt1.y - ), - a - ), - s, s - ), - newPt1.x, newPt1.y - ); + MatrixT m = math::Shift( + math::Scale(math::Rotate(math::Shift(math::Identity<double, 3>(), -oldPt1.x, -oldPt1.y), a), + s, s), + newPt1.x, newPt1.y); return m; } @@ -296,7 +265,7 @@ void ScreenBase::GetTouchRect(m2::PointD const & pixPoint, double pixRadius, void ScreenBase::GetTouchRect(m2::PointD const & pixPoint, double const pxWidth, double const pxHeight, m2::AnyRectD & glbRect) const { - double const width = pxWidth * m_Scale; + double const width = pxWidth * m_Scale; double const height = pxHeight * m_Scale; glbRect = m2::AnyRectD(PtoG(pixPoint), m_Angle, m2::RectD(-width, -height, width, height)); } @@ -309,17 +278,18 @@ bool IsPanningAndRotate(ScreenBase const & s1, ScreenBase const & s2) m2::PointD c1 = r1.Center(); m2::PointD c2 = r2.Center(); - m2::PointD globPt(c1.x - r1.minX(), - c1.y - r1.minY()); + m2::PointD globPt(c1.x - r1.minX(), c1.y - r1.minY()); - m2::PointD p1 = s1.GtoP(s1.GlobalRect().ConvertFrom(c1)) - s1.GtoP(s1.GlobalRect().ConvertFrom(c1 + globPt)); - m2::PointD p2 = s2.GtoP(s2.GlobalRect().ConvertFrom(c2)) - s2.GtoP(s2.GlobalRect().ConvertFrom(c2 + globPt)); + m2::PointD p1 = + s1.GtoP(s1.GlobalRect().ConvertFrom(c1)) - s1.GtoP(s1.GlobalRect().ConvertFrom(c1 + globPt)); + m2::PointD p2 = + s2.GtoP(s2.GlobalRect().ConvertFrom(c2)) - s2.GtoP(s2.GlobalRect().ConvertFrom(c2 + globPt)); return p1.EqualDxDy(p2, 0.00001); } -void ScreenBase::ExtractGtoPParams(MatrixT const & m, - double & a, double & s, double & dx, double & dy) +void ScreenBase::ExtractGtoPParams(MatrixT const & m, double & a, double & s, double & dx, + double & dy) { s = sqrt(m(0, 0) * m(0, 0) + m(0, 1) * m(0, 1)); @@ -336,7 +306,8 @@ double ScreenBase::CalculateScale3d(double rotationAngle) const // Ratio of the expanded plane's size to the original size. double const y3dScale = cos(rotationAngle) + sin(rotationAngle) * tan(halfFOV + rotationAngle); - double const x3dScale = 1.0 + 2 * sin(rotationAngle) * cos(halfFOV) / (cameraZ * cos(halfFOV + rotationAngle)); + double const x3dScale = + 1.0 + 2 * sin(rotationAngle) * cos(halfFOV) / (cameraZ * cos(halfFOV + rotationAngle)); return max(x3dScale, y3dScale); } @@ -358,7 +329,8 @@ m2::RectD ScreenBase::CalculatePixelRect(double scale) const // Place the camera at the distance, where it gives the same view of plane as the // orthogonal projection does. Calculate what part of the map would be visible, // when it is rotated through maxRotationAngle around its near horizontal side. -void ScreenBase::ApplyPerspective(double currentRotationAngle, double maxRotationAngle, double angleFOV) +void ScreenBase::ApplyPerspective(double currentRotationAngle, double maxRotationAngle, + double angleFOV) { ASSERT_GREATER(angleFOV, 0.0, ()); ASSERT_LESS(angleFOV, math::pi2, ()); @@ -418,11 +390,10 @@ void ScreenBase::SetRotationAngle(double rotationAngle) Matrix3dT projectionM = math::Zero<double, 4>(); m_3dFarZ = cameraZ + 2.0 * sin(m_3dAngleX) * m_3dScale; projectionM(0, 0) = projectionM(1, 1) = cameraZ; - projectionM(2, 2) = m_3dAngleX != 0.0 ? (m_3dFarZ + m_3dNearZ) / (m_3dFarZ - m_3dNearZ) - : 0.0; + projectionM(2, 2) = m_3dAngleX != 0.0 ? (m_3dFarZ + m_3dNearZ) / (m_3dFarZ - m_3dNearZ) : 0.0; projectionM(2, 3) = 1.0; - projectionM(3, 2) = m_3dAngleX != 0.0 ? -2.0 * m_3dFarZ * m_3dNearZ / (m_3dFarZ - m_3dNearZ) - : 0.0; + projectionM(3, 2) = + m_3dAngleX != 0.0 ? -2.0 * m_3dFarZ * m_3dNearZ / (m_3dFarZ - m_3dNearZ) : 0.0; m_Pto3d = scaleM * rotateM * translateM * projectionM; m_3dtoP = math::Inverse(m_Pto3d); @@ -442,10 +413,7 @@ void ScreenBase::ResetPerspective() Move(0.0, -old_dy / 2.0); } -m2::PointD ScreenBase::PtoP3d(m2::PointD const & pt) const -{ - return PtoP3d(pt, 0.0); -} +m2::PointD ScreenBase::PtoP3d(m2::PointD const & pt) const { return PtoP3d(pt, 0.0); } double ScreenBase::GetZScale() const { diff --git a/geometry/screenbase.hpp b/geometry/screenbase.hpp index 7f45f9b3ac..2278883134 100644 --- a/geometry/screenbase.hpp +++ b/geometry/screenbase.hpp @@ -1,12 +1,11 @@ #pragma once +#include "geometry/any_rect2d.hpp" #include "geometry/point2d.hpp" #include "geometry/rect2d.hpp" -#include "geometry/any_rect2d.hpp" #include "base/matrix.hpp" - class ScreenBase { public: @@ -14,55 +13,9 @@ public: using Matrix3dT = math::Matrix<double, 4, 4>; using Vector3dT = math::Matrix<double, 1, 4>; -private: - m2::RectD m_ViewportRect; - m2::RectD m_PixelRect; - - double m_Scale; - ang::AngleD m_Angle; - m2::PointD m_Org; - - double m_3dFOV; - double m_3dNearZ; - double m_3dFarZ; - double m_3dAngleX; - double m_3dMaxAngleX; - double m_3dScale; - bool m_isPerspective; - bool m_isAutoPerspective; - -protected: - /// @group Dependent parameters - /// Global to Pixel conversion matrix. - /// |a11 a12 0| - /// |x, y, 1| * |a21 a22 0| = |x', y', 1| - /// |a31 a32 1| - /// @{ - MatrixT m_GtoP; - - /// Pixel to Global conversion matrix. Inverted GtoP matrix. - MatrixT m_PtoG; - - /// Global Rect - m2::AnyRectD m_GlobalRect; - - /// X-axis aligned global rect used for clipping - m2::RectD m_ClipRect; - - /// @} - - Matrix3dT m_Pto3d; - Matrix3dT m_3dtoP; - - // Update dependent parameters from base parameters. - // Must be called when base parameters changed. - void UpdateDependentParameters(); - -public: ScreenBase(); ScreenBase(m2::RectI const & pxRect, m2::AnyRectD const & glbRect); - ScreenBase(ScreenBase const & s, - m2::PointD const & org, double scale, double angle); + ScreenBase(ScreenBase const & s, m2::PointD const & org, double scale, double angle); void SetFromRect(m2::AnyRectD const & rect); @@ -91,24 +44,18 @@ public: int GetWidth() const; int GetHeight() const; - inline m2::PointD GtoP(m2::PointD const & pt) const - { - return pt * m_GtoP; - } + m2::PointD GtoP(m2::PointD const & pt) const { return pt * m_GtoP; } - inline m2::PointD PtoG(m2::PointD const & pt) const - { - return pt * m_PtoG; - } + m2::PointD PtoG(m2::PointD const & pt) const { return pt * m_PtoG; } - inline void GtoP(double & x, double & y) const + void GtoP(double & x, double & y) const { double tempX = x; x = tempX * m_GtoP(0, 0) + y * m_GtoP(1, 0) + m_GtoP(2, 0); y = tempX * m_GtoP(1, 0) + y * m_GtoP(1, 1) + m_GtoP(2, 1); } - inline void PtoG(double & x, double & y) const + void PtoG(double & x, double & y) const { double tempX = x; x = tempX * m_PtoG(0, 0) + y * m_PtoG(1, 0) + m_PtoG(2, 0); @@ -122,8 +69,8 @@ public: void MatchGandP3d(m2::PointD const & g, m2::PointD const & p3d); void GetTouchRect(m2::PointD const & pixPoint, double pixRadius, m2::AnyRectD & glbRect) const; - void GetTouchRect(m2::PointD const & pixPoint, double const pxWidth, - double const pxHeight, m2::AnyRectD & glbRect) const; + void GetTouchRect(m2::PointD const & pixPoint, double const pxWidth, double const pxHeight, + m2::AnyRectD & glbRect) const; MatrixT const & GtoPMatrix() const { return m_GtoP; } MatrixT const & PtoGMatrix() const { return m_PtoG; } @@ -156,10 +103,7 @@ public: m2::PointD PtoP3d(m2::PointD const & pt) const; m2::PointD PtoP3d(m2::PointD const & pt, double ptZ) const; - m2::RectD const & PixelRectIn3d() const - { - return m_ViewportRect; - } + m2::RectD const & PixelRectIn3d() const { return m_ViewportRect; } double CalculateScale3d(double rotationAngle) const; m2::RectD CalculatePixelRect(double scale) const; @@ -171,27 +115,69 @@ public: static double CalculateAutoPerspectiveAngle(double scale); static double GetStartPerspectiveScale(); - /// Compute arbitrary pixel transformation, that translates the (oldPt1, oldPt2) -> (newPt1, newPt2) + /// Compute arbitrary pixel transformation, that translates the (oldPt1, oldPt2) -> (newPt1, + /// newPt2) static MatrixT const CalcTransform(m2::PointD const & oldPt1, m2::PointD const & oldPt2, m2::PointD const & newPt1, m2::PointD const & newPt2, bool allowRotate); - /// Setting GtoP matrix extracts the Angle and m_Org parameters, leaving PixelRect intact void SetGtoPMatrix(MatrixT const & m); /// Extracting parameters from matrix, that is supposed to represent GtoP transformation - static void ExtractGtoPParams(MatrixT const & m, double & a, double & s, double & dx, double & dy); + static void ExtractGtoPParams(MatrixT const & m, double & a, double & s, double & dx, + double & dy); - bool operator != (ScreenBase const & src) const - { - return !(*this == src); - } + bool operator!=(ScreenBase const & src) const { return !(*this == src); } - bool operator == (ScreenBase const & src) const + bool operator==(ScreenBase const & src) const { return (m_GtoP == src.m_GtoP) && (m_PtoG == src.m_PtoG); } + +protected: + // Update dependent parameters from base parameters. + // Must be called when base parameters changed. + void UpdateDependentParameters(); + + /// @group Dependent parameters + /// Global to Pixel conversion matrix. + /// |a11 a12 0| + /// |x, y, 1| * |a21 a22 0| = |x', y', 1| + /// |a31 a32 1| + /// @{ + MatrixT m_GtoP; + + /// Pixel to Global conversion matrix. Inverted GtoP matrix. + MatrixT m_PtoG; + + /// Global Rect + m2::AnyRectD m_GlobalRect; + + /// X-axis aligned global rect used for clipping + m2::RectD m_ClipRect; + + /// @} + + Matrix3dT m_Pto3d; + Matrix3dT m_3dtoP; + +private: + m2::RectD m_ViewportRect; + m2::RectD m_PixelRect; + + double m_Scale; + ang::AngleD m_Angle; + m2::PointD m_Org; + + double m_3dFOV; + double m_3dNearZ; + double m_3dFarZ; + double m_3dAngleX; + double m_3dMaxAngleX; + double m_3dScale; + bool m_isPerspective; + bool m_isAutoPerspective; }; /// checking whether the s1 transforms into s2 without scaling, only with shift and rotation diff --git a/geometry/segment2d.cpp b/geometry/segment2d.cpp index f51d5940c7..913f83542c 100644 --- a/geometry/segment2d.cpp +++ b/geometry/segment2d.cpp @@ -3,16 +3,12 @@ #include "geometry/robust_orientation.hpp" #include <algorithm> +#include <string> using namespace std; namespace m2 { -string DebugPrint(Segment2D const & segment) -{ - return "(" + DebugPrint(segment.m_u) + ", " + DebugPrint(segment.m_v) + ")"; -} - bool IsPointOnSegmentEps(PointD const & pt, PointD const & p1, PointD const & p2, double eps) { double const t = robust::OrientedS(p1, p2, pt); @@ -43,4 +39,9 @@ bool IsPointOnSegment(PointD const & pt, PointD const & p1, PointD const & p2) double const kEps = 1e-100; return IsPointOnSegmentEps(pt, p1, p2, kEps); } + +std::string DebugPrint(Segment2D const & segment) +{ + return "(" + DebugPrint(segment.m_u) + ", " + DebugPrint(segment.m_v) + ")"; +} } // namespace m2 diff --git a/geometry/tree4d.hpp b/geometry/tree4d.hpp index 69aaf55f6c..e9011ae1e1 100644 --- a/geometry/tree4d.hpp +++ b/geometry/tree4d.hpp @@ -1,277 +1,243 @@ #pragma once -#include "geometry/rect2d.hpp" #include "geometry/point2d.hpp" +#include "geometry/rect2d.hpp" -#include "base/stl_add.hpp" #include "base/logging.hpp" +#include "base/stl_add.hpp" -#include "std/sstream.hpp" -#include "std/vector.hpp" +#include <sstream> +#include <string> +#include <vector> #include "3party/kdtree++/kdtree.hpp" - namespace m4 { - template <typename T> - struct TraitsDef - { - m2::RectD const LimitRect(T const & t) const - { - return t.GetLimitRect(); - } - }; +template <typename T> +struct TraitsDef +{ + m2::RectD const LimitRect(T const & t) const { return t.GetLimitRect(); } +}; - template <class T, typename Traits = TraitsDef<T> > - class Tree +template <typename T, typename Traits = TraitsDef<T>> +class Tree +{ + class ValueT { - class ValueT + void SetRect(m2::RectD const & r) { - void SetRect(m2::RectD const & r) - { - m_pts[0] = r.minX(); - m_pts[1] = r.minY(); - m_pts[2] = r.maxX(); - m_pts[3] = r.maxY(); - } + m_pts[0] = r.minX(); + m_pts[1] = r.minY(); + m_pts[2] = r.maxX(); + m_pts[3] = r.maxY(); + } - public: - T m_val; - double m_pts[4]; + public: + T m_val; + double m_pts[4]; - typedef double value_type; + typedef double value_type; - ValueT(T const & t, m2::RectD const & r) : m_val(t) - { - SetRect(r); - } - ValueT(T && t, m2::RectD const & r) : m_val(move(t)) - { - SetRect(r); - } + ValueT(T const & t, m2::RectD const & r) : m_val(t) { SetRect(r); } + ValueT(T && t, m2::RectD const & r) : m_val(move(t)) { SetRect(r); } - bool IsIntersect(m2::RectD const & r) const - { - return !((m_pts[2] <= r.minX()) || (m_pts[0] >= r.maxX()) || - (m_pts[3] <= r.minY()) || (m_pts[1] >= r.maxY())); - } + bool IsIntersect(m2::RectD const & r) const + { + return !((m_pts[2] <= r.minX()) || (m_pts[0] >= r.maxX()) || (m_pts[3] <= r.minY()) || + (m_pts[1] >= r.maxY())); + } - bool operator ==(ValueT const & r) const - { - return (m_val == r.m_val); - } + bool operator==(ValueT const & r) const { return (m_val == r.m_val); } - string DebugPrint() const - { - ostringstream out; + std::string DebugPrint() const + { + std::ostringstream out; - out << DebugPrint(m_val) << ", (" - << m_pts[0] << ", " - << m_pts[1] << ", " - << m_pts[2] << ", " - << m_pts[3] << ")"; + out << DebugPrint(m_val) << ", (" << m_pts[0] << ", " << m_pts[1] << ", " << m_pts[2] << ", " + << m_pts[3] << ")"; - return out.str(); - } + return out.str(); + } - double operator[](size_t i) const { return m_pts[i]; } + double operator[](size_t i) const { return m_pts[i]; } - m2::RectD GetRect() const { return m2::RectD(m_pts[0], m_pts[1], m_pts[2], m_pts[3]); } - }; + m2::RectD GetRect() const { return m2::RectD(m_pts[0], m_pts[1], m_pts[2], m_pts[3]); } + }; - typedef KDTree::KDTree<4, ValueT> TreeT; - TreeT m_tree; + typedef KDTree::KDTree<4, ValueT> TreeT; + TreeT m_tree; - // Do-class for rect-iteration in tree. - template <class ToDo> class for_each_helper - { - m2::RectD const & m_rect; - ToDo m_toDo; - - public: - for_each_helper(m2::RectD const & r, ToDo toDo) - : m_rect(r), m_toDo(toDo) - { - } + // Do-class for rect-iteration in tree. + template <typename ToDo> + class for_each_helper + { + m2::RectD const & m_rect; + ToDo m_toDo; - bool ScanLeft(size_t plane, ValueT const & v) const - { - switch (plane & 3) // % 4 - { - case 2: return m_rect.minX() < v[2]; - case 3: return m_rect.minY() < v[3]; - default: return true; - } - } + public: + for_each_helper(m2::RectD const & r, ToDo toDo) : m_rect(r), m_toDo(toDo) {} - bool ScanRight(size_t plane, ValueT const & v) const + bool ScanLeft(size_t plane, ValueT const & v) const + { + switch (plane & 3) // % 4 { - switch (plane & 3) // % 4 - { - case 0: return m_rect.maxX() > v[0]; - case 1: return m_rect.maxY() > v[1]; - default: return true; - } + case 2: return m_rect.minX() < v[2]; + case 3: return m_rect.minY() < v[3]; + default: return true; } + } - void operator() (ValueT const & v) const + bool ScanRight(size_t plane, ValueT const & v) const + { + switch (plane & 3) // % 4 { - if (v.IsIntersect(m_rect)) - m_toDo(v); + case 0: return m_rect.maxX() > v[0]; + case 1: return m_rect.maxY() > v[1]; + default: return true; } - }; + } - template <class ToDo> for_each_helper<ToDo> GetFunctor(m2::RectD const & rect, ToDo toDo) const + void operator()(ValueT const & v) const { - return for_each_helper<ToDo>(rect, toDo); + if (v.IsIntersect(m_rect)) + m_toDo(v); } + }; - protected: - Traits m_traits; - m2::RectD GetLimitRect(T const & t) const { return m_traits.LimitRect(t); } + template <typename ToDo> + for_each_helper<ToDo> GetFunctor(m2::RectD const & rect, ToDo toDo) const + { + return for_each_helper<ToDo>(rect, toDo); + } - public: - Tree(Traits const & traits = Traits()) : m_traits(traits) {} +protected: + Traits m_traits; + m2::RectD GetLimitRect(T const & t) const { return m_traits.LimitRect(t); } - typedef T elem_t; +public: + Tree(Traits const & traits = Traits()) : m_traits(traits) {} - void Add(T const & obj) - { - Add(obj, GetLimitRect(obj)); - } - void Add(T && obj) - { - Add(move(obj), GetLimitRect(obj)); - } + typedef T elem_t; - void Add(T const & obj, m2::RectD const & rect) - { - m_tree.insert(ValueT(obj, rect)); - } - void Add(T && obj, m2::RectD const & rect) - { - m_tree.insert(ValueT(move(obj), rect)); - } + void Add(T const & obj) { Add(obj, GetLimitRect(obj)); } + void Add(T && obj) { Add(move(obj), GetLimitRect(obj)); } - private: - template <class CompareT> - void ReplaceImpl(T const & obj, m2::RectD const & rect, CompareT comp) - { - bool skip = false; - vector<ValueT const *> isect; + void Add(T const & obj, m2::RectD const & rect) { m_tree.insert(ValueT(obj, rect)); } + void Add(T && obj, m2::RectD const & rect) { m_tree.insert(ValueT(move(obj), rect)); } - m_tree.for_each(GetFunctor(rect, [&] (ValueT const & v) - { - if (skip) - return; - - switch (comp(obj, v.m_val)) - { - case 1: - isect.push_back(&v); - break; - case -1: - skip = true; - break; - } - })); +private: + template <typename CompareT> + void ReplaceImpl(T const & obj, m2::RectD const & rect, CompareT comp) + { + bool skip = false; + std::vector<ValueT const *> isect; + m_tree.for_each(GetFunctor(rect, [&](ValueT const & v) { if (skip) return; - for (ValueT const * v : isect) - m_tree.erase(*v); + switch (comp(obj, v.m_val)) + { + case 1: isect.push_back(&v); break; + case -1: skip = true; break; + } + })); - Add(obj, rect); - } + if (skip) + return; - public: - template <class CompareT> - void ReplaceAllInRect(T const & obj, CompareT comp) - { - ReplaceImpl(obj, GetLimitRect(obj), [&comp] (T const & t1, T const & t2) - { + for (ValueT const * v : isect) + m_tree.erase(*v); + + Add(obj, rect); + } + +public: + template <typename CompareT> + void ReplaceAllInRect(T const & obj, CompareT comp) + { + ReplaceImpl(obj, GetLimitRect(obj), + [&comp](T const & t1, T const & t2) { return comp(t1, t2) ? 1 : -1; }); + } + + template <typename EqualT, class CompareT> + void ReplaceEqualInRect(T const & obj, EqualT eq, CompareT comp) + { + ReplaceImpl(obj, GetLimitRect(obj), [&](T const & t1, T const & t2) { + if (eq(t1, t2)) return comp(t1, t2) ? 1 : -1; - }); - } + else + return 0; + }); + } - template <class EqualT, class CompareT> - void ReplaceEqualInRect(T const & obj, EqualT eq, CompareT comp) - { - ReplaceImpl(obj, GetLimitRect(obj), [&] (T const & t1, T const & t2) - { - if (eq(t1, t2)) - return comp(t1, t2) ? 1 : -1; - else - return 0; - }); - } + void Erase(T const & obj, m2::RectD const & r) + { + ValueT val(obj, r); + m_tree.erase_exact(val); + } - void Erase(T const & obj, m2::RectD const & r) - { - ValueT val(obj, r); - m_tree.erase_exact(val); - } + void Erase(T const & obj) + { + ValueT val(obj, m_traits.LimitRect(obj)); + m_tree.erase_exact(val); + } - void Erase(T const & obj) - { - ValueT val(obj, m_traits.LimitRect(obj)); - m_tree.erase_exact(val); - } + template <typename ToDo> + void ForEach(ToDo && toDo) const + { + for (ValueT const & v : m_tree) + toDo(v.m_val); + } - template <class ToDo> - void ForEach(ToDo && toDo) const - { - for (ValueT const & v : m_tree) - toDo(v.m_val); - } - template <class ToDo> - void ForEachEx(ToDo && toDo) const - { - for (ValueT const & v : m_tree) - toDo(v.GetRect(), v.m_val); - } + template <typename ToDo> + void ForEachEx(ToDo && toDo) const + { + for (ValueT const & v : m_tree) + toDo(v.GetRect(), v.m_val); + } - template <class ToDo> - bool FindNode(ToDo && toDo) const - { - for (ValueT const & v : m_tree) - if (toDo(v.m_val)) - return true; + template <typename ToDo> + bool FindNode(ToDo && toDo) const + { + for (ValueT const & v : m_tree) + if (toDo(v.m_val)) + return true; - return false; - } + return false; + } - template <class ToDo> - void ForEachInRect(m2::RectD const & rect, ToDo && toDo) const - { - m_tree.for_each(GetFunctor(rect, [&toDo] (ValueT const & v) { toDo(v.m_val); })); - } - template <class ToDo> - void ForEachInRectEx(m2::RectD const & rect, ToDo && toDo) const - { - m_tree.for_each(GetFunctor(rect, [&toDo] (ValueT const & v) { toDo(v.GetRect(), v.m_val); })); - } + template <typename ToDo> + void ForEachInRect(m2::RectD const & rect, ToDo && toDo) const + { + m_tree.for_each(GetFunctor(rect, [&toDo](ValueT const & v) { toDo(v.m_val); })); + } - bool IsEmpty() const { return m_tree.empty(); } + template <typename ToDo> + void ForEachInRectEx(m2::RectD const & rect, ToDo && toDo) const + { + m_tree.for_each(GetFunctor(rect, [&toDo](ValueT const & v) { toDo(v.GetRect(), v.m_val); })); + } - size_t GetSize() const { return m_tree.size(); } + bool IsEmpty() const { return m_tree.empty(); } - void Clear() { m_tree.clear(); } + size_t GetSize() const { return m_tree.size(); } - string DebugPrint() const - { - ostringstream out; - for (ValueT const & v : m_tree.begin()) - out << v.DebugPrint() << ", "; - return out.str(); - } - }; + void Clear() { m_tree.clear(); } - template <typename T, typename Traits> - string DebugPrint(Tree<T, Traits> const & t) + std::string DebugPrint() const { - return t.DebugPrint(); + std::ostringstream out; + for (ValueT const & v : m_tree.begin()) + out << v.DebugPrint() << ", "; + return out.str(); } +}; + +template <typename T, typename Traits> +std::string DebugPrint(Tree<T, Traits> const & t) +{ + return t.DebugPrint(); } +} // namespace m4 |