added axis-aligned 2d rect.

4 files changed, 177 insertions, 0 deletions

diff --git a/geometry/aa_rect2d.hpp b/geometry/aa_rect2d.hpp
new file mode 100644
index 0000000000..42b9210ea5
--- /dev/null
+++ b/geometry/aa_rect2d.hpp
@@ -0,0 +1,131 @@
+#pragma once
+
+#include "point2d.hpp"
+#include "rect2d.hpp"
+#include <cmath>
+
+namespace m2
+{
+  /// axis aligned rect
+  template <typename T>
+  class AARect
+  {
+  private:
+
+    Point<T> m_i;
+    Point<T> m_j;
+    Point<T> m_zero;
+    Rect<T>  m_rect;
+
+    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> i(1, 0);
+      Point<T> j(0, 1);
+
+      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;
+    }
+
+    Point<T> const CoordConvertTo(Point<T> const & p)
+    {
+      Point<T> i(1, 0);
+      Point<T> j(0, 1);
+
+      Point<T> res;
+
+      res.x = p.x * DotProduct(i, m_i) + p.y * DotProduct(j, m_i);
+      res.y = p.x * DotProduct(i, m_j) + p.y * DotProduct(j, m_j);
+
+      return res;
+    }
+
+    Point<T> const CoordConvertFrom(Point<T> const & p)
+    {
+      Point<T> res;
+
+      Point<T> i(1, 0);
+      Point<T> j(0, 1);
+
+      res.x = p.x * DotProduct(m_i, i) + p.y * DotProduct(m_j, i);
+      res.y = p.x * DotProduct(m_i, j) + p.y * DotProduct(m_j, j);
+
+      return res;
+    }
+
+  public:
+
+    AARect(Point<T> const & zero, T const & angle, Rect<T> const & r)
+      : m_i(cos(angle), sin(angle)), m_j(-sin(angle), cos(angle)),
+        m_zero(CoordConvertTo(zero)),
+        m_rect(r)
+    {
+    }
+    bool IsPointInside(Point<T> const & pt);
+
+    bool IsIntersect(AARect<T> const & r);
+
+    Point<T> const ConvertTo(Point<T> const & p)
+    {
+      m2::PointD i(1, 0);
+      m2::PointD j(0, 1);
+      return Convert(p - Convert(m_zero, m_i, m_j, i, j), i, j, m_i, m_j);
+    }
+
+    void ConvertTo(Point<T> * pts, size_t count)
+    {
+      for (size_t i = 0; i < count; ++i)
+        pts[i] = ConvertTo(pts[i]);
+    }
+
+    Point<T> const ConvertFrom(Point<T> const & p)
+    {
+      m2::PointD i(1, 0);
+      m2::PointD j(0, 1);
+      return Convert(p + m_zero, m_i, m_j, i, j);
+    }
+
+    void ConvertFrom(Point<T> * pts, size_t count)
+    {
+      for (size_t i = 0; i < count; ++i)
+        pts[i] = ConvertFrom(pts[i]);
+    }
+
+    Rect<T> const GetLocalRect()
+    {
+      return m_rect;
+    }
+
+    Rect<T> const GetGlobalRect()
+    {
+      Point<T> pts[4];
+      GetGlobalPoints(pts);
+
+      Rect<T> res(pts[0].x, pts[0].y, pts[0].x, pts[0].y);
+
+      res.Add(pts[1]);
+      res.Add(pts[2]);
+      res.Add(pts[3]);
+
+      return res;
+    }
+
+    void GetGlobalPoints(Point<T> * pts)
+    {
+      pts[0] = ConvertFrom(Point<T>(m_rect.minX(), m_rect.minY()));
+      pts[1] = ConvertFrom(Point<T>(m_rect.minX(), m_rect.maxY()));
+      pts[2] = ConvertFrom(Point<T>(m_rect.maxX(), m_rect.maxY()));
+      pts[3] = ConvertFrom(Point<T>(m_rect.maxX(), m_rect.minY()));
+    }
+  };
+
+  typedef AARect<double> AARectD;
+  typedef AARect<float> AARectF;
+}
diff --git a/geometry/geometry.pro b/geometry/geometry.pro
index 345ae13e50..2cfbb0f783 100644
--- a/geometry/geometry.pro
+++ b/geometry/geometry.pro
@@ -31,3 +31,4 @@ HEADERS += \
   polygon.hpp \
   region2d.hpp \
   robust_orientation.hpp \
