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
|
#pragma once
#include "indexer/cell_id.hpp"
#include "base/buffer_vector.hpp"
#include "std/queue.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 BoundsT, typename CellIdT>
inline size_t SplitRectCell(CellIdT const & id, m2::RectD const & rect,
array<pair<CellIdT, m2::RectD>, 4> & result)
{
size_t index = 0;
for (int8_t i = 0; i < 4; ++i)
{
CellIdT const child = id.Child(i);
double minCellX, minCellY, maxCellX, maxCellY;
CellIdConverter<BoundsT, CellIdT>::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 BoundsT, typename CellIdT>
inline void CoverRect(m2::RectD rect, size_t cellsCount, int maxDepth, vector<CellIdT> & result)
{
ASSERT(result.empty(), ());
{
// Cut rect with world bound coordinates.
if (!rect.Intersect({BoundsT::minX, BoundsT::minY, BoundsT::maxX, BoundsT::maxY}))
return;
ASSERT(rect.IsValid(), ());
}
CellIdT const commonCell = CellIdConverter<BoundsT, CellIdT>::Cover2PointsWithCell(
rect.minX(), rect.minY(), rect.maxX(), rect.maxY());
priority_queue<CellIdT, buffer_vector<CellIdT, SPLIT_RECT_CELLS_COUNT>,
typename CellIdT::GreaterLevelOrder>
cellQueue;
cellQueue.push(commonCell);
maxDepth -= 1;
while (!cellQueue.empty() && cellQueue.size() + result.size() < cellsCount)
{
CellIdT id = cellQueue.top();
cellQueue.pop();
while (id.Level() > maxDepth)
id = id.Parent();
if (id.Level() == maxDepth)
{
result.push_back(id);
break;
}
array<pair<CellIdT, m2::RectD>, 4> arr;
size_t const count = SplitRectCell<BoundsT>(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())
{
CellIdT id = cellQueue.top();
while (id.Level() < maxDepth)
{
array<pair<CellIdT, m2::RectD>, 4> arr;
size_t const count = SplitRectCell<BoundsT>(id, rect, arr);
ASSERT_GREATER(count, 0, ());
if (count > 1)
break;
id = arr[0].first;
}
result.push_back(id);
}
}
|
