feat: Implement a k-d tree data structure

[stephenswat]

This pull request is part three of four in my attempt to implement an orthogonal range search seed finder. Parts one and two are #985 and #986.

k-d trees are data structures that allow certain operations to be performed efficiently on point cloud data. Most commonly, these
operations are (orthogonal) range search and nearest neighbour search. For my implementation, I need only the first, and as such nearest neighbour search is omitted in name of the YAGNI principle.

I have implemented this class with performance and GPU-compatibility in mind, and therefore the memory is efficiently laid out wherever possible (although some improvements can still be made later).

The implementation supports a more classical C++ interface where vectors of items are returned, as well as a more functional approach which employs higher-order functions to effect the required computation. This functional approach is the backbone to the classical approach as well.

I believe that a k-d tree implementation is a good thing to have in Acts, since they are very versatile and I can see them being used in several other parts of the code.

Again, I have added tests for the k-d tree as well, to ensure that the implementation works as intended.

This pull request cannot be merged until #985 and #986 are merged.

[codecov]

Codecov Report

Merging #987 (7c95c47) into main (d9c04a6) will increase coverage by 0.06%.
The diff coverage is 56.30%.

@@            Coverage Diff             @@
##             main     #987      +/-   ##
==========================================
+ Coverage   48.67%   48.73%   +0.06%     
==========================================
  Files         336      337       +1     
  Lines       17158    17281     +123     
  Branches     8098     8162      +64     
==========================================
+ Hits         8351     8422      +71     
- Misses       3100     3118      +18     
- Partials     5707     5741      +34     

Impacted Files	Coverage Δ
Core/include/Acts/Utilities/KDTree.hpp	56.30% <56.30%> (ø)
Core/include/Acts/Utilities/Range1D.hpp	97.36% <0.00%> (+0.30%)	⬆️

---

Continue to review full report at Codecov.

Legend - Click here to learn more
Δ = absolute <relative> (impact), ø = not affected, ? = missing data
Powered by Codecov. Last update d9c04a6...7c95c47. Read the comment docs.

[stephenswat]

Hmm, that test coverage is quite low. I'll work on improving that.

[stephenswat]

I've updated the commit with the following changes:

1. The str methods have been renamed to toString methods, just like in feat: Implement a k-dimensional range class #986.
2. The license header has been fixed.
3. An undocumented parameter which was causing the docs generation to crash has been documented.
4. Additional tests have been added to cover some edge cases.
5. The k-d tree has been modified to work with the new half-open intervals (which was somewhat awkward).

[asalzburger]

Very nice to get this together, I saw you fixed the doc compilation already, so that's great.

I had two questions for my understanding, but other than that I am happy to merge this in.

[stephenswat]

So I've noticed the Mac OS CI build timed out; is that something that sometimes happens? Is the OS X build just slow?

[asalzburger]

So I've noticed the Mac OS CI build timed out; is that something that sometimes happens? Is the OS X build just slow?

Ha, no idea, let's just re-start the CI and see.