I’d like to

- Store a set of many infinite undirected 3D lines.
- Make lookups against this set – i.e. given an arbitrary line, ask “Does the set contain a line coincident with this one?”

The incidence-checks would of course have to be fuzzy to account for floating-point errors.

### Question:

What would be a good data structure to implement such a set?

### My thoughts so far:

Each line is originally represented as:

$ $ \begin{align*} p &= \text{an arbitrary point on the line} &= 3 \;\text{floats} \ v &= \text{an arbitrary vector parallel to the line} &= 3 \;\text{floats} \end{align*}$ $

To facilitate lookups, this should probably be converted such that coincident lines turn into the same tuple of floating-point numbers (within the margin of error). For example like this:

$ $ \begin{align*} p’ &= \text{the point on the line closest to}\;(0,0,0) &= 3 \;\text{floats} \ v’ &= \text{normalized direction vector} &= 2 \;\text{floats} \end{align*}$ $

Where “normalized” means unified (that’s easy) and reversed in half the cases (this will be a bit tricky to do without introducing inconsistencies).

And then I’d just need a data structure for fuzzy look-up of tuples of 5 floats.

- A 5-dimensional Binary Space Partitioning Tree, maybe?
- Or just multiply the 5 floats together to get one float per line, use them as keys in a sorted map (e.g.
`std::multimap<double, Line3D*>`

in C++ or `TreeSet<Double, List<Line3D>>`

in Java), and do range lookups like $ [x – \epsilon, x + \epsilon)$ for a given key $ x$ and error margin $ \epsilon$ and then only do the full incidence check for each line in that range?

Or maybe there’s an altogether different approach?