Edits migration.

5 files changed, 309 insertions, 0 deletions

diff --git a/geometry/algorithm.cpp b/geometry/algorithm.cpp
new file mode 100644
index 0000000000..76ebe95f09
--- /dev/null
+++ b/geometry/algorithm.cpp
@@ -0,0 +1,81 @@
+#include "geometry/algorithm.hpp"
+#include "geometry/triangle2d.hpp"
+
+#include "base/logging.hpp"
+
+namespace m2
+{
+// CalculatePolyLineCenter -----------------------------------------------------------------------------
+
+void CalculatePolyLineCenter::operator()(m2::PointD const & pt)
+{
+  m_length += (m_poly.empty() ? 0.0 : m_poly.back().m_p.Length(pt));
+  m_poly.emplace_back(pt, m_length);
+}
+
+PointD CalculatePolyLineCenter::GetCenter() const
+{
+  using TIter = vector<Value>::const_iterator;
+
+  double const l = m_length / 2.0;
+
+  TIter e = lower_bound(m_poly.begin(), m_poly.end(), Value(m2::PointD(0, 0), l));
+  if (e == m_poly.begin())
+  {
+    /// @todo It's very strange, but we have linear objects with zero length.
+    LOG(LWARNING, ("Zero length linear object"));
+    return e->m_p;
+  }
+
+  TIter b = e - 1;
+
+  double const f = (l - b->m_len) / (e->m_len - b->m_len);
+
+  // For safety reasons (floating point calculations) do comparison instead of ASSERT.
+  if (0.0 <= f && f <= 1.0)
+    return (b->m_p * (1 - f) + e->m_p * f);
+  else
+    return ((b->m_p + e->m_p) / 2.0);
+}
+
+// CalculatePointOnSurface -------------------------------------------------------------------------
+
+CalculatePointOnSurface::CalculatePointOnSurface(m2::RectD const & rect)
+  : m_rectCenter(rect.Center())
+  , m_center(m_rectCenter)
+  , m_squareDistanceToApproximate(numeric_limits<double>::max())
+{
+}
+
+void CalculatePointOnSurface::operator()(PointD const & p1, PointD const & p2, PointD const & p3)
+{
+  if (m_squareDistanceToApproximate == 0.0)
+    return;
+  if (m2::IsPointInsideTriangle(m_rectCenter, p1, p2, p3))
+  {
+    m_center = m_rectCenter;
+    m_squareDistanceToApproximate = 0.0;
+    return;
+  }
+  PointD triangleCenter(p1);
+  triangleCenter += p2;
+  triangleCenter += p3;
+  triangleCenter = triangleCenter / 3.0;
+
+  double triangleDistance = m_rectCenter.SquareLength(triangleCenter);
+  if (triangleDistance <= m_squareDistanceToApproximate)
+  {
+    m_center = triangleCenter;
+    m_squareDistanceToApproximate = triangleDistance;
+  }
+}
+
+// CalculateBoundingBox ----------------------------------------------------------------------------
+
+void CalculateBoundingBox::operator()(PointD const & p)
+{
+  // Works just fine. If you don't belive me, see geometry/rect2d.hpp.
+  // Pay attention to MakeEmpty and Add functions.
+  m_boundingBox.Add(p);
+}
+}  // namespace m2
diff --git a/geometry/algorithm.hpp b/geometry/algorithm.hpp
new file mode 100644
index 0000000000..6513bd6885
--- /dev/null
+++ b/geometry/algorithm.hpp
@@ -0,0 +1,59 @@
+#pragma once
+
+#include "geometry/point2d.hpp"
+#include "geometry/rect2d.hpp"
+
+#include "std/vector.hpp"
+
+namespace m2
+{
+// This class is used to calculate a point on a polyline
+// such as that the paths (not the distance) from that point
+// to both ends of a polyline have the same length.
+class CalculatePolyLineCenter
+{
+public:
+  CalculatePolyLineCenter() : m_length(0.0) {}
+  void operator()(PointD const & pt);
+
+  PointD GetCenter() const;
+
+private:
+  struct Value
+  {
+    Value(PointD const & p, double l) : m_p(p), m_len(l) {}
+    bool operator<(Value const & r) const { return (m_len < r.m_len); }
+    PointD m_p;
+    double m_len;
+  };
+
+  vector<Value> m_poly;
+  double m_length;
+};
+
+// This class is used to calculate a point such as that
+// it lays on the figure triangle that is the closest to
+// figure bounding box center.
+class CalculatePointOnSurface
+{
+public:
+  CalculatePointOnSurface(RectD const & rect);
+
+  void operator()(PointD const & p1, PointD const & p2, PointD const & p3);
+  PointD GetCenter() const { return m_center; }
+private:
+  PointD m_rectCenter;
+  PointD m_center;
+  double m_squareDistanceToApproximate;
+};
+
+// Calculates the smallest rect that includes given geometry.
+class CalculateBoundingBox
+{
+public:
+  void operator()(PointD const & p);
+  RectD GetBoundingBox() const { return m_boundingBox; }
+private:
+  RectD m_boundingBox;
+};
+}  // namespace m2
diff --git a/geometry/geometry.pro b/geometry/geometry.pro
index 9f297dacbf..ff07f193ff 100644
--- a/geometry/geometry.pro
+++ b/geometry/geometry.pro
@@ -9,6 +9,7 @@ ROOT_DIR = ..
 include($$ROOT_DIR/common.pri)
 
 SOURCES += \
