2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "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? $\endgroup$ – smls Oct 13 at 8:37
  • 1
    $\begingroup$ @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. $\endgroup$ – D.W. Oct 13 at 22:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.