Bounding Box Errors in SPBS

[biberger]

Describe the bug
The current SPBS algorithm produces too many bounding boxes and said bounding boxes collide massively.

To Reproduce
Steps to reproduce the behavior:
Let input be an arbitrary input point cloud or occupancy grid. The output of the SPBS algorithm will be called boxes. kr
specifies the kernel radius, which also controls the size of the bounding boxes.

import cestimii.split as split
boxes = split.spbs_pointcloud(input) or boxes = split.spbs_ocg(input)

The resulting many amounts of colliding bounding boxes.

Expected behavior
Bounding boxes that organically cover the surface, whereby the bounding boxes can collide, but only in edge cases. Here's the output of the simple algorithm, that shows a working surface covering (whereby keep in mind the disadvantages of using the simple algorithm).

Screenshots
Just to provide context, here's the surface without any bounding boxes.

Probable causes
There are really just three probable causes for the bug.

• The regional sweep plane status is not updated properly and does not contain all relevant neighbouring boxes, thus causing the collision check method to fail as it does not contain all bounding boxes for which it has to check collisions.
• The collision check method is not working properly, thus causing colliding boxes.
• Covered points/voxels are not deleted properly, thus leading to an event point queue with too many points. This would make it nearly impossible to find overlap-free new bounding boxes and would cause too many bounding boxes to be constructed.
  I think I should focus on the third point in the near future.

Additional context
I have known about this bug for a while, but haven't had the time to fix it. I did look at the regional sweep plane status and the collision check method already, but could not find any issues. Maybe I should add 2D functionality to the algorithm and test it in two dimensions first.

Solution (in the meantime)
Don't use the SPBS algorithm. If you want to use the split methods, use the simple algorithm. It's immensely fast and yields good results in most cases.