Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- void
- buildTreeR(TreeNode **node, size_t depth, std::vector<PointIndexPair> &points)
- {
- // splitting into x, y, z dimension
- if (points.size() != 0) {
- size_t dim = depth % 3;
- // sort the coordinates to figure out median of dimension x, y or z
- if (dim == 0) {
- std::sort(points.begin(), points.end(), compDim0);
- } else if (dim == 1) {
- std::sort(points.begin(), points.end(), compDim1);
- } else {
- std::sort(points.begin(), points.end(), compDim2);
- }
- // median of coordinates = root
- size_t center = points.size() / 2;
- *node = new TreeNode(0, 0, points[center].index);
- if (points.size() > 1) {
- // left child of median/root
- std::vector<PointIndexPair> points1(points.begin(), points.begin() + center);
- // build left subtree
- buildTreeR(&(*node)->child0, depth + 1, points1);
- // right child of median/root
- std::vector<PointIndexPair> points2(points.begin() + center + 1, points.end());
- // build right subtree
- buildTreeR(&(*node)->child1, depth + 1, points2);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement