From 7a1c013f934e89411b304b81686541d4c95fcb51 Mon Sep 17 00:00:00 2001 From: Maxim Pimenov Date: Tue, 24 Jul 2018 19:31:29 +0300 Subject: Review fixes. --- geometry/angles.hpp | 10 +-- geometry/any_rect2d.hpp | 31 ++++---- geometry/avg_vector.hpp | 69 ++++++++-------- geometry/covering_utils.hpp | 20 +++-- geometry/distance.hpp | 2 +- geometry/distance_on_sphere.cpp | 26 ++++++ geometry/distance_on_sphere.hpp | 23 +----- geometry/geometry_tests/anyrect_test.cpp | 23 +++--- geometry/geometry_tests/polygon_test.cpp | 107 +++++++++++-------------- geometry/geometry_tests/region_test.cpp | 131 ++++++++++++++++--------------- geometry/point2d.hpp | 4 +- geometry/region2d.hpp | 87 ++++++++++---------- geometry/region2d/boost_concept.hpp | 26 +++--- geometry/robust_orientation.hpp | 20 ++--- geometry/screenbase.cpp | 2 +- geometry/tree4d.hpp | 113 ++++++++++++++------------ 16 files changed, 363 insertions(+), 331 deletions(-) (limited to 'geometry') diff --git a/geometry/angles.hpp b/geometry/angles.hpp index e4ca1a3a3d..a97cb8d5d6 100644 --- a/geometry/angles.hpp +++ b/geometry/angles.hpp @@ -14,8 +14,8 @@ class Angle { public: Angle() = default; - 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) {} + explicit Angle(T const & val) : m_val(val), m_sin(std::sin(val)), m_cos(std::cos(val)) {} + Angle(T const & sin, T const & cos) : m_val(std::atan2(sin, cos)), m_sin(sin), m_cos(cos) {} T const & val() const { return m_val; } @@ -25,15 +25,15 @@ public: Angle const & operator*=(math::Matrix const & m) { - m2::Point pt0(0, 0); + m2::Point pt0 = m2::Point::Zero(); m2::Point 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); + m_sin = std::sin(m_val); + m_cos = std::cos(m_val); return *this; } diff --git a/geometry/any_rect2d.hpp b/geometry/any_rect2d.hpp index bad6da6eb3..e66eed6f1f 100644 --- a/geometry/any_rect2d.hpp +++ b/geometry/any_rect2d.hpp @@ -7,6 +7,7 @@ #include "base/math.hpp" +#include #include #include @@ -17,6 +18,8 @@ template class AnyRect { public: + using Corners = std::array, 4>; + AnyRect() = default; /// creating from regular rect @@ -69,15 +72,15 @@ public: bool EqualDxDy(AnyRect const & r, T eps) const { - std::array, 4> arr1; + Corners arr1; GetGlobalPoints(arr1); - sort(arr1, arr1 + 4); + std::sort(arr1.begin(), arr1.end()); - std::array, 4> arr2; + Corners arr2; r.GetGlobalPoints(arr2); - sort(arr2, arr2 + 4); + std::sort(arr2.begin(), arr2.end()); - for (size_t i = 0; i < 4; ++i) + for (size_t i = 0; i < arr1.size(); ++i) { if (!arr1[i].EqualDxDy(arr2[i], eps)) return false; @@ -90,7 +93,7 @@ public: bool IsRectInside(AnyRect const & r) const { - std::array, 4> pts; + Corners pts; r.GetGlobalPoints(pts); ConvertTo(pts); return m_rect.IsPointInside(pts[0]) && m_rect.IsPointInside(pts[1]) && @@ -101,7 +104,7 @@ public: { if (r.GetLocalRect() == Rect()) return false; - std::array, 4> pts; + Corners pts; r.GetGlobalPoints(pts); ConvertTo(pts); @@ -132,7 +135,7 @@ public: return Convert(p - Convert(m_zero, i(), j(), i1, j1), i1, j1, i(), j()); } - void ConvertTo(std::array, 4> & pts) const + void ConvertTo(Corners & pts) const { for (auto & p : pts) p = ConvertTo(p); @@ -148,7 +151,7 @@ public: Rect GetGlobalRect() const { - std::array, 4> pts; + Corners pts; GetGlobalPoints(pts); Rect res; @@ -157,7 +160,7 @@ public: return res; } - void GetGlobalPoints(std::array, 4> & pts) const + void GetGlobalPoints(Corners & pts) const { pts[0] = ConvertFrom(Point(m_rect.minX(), m_rect.minY())); pts[1] = ConvertFrom(Point(m_rect.minX(), m_rect.maxY())); @@ -173,7 +176,7 @@ public: void Add(AnyRect const & r) { - std::array, 4> pts; + Corners pts; r.GetGlobalPoints(pts); ConvertTo(pts); for (auto const & p : pts) @@ -214,7 +217,7 @@ using AnyRectD = AnyRect; using AnyRectF = AnyRect; template -AnyRect const Offset(AnyRect const & r, Point const & pt) +AnyRect Offset(AnyRect const & r, Point const & pt) { AnyRect res(r); res.Offset(pt); @@ -222,7 +225,7 @@ AnyRect const Offset(AnyRect const & r, Point const & pt) } template -AnyRect const Inflate(AnyRect const & r, U const & dx, U const & dy) +AnyRect Inflate(AnyRect const & r, U const & dx, U const & dy) { AnyRect res = r; res.Inflate(dx, dy); @@ -230,7 +233,7 @@ AnyRect const Inflate(AnyRect const & r, U const & dx, U const & dy) } template -AnyRect const Inflate(AnyRect const & r, Point const & pt) +AnyRect Inflate(AnyRect const & r, Point const & pt) { return Inflate(r, pt.x, pt.y); } diff --git a/geometry/avg_vector.hpp b/geometry/avg_vector.hpp index 06eefbaa0e..9bd6f6e10d 100644 --- a/geometry/avg_vector.hpp +++ b/geometry/avg_vector.hpp @@ -5,6 +5,7 @@ #include #include +#include #include #include #include @@ -15,22 +16,45 @@ namespace math template class AvgVector { - typedef std::deque> ContT; - typedef typename ContT::value_type ValueT; +public: + explicit AvgVector(size_t count = 1) : m_count(count) + { + static_assert(std::is_floating_point::value, ""); + } + + void SetCount(size_t count) { m_count = count; } + + /// @param[in] Next measurement. + /// @param[out] Average value. + void Next(T * arr) + { + if (m_vectors.size() == m_count) + m_vectors.pop_front(); + + m_vectors.push_back({}); + std::memcpy(m_vectors.back().data(), arr, Dim * sizeof(T)); - ContT m_vectors; + if (m_vectors.size() > 1) + CalcAverage(arr); + } + +private: + using Cont = std::deque>; + using Value = typename Cont::value_type; + + Cont m_vectors; size_t m_count; - static T Distance(ValueT const & a1, ValueT const & a2) + static T Distance(Value const & a1, Value 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 std::sqrt(res); } - static void Average(ValueT const & a1, ValueT const & a2, T * res) + static void Average(Value const & a1, Value const & a2, T * res) { for (size_t i = 0; i < Dim; ++i) res[i] = (a1[i] + a2[i]) / 2.0; @@ -44,6 +68,7 @@ class AvgVector 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]); @@ -54,31 +79,10 @@ class AvgVector 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::value, ""); - } - - void SetCount(size_t count) { m_count = count; } - - /// @param[in] Next measurement. - /// @param[out] Average value. - void Next(T * arr) - { - 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 @@ -93,12 +97,7 @@ public: template class LowPassVector { - typedef std::array ArrayT; - ArrayT m_val; - T m_factor; - public: - LowPassVector() : m_factor(0.15) { m_val.fill(T()); } void SetFactor(T t) { m_factor = t; } /// @param[in] Next measurement. @@ -111,5 +110,9 @@ public: arr[i] = m_val[i]; } } + +private: + std::array m_val{}; + T m_factor = 0.15; }; } // namespace math diff --git a/geometry/covering_utils.hpp b/geometry/covering_utils.hpp index 6ef89e377f..06d660a740 100644 --- a/geometry/covering_utils.hpp +++ b/geometry/covering_utils.hpp @@ -11,6 +11,9 @@ #include "base/math.hpp" #include +#include +#include +#include namespace covering { @@ -24,8 +27,8 @@ enum CellObjectIntersection OBJECT_INSIDE_CELL = 3 }; -template -CellObjectIntersection IntersectCellWithLine(CellIdT const cell, m2::PointD const & a, +template +CellObjectIntersection IntersectCellWithLine(CellId const cell, m2::PointD const & a, m2::PointD const & b) { std::pair const xy = cell.XY(); @@ -34,15 +37,17 @@ CellObjectIntersection IntersectCellWithLine(CellIdT const cell, m2::PointD cons 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; + } if (xy.first - r <= a.x && a.x <= xy.first + r && xy.second - r <= a.y && a.y <= xy.second + r) return OBJECT_INSIDE_CELL; return CELL_OBJECT_NO_INTERSECTION; } -template -CellObjectIntersection IntersectCellWithTriangle(CellIdT const cell, m2::PointD const & a, +template +CellObjectIntersection IntersectCellWithTriangle(CellId const cell, m2::PointD const & a, m2::PointD const & b, m2::PointD const & c) { CellObjectIntersection const i1 = IntersectCellWithLine(cell, a, b); @@ -69,9 +74,9 @@ CellObjectIntersection IntersectCellWithTriangle(CellIdT const cell, m2::PointD return CELL_OBJECT_NO_INTERSECTION; } -template +template void CoverObject(IntersectF const & intersect, uint64_t cellPenaltyArea, CellIdContainerT & out, - int cellDepth, CellIdT cell) + int cellDepth, CellId cell) { if (cell.Level() == cellDepth - 1) { @@ -90,7 +95,7 @@ void CoverObject(IntersectF const & intersect, uint64_t cellPenaltyArea, CellIdC return; } - buffer_vector subdiv; + buffer_vector subdiv; for (uint8_t i = 0; i < 4; ++i) CoverObject(intersect, cellPenaltyArea, subdiv, cellDepth, cell.Child(i)); @@ -111,5 +116,4 @@ void CoverObject(IntersectF const & intersect, uint64_t cellPenaltyArea, CellIdC out.push_back(subdiv[i]); } } - } // namespace covering diff --git a/geometry/distance.hpp b/geometry/distance.hpp index 219a57b824..559d23b7af 100644 --- a/geometry/distance.hpp +++ b/geometry/distance.hpp @@ -20,7 +20,7 @@ public: m_p0 = p0; m_p1 = p1; m_d = m_p1 - m_p0; - m_length = sqrt(SquaredLength(m_d)); + m_length = std::sqrt(SquaredLength(m_d)); if (my::AlmostEqualULPs(m_length, 0.0)) { diff --git a/geometry/distance_on_sphere.cpp b/geometry/distance_on_sphere.cpp index 7aadd2b876..5900059769 100644 --- a/geometry/distance_on_sphere.cpp +++ b/geometry/distance_on_sphere.cpp @@ -3,9 +3,19 @@ #include "base/math.hpp" #include +#include using namespace std; +namespace +{ +// Earth radius in meters. +double constexpr kEarthRadiusMeters = 6378000; + +// Side of the one-degree square at the equator in meters. +double constexpr kOneDegreeEquatorLengthMeters = 111319.49079; +} // namespace + namespace ms { double DistanceOnSphere(double lat1Deg, double lon1Deg, double lat2Deg, double lon2Deg) @@ -26,4 +36,20 @@ double AreaOnSphere(ms::LatLon const & ll1, ms::LatLon const & ll2, ms::LatLon c fabs((ll2.lon - ll1.lon) * (ll3.lat - ll1.lat) - (ll3.lon - ll1.lon) * (ll2.lat - ll1.lat)); } + +double DistanceOnEarth(double lat1Deg, double lon1Deg, double lat2Deg, double lon2Deg) +{ + return kEarthRadiusMeters * DistanceOnSphere(lat1Deg, lon1Deg, lat2Deg, lon2Deg); +} + +double DistanceOnEarth(LatLon const & ll1, LatLon const & ll2) +{ + return DistanceOnEarth(ll1.lat, ll1.lon, ll2.lat, ll2.lon); +} + +double AreaOnEarth(LatLon const & ll1, LatLon const & ll2, LatLon const & ll3) +{ + return kOneDegreeEquatorLengthMeters * kOneDegreeEquatorLengthMeters * + AreaOnSphere(ll1, ll2, ll3); +} } // namespace ms diff --git a/geometry/distance_on_sphere.hpp b/geometry/distance_on_sphere.hpp index e8c6181e2f..29db2e3d3c 100644 --- a/geometry/distance_on_sphere.hpp +++ b/geometry/distance_on_sphere.hpp @@ -4,14 +4,9 @@ #include "base/base.hpp" -// namespace ms - "math on sphere", similar to the namespaces m2 and mn. +// namespace ms - "math on sphere", similar to namespace m2. namespace ms { -// Earth radius in meters. -inline double EarthRadiusMeters() { return 6378000; } -// Length of one degree square at the equator in meters. -inline double OneDegreeEquatorLengthMeters() { return 111319.49079; } - // Distance on unit sphere between (lat1, lon1) and (lat2, lon2). // lat1, lat2, lon1, lon2 - in degrees. double DistanceOnSphere(double lat1Deg, double lon1Deg, double lat2Deg, double lon2Deg); @@ -21,19 +16,9 @@ double AreaOnSphere(LatLon const & ll1, LatLon const & ll2, LatLon const & ll3); // Distance in meteres on Earth between (lat1, lon1) and (lat2, lon2). // lat1, lat2, lon1, lon2 - in degrees. -inline double DistanceOnEarth(double lat1Deg, double lon1Deg, double lat2Deg, double lon2Deg) -{ - return EarthRadiusMeters() * DistanceOnSphere(lat1Deg, lon1Deg, lat2Deg, lon2Deg); -} +double DistanceOnEarth(double lat1Deg, double lon1Deg, double lat2Deg, double lon2Deg); -inline double DistanceOnEarth(LatLon const & ll1, LatLon const & ll2) -{ - return DistanceOnEarth(ll1.lat, ll1.lon, ll2.lat, ll2.lon); -} +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); -} +double AreaOnEarth(LatLon const & ll1, LatLon const & ll2, LatLon const & ll3); } // namespace ms diff --git a/geometry/geometry_tests/anyrect_test.cpp b/geometry/geometry_tests/anyrect_test.cpp index f1575546cd..b09a4d044a 100644 --- a/geometry/geometry_tests/anyrect_test.cpp +++ b/geometry/geometry_tests/anyrect_test.cpp @@ -11,7 +11,7 @@ namespace m2 { UNIT_TEST(AnyRect_TestConvertTo) { - AnyRectD r(PointD(0, 0), math::pi / 4, RectD(0, 0, 10, 10)); + AnyRectD r(PointD(0, 0), ang::Angle(math::pi / 4), RectD(0, 0, 10, 10)); PointD pt1(100, 0); @@ -19,7 +19,7 @@ UNIT_TEST(AnyRect_TestConvertTo) TEST(r.ConvertTo(pt1).EqualDxDy(PointD(100 / sqrt2, -100 / sqrt2), 10e-5), ()); TEST(r.ConvertTo(PointD(100, 100)).EqualDxDy(PointD(100 * sqrt2, 0), 10e-5), ()); - AnyRectD r1(PointD(100, 100), math::pi / 4, RectD(0, 0, 10, 10)); + AnyRectD r1(PointD(100, 100), ang::Angle(math::pi / 4), RectD(0, 0, 10, 10)); PointD pt(100, 100 + 50 * sqrt2); @@ -28,7 +28,7 @@ UNIT_TEST(AnyRect_TestConvertTo) UNIT_TEST(AnyRect_TestConvertFrom) { - AnyRectD r(PointD(100, 100), math::pi / 6, RectD(0, 0, 10, 10)); + AnyRectD r(PointD(100, 100), ang::Angle(math::pi / 6), RectD(0, 0, 10, 10)); double const sqrt3 = sqrt(3.0); TEST(r.ConvertFrom(PointD(50, 0)).EqualDxDy(PointD(100 + 50 * sqrt3 / 2 , 100 + 50 * 1 / 2.0), 10e-5), ()); @@ -47,8 +47,8 @@ UNIT_TEST(AnyRect_ZeroRect) UNIT_TEST(AnyRect_TestIntersection) { - AnyRectD r0(PointD(93.196, 104.21), 1.03, RectD(2, 0, 4, 15)); - AnyRectD r1(PointD(99.713, 116.02), -1.03, RectD(0, 0, 14, 14)); + AnyRectD r0(PointD(93.196, 104.21), ang::Angle(+1.03), RectD(2, 0, 4, 15)); + AnyRectD r1(PointD(99.713, 116.02), ang::Angle(-1.03), RectD(0, 0, 14, 14)); array pts; r0.GetGlobalPoints(pts); @@ -63,22 +63,25 @@ UNIT_TEST(AnyRect_TestIntersection) UNIT_TEST(AnyRect_TestIsIntersect) { - AnyRectD r0(PointD(100, 100), math::pi / 6, RectD(0, 0, 50, 20)); - AnyRectD r1(PointD(100, 100), math::pi / 6, RectD(0, -10, 50, 10)); - AnyRectD r2(PointD(100, 100), math::pi / 6, RectD(0, -21, 50, -1)); + auto const pi6 = ang::Angle(math::pi / 6); + auto const pi8 = ang::Angle(math::pi / 8); + + AnyRectD r0(PointD(100, 100), pi6, RectD(0, 0, 50, 20)); + AnyRectD r1(PointD(100, 100), pi6, RectD(0, -10, 50, 10)); + AnyRectD r2(PointD(100, 100), pi6, RectD(0, -21, 50, -1)); TEST(r0.IsIntersect(r1), ()); TEST(r1.IsIntersect(r2), ()); TEST(!r0.IsIntersect(r2), ()); TEST(r1.IsIntersect(r2), ()); - AnyRectD r3(PointD(50, 50), math::pi / 8, RectD(0, 0, 80, 30)); + AnyRectD r3(PointD(50, 50), pi8, RectD(0, 0, 80, 30)); TEST(r0.IsIntersect(r3), ()); } UNIT_TEST(AnyRect_SetSizesToIncludePoint) { - AnyRectD rect(PointD(100, 100), math::pi / 6, RectD(0, 0, 50, 50)); + AnyRectD rect(PointD(100, 100), ang::Angle(math::pi / 6), RectD(0, 0, 50, 50)); TEST(!rect.IsPointInside(PointD(0, 0)), ()); TEST(!rect.IsPointInside(PointD(200, 200)), ()); diff --git a/geometry/geometry_tests/polygon_test.cpp b/geometry/geometry_tests/polygon_test.cpp index 0dfa606382..43160772fd 100644 --- a/geometry/geometry_tests/polygon_test.cpp +++ b/geometry/geometry_tests/polygon_test.cpp @@ -5,17 +5,63 @@ #include "geometry/triangle2d.hpp" #include "base/macros.hpp" +#include "base/stl_helpers.hpp" #include using namespace std; +using namespace m2::robust; namespace { using P = m2::PointD; -} // namespace -using namespace m2::robust; +template +void TestDiagonalVisible(Iter beg, Iter end, Iter i0, Iter i1, bool res) +{ + TEST_EQUAL(IsDiagonalVisible(beg, end, i0, i1), res, ()); + TEST_EQUAL(IsDiagonalVisible(beg, end, i1, i0), res, ()); +} + +void TestFindStrip(P const * beg, size_t n) +{ + size_t const i = FindSingleStrip(n, IsDiagonalVisibleFunctor