+  algorithm.cpp \
   angles.cpp \
   distance_on_sphere.cpp \
   latlon.cpp \
@@ -22,6 +23,7 @@ SOURCES += \
   triangle2d.cpp \
 
 HEADERS += \
+  algorithm.hpp \
   angles.hpp \
   any_rect2d.hpp \
   avg_vector.hpp \
diff --git a/geometry/geometry_tests/algorithm_test.cpp b/geometry/geometry_tests/algorithm_test.cpp
new file mode 100644
index 0000000000..3f349f9791
--- /dev/null
+++ b/geometry/geometry_tests/algorithm_test.cpp
@@ -0,0 +1,166 @@
+#include "testing/testing.hpp"
+
+#include "geometry/algorithm.hpp"
+
+#include "std/vector.hpp"
+
+using m2::PointD;
+using m2::RectD;
+using m2::CalculatePolyLineCenter;
+using m2::CalculatePointOnSurface;
+using m2::CalculateBoundingBox;
+
+namespace
+{
+PointD GetPolyLineCenter(vector<PointD> const & points)
+{
+  CalculatePolyLineCenter doCalc;
+  for (auto const & p : points)
+    doCalc(p);
+  return doCalc.GetCenter();
+}
+
+RectD GetBoundingBox(vector<PointD> const & points)
+{
+  CalculateBoundingBox doCalc;
+  for (auto const p : points)
+    doCalc(p);
+  return doCalc.GetBoundingBox();
+}
+
+PointD GetPointOnSurface(vector<PointD> const & points)
+{
+  ASSERT(!points.empty() && points.size() % 3 == 0, ());
+  CalculatePointOnSurface doCalc(GetBoundingBox(points));
+  for (auto i = 0; i < points.size() - 3; i += 3)
+    doCalc(points[i], points[i + 1], points[i + 2]);
+  return doCalc.GetCenter();
+
+}
+}  // namespace
+
+UNIT_TEST(CalculatePolyLineCenter)
+{
+  {
+    vector<PointD> const points {
+      {0, 0},
+      {1, 1},
+      {2, 2}
+    };
+    TEST_EQUAL(GetPolyLineCenter(points), PointD(1, 1), ());
+  }
+  {
+    vector<PointD> const points {
+      {0, 2},
+      {1, 1},
+      {2, 2}
+    };
+    TEST_EQUAL(GetPolyLineCenter(points), PointD(1, 1), ());
+  }
+  {
+    vector<PointD> const points {
+      {1, 1},
+      {2, 2},
+      {4, 4},
+    };
+    TEST_EQUAL(GetPolyLineCenter(points), PointD(2.5, 2.5), ());
+  }
+  {
+    vector<PointD> const points {
+      {0, 0},
+      {0, 0},
+      {0, 0},
+      {0, 0},
+      {0, 0},
+      {0, 0},
+      {0, 0}
+    };
+    // Also logs a warning message.
+    TEST_EQUAL(GetPolyLineCenter(points), PointD(0, 0), ());
+  }
+  {
+    vector<PointD> const points {
+      {0, 0},
+      {0, 0},
+      {0, 0},
+      {0, 0.000001},
+      {0, 0.000001},
+      {0, 0.000001},
+      {0, 0.000001}
+    };
+    // Also logs a warning message.
+    TEST(GetPolyLineCenter(points).EqualDxDy(PointD(0, .0000005), 1e-7), ());
+  }
+}
+
+UNIT_TEST(CalculateCenter)
+{
+  {
+    vector<PointD> const points {
+      {2, 2}
+    };
+    TEST_EQUAL(GetBoundingBox(points), RectD({2, 2},  {2, 2}), ());
+  }
+  {
+    vector<PointD> const points {
+      {0, 0},
+      {1, 1},
+      {2, 2}
+    };
+    TEST_EQUAL(GetBoundingBox(points), RectD({0, 0}, {2, 2}), ());
+  }
+  {
+    vector<PointD> const points {
+      {0, 2},
+      {1, 1},
+      {2, 2},
+      {1, 2},
+      {2, 2},
+      {2, 0}
+    };
+    TEST_EQUAL(GetBoundingBox(points), RectD({0, 0}, {2, 2}), ());
+  }
+}
+
+UNIT_TEST(CalculatePointOnSurface)
+{
+  {
+    vector<PointD> const points {
+      {0, 0},
+      {1, 1},
+      {2, 2}
+    };
+    TEST_EQUAL(GetPointOnSurface(points), PointD(1, 1), ());
+  }
+  {
+    vector<PointD> const points {
+      {0, 2},
+      {1, 1},
+      {2, 2},
+      {1, 2},
+      {2, 2},
+      {2, 0}
+    };
+    TEST_EQUAL(GetPointOnSurface(points), PointD(1, 1), ());
+  }
+  {
+    vector<PointD> const points {
+      {0, 0}, {1, 1}, {2, 0},
+      {1, 1}, {2, 0}, {3, 1},
+      {2, 0}, {3, 1}, {4, 0},
+
+      {4, 0}, {3, 1}, {4, 2},
+      {3, 1}, {4, 2}, {3, 3},
+      {4, 2}, {3, 3}, {4, 4},
+
+      {3, 3}, {4, 4}, {2, 4},
+      {3, 3}, {2, 4}, {1, 3},
+      {1, 3}, {2, 4}, {0, 4},
+
+      {0, 4}, {1, 3}, {0, 2},
+      {1, 3}, {0, 2}, {1, 1},  // Center of this triangle is used as a result.
+      {0, 2}, {1, 1}, {0, 0},
+    };
+    TEST_EQUAL(GetPointOnSurface(points), PointD(2.0 / 3.0, 2), ());
+  }
+}
diff --git a/geometry/geometry_tests/geometry_tests.pro b/geometry/geometry_tests/geometry_tests.pro
index e9c04c136c..050968f793 100644
--- a/geometry/geometry_tests/geometry_tests.pro
+++ b/geometry/geometry_tests/geometry_tests.pro
@@ -19,6 +19,7 @@ HEADERS += \
 
 SOURCES += \
   ../../testing/testingmain.cpp \
+  algorithm_test.cpp \
   angle_test.cpp \
   anyrect_test.cpp \
   cellid_test.cpp \