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 &= \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?

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.

• "round p,v to the nearest multiple of ϵ" -- But then there would be some almost-identical lines that get different keys in the hash table, wouldn't there?
– smls
Oct 13 '19 at 8:37
• @smls, yup. You could deal with by doing multiple lookups in the hashtable. For instance, after looking up $(p,v)$, you look up $(p,v)+(r_1,\dots,r_6)$ where each $r_i$ is either $0$ or $\pm \epsilon$ (choose $+\epsilon$ if rounding the $i$th component of $p$ causes you to round down, or $-\epsilon$ otherwise). You can reduce the number of lookups in a variety of ways. Or, you can use a k-d tree.
– D.W.
Oct 13 '19 at 22:52