我实际上还没有在我的项目中使用该文件，只需将其复制到我的项目中即可。
我的头文件：
//
// Algorithm.h
// Cellular Radar
//
// Created by Idan Moshe on 15/09/13.
// Copyright (c) 2013 Netroads. All rights reserved.
//
#import <Foundation/Foundation.h>
#import <UIKit/UIKit.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#define MAX_DIM 3
#define N 1000000
#define rand1() (rand() / (double)RAND_MAX)
#define rand_pt(v) { v.x[0] = rand1(); v.x[1] = rand1(); v.x[2] = rand1(); }
struct kd_node_t {
int trapID;
double x[MAX_DIM];
struct kd_node_t *left, *right;
};
int visited;
struct kd_node_t allTraps[1000];
inline double theDistance(struct kd_node_t *a, struct kd_node_t *b, int dim);
static void swap(struct kd_node_t *x, struct kd_node_t *y);
struct kd_node_t* find_median(struct kd_node_t *start, struct kd_node_t *end, int idx);
struct kd_node_t* make_tree(struct kd_node_t *t, int len, int i, int dim);
void theNearest(struct kd_node_t *root, struct kd_node_t *nd, int i, int dim, struct kd_node_t **best, double *best_dist);
void getCloseTrap_KD_TREE(void);
@interface Algorithm : NSObject
@end
编辑：
我更改了对象“dist”和“nearest”的名称，出现以下问题：
体系结构 i386 的未定义符号：“_theDistance”，引用自：KDTree.o ld 中的 _theNearest：未找到体系结构 i386 的符号 clang：错误：链接器命令失败，退出代码为 1（使用 -v 查看调用）
编辑2：
//
// Algorithm.m
// Cellular Radar
//
// Created by Idan Moshe on 15/09/13.
// Copyright (c) 2013 Netroads. All rights reserved.
//
#import "Algorithm.h"
@implementation Algorithm
inline double theDistance(struct kd_node_t *a, struct kd_node_t *b, int dim)
{
double t, d = 0;
while (dim--) {
t = a->x[dim] - b->x[dim];
d += t * t;
}
return d;
}
static void swap(struct kd_node_t *x, struct kd_node_t *y)
{
double tmp[MAX_DIM];
memcpy(tmp, x->x, sizeof(tmp));
memcpy(x->x, y->x, sizeof(tmp));
memcpy(y->x, tmp, sizeof(tmp));
}
/* see quickselect method */
struct kd_node_t* find_median(struct kd_node_t *start, struct kd_node_t *end, int idx)
{
if (end <= start) return NULL;
if (end == start + 1)
return start;
struct kd_node_t *p, *store, *md = start + (end - start) / 2;
double pivot;
while (1) {
pivot = md->x[idx];
swap(md, end - 1);
for (store = p = start; p < end; p++) {
if (p->x[idx] < pivot) {
if (p != store)
swap(p, store);
store++;
}
}
swap(store, end - 1);
/* median has duplicate values */
if (store->x[idx] == md->x[idx])
return md;
if (store > md) end = store;
else start = store;
}
}
struct kd_node_t* make_tree(struct kd_node_t *t, int len, int i, int dim)
{
struct kd_node_t *n;
if (!len) return 0;
if ((n = find_median(t, t + len, i))) {
i = (i + 1) % dim;
n->left = make_tree(t, n - t, i, dim);
n->right = make_tree(n + 1, t + len - (n + 1), i, dim);
}
return n;
}
void theNearest(struct kd_node_t *root, struct kd_node_t *nd, int i, int dim,
struct kd_node_t **best, double *best_dist)
{
double d, dx, dx2;
if (!root) return;
d = theDistance(root, nd, dim);
dx = root->x[i] - nd->x[i];
dx2 = dx * dx;
visited ++;
if (!*best || d < *best_dist) {
*best_dist = d;
*best = root;
}
/* if chance of exact match is high */
if (!*best_dist) return;
if (++i >= dim) i = 0;
theNearest(dx > 0 ? root->left : root->right, nd, i, dim, best, best_dist);
if (dx2 >= *best_dist) return;
theNearest(dx > 0 ? root->right : root->left, nd, i, dim, best, best_dist);
}
void getCloseTrap_KD_TREE(void)
{
// int i;
struct kd_node_t wp[] =
{
{1, {2, 3}}, {1, {5, 4}}, {1, {9, 6}}, {1, {4, 7}}, {1, {8, 1}}, {1, {7, 2}}
};
struct kd_node_t searchPoint = {1, {9, 2}};
struct kd_node_t *root, *found;
// struct kd_node_t *million;
double best_dist;
root = make_tree(wp, sizeof(wp) / sizeof(wp[1]), 0, 2);
visited = 0;
found = 0;
theNearest(root, &searchPoint, 0, 2, &found, &best_dist);
printf(">> WP tree\nsearching for (%g, %g)\n"
"found (%g, %g) dist %g\nseen %d nodes\n\n",
searchPoint.x[0], searchPoint.x[1],
found->x[0], found->x[1], sqrt(best_dist), visited);
NSLog(@">> WP tree\nsearching for (%g, %g)\nfound (%g, %g) dist %g\nseen %d nodes\n\n", searchPoint.x[0], searchPoint.x[1], found->x[0], found->x[1], sqrt(best_dist), visited);
/*
million = calloc(N, sizeof(struct kd_node_t));
srand(time(0));
for (i = 0; i < N; i++) rand_pt(million[i]);
root = make_tree(million, N, 0, 3);
rand_pt(searchPoint);
visited = 0;
found = 0;
theNearest(root, &searchPoint, 0, 3, &found, &best_dist);
printf(">> Million tree\nsearching for (%g, %g, %g)\n"
"found (%g, %g, %g) dist %g\nseen %d nodes\n",
searchPoint.x[0], searchPoint.x[1], searchPoint.x[2],
found->x[0], found->x[1], found->x[2],
sqrt(best_dist), visited);
// search many random points in million tree to see average behavior.
// tree size vs avg nodes visited:
// 10 ~ 7
// 100 ~ 16.5
// 1000 ~ 25.5
// 10000 ~ 32.8
// 100000 ~ 38.3
// 1000000 ~ 42.6
// 10000000 ~ 46.7
int sum = 0, test_runs = 100000;
for (i = 0; i < test_runs; i++) {
found = 0;
visited = 0;
rand_pt(searchPoint);
theNearest(root, &searchPoint, 0, 3, &found, &best_dist);
sum += visited;
}
printf("\n>> Million tree\n"
"visited %d nodes for %d random findings (%f per lookup)\n",
sum, test_runs, sum/(double)test_runs);
// free(million);
*/
}
@end