+    aa_rect2d.hpp
diff --git a/geometry/geometry_tests/aarect_test.cpp b/geometry/geometry_tests/aarect_test.cpp
new file mode 100644
index 0000000000..4f35cc2943
--- /dev/null
+++ b/geometry/geometry_tests/aarect_test.cpp
@@ -0,0 +1,44 @@
+#include "../../base/SRC_FIRST.hpp"
+#include "../../testing/testing.hpp"
+#include "../aa_rect2d.hpp"
+
+UNIT_TEST(AARect_TestConvertTo)
+{
+  m2::AARectD r(m2::PointD(0, 0), math::pi / 4, m2::RectD(0, 0, 10, 10));
+
+  m2::PointD pt1(100, 0);
+
+  TEST(r.ConvertTo(pt1).EqualDxDy(m2::PointD(100 / sqrt(2), -100 / sqrt(2)), 10e-5), ());
+  TEST(r.ConvertTo(m2::PointD(100, 100)).EqualDxDy(m2::PointD(100 * sqrt(2), 0), 10e-5), ());
+
+  m2::AARectD r1(m2::PointD(100, 100), math::pi / 4, m2::RectD(0, 0, 10, 10));
+
+  m2::PointD pt(100, 100 + 50 * sqrt(2));
+
+  TEST(r1.ConvertTo(pt).EqualDxDy(m2::PointD(50, 50), 10e-5), ());
+}
+
+UNIT_TEST(AARect_TestConvertFrom)
+{
+  m2::AARectD r(m2::PointD(100, 100), math::pi / 6, m2::RectD(0, 0, 10, 10));
+
+  TEST(r.ConvertFrom(m2::PointD(50, 0)).EqualDxDy(m2::PointD(100 + 50 * sqrt(3) / 2 , 100 + 50 * 1 / 2.0), 10e-5), ());
+  TEST(r.ConvertTo(m2::PointD(100 + 50 * sqrt(3) / 2, 100 + 50 * 1.0 / 2)).EqualDxDy(m2::PointD(50, 0), 10e-5), ());
+}
+
+UNIT_TEST(AARect_TestIntersection)
+{
+  m2::AARectD r0(m2::PointD(93.196, 104.21),  1.03, m2::RectD(2, 0, 4, 15));
+  m2::AARectD r1(m2::PointD(99.713, 116.02), -1.03, m2::RectD(0, 0, 14, 14));
+
+  m2::PointD pts[4];
+  r0.GetGlobalPoints(pts);
+  r1.ConvertTo(pts, 4);
+  m2::RectD r2(pts[0].x, pts[0].y, pts[0].x, pts[0].y);
+  r2.Add(pts[1]);
+  r2.Add(pts[2]);
+  r2.Add(pts[3]);
+
+  TEST(r1.GetLocalRect().IsIntersect(r2) == false, ());
+}
+
diff --git a/geometry/geometry_tests/geometry_tests.pro b/geometry/geometry_tests/geometry_tests.pro
index 51bc49822b..9fbbec2cc4 100644
--- a/geometry/geometry_tests/geometry_tests.pro
+++ b/geometry/geometry_tests/geometry_tests.pro
@@ -34,3 +34,4 @@ SOURCES += \
   region_test.cpp \
   rect_test.cpp \
   robust_test.cpp \
+  aarect_test.cpp