Exposing Populated Nodes

[charlierix]

I had a crudely written point deduper that was incredibly slow when the number of points got over 10000

I made a copy of the point octree, exposed Node as a public and was able to get a very large speed boost

I doubt you would want some of this stuff exposed like that. Maybe return some kind of specific node. Or maybe you don't like this idea at all. Just figured I'd share

Here is my calling code:

public static Point3D[] GetUnique(IEnumerable<Point3D> points)
{
	Point3D[] arr = points.ToArray();

	var aabb = GetAABB(arr);
	float size = (float)Math1D.Avg(aabb.max.X - aabb.min.X, aabb.max.Y - aabb.min.Y, aabb.max.Z - aabb.min.Z);

	var center = GetCenter(arr).ToVector3();

	//NOTE: using the custom copy of octree (not the nuget reference)
	var tree = new NetOctree.Octree.PointOctree<Point3D>(size * 2, center, size * 0.02f);

	foreach (Point3D point in arr)
	{
		tree.Add(point, point.ToVector3());
	}

	var nodes = tree.GetAllUsedNodes();

	var retVal = nodes.
		AsParallel().
		Select(o =>
		{
			var list = new List<Point3D>();
			o.GetAll(list);
			return GetUnique_BRUTEFORCE(list);
		}).
		SelectMany(o => o).
		ToArray();

	//Point3D[] test = GetUnique_BRUTEFORCE(retVal);      // the count is the same

	return retVal;
}

Here are added functions:

/// <summary>
/// Returns all nodes in a flattened list.  Useful for debugging or processing items by cell (like a dedupe)
/// </summary>
public Node[] PointOctree::GetAllUsedNodes()
{
	return _rootNode.GetSelfAndAllDescendantNodes().
		Where(o => o.HasObjects_SelfOnly).
		ToArray();
}

public bool Node::HasObjects_SelfOnly => _objects.Count > 0;

public Node[] Node::GetSelfAndAllDescendantNodes()
{
	var retVal = new List<Node>();

	retVal.Add(this);

	if (_children != null)
	{
		foreach (Node child in _children)
		{
			retVal.AddRange(child.GetSelfAndAllDescendantNodes());
		}
	}

	return retVal.ToArray();
}