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