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
|
#pragma once
#include "PolygonDictionary.h"
#include "PolygonDictionaryUtils.h"
#include <vector>
namespace DB
{
/** Simple implementation of the polygon dictionary. Doesn't generate anything during its construction.
* Iterates over all stored polygons for each query, checking each of them in linear time.
* Retrieves the polygon with the smallest area containing the given point.
* If there is more than one any such polygon may be returned.
*/
class PolygonDictionarySimple : public IPolygonDictionary
{
public:
PolygonDictionarySimple(
const StorageID & dict_id_,
const DictionaryStructure & dict_struct_,
DictionarySourcePtr source_ptr_,
DictionaryLifetime dict_lifetime_,
Configuration configuration_);
std::shared_ptr<const IExternalLoadable> clone() const override;
private:
bool find(const Point & point, size_t & polygon_index) const override;
};
/** A polygon dictionary which generates a recursive grid in order to efficiently cut the number
* of polygons to be checked for a given point.
* For more detail see the GridRoot and FinalCell classes.
* Separately, a slab index is built for each individual polygon. This allows to check the
* candidates more efficiently.
*/
class PolygonDictionaryIndexEach : public IPolygonDictionary
{
public:
PolygonDictionaryIndexEach(
const StorageID & dict_id_,
const DictionaryStructure & dict_struct_,
DictionarySourcePtr source_ptr_,
DictionaryLifetime dict_lifetime_,
Configuration configuration_,
int min_intersections_,
int max_depth_);
std::shared_ptr<const IExternalLoadable> clone() const override;
static constexpr size_t kMinIntersectionsDefault = 1;
static constexpr size_t kMaxDepthDefault = 5;
private:
bool find(const Point & point, size_t & polygon_index) const override;
std::vector<SlabsPolygonIndex> buckets;
GridRoot<FinalCell> grid;
const size_t min_intersections;
const size_t max_depth;
};
/** Uses single SlabsPolygonIndex for all queries. */
class PolygonDictionaryIndexCell : public IPolygonDictionary
{
public:
PolygonDictionaryIndexCell(
const StorageID & dict_id_,
const DictionaryStructure & dict_struct_,
DictionarySourcePtr source_ptr_,
DictionaryLifetime dict_lifetime_,
Configuration configuration_,
size_t min_intersections_,
size_t max_depth_);
std::shared_ptr<const IExternalLoadable> clone() const override;
static constexpr size_t kMinIntersectionsDefault = 1;
static constexpr size_t kMaxDepthDefault = 5;
private:
bool find(const Point & point, size_t & polygon_index) const override;
GridRoot<FinalCellWithSlabs> index;
const size_t min_intersections;
const size_t max_depth;
};
}
|
