55 if(
x -
hw > point[0])
return false;
56 if(
x +
hw < point[0])
return false;
57 if(
y -
hh > point[1])
return false;
58 if(
y +
hh < point[1])
return false;
105 double* max_Y =
new double[
QT_NO_DIMS];
for(
int d = 0; d <
QT_NO_DIMS; d++) max_Y[d] = -DBL_MAX;
106 for(
int n = 0; n < N; n++) {
108 mean_Y[d] += inp_data[n * QT_NO_DIMS + d];
109 if(inp_data[n * QT_NO_DIMS + d] < min_Y[d]) min_Y[d] = inp_data[n * QT_NO_DIMS + d];
110 if(inp_data[n * QT_NO_DIMS + d] > max_Y[d]) max_Y[d] = inp_data[n * QT_NO_DIMS + d];
113 for(
int d = 0; d <
QT_NO_DIMS; d++) mean_Y[d] /= (
double) N;
116 init(NULL, inp_data, mean_Y[0], mean_Y[1], std::max(max_Y[0] - mean_Y[0], mean_Y[0] - min_Y[0]) + 1e-5,
117 std::max(max_Y[1] - mean_Y[1], mean_Y[1] - min_Y[1]) + 1e-5);
119 delete[] mean_Y;
delete[] max_Y;
delete[] min_Y;
123 QuadTree(
double* inp_data,
double inp_x,
double inp_y,
double inp_hw,
double inp_hh) :
127 init(NULL, inp_data, inp_x, inp_y, inp_hw, inp_hh);
131 QuadTree(
double* inp_data,
int N,
double inp_x,
double inp_y,
double inp_hw,
double inp_hh) :
135 init(NULL, inp_data, inp_x, inp_y, inp_hw, inp_hh);
140 QuadTree(
QuadTree* inp_parent,
double* inp_data,
int N,
double inp_x,
double inp_y,
double inp_hw,
double inp_hh) :
144 init(inp_parent, inp_data, inp_x, inp_y, inp_hw, inp_hh);
149 QuadTree(
QuadTree* inp_parent,
double* inp_data,
double inp_x,
double inp_y,
double inp_hw,
double inp_hh) :
153 init(inp_parent, inp_data, inp_x, inp_y, inp_hw, inp_hh);
188 double mult2 = 1.0 / (double)
cum_size;
200 bool any_duplicate =
false;
201 for(
int n = 0; n <
size; n++) {
202 bool duplicate =
true;
204 if(point[d] !=
data[
index[n] * QT_NO_DIMS + d]) { duplicate =
false;
break; }
206 any_duplicate = any_duplicate | duplicate;
208 if(any_duplicate)
return true;
233 for(
int i = 0; i <
size; i++) {
234 bool success =
false;
250 for(
int n = 0; n <
size; n++) {
264 for(
int n = 0; n <
size; n++) {
270 int rem_index =
index[n];
272 index[size - 1] = -1;
283 if(node->
getParent() == NULL) done =
true;
332 double Q = 1.0 / (1.0 + D);
353 for(
int n = 0; n < N; n++) {
355 for(
int i = row_P[n]; i < row_P[n + 1]; i++) {
363 D = val_P[i] / (1.0 + D);
366 for(
int d = 0; d <
QT_NO_DIMS; d++) pos_f[ind1 + d] += D *
buff[d];
375 printf(
"Empty node\n");
380 printf(
"Leaf node; data = [");
381 for(
int i = 0; i <
size; i++) {
383 for(
int d = 0; d <
QT_NO_DIMS; d++) printf(
"%f, ", point[d]);
384 printf(
" (index = %d)",
index[i]);
385 if(i < size - 1) printf(
"\n");
390 printf(
"Intersection node with center-of-mass = [");
392 printf(
"]; children are:\n");
405 void init(
QuadTree* inp_parent,
double* inp_data,
double inp_x,
double inp_y,
double inp_hw,
double inp_hh)
426 for(
int i = 0; i < N; i++)
insert(i);
434 for(
int i = 0; i <
size; i++) indices[loc + i] =
index[i];
void getAllIndices(int *indices)
bool containsPoint(double point[])
double center_of_mass[QT_NO_DIMS]
void setData(double *inp_data)
static const int QT_NODE_CAPACITY
void computeEdgeForces(int *row_P, int *col_P, double *val_P, int N, double *pos_f)
QuadTree(double *inp_data, int N, double inp_x, double inp_y, double inp_hw, double inp_hh)
QuadTree(QuadTree *inp_parent, double *inp_data, double inp_x, double inp_y, double inp_hw, double inp_hh)
int index[QT_NODE_CAPACITY]
static const int QT_NO_DIMS
bool insert(int new_index)
int getAllIndices(int *indices, int loc)
QuadTree(QuadTree *inp_parent, double *inp_data, int N, double inp_x, double inp_y, double inp_hw, double inp_hh)
QuadTree(double *inp_data, int N)
QuadTree & operator=(const QuadTree &)
void init(QuadTree *inp_parent, double *inp_data, double inp_x, double inp_y, double inp_hw, double inp_hh)
QuadTree(double *inp_data, double inp_x, double inp_y, double inp_hw, double inp_hh)
void computeNonEdgeForces(int point_index, double theta, double neg_f[], double *sum_Q)