c++ - 快速找到不在 vector c++中的所有元素

Question

我有一个点 vector allPoints 和一个点 vector badPoints。我想快速获得一组 goodPoints，其中包含 allPoints 中不在 badPoints 中的所有内容。目前我有:

    int i = 0;
    for (auto point : allPoints)
    {
        bool add = true;
        for (auto x : badPoints)
        {
            if (point == x)
            {
                add = false;
                break;
            }
        }
        if (add)
        {
            goodPoints.insert(point);
        }
        i++;
    }

我觉得这比应该的要慢，但我不知道更好的方法。有什么想法吗？

Answer 1

根据点的维度，排序可能不太可行(例如，您只能在一个维度上排序)。更好的方法是拥有一个 kD 树(例如，如果点是二维的，则为这些点创建一个二维树结构)，这样，而不是比较所有的点，你只需要比较中的点树的叶子。

另一种更简单但不那么优雅的方法是将您的空间划分为网格。例如，如果这些点是二维的，将您的平面划分为 NxN 网格，并根据您的单元格所在的网格单元格，仅检查该单元格内的重叠。您需要调整单元格的大小(或 N)以在单元格数量和单元格内的点数之间找到平衡。