kd_tree.h

Go to the documentation of this file.

#pragma once
 
 
#include <stddef.h>
#include <inttypes.h>
#include <stdbool.h>
 
#include <crater/vec.h>
 
typedef struct cr8r_kd_ft cr8r_kd_ft;
struct cr8r_kd_ft{
    cr8r_vec_ft super;
    uint64_t dim;
    size_t bounds_size;
    void (*split)(const cr8r_kd_ft *ft, const void *self, const void *root_pt, void *o1, void *o2);
    void (*update)(const cr8r_kd_ft *ft, void *self, const void *pt);
    double (*min_sqdist)(const cr8r_kd_ft *ft, const void *self, const void *pt);
    double (*sqdist)(const cr8r_kd_ft *ft, const void *a, const void *b);
};
 
typedef struct{
    int64_t bl[3];
    int64_t tr[3];
} cr8r_kdwin_s2i64;
 
typedef struct{
    cr8r_kd_ft ft;
    const void *pt;
    cr8r_vec *ents;
    uint64_t k;
    double max_sqdist;
} cr8r_kd_k_closest_state;
 
typedef cr8r_walk_decision (*cr8r_kdvisitor)(cr8r_kd_ft *ft, const void *win, void *ent, void *data);
 
bool cr8r_kdwin_init_s2i64(cr8r_kdwin_s2i64*, const int64_t bl[3], const int64_t tr[3]);
 
bool cr8r_kdwin_init_c3i64(cr8r_kdwin_s2i64*, const int64_t bl[3], const int64_t tr[3]);
 
bool cr8r_kdwin_bounding_i64x3(cr8r_kdwin_s2i64*, const cr8r_vec *ents, const cr8r_kd_ft *ft);
 
bool cr8r_kd_ify(cr8r_vec*, cr8r_kd_ft *ft, uint64_t a, uint64_t b);
 
void cr8r_kd_walk(cr8r_vec*, const cr8r_kd_ft *ft, const void *bounds, cr8r_kdvisitor visitor, void *data);
 
bool cr8r_kd_k_closest(cr8r_vec*, cr8r_kd_ft *ft, const void *bounds, const void *pt, uint64_t k, cr8r_vec *out);
 
int cr8r_default_cmp_kd_kcs_pt_dist(const cr8r_base_ft *_ft, const void *a, const void *b);
extern cr8r_kd_ft cr8r_kdft_s2i64;
extern cr8r_kd_ft cr8r_kdft_c3i64;