1 |
/* |
2 |
========================================================================= |
3 |
k-nearest neighbour lookup routines for out-of-core octree data structure |
4 |
|
5 |
Roland Schregle (roland.schregle@{hslu.ch, gmail.com}) |
6 |
(c) Lucerne University of Applied Sciences and Arts, |
7 |
supported by the Swiss National Science Foundation (SNSF, #147053) |
8 |
========================================================================= |
9 |
|
10 |
$Id: oocnn.h,v 1.14 2015/11/13 18:05:15 taschreg Exp taschreg $ |
11 |
*/ |
12 |
|
13 |
|
14 |
|
15 |
#ifndef OOC_SEARCH_H |
16 |
#define OOC_SEARCH_H |
17 |
|
18 |
#include "oococt.h" |
19 |
|
20 |
/* Priority queue node for octree lookups */ |
21 |
typedef struct { |
22 |
float dist2; /* Record's *SQUARED* distance to query point */ |
23 |
unsigned idx; /* Record's index in queue buffer */ |
24 |
} OOC_SearchQueueNode; |
25 |
|
26 |
|
27 |
/* Priority queue for octree lookups. Note that we explicitly store the |
28 |
* NN candidates in a local in-core buffer nnRec for later retrieval |
29 |
* without incurring additional disk I/O. */ |
30 |
typedef struct { |
31 |
OOC_SearchQueueNode *node; |
32 |
unsigned len, tail, recSize; |
33 |
void *nnRec; |
34 |
} OOC_SearchQueue; |
35 |
|
36 |
|
37 |
/* Filter for k-NN search; records are accepted for which func(rec, data) |
38 |
* returns nonzero */ |
39 |
typedef struct { |
40 |
int (*func)(void *rec, void *data); |
41 |
void *data; |
42 |
} OOC_SearchFilter; |
43 |
|
44 |
|
45 |
|
46 |
float OOC_FindNearest (OOC_Octree *oct, OOC_Node *node, |
47 |
OOC_DataIdx dataIdx, const FVECT org, float size, |
48 |
const FVECT key, const OOC_SearchFilter *filter, |
49 |
OOC_SearchQueue *queue, float maxDist2); |
50 |
/* Find k nearest neighbours (where k = queue -> len) within a maximum |
51 |
* SQUARED distance of maxDist2 around key. Returns the corresponding |
52 |
* data records with their SQUARED distances in the search queue |
53 |
* (queue -> node [0] .. queue -> node [queue -> tail - 1]), with the |
54 |
* furthest neighbour at the queue head and queue->tail <= queue->len. |
55 |
* |
56 |
* This is a recursive function requiring params for the current node: |
57 |
* DataIdx is the data offset for records in the current node, which is |
58 |
* necessary for implied addressing into the leaf file. Org and size are |
59 |
* the origin and size of the current node's bounding box. |
60 |
* |
61 |
* An optional filter may be specified; if filter != NULL, filter->func() |
62 |
* is called for each potential nearest neighbour along with additional |
63 |
* data provided by the caller; see OOC_SearchFilter typedef above. |
64 |
* |
65 |
* Return value is the SQUARED distance to furthest neighbour on success, |
66 |
* else -1 on failure. */ |
67 |
|
68 |
|
69 |
float OOC_Find1Nearest (OOC_Octree *oct, OOC_Node *node, |
70 |
OOC_DataIdx dataIdx, const FVECT org, float size, |
71 |
const FVECT key, const OOC_SearchFilter *filter, |
72 |
void *nnRec, float maxDist2); |
73 |
/* Find single nearest neighbour within max SQUARED distance maxDist2 |
74 |
* around key and copy corresponding record in nnRec. This is an |
75 |
* optimised version of OOC_FindNearest() without a search queue */ |
76 |
|
77 |
|
78 |
int OOC_InitNearest (OOC_SearchQueue *squeue, |
79 |
unsigned len, unsigned recSize); |
80 |
/* Initialise NN search queue of length len and local buffa for records |
81 |
* of size recSize; precondition to calling OOC_FindNearest() */ |
82 |
|
83 |
|
84 |
void *OOC_GetNearest (const OOC_SearchQueue *queue, unsigned idx); |
85 |
/* Return pointer to record at pos idx in search queue after calling |
86 |
* OOC_FindNearest() */ |
87 |
#endif |