4
$\begingroup$

There are two non parallel line segments $U$ and $V$ in $\mathbb{R}^3$, each given by their two end points $u_0, u_1$ and $v_0, v_1$, such that if they are projected into $\mathbb{R}^2$ by their $x$ and $y$ coordinates, they intersect. We want to know whether the line $U$ is above $V$. More exactly, suppose their projections on $\mathbb{R}^2$ intersects at point $(x, y)$. We want to know whether the $z$ coordinates of line segment $U$ at point $(x, y)$ is larger than the $z$ coordinates of line segment $V$ at point $(x, y)$.

Assuming that $u_0, u_1, v_0, v_1$ are all lattice points, is there a way to do this that doesn't explicitly calculates the $x$, $y$ and $z$ coordinates? In order words, how to check this without floating point arithmetic?

Motivation

This comes up when I am trying to compute the 3D convex hull of the projection of a triangulation of polygon from $\mathbb{R}^2$ into $\mathbb{R}^3$ during the computation of the weighted delaunay triangulation of the set of points.

$\endgroup$
3
+50
$\begingroup$

I think this condition does the job: $$ 0 \le \det\left[\begin{matrix} v_0-u_0 & u_1-u_0 & v_1-v_0 \end{matrix}\right] \det\left[\begin{matrix} P(u_1-u_0) & P(v_1-v_0) \end{matrix}\right] \tag{$\ast$} $$ Here $P$ is the coordinate projection onto the $xy$-plane; the matrix $\left[\begin{matrix} a & b \end{matrix}\right]$ means the matrix with vectors $a$ and $b$ as columns; the first determinant is $3\times3$ and the second is $2\times 2$. (Note that the latter determinant is a subdeterminant of the former, so there's some opportunity to reuse computational results.)

To derive this, consider the following method of solving the problem directly by computing $x,y,z$. First we find the intersection of the projections by solving the system $$ P(u_0) + s(P(u_1)-P(u_0)) = P(v_0) + t(P(v_1)-P(v_0)) \tag1 $$ Then we compute the $z$ coordinates and compare them: $$ u_{0z} + s(u_{1z}-u_{0z}) \mathrel{\stackrel{?}{\le}} v_{0z} + t(v_{1z}-v_{0z}) \tag2 $$ If you solve the system (1) using Cramer's rule and plug the resulting $s$ and $t$ into (2), you'll find that it's equivalent to ($\ast$)... assuming I haven't made some elementary error.

(Geometrically, ($\ast$) is checking the handedness of the tetrahedron formed by the four vertices.)

$\endgroup$
0

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.