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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
|
#pragma once
#include "indexer/cell_id.hpp"
#include "geometry/rect2d.hpp"
#include "base/buffer_vector.hpp"
#include "std/array.hpp"
#include "std/cstdint.hpp"
#include "std/queue.hpp"
#include "std/utility.hpp"
#include "std/vector.hpp"
// TODO: Move neccessary functions to geometry/covering_utils.hpp and delete this file.
constexpr int SPLIT_RECT_CELLS_COUNT = 512;
template <typename Bounds, typename CellId>
inline size_t SplitRectCell(CellId const & id, m2::RectD const & rect,
array<pair<CellId, m2::RectD>, 4> & result)
{
size_t index = 0;
for (int8_t i = 0; i < 4; ++i)
{
auto const child = id.Child(i);
double minCellX, minCellY, maxCellX, maxCellY;
CellIdConverter<Bounds, CellId>::GetCellBounds(child, minCellX, minCellY, maxCellX, maxCellY);
m2::RectD const childRect(minCellX, minCellY, maxCellX, maxCellY);
if (rect.IsIntersect(childRect))
result[index++] = {child, childRect};
}
return index;
}
template <typename Bounds, typename CellId>
inline void CoverRect(m2::RectD rect, size_t cellsCount, int maxDepth, vector<CellId> & result)
{
ASSERT(result.empty(), ());
{
// Cut rect with world bound coordinates.
if (!rect.Intersect(Bounds::FullRect()))
return;
ASSERT(rect.IsValid(), ());
}
auto const commonCell = CellIdConverter<Bounds, CellId>::Cover2PointsWithCell(
rect.minX(), rect.minY(), rect.maxX(), rect.maxY());
priority_queue<CellId, buffer_vector<CellId, SPLIT_RECT_CELLS_COUNT>,
typename CellId::GreaterLevelOrder>
cellQueue;
cellQueue.push(commonCell);
maxDepth -= 1;
while (!cellQueue.empty() && cellQueue.size() + result.size() < cellsCount)
{
auto id = cellQueue.top();
cellQueue.pop();
while (id.Level() > maxDepth)
id = id.Parent();
if (id.Level() == maxDepth)
{
result.push_back(id);
break;
}
array<pair<CellId, m2::RectD>, 4> arr;
size_t const count = SplitRectCell<Bounds>(id, rect, arr);
if (cellQueue.size() + result.size() + count <= cellsCount)
{
for (size_t i = 0; i < count; ++i)
{
if (rect.IsRectInside(arr[i].second))
result.push_back(arr[i].first);
else
cellQueue.push(arr[i].first);
}
}
else
{
result.push_back(id);
}
}
for (; !cellQueue.empty(); cellQueue.pop())
{
auto id = cellQueue.top();
while (id.Level() < maxDepth)
{
array<pair<CellId, m2::RectD>, 4> arr;
size_t const count = SplitRectCell<Bounds>(id, rect, arr);
ASSERT_GREATER(count, 0, ());
if (count > 1)
break;
id = arr[0].first;
}
result.push_back(id);
}
}
// Covers rect with cells using spiral order starting from the rect center.
template <typename Bounds, typename CellId>
void CoverSpiral(m2::RectD rect, int maxDepth, vector<CellId> & result)
{
using Converter = CellIdConverter<Bounds, CellId>;
enum class Direction : uint8_t
{
Right = 0,
Down = 1,
Left = 2,
Up = 3
};
CHECK(result.empty(), ());
// Cut rect with world bound coordinates.
if (!rect.Intersect(Bounds::FullRect()))
return;
CHECK(rect.IsValid(), ());
auto centralCell = Converter::ToCellId(rect.Center().x, rect.Center().y);
while (centralCell.Level() > maxDepth && centralCell.Level() > 0)
centralCell = centralCell.Parent();
if (centralCell.Level() > maxDepth)
return;
result.push_back(centralCell);
// Area around CentralCell will be covered with surrounding cells.
//
// * -> * -> * -> *
// ^ |
// | V
// * C -> * *
// ^ | |
// | V V
// * <- * <- * *
//
// To get the best ranking quality we should use the smallest cell size but it's not
// efficient because it generates too many index requests. To get good quality-performance
// tradeoff we cover area with |maxCount| small cells, then increase cell size and cover
// area with |maxCount| bigger cells. We increase cell size until |rect| is covered.
// We start covering from the center each time and it's ok for ranking because each object
// appears in result at most once.
// |maxCount| may be adjusted after testing to ensure better quality-performance tradeoff.
uint32_t constexpr maxCount = 64;
auto const nextDirection = [](Direction direction) {
return static_cast<Direction>((static_cast<uint8_t>(direction) + 1) % 4);
};
auto const nextCoords = [](pair<int32_t, int32_t> const & xy, Direction direction, uint32_t step) {
auto res = xy;
switch (direction)
{
case Direction::Right: res.first += step; break;
case Direction::Down: res.second -= step; break;
case Direction::Left: res.first -= step; break;
case Direction::Up: res.second += step; break;
}
return res;
};
auto const coordsAreValid = [](pair<int32_t, int32_t> const & xy) {
return xy.first >= 0 && xy.second >= 0 && xy.first <= CellId::MAX_COORD &&
xy.second <= CellId::MAX_COORD;
};
m2::RectD coveredRect;
static_assert(CellId::MAX_COORD == static_cast<int32_t>(CellId::MAX_COORD), "");
while (centralCell.Level() > 0 && !coveredRect.IsRectInside(rect))
{
uint32_t count = 0;
auto const centerXY = centralCell.XY();
// We support negative coordinates while covering and check coordinates validity before pushing
// cell to |result|.
pair<int32_t, int32_t> xy{centerXY.first, centerXY.second};
auto direction = Direction::Right;
int sideLength = 1;
// Indicates whether it is the first pass with current |sideLength|. We use spiral cells order and
// must increment |sideLength| every second side pass. |sideLength| and |direction| will behave like:
// 1 right, 1 down, 2 left, 2 up, 3 right, 3 down, etc.
bool evenPass = true;
while (count <= maxCount && !coveredRect.IsRectInside(rect))
{
for (int i = 0; i < sideLength; ++i)
{
xy = nextCoords(xy, direction, centralCell.Radius() * 2);
if (coordsAreValid(xy))
{
auto const cell = CellId::FromXY(xy.first, xy.second, centralCell.Level());
double minCellX, minCellY, maxCellX, maxCellY;
Converter::GetCellBounds(cell, minCellX, minCellY, maxCellX, maxCellY);
auto const cellRect = m2::RectD(minCellX, minCellY, maxCellX, maxCellY);
coveredRect.Add(cellRect);
if (rect.IsIntersect(cellRect))
result.push_back(cell);
}
++count;
}
if (!evenPass)
++sideLength;
direction = nextDirection(direction);
evenPass = !evenPass;
}
centralCell = centralCell.Parent();
}
}
|
