diff options
author | vng <viktor.govako@gmail.com> | 2011-04-24 17:41:31 +0400 |
---|---|---|
committer | Alex Zolotarev <alex@maps.me> | 2015-09-23 01:16:17 +0300 |
commit | 69c15b4fb0dd95737300362e31f8b48ea69e7144 (patch) | |
tree | cfdf00a50b7459058759906635e4f51834ac9b58 /geometry/point2d.hpp | |
parent | d0361b1bb21f770ec2374ae8d0b77f2d7941c65a (diff) |
- Add robust algorithms (OrientedS, SegmentsIntersect, PolygonSelfIntersections).
- Move IsSegmentInCone to point2d.hpp.
- Use robust OrientedS in IsPolygonCCW function.
Diffstat (limited to 'geometry/point2d.hpp')
-rw-r--r-- | geometry/point2d.hpp | 34 |
1 files changed, 31 insertions, 3 deletions
diff --git a/geometry/point2d.hpp b/geometry/point2d.hpp index d2b4c5e8bc..f595995940 100644 --- a/geometry/point2d.hpp +++ b/geometry/point2d.hpp @@ -167,7 +167,7 @@ namespace m2 } template <typename T> - Point<T> const Rotate(Point<T> const & pt, T a) + Point<T> const Rotate(Point<T> const & pt, T a) { Point<T> res(pt); res.Rotate(a); @@ -175,13 +175,13 @@ namespace m2 } template <typename T, typename U> - Point<T> const Shift(Point<T> const & pt, U const & dx, U const & dy) + Point<T> const Shift(Point<T> const & pt, U const & dx, U const & dy) { return Point<T>(pt.x + dx, pt.y + dy); } template <typename T, typename U> - Point<T> const Shift(Point<T> const & pt, Point<U> const & offset) + Point<T> const Shift(Point<T> const & pt, Point<U> const & offset) { return Shift(pt, offset.x, offset.y); } @@ -209,6 +209,34 @@ namespace m2 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::AlmostEqual(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 T> string debug_print(m2::Point<T> const & p) { ostringstream out; |