Fail case with some point clouds

[zeraphil]

Hi, I'm attempting to use this library to align some point clouds. On some clouds, for reasons I've yet to identify, I'm getting crashes in the build_tree_for_Range function, particularly in

` int c = -1;
float maxspread = 0.0;
int m;

  for (int i=0;i<dim;i++) {
    if ((parent == NULL) || (parent->cut_dim == i)) {
      spread_in_coordinate(i, l, u, node->box[i]);
    } else {
      node->box[i] = parent->box[i];
    }
    float spread = node->box[i].upper - node->box[i].lower;
    if (spread>maxspread) {
      maxspread = spread;
      c=i;
    }
  }`

where spread>maxspread never hits, and the array tries to index c=-1, which crashes.

[rana1991]

In my case, that was because the code my points required a higher accuracy. The code was rounding them off, and thus many points now had the same coordinates. In this case, the bounding box becomes just one point. To solve this, you can increase the accuracy to long double for all involved variables. Or, depending on your application, you can have this fix:

	for (int i = 0; i < dim; i++) {
		if ((parent == NULL) || (parent->cut_dim == i)) {
			spread_in_coordinate(i, l, u, node->box[i]);
			if (node->box[i].upper == node->box[i].lower)
				node->box[i].upper = node->box[i].upper;
		}
		else {
			node->box[i] = parent->box[i];
		}
		float spread = node->box[i].upper - node->box[i].lower;//also known as depth
		if (spread > maxspread) {
			maxspread = spread;
			c = i;
		}
	}

	if (c != -1) {

		//
		// now, c is the identity of which coordinate has the greatest spread
		//

		if (false) {
			m = (l + u) / 2;
			select_on_coordinate(c, m, l, u);
		}
		else {
			float sum;
			float average;

			if (true) {
				sum = 0.0;
				for (int k = l; k <= u; k++) {
					if (c < 0 || c>2)
						c = c;
					sum += the_data[ind[k]][c];
				}
				average = sum / static_cast<float> (u - l + 1); //median?
			}
			else {
				// average of top and bottom nodes.
				average = (node->box[c].upper + node->box[c].lower)*0.5F;
			}
			m = select_on_coordinate_value(c, average, l, u); //rerranges indices inside
		}


		// move the indices around to cut on dim 'c'.
		node->cut_dim = c;
		node->l = l;
		node->u = u;

		node->left = build_tree_for_range(l, m, node);

		node->right = build_tree_for_range(m + 1, u, node);

		if (node->right == NULL) {
			for (int i = 0; i < dim; i++)
				node->box[i] = node->left->box[i];
			node->cut_val = node->left->box[c].upper;
			node->cut_val_left = node->cut_val_right = node->cut_val;
		}
		else if (node->left == NULL) {
			for (int i = 0; i < dim; i++)
				node->box[i] = node->right->box[i];
			node->cut_val = node->right->box[c].upper;
			node->cut_val_left = node->cut_val_right = node->cut_val;
		}
		else {
			node->cut_val_right = node->right->box[c].lower;
			node->cut_val_left = node->left->box[c].upper;
			node->cut_val = (node->cut_val_left + node->cut_val_right) / 2.0F;
			//
			// now recompute true bounding box as union of subtree boxes.
			// This is now faster having built the tree, being logarithmic in
			// N, not linear as would be from naive method.
			//
			for (int i = 0; i < dim; i++) {
				node->box[i].upper = std::max(node->left->box[i].upper,
					node->right->box[i].upper);

				node->box[i].lower = std::min(node->left->box[i].lower,
					node->right->box[i].lower);
			}
		}
	}
	else {
		//create terminal node
		//possibly repeated points: bounding box --> one point
		//maxspread = 0
		node->cut_dim = 0;
		node->cut_val = 0.0;
		node->l = l;
		node->u = u;
		node->left = node->right = NULL;
	}
}
return(node);

}

[zeraphil]

Thanks, I found this was exactly the reason for the error. I had rounding causing many points to have the same coordinates (origin) and the stack overflow was due to the ties. I didn't implement this fix, instead ensured that my data was not extremely flat (that was a fault on my end), but thanks for providing this, I'll give it a go.