diff options
author | vng <viktor.govako@gmail.com> | 2015-12-23 19:33:05 +0300 |
---|---|---|
committer | Sergey Yershov <yershov@corp.mail.ru> | 2016-03-23 16:03:17 +0300 |
commit | f6ac3786d755afde9534b28e9a1977e38b3aa470 (patch) | |
tree | 239acb986e517ef84c31d4991a37df7f6d3bc4c1 /geometry | |
parent | 8c57791e1d87fa500b3f7bb1b13f45282edc0cf1 (diff) |
Refactored some geometry functions.
Correct implementation of feature::GetMinDistanceMeters().
Diffstat (limited to 'geometry')
-rw-r--r-- | geometry/covering_utils.hpp | 8 | ||||
-rw-r--r-- | geometry/geometry.pro | 1 | ||||
-rw-r--r-- | geometry/geometry_tests/point_test.cpp | 4 | ||||
-rw-r--r-- | geometry/geometry_tests/polygon_test.cpp | 7 | ||||
-rw-r--r-- | geometry/geometry_tests/robust_test.cpp | 33 | ||||
-rw-r--r-- | geometry/geometry_tests/segments_intersect_test.cpp | 20 | ||||
-rw-r--r-- | geometry/point2d.hpp | 72 | ||||
-rw-r--r-- | geometry/polygon.hpp | 4 | ||||
-rw-r--r-- | geometry/robust_orientation.cpp | 24 | ||||
-rw-r--r-- | geometry/robust_orientation.hpp | 8 | ||||
-rw-r--r-- | geometry/triangle2d.cpp | 33 | ||||
-rw-r--r-- | geometry/triangle2d.hpp | 12 |
12 files changed, 132 insertions, 94 deletions
diff --git a/geometry/covering_utils.hpp b/geometry/covering_utils.hpp index 83d9c06cb4..24556eead2 100644 --- a/geometry/covering_utils.hpp +++ b/geometry/covering_utils.hpp @@ -1,10 +1,14 @@ #pragma once -#include "geometry/point2d.hpp" +#include "point2d.hpp" +#include "robust_orientation.hpp" +#include "triangle2d.hpp" + #include "base/assert.hpp" #include "base/base.hpp" #include "base/buffer_vector.hpp" #include "base/logging.hpp" #include "base/math.hpp" + #include "std/algorithm.hpp" namespace covering @@ -35,7 +39,7 @@ inline CellObjectIntersection IntersectCellWithLine(CellIdT const cell, m2::PointD(xy.first + r, xy.second - r) }; for (int i = 0; i < 4; ++i) - if (m2::SegmentsIntersect(a, b, cellCorners[i], cellCorners[i == 0 ? 3 : i - 1])) + 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; diff --git a/geometry/geometry.pro b/geometry/geometry.pro index d51bfbb054..c53293ca49 100644 --- a/geometry/geometry.pro +++ b/geometry/geometry.pro @@ -18,6 +18,7 @@ SOURCES += \ robust_orientation.cpp \ screenbase.cpp \ spline.cpp \ + triangle2d.cpp \ HEADERS += \ angles.hpp \ diff --git a/geometry/geometry_tests/point_test.cpp b/geometry/geometry_tests/point_test.cpp index 116c8ef246..0c15ef621b 100644 --- a/geometry/geometry_tests/point_test.cpp +++ b/geometry/geometry_tests/point_test.cpp @@ -1,7 +1,9 @@ -#include "base/SRC_FIRST.hpp" #include "testing/testing.hpp" + #include "geometry/geometry_tests/equality.hpp" #include "geometry/point2d.hpp" +#include "geometry/triangle2d.hpp" + UNIT_TEST(Point_Rotate) { diff --git a/geometry/geometry_tests/polygon_test.cpp b/geometry/geometry_tests/polygon_test.cpp index 8fd6d5970d..6f62603c97 100644 --- a/geometry/geometry_tests/polygon_test.cpp +++ b/geometry/geometry_tests/polygon_test.cpp @@ -9,10 +9,9 @@ #include "std/algorithm.hpp" -namespace -{ - typedef m2::PointD P; -} +namespace { typedef m2::PointD P; } + +using namespace m2::robust; UNIT_TEST(IsSegmentInCone) { diff --git a/geometry/geometry_tests/robust_test.cpp b/geometry/geometry_tests/robust_test.cpp index 04e5f356c2..0eb3d79091 100644 --- a/geometry/geometry_tests/robust_test.cpp +++ b/geometry/geometry_tests/robust_test.cpp @@ -1,20 +1,47 @@ #include "testing/testing.hpp" #include "geometry/robust_orientation.hpp" +#include "geometry/triangle2d.hpp" -typedef m2::PointD P; +using namespace m2::robust; namespace { + typedef m2::PointD P; + template <typename IterT> void CheckSelfIntersections(IterT beg, IterT end, bool res) { - TEST_EQUAL(m2::robust::CheckPolygonSelfIntersections(beg, end), res, ()); + TEST_EQUAL(CheckPolygonSelfIntersections(beg, end), res, ()); typedef std::reverse_iterator<IterT> ReverseIterT; - TEST_EQUAL(m2::robust::CheckPolygonSelfIntersections(ReverseIterT(end), ReverseIterT(beg)), res, ()); + TEST_EQUAL(CheckPolygonSelfIntersections(ReverseIterT(end), ReverseIterT(beg)), res, ()); } } +UNIT_TEST(OrientedS_Smoke) +{ + m2::PointD arr[] = {{-1, -1}, {0, 0}, {1, -1}}; + TEST(OrientedS(arr[0], arr[2], arr[1]) > 0, ()); + TEST(OrientedS(arr[2], arr[0], arr[1]) < 0, ()); +} + +UNIT_TEST(Triangle_Smoke) +{ + m2::PointD arr[] = {{0, 0}, {0, 3}, {3, 0}}; + + TEST(IsPointInsideTriangle(arr[0], arr[0], arr[1], arr[2]), ()); + TEST(IsPointInsideTriangle(arr[1], arr[0], arr[1], arr[2]), ()); + TEST(IsPointInsideTriangle(arr[2], arr[0], arr[1], arr[2]), ()); + TEST(IsPointInsideTriangle({1, 1}, arr[0], arr[1], arr[2]), ()); + TEST(IsPointInsideTriangle({1, 2}, arr[0], arr[1], arr[2]), ()); + TEST(IsPointInsideTriangle({2, 1}, arr[0], arr[1], arr[2]), ()); + + double constexpr eps = 1.0E-10; + TEST(!IsPointInsideTriangle({-eps, -eps}, arr[0], arr[1], arr[2]), ()); + TEST(!IsPointInsideTriangle({1 + eps, 2}, arr[0], arr[1], arr[2]), ()); + TEST(!IsPointInsideTriangle({2, 1 + eps}, arr[0], arr[1], arr[2]), ()); +} + UNIT_TEST(PolygonSelfIntersections_IntersectSmoke) { { diff --git a/geometry/geometry_tests/segments_intersect_test.cpp b/geometry/geometry_tests/segments_intersect_test.cpp index a92c62c163..d10369864f 100644 --- a/geometry/geometry_tests/segments_intersect_test.cpp +++ b/geometry/geometry_tests/segments_intersect_test.cpp @@ -1,18 +1,20 @@ #include "testing/testing.hpp" -#include "geometry/point2d.hpp" + +#include "geometry/robust_orientation.hpp" + typedef m2::PointD P; bool SegmentsIntersect(P a, P b, P c, P d) { - bool res = m2::SegmentsIntersect(a, b, c, d); - TEST_EQUAL(res, m2::SegmentsIntersect(a, b, d, c), (a, b, c, d)); - TEST_EQUAL(res, m2::SegmentsIntersect(b, a, c, d), (a, b, c, d)); - TEST_EQUAL(res, m2::SegmentsIntersect(b, a, d, c), (a, b, c, d)); - TEST_EQUAL(res, m2::SegmentsIntersect(c, d, a, b), (a, b, c, d)); - TEST_EQUAL(res, m2::SegmentsIntersect(c, d, b, a), (a, b, c, d)); - TEST_EQUAL(res, m2::SegmentsIntersect(d, c, a, b), (a, b, c, d)); - TEST_EQUAL(res, m2::SegmentsIntersect(d, c, b, a), (a, b, c, d)); + bool const res = m2::robust::SegmentsIntersect(a, b, c, d); + TEST_EQUAL(res, m2::robust::SegmentsIntersect(a, b, d, c), (a, b, c, d)); + TEST_EQUAL(res, m2::robust::SegmentsIntersect(b, a, c, d), (a, b, c, d)); + TEST_EQUAL(res, m2::robust::SegmentsIntersect(b, a, d, c), (a, b, c, d)); + TEST_EQUAL(res, m2::robust::SegmentsIntersect(c, d, a, b), (a, b, c, d)); + TEST_EQUAL(res, m2::robust::SegmentsIntersect(c, d, b, a), (a, b, c, d)); + TEST_EQUAL(res, m2::robust::SegmentsIntersect(d, c, a, b), (a, b, c, d)); + TEST_EQUAL(res, m2::robust::SegmentsIntersect(d, c, b, a), (a, b, c, d)); return res; } diff --git a/geometry/point2d.hpp b/geometry/point2d.hpp index 23a3597966..142a5c0641 100644 --- a/geometry/point2d.hpp +++ b/geometry/point2d.hpp @@ -245,78 +245,6 @@ namespace m2 return res; } - template <typename T> - bool IsPointInsideTriangle(Point<T> const & p, - Point<T> const & a, Point<T> const & b, Point<T> const & c) - { - T const cpab = CrossProduct(b - a, p - a); - T const cpbc = CrossProduct(c - b, p - b); - T const cpca = CrossProduct(a - c, p - c); - return (cpab <= 0 && cpbc <= 0 && cpca <= 0) || (cpab >= 0 && cpbc >= 0 && cpca >= 0); - } - - template <typename T> - bool IsPointStrictlyInsideTriangle(Point<T> const & p, - Point<T> const & a, Point<T> const & b, Point<T> const & c) - { - T const cpab = CrossProduct(b - a, p - a); - T const cpbc = CrossProduct(c - b, p - b); - T const cpca = CrossProduct(a - c, p - c); - return (cpab < 0 && cpbc < 0 && cpca < 0) || (cpab > 0 && cpbc > 0 && cpca > 0); - } - - template <typename T> - bool SegmentsIntersect(Point<T> const & a, Point<T> const & b, - Point<T> const & c, Point<T> 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) && - CrossProduct(c - a, b - a) * CrossProduct(d - a, b - a) <= 0 && - CrossProduct(a - c, d - c) * CrossProduct(b - c, d - c) <= 0; - } - - /// Is segment (v, v1) in cone (vPrev, v, vNext)? - /// @precondition Orientation CCW!!! - template <typename PointT> bool IsSegmentInCone(PointT v, PointT v1, PointT vPrev, PointT vNext) - { - PointT const diff = v1 - v; - PointT const edgeL = vPrev - v; - PointT const edgeR = vNext - v; - double const cpLR = CrossProduct(edgeR, edgeL); - - if (my::AlmostEqualULPs(cpLR, 0.0)) - { - // Points vPrev, v, vNext placed on one line; - // use property that polygon has CCW orientation. - return CrossProduct(vNext - vPrev, v1 - vPrev) > 0.0; - } - - if (cpLR > 0) - { - // vertex is convex - return CrossProduct(diff, edgeR) < 0 && CrossProduct(diff, edgeL) > 0.0; - } - else - { - // vertex is reflex - return CrossProduct(diff, edgeR) < 0 || CrossProduct(diff, edgeL) > 0.0; - } - } - - template <typename PointT> - int GetOrientation(PointT const & p1, PointT const & p2, PointT const & pt) - { - double const sa = CrossProduct(p1 - pt, p2 - pt); - if (sa > 0.0) - return 1; - if (sa < 0.0) - return -1; - return 0; - } - template <typename T> string DebugPrint(m2::Point<T> const & p) { ostringstream out; diff --git a/geometry/polygon.hpp b/geometry/polygon.hpp index 6274795c13..57272b29b6 100644 --- a/geometry/polygon.hpp +++ b/geometry/polygon.hpp @@ -91,7 +91,7 @@ template <typename IterT> bool IsPolygonCCW(IterT beg, IterT end) IterT iNext = NextIterInCycle(iRes, beg, end); cp = m2::robust::OrientedS(*iPrev, *iRes, *iNext); - ASSERT_NOT_EQUAL ( cp, 0.0, (*iPrev, *iRes, *iNext) ); + ASSERT_NOT_EQUAL(cp, 0.0, (*iPrev, *iRes, *iNext)); return (cp > 0.0); } @@ -109,7 +109,7 @@ bool IsDiagonalVisible(IterT beg, IterT end, IterT i0, IterT i1) if (prev == i1 || next == i1) return true; - if (!m2::IsSegmentInCone(*i0, *i1, *prev, *next)) + if (!m2::robust::IsSegmentInCone(*i0, *i1, *prev, *next)) return false; for (IterT j0 = beg, j1 = PrevIterInCycle(beg, beg, end); j0 != end; j1 = j0++) diff --git a/geometry/robust_orientation.cpp b/geometry/robust_orientation.cpp index e7f2e99aad..98987e5096 100644 --- a/geometry/robust_orientation.cpp +++ b/geometry/robust_orientation.cpp @@ -38,6 +38,30 @@ namespace m2 { namespace robust return orient2d(a, b, c); } + 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) + { + // Points vPrev, v, vNext placed on one line; + // use property that polygon has CCW orientation. + return OrientedS(vPrev, vNext, v1) > 0.0; + } + + if (cpLR < 0) + { + // vertex is concave + return OrientedS(v, vPrev, v1) < 0 && OrientedS(v, vNext, v1) > 0.0; + } + else + { + // vertex is convex + return OrientedS(v, vPrev, v1) < 0 || OrientedS(v, vNext, v1) > 0.0; + } + } + bool SegmentsIntersect(PointD const & a, PointD const & b, PointD const & c, PointD const & d) { diff --git a/geometry/robust_orientation.hpp b/geometry/robust_orientation.hpp index f2fb074c92..e4f81b65db 100644 --- a/geometry/robust_orientation.hpp +++ b/geometry/robust_orientation.hpp @@ -9,8 +9,16 @@ namespace m2 { namespace robust { 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); + /// 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); diff --git a/geometry/triangle2d.cpp b/geometry/triangle2d.cpp new file mode 100644 index 0000000000..ba790a084d --- /dev/null +++ b/geometry/triangle2d.cpp @@ -0,0 +1,33 @@ +#include "triangle2d.hpp" + +#include "robust_orientation.hpp" + + +namespace m2 +{ + +using namespace robust; + +bool IsPointInsideTriangle(m2::PointD const & pt, m2::PointD const & p1, + m2::PointD const & p2, m2::PointD const & p3) +{ + double const s1 = OrientedS(p1, p2, pt); + double const s2 = OrientedS(p2, p3, pt); + double const s3 = OrientedS(p3, p1, pt); + + return ((s1 >= 0.0 && s2 >= 0.0 && s3 >= 0.0) || + (s1 <= 0.0 && s2 <= 0.0 && s3 <= 0.0)); +} + +bool IsPointStrictlyInsideTriangle(m2::PointD const & pt, m2::PointD const & p1, + m2::PointD const & p2, m2::PointD const & p3) +{ + double const s1 = OrientedS(p1, p2, pt); + double const s2 = OrientedS(p2, p3, pt); + double const s3 = OrientedS(p3, p1, pt); + + return ((s1 > 0.0 && s2 > 0.0 && s3 > 0.0) || + (s1 < 0.0 && s2 < 0.0 && s3 < 0.0)); +} + +} // namespace m2; diff --git a/geometry/triangle2d.hpp b/geometry/triangle2d.hpp index 7cd828b96c..6dbfebde85 100644 --- a/geometry/triangle2d.hpp +++ b/geometry/triangle2d.hpp @@ -11,4 +11,14 @@ double GetTriangleArea(Point<T> const & p1, Point<T> const & p2, Point<T> const return 0.5 * fabs((p2.x - p1.x)*(p3.y - p1.y) - (p3.x - p1.x)*(p2.y - p1.y)); } -} +/// @param[in] pt - Point to check +/// @param[in] p1, p2, p3 - Triangle +//@{ +bool IsPointInsideTriangle(m2::PointD const & pt, m2::PointD const & p1, + m2::PointD const & p2, m2::PointD const & p3); + +bool IsPointStrictlyInsideTriangle(m2::PointD const & pt, m2::PointD const & p1, + m2::PointD const & p2, m2::PointD const & p3); +//@} + +} // namespace m2 |