用C++和PCL库构建KD树，并且使所有叶子内点的数量大于100

由于KD树的构建需要考虑数据的维度和切分方式，因此具体步骤如下：

1. 定义节点结构体

首先，我们先定义一个节点的结构体，包括了节点的位置、分割维度和左右子节点。为了便于查找，我们还可以添加一个标识节点是否为叶子节点的字段。

typedef struct node
{
    double pos[3];
    int splitDim;
    bool isLeaf;
    struct node *left, *right;
}Node;

2. 选择切分维度和位置

对于每个节点，我们需要选择一个切分维度和位置。一般采用以下两种方式之一：

- 均匀采样

对于数据点中的所有维度，计算出其最大、最小值的范围，并对每个维度均匀采样若干个值。然后，对所有采样点分别计算分割维度和位置，选择能够使分割点左右数据量最平衡的点。

- 方差最大化

对于数据点中的所有维度，计算出其方差。选择方差最大的维度作为分割维度，然后选择该维度上的中位数作为分割点。

以下是基于均匀采样的实现方法：

int sample_num = 6; // 采样点数
int splitDim = -1;
double splitPos = -1;
double range[3][2]; // 存储每个维度的最大、最小值
for (int i = 0; i < 3; i++)
{
    range[i][0] = INFINITY;
    range[i][1] = -INFINITY;
}
for (int i = l; i < r; i++)
{
    for (int j = 0; j < 3; j++)
    {
        range[j][0] = fmin(range[j][0], arr[i].pos[j]);
        range[j][1] = fmax(range[j][1], arr[i].pos[j]);
    }
}
for (int i = 0; i < sample_num; i++)
{
    double pos[3];
    for (int j = 0; j < 3; j++)
    {
        pos[j] = range[j][0] + (double)i / (sample_num - 1) * (range[j][1] - range[j][0]);
    }
    int dim = i % 3;
    double sum1 = 0, sum2 = 0;
    for (int j = 0; j < r - l; j++)
    {
        sum1 += arr[l + j].pos[dim];
        sum2 += arr[l + j].pos[dim] * arr[l + j].pos[dim];
    }
    double mean = sum1 / (r - l);
    double var = sum2 / (r - l) - mean * mean;
    int left = 0, right = 0;
    for (int j = l; j < r; j++)
    {
        if (arr[j].pos[dim] < pos[dim]) left++;
        if (arr[j].pos[dim] > pos[dim]) right++;
    }
    if (fmin(left, right) < fmin(bestLeft, bestRight))
    {
        bestLeft = left;
        bestRight = right;
        splitDim = dim;
        splitPos = pos[dim];
    }
}

3. 递归构建KD树

在选择了分割维度和位置之后，我们就可以将数据分成左右两部分，并将该节点设为分割点。然后，递归地构建左右子节点。

为了使叶子内点的数量大于100，我们可以在每个节点上设一个阈值，当节点内的数据量小于该阈值时，将该节点标记为叶子节点。同时，如果数据量较小，也可以直接使用暴力搜索的方式来查找最近邻。

以下是递归构建KD树的实现方法：

Node* buildKDTree(Point* arr, int l, int r, int depth)
{
    if (r - l < THRESHOLD)
    {
        Node* node = new Node();
        node->pos[0] = node->pos[1] = node->pos[2] = 0;
        for (int i = l; i < r; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                node->pos[j] += arr[i].pos[j];
            }
        }
        for (int j = 0; j < 3; j++)
        {
            node->pos[j] /= (r - l);
        }
        node->isLeaf = true;
        return node;
    }
    int splitDim = -1;
    double splitPos = -1;
    findSplitPos(arr, l, r, splitDim, splitPos);
    int mid = l + (r - l) / 2;
    std::nth_element(arr + l, arr + mid, arr + r, compare(splitDim));
    Node* node = new Node();
    node->pos[0] = arr[mid].pos[0];
    node->pos[1] = arr[mid].pos[1];
    node->pos[2] = arr[mid].pos[2];
    node->splitDim = splitDim;
    node->isLeaf = false;
    node->left = buildKDTree(arr, l, mid, depth + 1);
    node->right = buildKDTree(arr, mid + 1, r, depth + 1);
    return node;
}

4. 近邻搜索

最后，我们还需要实现一个近邻搜索算法，用于根据查询点查找最近的数据点。

具体实现可以使用递归的方式，按照KD树的结构进行搜索。具体步骤如下：

- 1. 从根节点开始，找到查询点在KD树中的位置。

- 2. 如果该位置是一个叶子节点，那么直接返回该节点的位置。

- 3. 否则，根据查询点与分割点的位置关系，确定应该往左子树还是右子树搜索。

- 4. 递归搜索左子树或右子树，并返回离查询点最近的数据点。

- 5. 对于每个子树，判断其是否和另一侧的子树可能存在更近的点。如果存在，则递归搜索另一侧的子树。

以下是实现该算法的核心代码：

void search(Node* node, Point* arr, Point& query, Point& nearest)
{
    if (node == NULL) return;
    if (node->isLeaf)
    {
        for (int i = 0; i < THRESHOLD && node + i != NULL; i++)
        {
            double dist = distance(node[i].pos, query.pos);
            if (dist < distance(nearest.pos, query.pos))
            {
                nearest.pos[0] = node[i].pos[0];
                nearest.pos[1] = node[i].pos[1];
                nearest.pos[2] = node[i].pos[2];
            }
        }
        return;
    }
    int cur = node->splitDim;
    if (query.pos[cur] < node->pos[cur])
    {
        search(node->left, arr, query, nearest);
        if (distance(node->pos, query.pos) < distance(nearest.pos, query.pos))
        {
            search(node->right, arr, query, nearest);
        }
    }
    else
    {
        search(node->right, arr, query, nearest);
        if (distance(node->pos, query.pos) < distance(nearest.pos, query.pos))
        {
            search(node->left, arr, query, nearest);
        }
    }
}

完整代码如下：