Efficient data structure for matching 3D lines 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 &amp;= \text{an arbitrary point on the line} &amp;= 3 \;\text{floats} \\
    v &amp;= \text{an arbitrary vector parallel to the line} &amp;= 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' &amp;= \text{the point on the line closest to}\;(0,0,0) &amp;= 3 \;\text{floats} \\
    v' &amp;= \text{normalized direction vector} &amp;= 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&lt;double, Line3D*&gt; in C++ or TreeSet&lt;Double, List&lt;Line3D&gt;&gt; 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?
Any line can be represented in the form $\{p + xv : x \in \mathbb{R}\}$, or in other words, by a point $p$ on the line and a vector $v$ parallel to the line.  Without loss of generality, we can take $v$ to have norm 1 (if not, replace $v$ with $v/\|v\|_2$).  Also, if we ignore lines where the $z$-component of $v$ is zero, then without loss of generality we can take $p$ to be a point whose $z$-component is zero.

So, let's represent any line by the pair $p,v$, where $v$ is chosen to have norm 1 and where $p$ is chosen to have its $z$-component be zero.  Then this is a canonical representation of the line: each line has a unique representation, and two lines coincide iff their $p,v$-representations are identical.

This means that you can store each line in a hash table, where you store the pair $p,v$.  Thus, it is a hash table where each key is a 6-tuple.  You could compress it so each key is a 4-tuple (you can represent $v$ with 2 dimensions, and you only need to store the $x$- and $y$-components of $p$), but this probably doesn't gain you much.

To deal with floating-point errors, you could round $p,v$ to the nearest multiple of $\epsilon$ before storing it in the hashtable.  Or, you could store it in a data structure that supports nearest neighbor queries, such as a k-d tree.