0

我为点创建了一个最小距离过滤器。该函数采用点流 (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）测试所有点。

如何改进？

4

2 回答 2

2

查找范围树，例如 en.wikipedia.org/wiki/Range_tree 。您可以使用此结构来存储二维点并快速找到位于查询矩形内的所有点。由于您想查找点 (a,b) 一定距离 d 内的点，因此您的查询矩形需要为 [ad,a+d]x[bd,b+d] 然后您测试在其中找到的任何点矩形以确保它们实际上在 (a,b) 的距离 d 内。范围树可以在 O(n log n) 时间和空间内构建，范围查询需要 O(log n + k) 时间，其中 k 是在矩形中找到的点数。似乎最适合您的问题。

于 2013-07-20T22:26:49.527 回答
2

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

于 2013-07-20T22:57:01.057 回答