这是其中一种情况，如果我知道我正在尝试做的事情的名称，我可能能够研究它。
本质上，我有一组 2D 点（顶点）在某些区域稀疏，而在其他区域集中。我想要做的是通过“智能”从更集中的区域移除点，同时将点留在稀疏区域中来简化这个集合。我想针对一个目标执行此操作，例如从 50,000 点开始并以 10,000 点结束（或在 10,000 点左右 - 它不需要 100% 精确）。
我敢肯定我以前见过这样做的技术，但我不记得它对我的生活有什么影响！任何帮助，将不胜感激。
问问题
1809 次
6 回答
2
下面是一些伪代码（因为我不知道您的首选语言），用于将一组点减少到每个网格分区的一个点。你给它一组点和沿任何轴的分区数。代码将首先遍历这些点以找到最大/最小端点以形成一个边界框。然后它将边界框拆分为沿 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
}
}
}
}
Andrew，OpenGeoCode.Org 的联合创始人
于 2013-11-06T19:10:42.100 回答
1
您可以尝试的方法是通过汇总与节点的距离（可能是某个距离内的所有节点）来评估每个节点，如果它高于某个阈值，则删除最接近它的节点。如果你对所有节点都这样做，你应该得到一个更稀疏的图。
于 2013-11-04T22:04:23.840 回答
0
我听说过这个概念叫做decimation.
您要寻找的最简单的版本是“每 5 个点中删除 4 个”，并希望您的稀疏区域有足够的数据来度过难关。这自然会从密集区域获得更多的分数，（它从每个区域中获得相同的百分比，但更密集的区域显然会获得更多的分数）。
除此之外，您还需要提供更多细节。如果您可以通过编程方式找到稀疏区域，则可以选择从抽取中忽略它们，或者不超过一定数量。它可能很简单，就像“在抽取时，如果该区域还剩下 <= x 个数字，则查找下一个区域。”
于 2013-11-04T22:03:56.213 回答
0
您可以围绕数据集创建一个框，然后将该框划分为一个网格。然后对于网格的每个区域，求和其中的点数。从最密集的区域随机删除点，直到它剩下的点与第二密集的区域一样多，然后重新处理网格。
于 2013-11-04T22:08:14.990 回答
0
我想说这种技术的通用名称是“网格简化”（例如参见http://doc.cgal.org/latest/Surface_mesh_simplification/index.html）。您从点创建 Delaunay 三角剖分，然后迭代折叠最小边，直到达到所需的顶点数或三角剖分中的最小边长。
我相信你会很高兴提出为什么在这里使用三角剖分是自然的以及为什么三角剖分是 Delaunay 是自然的。
于 2013-11-06T07:34:44.787 回答