Welcome to mirror list, hosted at ThFree Co, Russian Federation.

segment2d.cpp « geometry - github.com/mapsme/omim.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
blob: 3b13bb04711696be0bd7db20a03b4c8bc95079b8 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include "geometry/segment2d.hpp"

#include "geometry/line2d.hpp"
#include "geometry/robust_orientation.hpp"

#include <algorithm>
#include <sstream>
#include <string>

using namespace std;

namespace m2
{
bool IsPointOnSegmentEps(PointD const & pt, PointD const & p1, PointD const & p2, double eps)
{
  double const t = robust::OrientedS(p1, p2, pt);

  if (fabs(t) > eps)
    return false;

  double minX = p1.x;
  double maxX = p2.x;
  if (maxX < minX)
    swap(maxX, minX);

  double minY = p1.y;
  double maxY = p2.y;
  if (maxY < minY)
    swap(maxY, minY);

  return pt.x >= minX - eps && pt.x <= maxX + eps && pt.y >= minY - eps && pt.y <= maxY + eps;
}

bool IsPointOnSegment(PointD const & pt, PointD const & p1, PointD const & p2)
{
  // The epsilon here is chosen quite arbitrarily, to pass paranoid
  // tests and to match our real-data geometry precision. If you have
  // better ideas how to check whether pt belongs to (p1, p2) segment
  // more precisely or without kEps, feel free to submit a pull
  // request.
  double const kEps = 1e-100;
  return IsPointOnSegmentEps(pt, p1, p2, kEps);
}

bool SegmentsIntersect(PointD const & a, PointD const & b, PointD const & c, PointD 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) &&
      robust::OrientedS(a, b, c) * robust::OrientedS(a, b, d) <= 0.0 &&
      robust::OrientedS(c, d, a) * robust::OrientedS(c, d, b) <= 0.0;
}

IntersectionResult Intersect(Segment2D const & seg1, Segment2D const & seg2, double eps)
{
  if (!SegmentsIntersect(seg1.m_u, seg1.m_v, seg2.m_u, seg2.m_v))
    return IntersectionResult(IntersectionResult::Type::Zero);

  Line2D const line1(seg1);
  Line2D const line2(seg2);
  auto const lineIntersection = Intersect(line1, line2, eps);
  if (lineIntersection.m_type != IntersectionResult::Type::One)
    return lineIntersection;

  if (IsPointOnSegmentEps(lineIntersection.m_point, seg1.m_u, seg1.m_v, eps) &&
      IsPointOnSegmentEps(lineIntersection.m_point, seg2.m_u, seg2.m_v, eps))
  {
    return lineIntersection;
  }

  return IntersectionResult(IntersectionResult::Type::Zero);
}

std::string DebugPrint(Segment2D const & segment)
{
  return "(" + DebugPrint(segment.m_u) + ", " + DebugPrint(segment.m_v) + ")";
}

string DebugPrint(IntersectionResult::Type type)
{
  using Type = IntersectionResult::Type;

  switch (type)
  {
  case Type::Zero: return "Zero";
  case Type::One: return "One";
  case Type::Infinity: return "Infinity";
  }
  UNREACHABLE();
}

string DebugPrint(IntersectionResult const & result)
{
  ostringstream os;
  os << "Result [";
  if (result.m_type == IntersectionResult::Type::One)
    os << DebugPrint(result.m_point);
  else
    os << DebugPrint(result.m_type);
  os << "]";
  return os.str();
}
}  // namespace m2