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
|