vpsearch 0.1.0

Vantage Point Tree search algorithm for fast nearest neighbour search in multi-dimensional metric spaces.
Documentation 
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

# VP-tree nearest neighbor search

A relatively simple and readable C (C99) implementation of Vantage Point tree search algorithm.

The VP tree algorithm doesn't need to know coordinates of items, only distances between them. It can efficiently search multi-dimensional spaces and abstract things as long as you can define similarity between them (e.g. points, colors, and even images).

Please see `vp.c` for details.

```C
#include "vp.h"
#include <math.h>
#include <stdio.h>

typedef struct point {float x,y;} point;

float get_distance(const void *a, const void *b) {
    float dx = ((point *)a)->x - ((point *)b)->x;
    float dy = ((point *)a)->y - ((point *)b)->y;

    return sqrt(dx*dx + dy*dy); // sqrt is required
}

int main(void) {

    // The library operates on pointers to elements
    point *points[] = {&(point){2,3}, &(point){0,1}, &(point){4,5}};

    vp_handle *vp = vp_init((void**)points, 3, get_distance);

    int index = vp_find_nearest(vp, &(point){1,2});

    printf("The nearest point is at (%f,%f)\n", points[index]->x, points[index]->y);

    vp_free(vp);
}
```