c++ - 改进点集的最小距离过滤器

Question

我为点创建了一个最小距离过滤器。 该函数采用点流 (x1,y1,x2,y2...) 并删除相应的点。

void minDistanceFilter(vector<float> &points, float distance = 0.0)
{
    float p0x, p0y;
    float dx, dy, dsq;
    float mdsq = distance*distance; // minimum distance square

    unsigned i, j, n = points.size();

    for(i=0; i<n; ++i)
    {
        p0x = points[i];
        p0y = points[i+1];

        for(j=0; j<n; j+=2)
        {
            //if (i == j) continue; // discard itself (seems like it slows down the algorithm)

            dx = p0x - points[j];   // delta x (p0x - p1x)
            dy = p0y - points[j+1]; // delta y (p0y - p1y)

            dsq = dx*dx + dy*dy; // distance square

            if (dsq < mdsq)
            {
                auto del = points.begin() + j;
                points.erase(del,del+3);
                n = points.size(); // update n
                j -= 2; // decrement j
            }
        }
    }
}

唯一一个非常慢的问题，因为它会针对所有点 (n^2) 测试所有点。

如何改进？

Answer 1

kd 树或范围树可用于解决您的问题。但是，如果您想从头开始编写代码并想要更简单的东西，那么您可以使用哈希表结构。对于每个点 (a,b)，使用键 (round(a/d),round(b/d)) 散列并将具有相同键的所有点存储在列表中。然后，对于哈希表中的每个键 (m,n)，将列表中的所有点与具有键 (m',n') 的所有 9 个选择 (m',n') 的点列表进行比较，其中 m ' = m + (-1 or 0 or 1) and n' = n + (-1 or 0 or 1).这些是唯一可以在具有键 (m,n) 的点的距离 d 内的点。与 kd 树或范围树相比的缺点是，对于给定的点，您实际上是在边长 3*d 的正方形内搜索距离可能为 d 或更小的点，而不是在边长的正方形内搜索2*d 如果你使用 kd 树或范围树，你会得到什么。但是，如果您是从头开始编码，那么编码起来会更容易；如果您只关心所有点的通用距离 d，那么 kd 树和范围树也有点矫枉过正。