(beg, beg + n)); + TEST_LESS(i, n, ()); + + vector test; + MakeSingleStripFromIndex(i, n, MakeBackInsertFunctor(test)); + + my::SortUnique(test); + TEST_EQUAL(test.size(), n, ()); +} + +void TestFindStripMulti(P const * beg, size_t n) +{ + for (size_t i = 3; i <= n; ++i) + TestFindStrip(beg, i); +} + +template +void TestPolygonCCW(Iter beg, Iter end) +{ + TEST_EQUAL(m2::robust::CheckPolygonSelfIntersections(beg, end), false, ()); + + TEST(IsPolygonCCW(beg, end), ()); + using ReverseIter = reverse_iterator; + TEST(!IsPolygonCCW(ReverseIter(end), ReverseIter(beg)), ()); +} + +template +void TestPolygonOrReverseCCW(Iter beg, Iter end) +{ + TEST_EQUAL(m2::robust::CheckPolygonSelfIntersections(beg, end), false, ()); + + bool const bForwardCCW = IsPolygonCCW(beg, end); + using ReverseIter = reverse_iterator; + bool const bReverseCCW = IsPolygonCCW(ReverseIter(end), ReverseIter(beg)); + TEST_NOT_EQUAL(bForwardCCW, bReverseCCW, ()); +} +} // namespace UNIT_TEST(IsSegmentInCone) { @@ -38,16 +84,6 @@ UNIT_TEST(IsSegmentInCone) TEST(!IsSegmentInCone(P(0, 0), P(-1, -3), P(-1, 1), P(1, 1)), ()); } -namespace -{ -template -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)}; @@ -65,29 +101,6 @@ UNIT_TEST(IsDiagonalVisible) TestDiagonalVisible(b, e, b + 5, b + 1, true); } -namespace -{ -void TestFindStrip(P const * beg, size_t n) -{ - size_t const i = FindSingleStrip(n, IsDiagonalVisibleFunctor

