diff options
author | vng <viktor.govako@gmail.com> | 2011-06-11 16:54:19 +0400 |
---|---|---|
committer | Alex Zolotarev <alex@maps.me> | 2015-09-23 01:19:20 +0300 |
commit | 7435ad01cffc6b12ea24d02398629eb5d9f92744 (patch) | |
tree | 32ad1c1dd9610087e52e3d59113bf4a4d6340d43 /geometry | |
parent | a3d2aa94ef1678f11919697d6c8e5be6b28bae7a (diff) |
Fix infinite loop in rect-section interaction.
Add unit tests.
Russian to english comments.
Diffstat (limited to 'geometry')
-rw-r--r-- | geometry/geometry_tests/intersect_test.cpp | 9 | ||||
-rw-r--r-- | geometry/rect_intersect.hpp | 37 |
2 files changed, 29 insertions, 17 deletions
diff --git a/geometry/geometry_tests/intersect_test.cpp b/geometry/geometry_tests/intersect_test.cpp index 052e09334a..ddec9a3ef8 100644 --- a/geometry/geometry_tests/intersect_test.cpp +++ b/geometry/geometry_tests/intersect_test.cpp @@ -171,3 +171,12 @@ UNIT_TEST(IntersectRect_Point) } } } + +UNIT_TEST(IntersectRect_NAN) +{ + m2::RectD r(-47.622792787168442885, -8.5438097219402173721, 134.06976090684074165, 9.0000000000000337508); + m2::PointD p1(134.06976090684077008, 9.0000000000001847411); + m2::PointD p2(134.06976090684074165, -8.5438097219401640814); + + m2::Intersect(r, p1, p2); +} diff --git a/geometry/rect_intersect.hpp b/geometry/rect_intersect.hpp index 2897b8f772..86cb903335 100644 --- a/geometry/rect_intersect.hpp +++ b/geometry/rect_intersect.hpp @@ -7,18 +7,20 @@ namespace m2 { namespace detail { - static const int LEFT = 1; // двоичное 0001 - static const int RIGHT = 2; // двоичное 0010 - static const int BOT = 4; // двоичное 0100 - static const int TOP = 8; // двоичное 1000 + // bit masks for code kinds + static const int LEFT = 1; + static const int RIGHT = 2; + static const int BOT = 4; + static const int TOP = 8; + // return accumulated bit mask for point-rect interaction template <class T> int vcode(m2::Rect<T> const & r, m2::Point<T> const & p) { - return ((p.x < r.minX() ? LEFT : 0) + // +1 если точка левее прямоугольника - (p.x > r.maxX() ? RIGHT : 0) + // +2 если точка правее прямоугольника - (p.y < r.minY() ? BOT : 0) + // +4 если точка ниже прямоугольника - (p.y > r.maxY() ? TOP : 0)); // +8 если точка выше прямоугольника + return ((p.x < r.minX() ? LEFT : 0) + + (p.x > r.maxX() ? RIGHT : 0) + + (p.y < r.minY() ? BOT : 0) + + (p.y > r.maxY() ? TOP : 0)); } } @@ -27,16 +29,16 @@ namespace m2 { int code[2] = { detail::vcode(r, p1), detail::vcode(r, p2) }; - // пока одна из точек отрезка вне прямоугольника + // do while one of the point is out of rect while (code[0] || code[1]) { if (code[0] & code[1]) { - // если обе точки с одной стороны прямоугольника, то отрезок не пересекает прямоугольник + // both point area on the one side of rect return false; } - // выбираем точку c с ненулевым кодом + // choose point with non-zero code m2::Point<T> * pp; int i; if (code[0]) @@ -50,37 +52,38 @@ namespace m2 pp = &p2; } - // если pp левее r, то передвигаем pp на прямую x = r->x_min - // если pp правее r, то передвигаем pp на прямую x = r->x_max + // added points compare to avoid NAN numbers if (code[i] & detail::LEFT) { + if (p1 == p2) return false; pp->y += (p1.y - p2.y) * (r.minX() - pp->x) / (p1.x - p2.x); pp->x = r.minX(); } else if (code[i] & detail::RIGHT) { + if (p1 == p2) return false; pp->y += (p1.y - p2.y) * (r.maxX() - pp->x) / (p1.x - p2.x); pp->x = r.maxX(); } - // если pp ниже r, то передвигаем pp на прямую y = r->y_min - // если pp выше r, то передвигаем pp на прямую y = r->y_max if (code[i] & detail::BOT) { + if (p1 == p2) return false; pp->x += (p1.x - p2.x) * (r.minY() - pp->y) / (p1.y - p2.y); pp->y = r.minY(); } else if (code[i] & detail::TOP) { + if (p1 == p2) return false; pp->x += (p1.x - p2.x) * (r.maxY() - pp->y) / (p1.y - p2.y); pp->y = r.maxY(); } - // обновляем код + // update code with new point code[i] = detail::vcode(r, *pp); } - // оба кода равны 0, следовательно обе точки в прямоугольнике + // both codes are equal to zero => points area inside rect return true; } } |