diff options
author | Yuri Gorshenin <y@maps.me> | 2016-02-02 14:12:55 +0300 |
---|---|---|
committer | Sergey Yershov <yershov@corp.mail.ru> | 2016-03-23 16:16:43 +0300 |
commit | 669636ec86cfbcab4e0a49ebe5716cfad2ed17ae (patch) | |
tree | b0354de94509a6640333a7feddae24619ff88bc7 /geometry | |
parent | 7e876d125ea384b941208e1e42ac3cfb50355644 (diff) |
[search] [geometry] Fixed IsPointInsideTriangle() for degenerate triangles.
Diffstat (limited to 'geometry')
-rw-r--r-- | geometry/geometry.pro | 2 | ||||
-rw-r--r-- | geometry/geometry_tests/robust_test.cpp | 86 | ||||
-rw-r--r-- | geometry/triangle2d.cpp | 13 |
3 files changed, 91 insertions, 10 deletions
diff --git a/geometry/geometry.pro b/geometry/geometry.pro index c53293ca49..9f297dacbf 100644 --- a/geometry/geometry.pro +++ b/geometry/geometry.pro @@ -17,6 +17,7 @@ SOURCES += \ region2d/binary_operators.cpp \ robust_orientation.cpp \ screenbase.cpp \ + segment2d.cpp \ spline.cpp \ triangle2d.cpp \ @@ -43,6 +44,7 @@ HEADERS += \ region2d/boost_concept.hpp \ robust_orientation.hpp \ screenbase.hpp \ + segment2d.hpp \ simplification.hpp \ spline.hpp \ transformations.hpp \ diff --git a/geometry/geometry_tests/robust_test.cpp b/geometry/geometry_tests/robust_test.cpp index f0ed0c2e19..d20703361f 100644 --- a/geometry/geometry_tests/robust_test.cpp +++ b/geometry/geometry_tests/robust_test.cpp @@ -1,6 +1,7 @@ #include "testing/testing.hpp" #include "geometry/robust_orientation.hpp" +#include "geometry/segment2d.hpp" #include "geometry/triangle2d.hpp" @@ -8,15 +9,26 @@ using namespace m2::robust; namespace { - using P = m2::PointD; +using P = m2::PointD; - template <typename IterT> void CheckSelfIntersections(IterT beg, IterT end, bool res) - { - TEST_EQUAL(CheckPolygonSelfIntersections(beg, end), res, ()); - using ReverseIterT = reverse_iterator<IterT>; - TEST_EQUAL(CheckPolygonSelfIntersections(ReverseIterT(end), ReverseIterT(beg)), res, ()); - } +template <typename IterT> +void CheckSelfIntersections(IterT beg, IterT end, bool res) +{ + TEST_EQUAL(CheckPolygonSelfIntersections(beg, end), res, ()); + using ReverseIterT = reverse_iterator<IterT>; + TEST_EQUAL(CheckPolygonSelfIntersections(ReverseIterT(end), ReverseIterT(beg)), res, ()); +} + +bool InsideSegment(P const & p, P const ps[]) +{ + return IsPointInsideSegment(p, ps[0], ps[1]); +} + +bool InsideTriangle(P const & p, P const ps[]) +{ + return IsPointInsideTriangle(p, ps[0], ps[1], ps[2]); } +} // namespace UNIT_TEST(OrientedS_Smoke) { @@ -25,6 +37,34 @@ UNIT_TEST(OrientedS_Smoke) TEST(OrientedS(arr[2], arr[0], arr[1]) < 0, ()); } +UNIT_TEST(Segment_Smoke) +{ + double constexpr eps = 1.0E-10; + { + P ps[] = {{0, 0}, {1, 0}}; + TEST(InsideSegment(ps[0], ps), ()); + TEST(InsideSegment(ps[1], ps), ()); + TEST(InsideSegment(P(0.5, 0), ps), ()); + + TEST(InsideSegment(P(eps, 0), ps), ()); + TEST(InsideSegment(P(1.0 - eps, 0), ps), ()); + + TEST(!InsideSegment(P(-eps, 0), ps), ()); + TEST(!InsideSegment(P(1.0 + eps, 0), ps), ()); + TEST(!InsideSegment(P(eps, eps), ps), ()); + TEST(!InsideSegment(P(eps, -eps), ps), ()); + } + + { + P ps[] = {{10, 10}, {10, 10}}; + TEST(InsideSegment(ps[0], ps), ()); + TEST(InsideSegment(ps[1], ps), ()); + TEST(!InsideSegment(P(10 - eps, 10), ps), ()); + TEST(!InsideSegment(P(10 + eps, 10), ps), ()); + TEST(!InsideSegment(P(0, 0), ps), ()); + } +} + UNIT_TEST(Triangle_Smoke) { P arr[] = {{0, 0}, {0, 3}, {3, 0}}; @@ -42,6 +82,38 @@ UNIT_TEST(Triangle_Smoke) TEST(!IsPointInsideTriangle({2, 1 + eps}, arr[0], arr[1], arr[2]), ()); } +UNIT_TEST(Triangle_PointInsideSegment) +{ + double constexpr eps = 1.0E-10; + + P ps[] = {{0, 0}, {0, 1}, {0, 1}}; + TEST(InsideTriangle(ps[0], ps), ()); + TEST(InsideTriangle(ps[1], ps), ()); + TEST(InsideTriangle(ps[2], ps), ()); + TEST(InsideTriangle(P(0, eps), ps), ()); + TEST(InsideTriangle(P(0, 1.0 - eps), ps), ()); + + TEST(!InsideTriangle(P(0, -eps), ps), ()); + TEST(!InsideTriangle(P(0, 1.0 + eps), ps), ()); + TEST(!InsideTriangle(P(-eps, eps), ps), ()); + TEST(!InsideTriangle(P(eps, eps), ps), ()); +} + +UNIT_TEST(Triangle_PointInsidePoint) +{ + double constexpr eps = 1.0E-10; + + P ps[] = {{0, 0}, {0, 0}, {0, 0}}; + TEST(InsideTriangle(ps[0], ps), ()); + TEST(InsideTriangle(ps[1], ps), ()); + TEST(InsideTriangle(ps[2], ps), ()); + + TEST(!InsideTriangle(P(0, eps), ps), ()); + TEST(!InsideTriangle(P(0, -eps), ps), ()); + TEST(!InsideTriangle(P(-eps, eps), ps), ()); + TEST(!InsideTriangle(P(eps, eps), ps), ()); +} + UNIT_TEST(PolygonSelfIntersections_IntersectSmoke) { { diff --git a/geometry/triangle2d.cpp b/geometry/triangle2d.cpp index ba790a084d..cbecf3a7f4 100644 --- a/geometry/triangle2d.cpp +++ b/geometry/triangle2d.cpp @@ -1,13 +1,12 @@ #include "triangle2d.hpp" #include "robust_orientation.hpp" +#include "segment2d.hpp" +using namespace m2::robust; namespace m2 { - -using namespace robust; - bool IsPointInsideTriangle(m2::PointD const & pt, m2::PointD const & p1, m2::PointD const & p2, m2::PointD const & p3) { @@ -15,6 +14,14 @@ bool IsPointInsideTriangle(m2::PointD const & pt, m2::PointD const & p1, double const s2 = OrientedS(p2, p3, pt); double const s3 = OrientedS(p3, p1, pt); + // In the case of degenerate triangles we need to check that pt lies + // on (p1, p2), (p2, p3) or (p3, p1). + if (s1 == 0.0 && s2 == 0.0 && s3 == 0.0) + { + return IsPointInsideSegment(pt, p1, p2) || IsPointInsideSegment(pt, p2, p3) || + IsPointInsideSegment(pt, p3, p1); + } + return ((s1 >= 0.0 && s2 >= 0.0 && s3 >= 0.0) || (s1 <= 0.0 && s2 <= 0.0 && s3 <= 0.0)); } |