1 //Copyright (c) 2016 Scott Lenser
2 //Copyright (c) 2018 Ultimaker B.V.
3 //CuraEngine is released under the terms of the AGPLv3 or higher.
4
5 #ifndef UTILS_SPARSE_POINT_GRID_INCLUSIVE_H
6 #define UTILS_SPARSE_POINT_GRID_INCLUSIVE_H
7
8 #include <cassert>
9 #include <unordered_map>
10 #include <vector>
11
12 #include "IntPoint.h"
13 #include "SparsePointGrid.h"
14
15 namespace cura {
16
17
18 namespace SparsePointGridInclusiveImpl {
19
20 template<class Val>
21 struct SparsePointGridInclusiveElem
22 {
SparsePointGridInclusiveElemSparsePointGridInclusiveElem23 SparsePointGridInclusiveElem()
24 {
25 }
26
SparsePointGridInclusiveElemSparsePointGridInclusiveElem27 SparsePointGridInclusiveElem(const Point &point_, const Val &val_) :
28 point(point_),
29 val(val_)
30 {
31 }
32
33 Point point;
34 Val val;
35 };
36
37 template<class T>
38 struct Locatoror
39 {
operatorLocatoror40 Point operator()(const SparsePointGridInclusiveElem<T> &elem)
41 {
42 return elem.point;
43 }
44 };
45
46 } // namespace SparseGridImpl
47
48 /*! \brief Sparse grid which can locate spatially nearby values efficiently.
49 *
50 * \tparam Val The value type to store.
51 */
52 template<class Val>
53 class SparsePointGridInclusive : public SparsePointGrid<SparsePointGridInclusiveImpl::SparsePointGridInclusiveElem<Val>,
54 SparsePointGridInclusiveImpl::Locatoror<Val> >
55 {
56 public:
57 using Base = SparsePointGrid<SparsePointGridInclusiveImpl::SparsePointGridInclusiveElem<Val>,
58 SparsePointGridInclusiveImpl::Locatoror<Val> >;
59
60 /*! \brief Constructs a sparse grid with the specified cell size.
61 *
62 * \param[in] cell_size The size to use for a cell (square) in the grid.
63 * Typical values would be around 0.5-2x of expected query radius.
64 * \param[in] elem_reserve Number of elements to research space for.
65 * \param[in] max_load_factor Maximum average load factor before rehashing.
66 */
67 SparsePointGridInclusive(coord_t cell_size, size_t elem_reserve=0U, float max_load_factor=1.0f);
68
69 /*! \brief Inserts an element with specified point and value into the sparse grid.
70 *
71 * This is a convenience wrapper over \ref SparsePointGrid::insert()
72 *
73 * \param[in] point The location for the element.
74 * \param[in] val The value for the element.
75 */
76 void insert(const Point &point, const Val &val);
77
78 /*! \brief Returns all values within radius of query_pt.
79 *
80 * Finds all values with location within radius of \p query_pt. May
81 * return additional values that are beyond radius.
82 *
83 * See \ref getNearby().
84 *
85 * \param[in] query_pt The point to search around.
86 * \param[in] radius The search radius.
87 * \return Vector of values found
88 */
89 std::vector<Val> getNearbyVals(const Point &query_pt, coord_t radius) const;
90
91 };
92
93 #define SG_TEMPLATE template<class Val>
94 #define SG_THIS SparsePointGridInclusive<Val>
95
96 SG_TEMPLATE
SparsePointGridInclusive(coord_t cell_size,size_t elem_reserve,float max_load_factor)97 SG_THIS::SparsePointGridInclusive(coord_t cell_size, size_t elem_reserve, float max_load_factor) :
98 Base(cell_size,elem_reserve,max_load_factor)
99 {
100 }
101
102 SG_TEMPLATE
insert(const Point & point,const Val & val)103 void SG_THIS::insert(const Point &point, const Val &val)
104 {
105 typename SG_THIS::Elem elem(point,val);
106 Base::insert(elem);
107 }
108
109 SG_TEMPLATE
110 std::vector<Val>
getNearbyVals(const Point & query_pt,coord_t radius)111 SG_THIS::getNearbyVals(const Point &query_pt, coord_t radius) const
112 {
113 std::vector<Val> ret;
114 std::function<bool (const SparsePointGridInclusiveImpl::SparsePointGridInclusiveElem<Val>&)> process_func = [&ret](const typename SG_THIS::Elem &elem)
115 {
116 ret.push_back(elem.val);
117 return true;
118 };
119 this->processNearby(query_pt, radius, process_func);
120 return ret;
121 }
122
123
124 #undef SG_TEMPLATE
125 #undef SG_THIS
126
127 } // namespace cura
128
129 #endif // UTILS_SPARSE_POINT_GRID_INCLUSIVE_H
130