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
|
/** \file
* Defines the interface of the _Region class.
*
* \author Martin F. Krafft <libkdtree@pobox.madduck.net>
*/
#ifndef INCLUDE_KDTREE_REGION_HPP
#define INCLUDE_KDTREE_REGION_HPP
#include <cstddef>
#include "node.hpp"
namespace KDTree
{
template <size_t const __K, typename _Val, typename _SubVal,
typename _Acc, typename _Cmp>
struct _Region
{
typedef _Val value_type;
typedef _SubVal subvalue_type;
// special typedef for checking against a fuzzy point (for find_nearest)
// Note the region (first) component is not supposed to have an area, its
// bounds should all be set to a specific point.
typedef std::pair<_Region,_SubVal> _CenterPt;
_Region(_Acc const& __acc=_Acc(), const _Cmp& __cmp=_Cmp())
: _M_acc(__acc), _M_cmp(__cmp) {}
template <typename Val>
_Region(Val const& __V,
_Acc const& __acc=_Acc(), const _Cmp& __cmp=_Cmp())
: _M_acc(__acc), _M_cmp(__cmp)
{
for (size_t __i = 0; __i != __K; ++__i)
{
_M_low_bounds[__i] = _M_high_bounds[__i] = _M_acc(__V,__i);
}
}
template <typename Val>
_Region(Val const& __V, subvalue_type const& __R,
_Acc const& __acc=_Acc(), const _Cmp& __cmp=_Cmp())
: _M_acc(__acc), _M_cmp(__cmp)
{
for (size_t __i = 0; __i != __K; ++__i)
{
_M_low_bounds[__i] = _M_acc(__V,__i) - __R;
_M_high_bounds[__i] = _M_acc(__V,__i) + __R;
}
}
// construct range for any V that: min(__V1, __V2) <= V <= max(__V1, __V2)
template <typename Val>
_Region(Val const& __V1, Val const& __V2,
_Acc const& __acc=_Acc(), const _Cmp& __cmp=_Cmp())
: _M_acc(__acc), _M_cmp(__cmp)
{
for (size_t __i = 0; __i != __K; ++__i)
{
_M_low_bounds[__i] = std::min(_M_acc(__V1,__i), _M_acc(__V2,__i));
_M_high_bounds[__i] = std::max(_M_acc(__V1,__i), _M_acc(__V2,__i));
}
}
bool
intersects_with(_CenterPt const& __THAT) const
{
for (size_t __i = 0; __i != __K; ++__i)
{
// does it fall outside the bounds?
// ! low-tolerance <= x <= high+tolerance
// ! (low-tol <= x and x <= high+tol)
// !low-tol<=x or !x<=high+tol
// low-tol>x or x>high+tol
// x<low-tol or high+tol<x
if (_M_cmp(__THAT.first._M_low_bounds[__i], _M_low_bounds[__i] - __THAT.second)
|| _M_cmp(_M_high_bounds[__i] + __THAT.second, __THAT.first._M_low_bounds[__i]))
return false;
}
return true;
}
bool
intersects_with(_Region const& __THAT) const
{
for (size_t __i = 0; __i != __K; ++__i)
{
if (_M_cmp(__THAT._M_high_bounds[__i], _M_low_bounds[__i])
|| _M_cmp(_M_high_bounds[__i], __THAT._M_low_bounds[__i]))
return false;
}
return true;
}
bool
intersect_with(value_type const& __V) const
{
return intersect_with(_Region(__V, __V));
}
bool
encloses(value_type const& __V) const
{
for (size_t __i = 0; __i != __K; ++__i)
{
if (_M_cmp(_M_acc(__V, __i), _M_low_bounds[__i])
|| _M_cmp(_M_high_bounds[__i], _M_acc(__V, __i)))
return false;
}
return true;
}
_Region&
set_high_bound(value_type const& __V, size_t const __L)
{
_M_high_bounds[__L % __K] = _M_acc(__V, __L % __K);
return *this;
}
_Region&
set_low_bound(value_type const& __V, size_t const __L)
{
_M_low_bounds[__L % __K] = _M_acc(__V, __L % __K);
return *this;
}
subvalue_type _M_low_bounds[__K], _M_high_bounds[__K];
_Acc _M_acc;
_Cmp _M_cmp;
};
} // namespace KDTree
#endif // include guard
/* COPYRIGHT --
*
* This file is part of libkdtree++, a C++ template KD-Tree sorting container.
* libkdtree++ is (c) 2004-2007 Martin F. Krafft <libkdtree@pobox.madduck.net>
* and Sylvain Bougerel <sylvain.bougerel.devel@gmail.com> distributed under the
* terms of the Artistic License 2.0. See the ./COPYING file in the source tree
* root for more information.
*
* THIS PACKAGE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR IMPLIED
* WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES
* OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
*/
|
