1 /******************************************************************************
2 * Copyright (c) 2015, Hobu Inc. (info@hobu.co)
3 *
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following
8 * conditions are met:
9 *
10 * * Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * * Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in
14 * the documentation and/or other materials provided
15 * with the distribution.
16 * * Neither the name of Hobu, Inc. nor the names of its contributors
17 * may be used to endorse or promote products derived from this
18 * software without specific prior written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
23 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
24 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
25 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
26 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
27 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
28 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
29 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
30 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY
31 * OF SUCH DAMAGE.
32 ****************************************************************************/
33
34 #include <pdal/pdal_test_main.hpp>
35
36 #include <pdal/KDIndex.hpp>
37
38 using namespace pdal;
39
TEST(KDIndex,neighbors2D)40 TEST(KDIndex, neighbors2D)
41 {
42 PointTable table;
43 PointLayoutPtr layout = table.layout();
44 PointView view(table);
45
46 layout->registerDim(Dimension::Id::X);
47 layout->registerDim(Dimension::Id::Y);
48
49 view.setField(Dimension::Id::X, 0, 0);
50 view.setField(Dimension::Id::Y, 0, 0);
51
52 view.setField(Dimension::Id::X, 1, 1);
53 view.setField(Dimension::Id::Y, 1, 1);
54
55 view.setField(Dimension::Id::X, 2, 3);
56 view.setField(Dimension::Id::Y, 2, 3);
57
58 view.setField(Dimension::Id::X, 3, 6);
59 view.setField(Dimension::Id::Y, 3, 6);
60
61 view.setField(Dimension::Id::X, 4, 10);
62 view.setField(Dimension::Id::Y, 4, 10);
63
64 KD2Index index(view);
65 index.build();
66
67 EXPECT_EQ(index.neighbor(0, 0), 0u);
68 EXPECT_EQ(index.neighbor(1.1, 1.1), 1u);
69 EXPECT_EQ(index.neighbor(3.3, 3.3), 2u);
70 EXPECT_EQ(index.neighbor(6.1, 6.1), 3u);
71 EXPECT_EQ(index.neighbor(15, 15), 4u);
72
73 PointIdList ids;
74 ids = index.neighbors(0, 0, 5);
75 EXPECT_EQ(ids.size(), 5u);
76 EXPECT_EQ(ids[0], 0u);
77 EXPECT_EQ(ids[1], 1u);
78 EXPECT_EQ(ids[2], 2u);
79 EXPECT_EQ(ids[3], 3u);
80 EXPECT_EQ(ids[4], 4u);
81
82 ids = index.neighbors(0, 0, 25);
83 EXPECT_EQ(ids.size(), 5u);
84 EXPECT_EQ(ids[0], 0u);
85 EXPECT_EQ(ids[1], 1u);
86 EXPECT_EQ(ids[2], 2u);
87 EXPECT_EQ(ids[3], 3u);
88 EXPECT_EQ(ids[4], 4u);
89
90 ids = index.neighbors(3.1, 3.1, 5);
91 EXPECT_EQ(ids.size(), 5u);
92 EXPECT_EQ(ids[0], 2u);
93 EXPECT_EQ(ids[1], 1u);
94 EXPECT_EQ(ids[2], 3u);
95 EXPECT_EQ(ids[3], 0u);
96 EXPECT_EQ(ids[4], 4u);
97
98 // Search by PointId
99 ids = index.neighbors(0, 5);
100 EXPECT_EQ(ids.size(), 5u);
101 EXPECT_EQ(ids[0], 0u);
102 EXPECT_EQ(ids[1], 1u);
103 EXPECT_EQ(ids[2], 2u);
104 EXPECT_EQ(ids[3], 3u);
105 EXPECT_EQ(ids[4], 4u);
106
107 // Search by PointRef
108 PointRef point = view.point(0);
109 ids = index.neighbors(point, 5);
110 EXPECT_EQ(ids.size(), 5u);
111 EXPECT_EQ(ids[0], 0u);
112 EXPECT_EQ(ids[1], 1u);
113 EXPECT_EQ(ids[2], 2u);
114 EXPECT_EQ(ids[3], 3u);
115 EXPECT_EQ(ids[4], 4u);
116 }
117
TEST(KDIndex,neighbors3D)118 TEST(KDIndex, neighbors3D)
119 {
120 PointTable table;
121 PointLayoutPtr layout = table.layout();
122 PointView view(table);
123
124 layout->registerDim(Dimension::Id::X);
125 layout->registerDim(Dimension::Id::Y);
126 layout->registerDim(Dimension::Id::Z);
127
128 view.setField(Dimension::Id::X, 0, 0);
129 view.setField(Dimension::Id::Y, 0, 0);
130 view.setField(Dimension::Id::Z, 0, 0);
131
132 view.setField(Dimension::Id::X, 1, 1);
133 view.setField(Dimension::Id::Y, 1, 1);
134 view.setField(Dimension::Id::Z, 1, 1);
135
136 view.setField(Dimension::Id::X, 2, 3);
137 view.setField(Dimension::Id::Y, 2, 3);
138 view.setField(Dimension::Id::Z, 2, 3);
139
140 view.setField(Dimension::Id::X, 3, 6);
141 view.setField(Dimension::Id::Y, 3, 6);
142 view.setField(Dimension::Id::Z, 3, 6);
143
144 view.setField(Dimension::Id::X, 4, 10);
145 view.setField(Dimension::Id::Y, 4, 10);
146 view.setField(Dimension::Id::Z, 4, 10);
147
148 KD3Index index(view);
149 index.build();
150
151 EXPECT_EQ(index.neighbor(0, 0, 0), 0u);
152 EXPECT_EQ(index.neighbor(1.1, 1.1, 1.1), 1u);
153 EXPECT_EQ(index.neighbor(3.3, 3.3, 3.3), 2u);
154 EXPECT_EQ(index.neighbor(6.1, 6.1, 6.1), 3u);
155 EXPECT_EQ(index.neighbor(15, 15, 15), 4u);
156
157 PointIdList ids;
158 ids = index.neighbors(0, 0, 0, 5);
159 EXPECT_EQ(ids.size(), 5u);
160 EXPECT_EQ(ids[0], 0u);
161 EXPECT_EQ(ids[1], 1u);
162 EXPECT_EQ(ids[2], 2u);
163 EXPECT_EQ(ids[3], 3u);
164 EXPECT_EQ(ids[4], 4u);
165
166 ids = index.neighbors(0, 0, 0, 25);
167 EXPECT_EQ(ids.size(), 5u);
168 EXPECT_EQ(ids[0], 0u);
169 EXPECT_EQ(ids[1], 1u);
170 EXPECT_EQ(ids[2], 2u);
171 EXPECT_EQ(ids[3], 3u);
172 EXPECT_EQ(ids[4], 4u);
173
174 ids = index.neighbors(3.1, 3.1, 3.1, 5);
175 EXPECT_EQ(ids.size(), 5u);
176 EXPECT_EQ(ids[0], 2u);
177 EXPECT_EQ(ids[1], 1u);
178 EXPECT_EQ(ids[2], 3u);
179 EXPECT_EQ(ids[3], 0u);
180 EXPECT_EQ(ids[4], 4u);
181
182 // Search by PointId
183 ids = index.neighbors(0, 5);
184 EXPECT_EQ(ids.size(), 5u);
185 EXPECT_EQ(ids[0], 0u);
186 EXPECT_EQ(ids[1], 1u);
187 EXPECT_EQ(ids[2], 2u);
188 EXPECT_EQ(ids[3], 3u);
189 EXPECT_EQ(ids[4], 4u);
190
191 // Search by PointRef
192 PointRef point = view.point(0);
193 ids = index.neighbors(point, 5);
194 EXPECT_EQ(ids.size(), 5u);
195 EXPECT_EQ(ids[0], 0u);
196 EXPECT_EQ(ids[1], 1u);
197 EXPECT_EQ(ids[2], 2u);
198 EXPECT_EQ(ids[3], 3u);
199 EXPECT_EQ(ids[4], 4u);
200
201 // Search with stride
202 ids = index.neighbors(0, 0, 0, 2, 1);
203 EXPECT_EQ(ids.size(), 2u);
204 EXPECT_EQ(ids[0], 0u);
205 EXPECT_EQ(ids[1], 1u);
206
207 ids = index.neighbors(0, 0, 0, 2, 2);
208 EXPECT_EQ(ids.size(), 2u);
209 EXPECT_EQ(ids[0], 0u);
210 EXPECT_EQ(ids[1], 2u);
211
212 ids = index.neighbors(0, 0, 0, 2, 3);
213 EXPECT_EQ(ids.size(), 2u);
214 EXPECT_EQ(ids[0], 0u);
215 EXPECT_EQ(ids[1], 3u);
216
217 ids = index.neighbors(0, 0, 0, 3, 2);
218 EXPECT_EQ(ids.size(), 3u);
219 EXPECT_EQ(ids[0], 0u);
220 EXPECT_EQ(ids[1], 2u);
221 EXPECT_EQ(ids[2], 4u);
222 }
223
TEST(KDIndex,neighbordims)224 TEST(KDIndex, neighbordims)
225 {
226 PointTable table;
227 PointLayoutPtr layout = table.layout();
228 PointView view(table);
229
230 layout->registerDim(Dimension::Id::X);
231 layout->registerDim(Dimension::Id::Z);
232
233 view.setField(Dimension::Id::X, 0, 0);
234 view.setField(Dimension::Id::Z, 0, 0);
235
236 view.setField(Dimension::Id::X, 1, 1);
237 view.setField(Dimension::Id::Z, 1, 1);
238
239 EXPECT_THROW(KD2Index index(view), pdal_error);
240
241 PointTable table2;
242 PointLayoutPtr layout2 = table.layout();
243 PointView view2(table2);
244
245 layout->registerDim(Dimension::Id::X);
246 layout->registerDim(Dimension::Id::Y);
247
248 view.setField(Dimension::Id::X, 0, 0);
249 view.setField(Dimension::Id::Y, 0, 0);
250
251 view.setField(Dimension::Id::X, 1, 1);
252 view.setField(Dimension::Id::Y, 1, 1);
253
254 EXPECT_THROW(KD3Index index(view2), pdal_error);
255 }
256
TEST(KDIndex,radius2D)257 TEST(KDIndex, radius2D)
258 {
259 PointTable table;
260 PointLayoutPtr layout = table.layout();
261 PointView view(table);
262
263 layout->registerDim(Dimension::Id::X);
264 layout->registerDim(Dimension::Id::Y);
265
266 view.setField(Dimension::Id::X, 0, 0);
267 view.setField(Dimension::Id::Y, 0, 0);
268
269 view.setField(Dimension::Id::X, 1, 1);
270 view.setField(Dimension::Id::Y, 1, 1);
271
272 view.setField(Dimension::Id::X, 2, 3);
273 view.setField(Dimension::Id::Y, 2, 3);
274
275 view.setField(Dimension::Id::X, 3, 6);
276 view.setField(Dimension::Id::Y, 3, 6);
277
278 view.setField(Dimension::Id::X, 4, 10);
279 view.setField(Dimension::Id::Y, 4, 10);
280
281 KD2Index index(view);
282 index.build();
283
284 PointIdList ids;
285 ids = index.radius(0, 0, 4.25);
286
287 EXPECT_EQ(ids.size(), 3u);
288 EXPECT_EQ(ids[0], 0u);
289 EXPECT_EQ(ids[1], 1u);
290 EXPECT_EQ(ids[2], 2u);
291
292 ids = index.radius(3.1, 3.1, 10);
293 EXPECT_EQ(ids.size(), 5u);
294 EXPECT_EQ(ids[0], 2u);
295 EXPECT_EQ(ids[1], 1u);
296 EXPECT_EQ(ids[2], 3u);
297 EXPECT_EQ(ids[3], 0u);
298 EXPECT_EQ(ids[4], 4u);
299
300 // Search by PointId
301 ids = index.radius(0, 4.25);
302 EXPECT_EQ(ids.size(), 3u);
303 EXPECT_EQ(ids[0], 0u);
304 EXPECT_EQ(ids[1], 1u);
305 EXPECT_EQ(ids[2], 2u);
306
307 // Search by PointRef
308 PointRef point = view.point(0);
309 ids = index.radius(point, 4.25);
310 EXPECT_EQ(ids.size(), 3u);
311 EXPECT_EQ(ids[0], 0u);
312 EXPECT_EQ(ids[1], 1u);
313 EXPECT_EQ(ids[2], 2u);
314 }
315
TEST(KDIndex,radius3D)316 TEST(KDIndex, radius3D)
317 {
318 PointTable table;
319 PointLayoutPtr layout = table.layout();
320 PointView view(table);
321
322 layout->registerDim(Dimension::Id::X);
323 layout->registerDim(Dimension::Id::Y);
324 layout->registerDim(Dimension::Id::Z);
325
326 view.setField(Dimension::Id::X, 0, 0);
327 view.setField(Dimension::Id::Y, 0, 0);
328 view.setField(Dimension::Id::Z, 0, 0);
329
330 view.setField(Dimension::Id::X, 1, 1);
331 view.setField(Dimension::Id::Y, 1, 1);
332 view.setField(Dimension::Id::Z, 1, 1);
333
334 view.setField(Dimension::Id::X, 2, 3);
335 view.setField(Dimension::Id::Y, 2, 3);
336 view.setField(Dimension::Id::Z, 2, 3);
337
338 view.setField(Dimension::Id::X, 3, 6);
339 view.setField(Dimension::Id::Y, 3, 6);
340 view.setField(Dimension::Id::Z, 3, 6);
341
342 view.setField(Dimension::Id::X, 4, 10);
343 view.setField(Dimension::Id::Y, 4, 10);
344 view.setField(Dimension::Id::Z, 4, 10);
345
346 KD3Index index(view);
347 index.build();
348
349 PointIdList ids;
350 ids = index.radius(0, 0, 0, 5.2);
351
352 EXPECT_EQ(ids.size(), 3u);
353 EXPECT_EQ(ids[0], 0u);
354 EXPECT_EQ(ids[1], 1u);
355 EXPECT_EQ(ids[2], 2u);
356
357 ids = index.radius(3.1, 3.1, 3.1, 12.2);
358 EXPECT_EQ(ids.size(), 5u);
359 EXPECT_EQ(ids[0], 2u);
360 EXPECT_EQ(ids[1], 1u);
361 EXPECT_EQ(ids[2], 3u);
362 EXPECT_EQ(ids[3], 0u);
363 EXPECT_EQ(ids[4], 4u);
364
365 // Search by PointId
366 ids = index.radius(0, 5.2);
367 EXPECT_EQ(ids.size(), 3u);
368 EXPECT_EQ(ids[0], 0u);
369 EXPECT_EQ(ids[1], 1u);
370 EXPECT_EQ(ids[2], 2u);
371
372 // Search by PointRef
373 PointRef point = view.point(0);
374 ids = index.radius(point, 5.2);
375 EXPECT_EQ(ids.size(), 3u);
376 EXPECT_EQ(ids[0], 0u);
377 EXPECT_EQ(ids[1], 1u);
378 EXPECT_EQ(ids[2], 2u);
379 }
380
381