Efficient data structure for matching 3D lines

Question

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?

Answer 1

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.