如何总结点云列表

Question

我有一个名为“Spot”的特定数据类型的大列表。列表的每个元素都包含一个点列表（Point => struct from Systems.Drawing）以及其他字段。

public class Spot
{
    public List<Point> PointCloud { get; set; }
    ...
}
List<Spot> spots = new List<Spot>();

我想用以下方式总结列表点：如果spots的一个元素在其PointCloud中至少有一个Point等于另一个元素PointCloud中的一个Point，那么它们可以是summarized/merged。这意味着 PointClouds 被联合为一个（使用 Union-Method 很容易）并且可以从列表点中删除一个元素。我已经知道了：

while (spots[counterA].PointCloud.Any(p => spots[counterB].PointCloud.Contains(p)))
{
     spots[counterA].PointCloud.Union(spots[counterB].PointCloud);
     spots.Remove(spots[counterB]);
     ...
}

问题是，一个元素的点云变大了。因此，在每次联合之后，我必须从头开始再次检查剩余元素的整个列表以获得相等的点数。我不确定如何设置循环和计数器，性能不会为零。也许还有一种没有循环的方法。我希望有人能帮我找到一个有效的方法来总结列表。

Answer 1

如果点完全相同，您可以使用 HashSet 来存储点。这将对性能有很大帮助，因为 HashSet.Contains 是 O(0) 而不是 O(n)。

此外，您对 Union 的用法不正确，这是 return 一个新列表，您没有将其分配给任何东西。相反，将点添加到现有列表会更有效。我不确定你打算如何让循环工作，因为你现在显示了整个代码，我可能会使用这样的东西：

public class Spot
{
    public HashSet<Point> PointCloud { get; }
    public bool Intersect(Spot other) => other.PointCloud.Any(p => PointCloud.Contains(p));

    public void Add(Spot other)
    {
        foreach (var p in other.PointCloud)
        {
            PointCloud.Add(p);
        }
    }
}

和

    public static IEnumerable<Spot> Merge(List<Spot> spots)
    {
        for (int i = 0; i < spots.Count; i++)
        {
            for (int j = i+1; j <spots.Count; j++)
            {
                if (spots[i].Intersect(spots[j]))
                {
                    spots[i].Add(spots[j]);
                    // Remove the merged object, 
                    // and restart the loop,
                    // Since the merged set might intersect a previous spot
                    spots.RemoveAt(j);
                    j = i+1;
                }
            }

            yield return spots[i];
        }
       
    }

请注意，如果点不完全相同，则不能使用 HashSet 来加速搜索。相反，您需要使用诸如 KD 树或其他搜索结构之类的东西，以便以合理的速度找到最近点。

另外，使用hashSet只会保留每个点的一次实例。因此，如果两个点各有一个点 (1,1)，则合并后的集合将只有一个这样的点，而不是两个。不确定这是否是个问题。

如何总结点云列表

How to summarize a list of point-clouds

c#

list

union

point-clouds

any