c# - How to summarize a list of point-clouds

Question

I have a large list of a specific datatype called "Spot". Each element of the list contains a list of Points (Point => struct from Systems.Drawing) among other fields.

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

I'd like to summarize the list spots in the following way: If one element of spots contains at least one Point in its PointCloud which is equal to one Point of the PointCloud of another element, then they can be summarized/merged. That means that the PointClouds are united to one (easy with Union-Method) and one element can be removed from the list spots. I already got that:

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

The problems is, that the PointCloud of one element gets larger. So after each union I have to check the whole list of remaining elements again from the start for equal Points. I'm not sure how to set the loops and counters, that the performance isn't going to zero. Maybe there's also a way to to this without loops. I hope someone can help me to find an efficient way to summarize the list.

question from:https://stackoverflow.com/questions/65933702/how-to-summarize-a-list-of-point-clouds

Answer 1

If the points are exactly the same you can use a HashSet to store the points. This will help greatly with performance since HashSet.Contains is O(0) instead of O(n).

Also, your usage of Union is incorrect, this return a new list, and you are not assigning it to anything. It would be more efficient to add the points to the existing list instead. I'm not sure how you intend the loop to work since you do now show the whole code, I would probably use something like this:

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);
        }
    }
}

and

    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];
        }
       
    }

Note that if points are not exactly the same you cannot use HashSet to speedup the search. You would instead need to use something like a KD-tree or other search structure that allows for a reasonable fast way to find the closest point.

Also, the use of hashSet will only keep once instance of each point. So if two spots each have a point(1,1), the merged set will only have one such points and not two. Not sure if this is a problem or not.