c# - 简化一组点

Question

在这种情况下，如果我知道我要尝试做的事情的名称，我可能就能对其进行研究。

本质上，我有一组二维点(顶点)，它们在某些区域稀疏，而在其他区域集中。我想要做的是通过“智能地”从更集中的区域移除点，同时将点留在稀疏区域来简化这个集合。我想针对一个目标执行此操作，因此例如从 50,000 点开始到 10,000 点结束(或在 10,000 附近 - 它不需要 100% 精确)。

我敢肯定我以前见过执行此操作的技术，但我记不起它是什么了!任何帮助将不胜感激。

Answer 1

下面是一些伪代码(因为我不知道你的首选语言)，用于将每个网格分区的一组点减少到一个点。你给它点集和沿任何轴的分区数。代码将首先遍历点以找到最大/最小端点以形成边界框。然后它将边界框沿 X 轴和 Y 轴拆分为多个分区。

然后代码将遍历每个网格分区并检查网格中的点数组。如果该点在网格中，它将保留第一个匹配项并删除剩余的点。享受转换代码或更改标准以保持观点的乐趣。

function ReduceGrid( array points, int npartitions )
{
    int max_x = 0, max_y = 0;
    int min_x = MAX_INT, min_y = MAX_INT

    // Find the bounding box of the points
    foreach point in points
    {
        if ( point.X > max_x )
            max_x = point.X;
        if ( point.Y < min_x )
            min_x = point.X;
        if ( point.Y > max_y )
            max_y = point.Y;
        if ( point.Y < min_y )
            min_y = point.Y;
    }

    // Get the X and Y axis lengths of the paritions
    float partition_length_x =  ( ( float ) ( max_x - min_x ) ) / npartitions;
    float partition_length_y =  ( ( float ) ( max_y - min_y ) ) / npartitions;

    // Reduce the points to one in each grid partition
    for ( int n = 0; n < npartitions; n++ )
    {
        // Get the boundary of this grid paritition
        int min_X = min_x + ( n * partition_length_x );
        int min_Y = min_y + ( n * partition_length_y );
        int max_X = min_x + ( ( n + 1 ) * partition_length_x );
        int max_Y = min_y + ( ( n + 1 ) * partition_length_y );

        boolean reduce = false; // set to true after finding the first point in the paritition
        foreach point in points
        {
            // the point is in the grid parition
            if ( point.X >= min_x && point.X < max_x &&
                 point.Y >= min_y && point.X < max_y )
            {
                // first point found
                if ( false == reduce )
                    reduce = true;
                else
                    points.Remove( point ); // remove the point from the list
            }
        }
    }
}

安德鲁，OpenGeoCode.Org 的联合创始人