(beg, beg + n)); - TEST_LESS(i, n, ()); - - vector test; - MakeSingleStripFromIndex(i, n, MakeBackInsertFunctor(test)); - - sort(test.begin(), test.end()); - unique(test.begin(), test.end()); - - TEST_EQUAL(test.size(), n, ()); -} - -void TestFindStripMulti(P const * beg, size_t n) -{ - for (size_t i = 3; i <= n; ++i) - TestFindStrip(beg, i); -} -} - UNIT_TEST(FindSingleStrip) { { @@ -110,30 +123,6 @@ UNIT_TEST(FindSingleStrip) } } -namespace -{ -template -void TestPolygonCCW(IterT beg, IterT end) -{ - TEST_EQUAL(m2::robust::CheckPolygonSelfIntersections(beg, end), false, ()); - - TEST(IsPolygonCCW(beg, end), ()); - typedef std::reverse_iterator ReverseIterT; - TEST(!IsPolygonCCW(ReverseIterT(end), ReverseIterT(beg)), ()); -} - -template -void TestPolygonOrReverseCCW(IterT beg, IterT end) -{ - TEST_EQUAL(m2::robust::CheckPolygonSelfIntersections(beg, end), false, ()); - - bool const bForwardCCW = IsPolygonCCW(beg, end); - typedef std::reverse_iterator ReverseIterT; - bool const bReverseCCW = IsPolygonCCW(ReverseIterT(end), ReverseIterT(beg)); - TEST_NOT_EQUAL(bForwardCCW, bReverseCCW, ()); -} -} - UNIT_TEST(IsPolygonCCW_Smoke) { P arr1[] = {P(1, 1), P(2, 0), P(3, 2)}; diff --git a/geometry/geometry_tests/region_test.cpp b/geometry/geometry_tests/region_test.cpp index 8c9899d3b3..fccfd24127 100644 --- a/geometry/geometry_tests/region_test.cpp +++ b/geometry/geometry_tests/region_test.cpp @@ -4,24 +4,26 @@ #include "geometry/region2d.hpp" - -namespace { - -template struct ContainsChecker +namespace +{ +template +struct ContainsChecker { - RegionT const & m_region; - ContainsChecker(RegionT const & region) : m_region(region) {} - void operator()(typename RegionT::ValueT const & pt) + ContainsChecker(Region const & region) : m_region(region) {} + + void operator()(typename Region::Value const & pt) { - TEST(m_region.Contains(pt), ("Region should contain all it's points")); + TEST(m_region.Contains(pt), ("Region should contain all its points")); } + + Region const & m_region; }; /// Region should have CCW orientation from left, down corner. -template -void TestContainsRectangular(PointT const * arr) +template +void TestContainsRectangular(Point const * arr) { - m2::Region region; + m2::Region region; size_t const count = 4; region.Assign(arr, arr + count); @@ -32,8 +34,8 @@ void TestContainsRectangular(PointT const * arr) region.Contains((arr[i] + arr[(i + count - 1) % count]) / 2); } - PointT dx(1, 0); - PointT dy(0, 1); + Point dx(1, 0); + Point dy(0, 1); TEST(!region.Contains(arr[0] - dx), ()); TEST(!region.Contains(arr[0] - dy), ()); @@ -56,38 +58,38 @@ void TestContainsRectangular(PointT const * arr) TEST(region.Contains(arr[3] + dx - dy), ()); } -template +template void TestContains() { - TRegion region; - ContainsChecker checker(region); + Region region; + ContainsChecker checker(region); // point type - using P = typename TRegion::ValueT; + using P = typename Region::Value; // rectangular polygon { - P const data[] = { P(1, 1), P(10, 1), P(10, 10), P(1, 10) }; + P const data[] = {P(1, 1), P(10, 1), P(10, 10), P(1, 10)}; TestContainsRectangular(data); } { - P const data[] = { P(-100, -100), P(-50, -100), P(-50, -50), P(-100, -50) }; + P const data[] = {P(-100, -100), P(-50, -100), P(-50, -50), P(-100, -50)}; TestContainsRectangular(data); } { - P const data[] = { P(-2000000000, -2000000000), P(-1000000000, -2000000000), - P(-1000000000, -1000000000), P(-2000000000, -1000000000) }; + P const data[] = {P(-2000000000, -2000000000), P(-1000000000, -2000000000), + P(-1000000000, -1000000000), P(-2000000000, -1000000000)}; TestContainsRectangular(data); } { - P const data[] = { P(1000000000, 1000000000), P(2000000000, 1000000000), - P(2000000000, 2000000000), P(1000000000, 2000000000) }; + P const data[] = {P(1000000000, 1000000000), P(2000000000, 1000000000), + P(2000000000, 2000000000), P(1000000000, 2000000000)}; TestContainsRectangular(data); } // triangle { - P const data[] = {P(0, 0), P(2, 0), P(2, 2) }; + P const data[] = {P(0, 0), P(2, 0), P(2, 2)}; region.Assign(data, data + ARRAY_SIZE(data)); } TEST_EQUAL(region.GetRect(), m2::Rect(0, 0, 2, 2), ()); @@ -98,10 +100,10 @@ void TestContains() // complex polygon { - P const data[] = { P(0, 0), P(2, 0), P(2, 2), P(3, 1), P(4, 2), P(5, 2), - P(3, 3), P(3, 2), P(2, 4), P(6, 3), P(7, 4), P(7, 2), P(8, 5), P(8, 7), - P(7, 7), P(8, 8), P(5, 9), P(6, 6), P(5, 7), P(4, 6), P(4, 8), P(3, 7), - P(2, 7), P(3, 6), P(4, 4), P(0, 7), P(2, 3), P(0, 2) }; + P const data[] = {P(0, 0), P(2, 0), P(2, 2), P(3, 1), P(4, 2), P(5, 2), P(3, 3), + P(3, 2), P(2, 4), P(6, 3), P(7, 4), P(7, 2), P(8, 5), P(8, 7), + P(7, 7), P(8, 8), P(5, 9), P(6, 6), P(5, 7), P(4, 6), P(4, 8), + P(3, 7), P(2, 7), P(3, 6), P(4, 4), P(0, 7), P(2, 3), P(0, 2)}; region.Assign(data, data + ARRAY_SIZE(data)); } TEST_EQUAL(region.GetRect(), m2::Rect(0, 0, 8, 9), ()); @@ -115,18 +117,29 @@ void TestContains() region.ForEachPoint(checker); } -} +template +class PointsSummator +{ +public: + PointsSummator(Point & res) : m_res(res) {} + + void operator()(Point const & pt) { m_res += pt; } + +private: + Point & m_res; +}; +} // namespace UNIT_TEST(Region) { typedef m2::PointD P; - P p1[] = { P(0.1, 0.2) }; + P p1[] = {P(0.1, 0.2)}; m2::Region

region(p1, p1 + ARRAY_SIZE(p1)); TEST(!region.IsValid(), ()); { - P p2[] = { P(1.0, 2.0), P(55.0, 33.0) }; + P p2[] = {P(1.0, 2.0), P(55.0, 33.0)}; region.Assign(p2, p2 + ARRAY_SIZE(p2)); } TEST(!region.IsValid(), ()); @@ -135,13 +148,14 @@ UNIT_TEST(Region) TEST(region.IsValid(), ()); { - // equality case - { - P const data[] = { P(1, 1), P(0, 4.995), P(1, 4.999996), P(1.000003, 5.000001), P(0.5, 10), P(10, 10), P(10, 1) }; - region.Assign(data, data + ARRAY_SIZE(data)); - } - TEST(!region.Contains(P(0.9999987, 0.9999938)), ()); - TEST(!region.Contains(P(0.999998, 4.9999987)), ()); + // equality case + { + P const data[] = {P(1, 1), P(0, 4.995), P(1, 4.999996), P(1.000003, 5.000001), + P(0.5, 10), P(10, 10), P(10, 1)}; + region.Assign(data, data + ARRAY_SIZE(data)); + } + TEST(!region.Contains(P(0.9999987, 0.9999938)), ()); + TEST(!region.Contains(P(0.999998, 4.9999987)), ()); } } @@ -153,7 +167,7 @@ UNIT_TEST(Region_Contains_int32) { using P = m2::PointI; m2::Region

region; - P const data[] = { P(1, -1), P(-2, -2), P(-3, 1) }; + P const data[] = {P(1, -1), P(-2, -2), P(-3, 1)}; region.Assign(data, data + ARRAY_SIZE(data)); TEST_EQUAL(region.GetRect(), m2::Rect(-3, -2, 1, 1), ()); @@ -166,7 +180,7 @@ UNIT_TEST(Region_Contains_int32) { using P = m2::PointI; m2::Region

region; - P const data[] = { P(1, -1), P(3, 0), P(3, 3), P(0, 3), P(0, 2), P(0, 1), P(2, 2) }; + P const data[] = {P(1, -1), P(3, 0), P(3, 3), P(0, 3), P(0, 2), P(0, 1), P(2, 2)}; region.Assign(data, data + ARRAY_SIZE(data)); TEST_EQUAL(region.GetRect(), m2::Rect(0, -1, 3, 3), ()); @@ -178,43 +192,29 @@ UNIT_TEST(Region_Contains_int32) } } -UNIT_TEST(Region_Contains_uint32) -{ - TestContains(); -} +UNIT_TEST(Region_Contains_uint32) { TestContains(); } UNIT_TEST(Region_Contains_double) { - using TRegion = m2::RegionD; - using TPoint = TRegion::ValueT; + using Region = m2::RegionD; + using Point = Region::Value; - TestContains(); + TestContains(); { - TRegion region; - TPoint const data[] = {{0, 7}, {4, 4}, {3, 6}, {8, 6}, {8, 5}, {6, 3}, {2, 2}}; + Region region; + Point const data[] = {{0, 7}, {4, 4}, {3, 6}, {8, 6}, {8, 5}, {6, 3}, {2, 2}}; region.Assign(data, data + ARRAY_SIZE(data)); - TEST_EQUAL(region.GetRect(), m2::Rect(0, 2, 8, 7), ()); + TEST_EQUAL(region.GetRect(), m2::Rect(0, 2, 8, 7), ()); TEST(!region.Contains({3, 5}), ()); } } -template class PointsSummator -{ - TPoint & m_res; -public: - PointsSummator(TPoint & res) : m_res(res) {} - void operator()(TPoint const & pt) - { - m_res += pt; - } -}; - UNIT_TEST(Region_ForEachPoint) { typedef m2::PointF P; - P const points[] = { P(0.0, 1.0), P(1.0, 2.0), P(10.5, 11.5) }; + P const points[] = {P(0.0, 1.0), P(1.0, 2.0), P(10.5, 11.5)}; m2::Region

region(points, points + ARRAY_SIZE(points)); P res(0, 0); @@ -226,7 +226,7 @@ UNIT_TEST(Region_ForEachPoint) UNIT_TEST(Region_point_at_border_test) { typedef m2::PointF P; - P const points[] = { P(0.0, 1.0), P(0.0, 10.0), P(10.0, 10.0), P(10.0, 1.0) }; + P const points[] = {P(0.0, 1.0), P(0.0, 10.0), P(10.0, 10.0), P(10.0, 1.0)}; m2::Region

region(points, points + ARRAY_SIZE(points)); P p1(0, 0); @@ -245,7 +245,7 @@ UNIT_TEST(Region_point_at_border_test) UNIT_TEST(Region_border_intersecion_Test) { typedef m2::PointF P; - P const points[] = { P(0.0, 1.0), P(0.0, 10.0), P(10.0, 10.0), P(10.0, 1.0) }; + P const points[] = {P(0.0, 1.0), P(0.0, 10.0), P(10.0, 10.0), P(10.0, 1.0)}; m2::Region

region(points, points + ARRAY_SIZE(points)); P intersection; @@ -259,5 +259,6 @@ UNIT_TEST(Region_border_intersecion_Test) TEST(region.FindIntersection(P(7.0, 7.0), P(7.0, 10.0), intersection), ()); TEST(intersection == P(7.0, 10.0), ()); - TEST(!region.FindIntersection(P(5.0, 5.0), P(2.0, 2.0), intersection), ("This case has no intersection")); + TEST(!region.FindIntersection(P(5.0, 5.0), P(2.0, 2.0), intersection), + ("This case has no intersection")); } diff --git a/geometry/point2d.hpp b/geometry/point2d.hpp index 3b46e05150..ae8ac498ae 100644 --- a/geometry/point2d.hpp +++ b/geometry/point2d.hpp @@ -41,7 +41,7 @@ public: T SquaredLength() const { return x * x + y * y; } - double Length(Point const & p) const { return sqrt(SquaredLength(p)); } + double Length(Point const & p) const { return std::sqrt(SquaredLength(p)); } bool IsAlmostZero() const { return AlmostEqualULPs(*this, Point(0, 0)); } @@ -110,7 +110,7 @@ public: } /// @name VectorOperationsOnPoint - double Length() const { return sqrt(SquaredLength()); } + double Length() const { return std::sqrt(SquaredLength()); } Point Normalize() const { diff --git a/geometry/region2d.hpp b/geometry/region2d.hpp index 5bdb252613..26e4ab8c5d 100644 --- a/geometry/region2d.hpp +++ b/geometry/region2d.hpp @@ -29,10 +29,10 @@ struct DefEqualFloat my::AlmostEqualAbs(p1.y, p2.y, static_cast(kPrecision)); } - template - bool EqualZeroSquarePrecision(TCoord val) const + template + bool EqualZeroSquarePrecision(Coord val) const { - static_assert(std::is_floating_point::value, ""); + static_assert(std::is_floating_point::value, ""); return my::AlmostEqualAbs(val, 0.0, kPrecision * kPrecision); } @@ -52,8 +52,8 @@ struct DefEqualInt return p1 == p2; } - template - bool EqualZeroSquarePrecision(TCoord val) const + template + bool EqualZeroSquarePrecision(Coord val) const { return val == 0; } @@ -65,17 +65,17 @@ struct DefEqualInt }; template -struct TraitsType; +struct Traitsype; template <> -struct TraitsType<1> +struct Traitsype<1> { typedef DefEqualFloat EqualType; typedef double BigType; }; template <> -struct TraitsType<0> +struct Traitsype<0> { typedef DefEqualInt EqualType; typedef int64_t BigType; @@ -86,14 +86,14 @@ template class Region { public: - using ValueT = Point; - using CoordT = typename Point::value_type; - using ContainerT = std::vector; - using TraitsT = detail::TraitsType::value>; + using Value = Point; + using Coord = typename Point::value_type; + using Container = std::vector; + using Traits = detail::Traitsype::value>; /// @name Needed for boost region concept. //@{ - using IteratorT = typename ContainerT::const_iterator; + using IteratorT = typename Container::const_iterator; IteratorT Begin() const { return m_points.begin(); } IteratorT End() const { return m_points.end(); } size_t Size() const { return m_points.size(); } @@ -101,27 +101,28 @@ public: Region() = default; - template + template ::value>> explicit Region(Points && points) : m_points(std::forward(points)) { CalcLimitRect(); } - template - Region(IterT first, IterT last) : m_points(first, last) + template + Region(Iter first, Iter last) : m_points(first, last) { CalcLimitRect(); } - template - void Assign(IterT first, IterT last) + template + void Assign(Iter first, Iter last) { m_points.assign(first, last); CalcLimitRect(); } - template - void AssignEx(IterT first, IterT last, Fn fn) + template + void AssignEx(Iter first, Iter last, Fn fn) { m_points.reserve(distance(first, last)); @@ -137,13 +138,13 @@ public: m_rect.Add(pt); } - template - void ForEachPoint(TFunctor toDo) const + template + void ForEachPoint(ToDo && toDo) const { - for_each(m_points.begin(), m_points.end(), toDo); + for_each(m_points.begin(), m_points.end(), std::forward(toDo)); } - m2::Rect const & GetRect() const { return m_rect; } + m2::Rect const & GetRect() const { return m_rect; } size_t GetPointsCount() const { return m_points.size(); } bool IsValid() const { return GetPointsCount() > 2; } @@ -153,12 +154,12 @@ public: std::swap(m_rect, rhs.m_rect); } - ContainerT const & Data() const { return m_points; } + Container const & Data() const { return m_points; } - template - 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) + template + static bool IsIntersect(Coord const & x11, Coord const & y11, Coord const & x12, + Coord const & y12, Coord const & x21, Coord const & y21, + Coord const & x22, Coord const & y22, EqualFn && equalF, Point & pt) { double const divider = ((y12 - y11) * (x22 - x21) - (x12 - x11) * (y22 - y21)); if (equalF.EqualZeroSquarePrecision(divider)) @@ -182,13 +183,13 @@ public: 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); + return IsIntersect(p1.x, p1.y, p2.x, p2.y, p3.x, p3.y, p4.x, p4.y, typename Traits::EqualType(), + pt); } /// Taken from Computational Geometry in C and modified - template - bool Contains(Point const & pt, TEqualF equalF) const + template + bool Contains(Point const & pt, EqualFn equalF) const { if (!m_rect.IsPointInside(pt)) return false; @@ -198,8 +199,8 @@ public: size_t const numPoints = m_points.size(); - using BigCoordT = typename TraitsT::BigType; - using BigPoint = ::m2::Point; + using BigCoord = typename Traits::BigType; + using BigPoint = ::m2::Point; BigPoint prev = BigPoint(m_points[numPoints - 1]) - BigPoint(pt); for (size_t i = 0; i < numPoints; ++i) @@ -216,8 +217,8 @@ public: { ASSERT_NOT_EQUAL(curr.y, prev.y, ()); - BigCoordT const delta = prev.y - curr.y; - BigCoordT const cp = CrossProduct(curr, prev); + BigCoord const delta = prev.y - curr.y; + BigCoord const cp = CrossProduct(curr, prev); // 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 @@ -248,7 +249,7 @@ public: return false; // outside } - bool Contains(Point const & pt) const { return Contains(pt, typename TraitsT::EqualType()); } + bool Contains(Point const & pt) const { return Contains(pt, typename Traits::EqualType()); } /// Finds point of intersection with the section. bool FindIntersection(Point const & point1, Point const & point2, Point & result) const @@ -266,8 +267,8 @@ public: } /// Slow check that point lies at the border. - template - bool AtBorder(Point const & pt, double const delta, TEqualF equalF) const + template + bool AtBorder(Point const & pt, double const delta, EqualFn equalF) const { if (!m_rect.IsPointInside(pt)) return false; @@ -297,7 +298,7 @@ public: bool AtBorder(Point const & pt, double const delta) const { - return AtBorder(pt, delta, typename TraitsT::EqualType()); + return AtBorder(pt, delta, typename Traits::EqualType()); } private: @@ -317,8 +318,8 @@ private: m_rect.Add(m_points[i]); } - ContainerT m_points; - m2::Rect m_rect; + Container m_points; + m2::Rect m_rect; }; template diff --git a/geometry/region2d/boost_concept.hpp b/geometry/region2d/boost_concept.hpp index edd3538fb9..831c18b7c2 100644 --- a/geometry/region2d/boost_concept.hpp +++ b/geometry/region2d/boost_concept.hpp @@ -14,11 +14,12 @@ #include "3party/boost/boost/polygon/polygon.hpp" #endif -#include "std/vector.hpp" - - -namespace boost { namespace polygon { +#include +namespace boost +{ +namespace polygon +{ typedef int32_t my_coord_t; //////////////////////////////////////////////////////////////////////////////// @@ -46,9 +47,9 @@ namespace boost { namespace polygon { template <> struct point_mutable_traits { - typedef my_point_t::value_type CoordT; + typedef my_point_t::value_type Coord; - static inline void set(my_point_t & p, orientation_2d o, CoordT v) + static inline void set(my_point_t & p, orientation_2d o, Coord v) { if (o == HORIZONTAL) p.x = v; @@ -56,7 +57,7 @@ namespace boost { namespace polygon { p.y = v; } - static inline my_point_t construct(CoordT x, CoordT y) + static inline my_point_t construct(Coord x, Coord y) { return my_point_t(x, y); } @@ -76,9 +77,9 @@ namespace boost { namespace polygon { template <> struct polygon_traits { - typedef my_region_t::CoordT coordinate_type; + typedef my_region_t::Coord coordinate_type; typedef my_region_t::IteratorT iterator_type; - typedef my_region_t::ValueT point_type; + typedef my_region_t::Value point_type; // Get the begin iterator static inline iterator_type begin_points(my_region_t const & t) @@ -128,7 +129,7 @@ namespace boost { namespace polygon { //////////////////////////////////////////////////////////////////////////////// // Polygon set concept. //////////////////////////////////////////////////////////////////////////////// - typedef vector my_region_set_t; + typedef std::vector my_region_set_t; template <> struct geometry_concept @@ -168,7 +169,7 @@ namespace boost { namespace polygon { poly_set.clear(); // this is kind of cheesy. I am copying the unknown input geometry - // into my own polygon set and then calling get to populate the vector + // into my own polygon set and then calling get to populate the std::vector polygon_set_data ps; ps.insert(b, e); ps.get(poly_set); @@ -177,4 +178,5 @@ namespace boost { namespace polygon { // to iterate through each polygon at this point and do something extra } }; -}} +} // namespace polygon +} // namespace boost diff --git a/geometry/robust_orientation.hpp b/geometry/robust_orientation.hpp index 3466ef9a0a..5417ff73c1 100644 --- a/geometry/robust_orientation.hpp +++ b/geometry/robust_orientation.hpp @@ -31,28 +31,28 @@ bool Between(T a, T b, T c) return std::min(a, b) <= c && c <= std::max(a, b); } -template -bool IsInSection(PointT const & p1, PointT const & p2, PointT const & p) +template +bool IsInSection(Point const & p1, Point const & p2, Point const & p) { return Between(p1.x, p2.x, p.x) && Between(p1.y, p2.y, p.y); } -template -bool CheckPolygonSelfIntersections(IterT beg, IterT end) +template +bool CheckPolygonSelfIntersections(Iter beg, Iter end) { - IterT last = end; + Iter last = end; --last; - for (IterT i = beg; i != last; ++i) + for (Iter i = beg; i != last; ++i) { - for (IterT j = i; j != end; ++j) + for (Iter 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); + Iter ii = NextIterInCycle(i, beg, end); + Iter jj = NextIterInCycle(j, beg, end); PointD a = *i, b = *ii, c = *j, d = *jj; // check for rect intersection @@ -72,7 +72,7 @@ bool CheckPolygonSelfIntersections(IterT beg, IterT end) continue; // Common principle if any point lay exactly on section, check 2 variants: - // - касание (><) - don't return as intersection; + // - only touching (><) - don't return as intersection; // - 'X'-crossing - return as intersection; // 'X'-crossing defines when points lay in different cones. diff --git a/geometry/screenbase.cpp b/geometry/screenbase.cpp index f2e05f3056..62e2260521 100644 --- a/geometry/screenbase.cpp +++ b/geometry/screenbase.cpp @@ -143,7 +143,7 @@ void ScreenBase::SetFromRect(m2::AnyRectD const & glbRect) { SetFromRects(glbRec void ScreenBase::SetFromParams(m2::PointD const & org, double angle, double scale) { m_Scale = scale; - m_Angle = angle; + m_Angle = ang::Angle(angle); m_Org = org; UpdateDependentParameters(); } diff --git a/geometry/tree4d.hpp b/geometry/tree4d.hpp index e9011ae1e1..95e7669f7b 100644 --- a/geometry/tree4d.hpp +++ b/geometry/tree4d.hpp @@ -8,6 +8,7 @@ #include #include +#include #include #include "3party/kdtree++/kdtree.hpp" @@ -23,24 +24,16 @@ struct TraitsDef template > class Tree { - class ValueT + class Value { - 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(); - } - public: - T m_val; - double m_pts[4]; + using value_type = double; - 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); } + template + Value(U && u, m2::RectD const & r) : m_val(std::forward(u)) + { + SetRect(r); + } bool IsIntersect(m2::RectD const & r) const { @@ -48,7 +41,7 @@ class Tree (m_pts[1] >= r.maxY())); } - bool operator==(ValueT const & r) const { return (m_val == r.m_val); } + bool operator==(Value const & r) const { return (m_val == r.m_val); } std::string DebugPrint() const { @@ -63,22 +56,32 @@ class Tree 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]); } + + T m_val; + double m_pts[4]; + + private: + 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(); + } }; - typedef KDTree::KDTree<4, ValueT> TreeT; - TreeT m_tree; + KDTree::KDTree<4, Value> m_tree; // Do-class for rect-iteration in tree. template 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) {} + for_each_helper(m2::RectD const & r, ToDo && toDo) : m_rect(r), m_toDo(std::forward(toDo)) + { + } - bool ScanLeft(size_t plane, ValueT const & v) const + bool ScanLeft(size_t plane, Value const & v) const { switch (plane & 3) // % 4 { @@ -88,7 +91,7 @@ class Tree } } - bool ScanRight(size_t plane, ValueT const & v) const + bool ScanRight(size_t plane, Value const & v) const { switch (plane & 3) // % 4 { @@ -98,17 +101,21 @@ class Tree } } - void operator()(ValueT const & v) const + void operator()(Value const & v) const { if (v.IsIntersect(m_rect)) m_toDo(v); } + + private: + m2::RectD const & m_rect; + ToDo m_toDo; }; template - for_each_helper GetFunctor(m2::RectD const & rect, ToDo toDo) const + for_each_helper GetFunctor(m2::RectD const & rect, ToDo && toDo) const { - return for_each_helper(rect, toDo); + return for_each_helper(rect, std::forward(toDo)); } protected: @@ -118,22 +125,28 @@ protected: public: Tree(Traits const & traits = Traits()) : m_traits(traits) {} - typedef T elem_t; + using elem_t = T; - void Add(T const & obj) { Add(obj, GetLimitRect(obj)); } - void Add(T && obj) { Add(move(obj), GetLimitRect(obj)); } + template + void Add(U && obj) + { + Add(std::forward(obj), GetLimitRect(obj)); + } - 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)); } + template + void Add(U && obj, m2::RectD const & rect) + { + m_tree.insert(Value(std::forward(obj), rect)); + } private: - template - void ReplaceImpl(T const & obj, m2::RectD const & rect, CompareT comp) + template + void ReplaceImpl(T const & obj, m2::RectD const & rect, Compare comp) { bool skip = false; - std::vector isect; + std::vector isect; - m_tree.for_each(GetFunctor(rect, [&](ValueT const & v) { + m_tree.for_each(GetFunctor(rect, [&](Value const & v) { if (skip) return; @@ -147,22 +160,22 @@ private: if (skip) return; - for (ValueT const * v : isect) + for (Value const * v : isect) m_tree.erase(*v); Add(obj, rect); } public: - template - void ReplaceAllInRect(T const & obj, CompareT comp) + template + void ReplaceAllInRect(T const & obj, Compare comp) { ReplaceImpl(obj, GetLimitRect(obj), [&comp](T const & t1, T const & t2) { return comp(t1, t2) ? 1 : -1; }); } - template - void ReplaceEqualInRect(T const & obj, EqualT eq, CompareT comp) + template + void ReplaceEqualInRect(T const & obj, Equal eq, Compare comp) { ReplaceImpl(obj, GetLimitRect(obj), [&](T const & t1, T const & t2) { if (eq(t1, t2)) @@ -174,36 +187,38 @@ public: void Erase(T const & obj, m2::RectD const & r) { - ValueT val(obj, r); + Value val(obj, r); m_tree.erase_exact(val); } void Erase(T const & obj) { - ValueT val(obj, m_traits.LimitRect(obj)); + Value val(obj, m_traits.LimitRect(obj)); m_tree.erase_exact(val); } template void ForEach(ToDo && toDo) const { - for (ValueT const & v : m_tree) + for (Value const & v : m_tree) toDo(v.m_val); } template void ForEachEx(ToDo && toDo) const { - for (ValueT const & v : m_tree) + for (Value const & v : m_tree) toDo(v.GetRect(), v.m_val); } template bool FindNode(ToDo && toDo) const { - for (ValueT const & v : m_tree) + for (Value const & v : m_tree) + { if (toDo(v.m_val)) return true; + } return false; } @@ -211,13 +226,13 @@ public: template void ForEachInRect(m2::RectD const & rect, ToDo && toDo) const { - m_tree.for_each(GetFunctor(rect, [&toDo](ValueT const & v) { toDo(v.m_val); })); + m_tree.for_each(GetFunctor(rect, [&toDo](Value const & v) { toDo(v.m_val); })); } template 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); })); + m_tree.for_each(GetFunctor(rect, [&toDo](Value const & v) { toDo(v.GetRect(), v.m_val); })); } bool IsEmpty() const { return m_tree.empty(); } @@ -229,7 +244,7 @@ public: std::string DebugPrint() const { std::ostringstream out; - for (ValueT const & v : m_tree.begin()) + for (Value const & v : m_tree.begin()) out << v.DebugPrint() << ", "; return out.str(); } -- cgit v1.2.3