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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
|
#pragma once
#include "search/segment_tree.hpp"
#include "geometry/point2d.hpp"
#include "geometry/rect2d.hpp"
#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <sstream>
#include <string>
#include <vector>
namespace search
{
class PointRectMatcher
{
public:
enum class RequestType : uint8_t
{
// A request to match every point to an arbitrary rectangle that contains it.
Any,
// A request to match every point to every rectangle that contains it.
// Every relevant (point, rectangle) pair must be listed exactly once.
All
};
struct PointIdPair
{
PointIdPair() = default;
PointIdPair(m2::PointD const & point, size_t id) : m_point(point), m_id(id) {}
m2::PointD m_point = m2::PointD::Zero();
size_t m_id = 0;
};
struct RectIdPair
{
RectIdPair() = default;
RectIdPair(m2::RectD const & rect, size_t id) : m_rect(rect), m_id(id) {}
m2::RectD m_rect;
size_t m_id = 0;
};
// For each point tries to find a rect containing the point. If
// there are several rects containing the point, selects an
// arbitrary one. Calls |fn| on matched pairs (point-id, rect-id).
//
// Complexity: O(n * log(n)), where n = |points| + |rects|.
template <typename Fn>
static void Match(std::vector<PointIdPair> const & points, std::vector<RectIdPair> const & rects,
RequestType requestType, Fn && fn)
{
std::vector<Event> events;
events.reserve(points.size() + 2 * rects.size());
for (auto const & p : points)
events.emplace_back(PointEvent(p.m_point.x, p.m_id), p.m_point.y);
std::vector<SegmentTree::Segment> segments;
segments.reserve(rects.size());
for (auto const & r : rects)
{
SegmentTree::Segment const segment(r.m_rect.minX(), r.m_rect.maxX(), r.m_id);
segments.push_back(segment);
events.emplace_back(Event::TYPE_SEGMENT_START, segment, r.m_rect.minY());
events.emplace_back(Event::TYPE_SEGMENT_END, segment, r.m_rect.maxY());
}
std::sort(segments.begin(), segments.end());
SegmentTree tree(segments);
std::sort(events.begin(), events.end());
for (auto const & e : events)
{
switch (e.m_type)
{
case Event::TYPE_SEGMENT_START: tree.Add(e.m_segment); break;
case Event::TYPE_POINT:
{
auto const segmentFn = [&](SegmentTree::Segment const & segment) {
fn(e.m_point.m_id, segment.m_id);
};
switch (requestType)
{
case RequestType::Any: tree.FindAny(e.m_point.m_x, segmentFn); break;
case RequestType::All: tree.FindAll(e.m_point.m_x, segmentFn); break;
}
}
break;
case Event::TYPE_SEGMENT_END: tree.Erase(e.m_segment); break;
}
}
}
private:
struct PointEvent
{
PointEvent() = default;
PointEvent(double x, size_t id) : m_x(x), m_id(id) {}
double m_x = 0;
size_t m_id = 0;
};
using SegmentEvent = SegmentTree::Segment;
struct Event
{
enum Type
{
TYPE_SEGMENT_START,
TYPE_POINT,
TYPE_SEGMENT_END,
};
Event(Type type, SegmentEvent const & segment, double time)
: m_segment(segment), m_time(time), m_type(type)
{
ASSERT(m_type == TYPE_SEGMENT_START || m_type == TYPE_SEGMENT_END, ());
}
Event(PointEvent const & point, double time) : m_point(point), m_time(time), m_type(TYPE_POINT)
{
}
bool operator<(Event const & rhs) const
{
if (m_time != rhs.m_time)
return m_time < rhs.m_time;
return m_type < rhs.m_type;
}
union {
SegmentEvent m_segment;
PointEvent m_point;
};
double m_time;
Type m_type;
};
};
} // namespace search
|
