vpsearch 0.2.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
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

#include <assert.h>
#include "libimagequant.h"
#include "pam.h"
#include "vp.h"
#include <stdio.h>
#include <math.h>

int checks = 0;

f_pixel rand_color() {
    return (f_pixel){
        .r = ((double)rand())/(double)RAND_MAX,
        .g = ((double)rand())/(double)RAND_MAX,
        .b = ((double)rand())/(double)RAND_MAX,
        .a = 1.f,
    };
}

static vp_distance compare(const vp_item *a, const vp_item *b) {
    // checks++;
    return sqrtf(colordifference(*((f_pixel*)a), *((f_pixel*)b)));
}

int find_slow(const f_pixel px, const colormap_item *pal, int colors) {
    double diff = colordifference(px, pal[0].acolor);
    int best = 0;
    for(int i=1; i < colors; i++) {
        const double dt = colordifference(px, pal[i].acolor);
        if (dt < diff) {
            diff = dt;
            best = i;
        }
    }
    return best;
}

int find_slow2(const f_pixel px, const colormap_item *pal, int colors) {
    double diff = 1e10;
    int best = -1;
    for(int i = colors-1; i >= 0; i--) {
        const double dt = colordifference(px, pal[i].acolor);
        if (dt < diff) {
            diff = dt;
            best = i;
        }
    }
    return best;
}

int main(void) {
    srand(234);
    const int colors = 256;
    colormap_item pal[colors];
    for(int i=0; i < colors; i++) {
        pal[i].acolor = rand_color();
    }
    void *vpitems[colors];
    for(int i=0; i < colors; i++) {
        vpitems[i] = &pal[i].acolor;
    }

    int bad=0, done=0;
    float badness = 0;
    const bool verbose = false;

    for(int j=0; j < 100; j++) {
        vp_handle *vp = vp_init(vpitems, colors, compare);
        for(int i = 0; i < 12800; i++) {
            checks+=2;
            const f_pixel s = rand_color();
            int slow = vp_find_nearest(vp, &s);//find_slow(s, pal, colors);
            int fast = vp_find_nearest(vp, &s);//nearest_search(n, s, 0, 1.0, NULL);
            if (slow != fast) {
                const float diff = colordifference(pal[slow].acolor, pal[0].acolor);
                if (diff > 0) {
                    if (verbose) {
                        for(int i=0; i < colors; i++) {
                            const f_pixel px = pal[i].acolor;
                            fprintf(stderr, "Pal %d = %f %f %f %f (diff %f)\n", i, px.r, px.g, px.b, px.a, colordifference(s, px));
                        }
                        fprintf(stderr, "Searching %f %f %f %f\n", s.r, s.g, s.b, s.a);
                        printf("C %d: sl!%d = vp!%d %f\n", i, slow, fast, diff);
                    }

                    bad++;
                    badness += colordifference(pal[slow].acolor, pal[fast].acolor);
                }
            }
            done++;
        }
        vp_free(vp);
    }
    printf("%d checks, %d %d%% bad, %.1f off\n", checks, bad, bad*100/done, badness);

    return 0;
}