22static double dist(
int dim,
double *x,
double *y){
25 for (k = 0; k <
dim; k++) d += (x[k] - y[k])*(x[k]-y[k]);
34 for (i = 0; i < k; i++){
43 for (i = 0; i < k; i++){
57void
furtherest_point(
int k,
int dim,
double *wgt,
double *pts,
double *
center,
double width,
int max_level,
double *dist_max,
double **argmax){
85 for (
int i = 0; i < k; i++) wmax =
MAX(wgt[i], wmax);
93 if (!(*argmax)) *argmax =
gv_calloc(
dim,
sizeof(
double));
94 memcpy(*argmax,
center,
sizeof(
double)*
dim);
96 qt_list_t candidates = {0};
97 qt_list_t candidates2 = {0};
98 qt_list_append(&candidates, qt);
103 while (level++ < max_level){
105 fprintf(stderr,
"level=%d=================\n", level);
107 qt_list_clear(&candidates2);
108 for (
size_t i = 0; i < qt_list_size(&candidates); i++){
111 qt = qt_list_get(&candidates, i);
115 fprintf(stderr,
"candidate %" PRISIZE_T " at {", i);
116 for (j = 0; j <
dim; j++) fprintf(stderr,
"%f, ", qt->
center[j]);
123 for (ii = 0; ii < 1<<
dim; ii++) {
130 fprintf(stderr,
"new distmax=%f, pt={", *dist_max);
131 for (j = 0; j <
dim; j++) fprintf(stderr,
"%f, ", qt->
qts[ii]->
center[j]);
132 fprintf(stderr,
"}\n");
134 memcpy(*argmax, qt->
qts[ii]->
center,
sizeof(
double)*
dim);
139 qt_list_append(&candidates2, qt->
qts[ii]);
144 SWAP(&candidates, &candidates2);
150 qt_list_free(&candidates);
151 qt_list_free(&candidates2);
155 double *dist_max,
double **argmax){
187 for (
int i = 0; i < k; i++) wmax =
MAX(wgt[i], wmax);
194 if (!(*argmax)) *argmax =
gv_calloc(
dim,
sizeof(
double));
195 memcpy(*argmax, average,
sizeof(
double)*
dim);
197 qt_list_t candidates = {0};
198 qt_list_t candidates2 = {0};
199 qt_list_append(&candidates, qt);
204 while (level++ < max_level){
206 fprintf(stderr,
"level=%d=================\n", level);
208 qt_list_clear(&candidates2);
209 for (
size_t i = 0; i < qt_list_size(&candidates); i++){
210 qt = qt_list_get(&candidates, i);
213 fprintf(stderr,
"candidate %" PRISIZE_T " at {", i);
214 for (j = 0; j <
dim; j++) fprintf(stderr,
"%f, ", qt->
center[j]);
219 if (qt->
n == 1 ||
distance + wmax*2*sqrt(((
double)
dim))*qt->
width < *dist_max)
continue;
222 if (!(qt->
qts))
continue;
224 for (ii = 0; ii < 1<<
dim; ii++) {
225 if (!(qt->
qts[ii]))
continue;
231 fprintf(stderr,
"new distmax=%f, pt={", *dist_max);
232 for (j = 0; j <
dim; j++) fprintf(stderr,
"%f, ", qt->
qts[ii]->
average[j]);
233 fprintf(stderr,
"}\n");
240 qt_list_append(&candidates2, qt->
qts[ii]);
245 SWAP(&candidates, &candidates2);
249 qt_list_free(&candidates);
250 qt_list_free(&candidates2);
QuadTree QuadTree_new_in_quadrant(int dim, double *center, double width, int max_level, int i)
QuadTree QuadTree_new(int dim, double *center, double width, int max_level)
void QuadTree_delete(QuadTree q)
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
void furtherest_point_in_list(int k, int dim, double *wgt, double *pts, QuadTree qt, int max_level, double *dist_max, double **argmax)
static double dist(int dim, double *x, double *y)
static double distance_to_group(int k, int dim, double *wgt, double *pts, double *center)
void furtherest_point(int k, int dim, double *wgt, double *pts, double *center, double width, int max_level, double *dist_max, double **argmax)
double distance(double *x, int dim, int i, int j)
Arithmetic helper functions.
#define DEFINE_LIST(name, type)
static point center(point vertex[], size_t n)