Detecting line intersection on a torus Suppose I am given two pairs of points on a 1.0 x 1.0 that has its edges identified so as to form a torus. Each pair of points is then joined so as to form the shortest (Euclidean) straight line between them.
What is an efficient algorithm to detect if these two lines intersect?
I have thought of an algorithm where multiple line segments represent those lines that cross the boundaries of the plane and then check as required. Is this the best approach?
 A: Note that the shortest segment connecting two given points on $T:={\mathbb R}^2/{\mathbb Z}^2$ need not be well defined, e.g., when the two points are represented by $(0,0)$ and $({1\over2},{1\over4})$. In the sequel I shall assume that the data are such that ambiguities, boundary cases and degeneracies do not occur.
We shall do our computations on the universal cover ${\mathbb R}^2$ of $T$. Each point $z=(x,y)\in{\mathbb R}^2$ projects to a well defined point $\hat z\in T$. Two points $z$, $z'\in{\mathbb R}^2$ project to the same point in $T$ iff  $z-z'\in{\mathbb Z}^2$. In this case we write $z\sim z'$.
For $x\in{\mathbb R}$ let $[x]:=\bigl\lfloor x+{1\over2}\bigr\rfloor$ denote the  integer nearest to  $x$. One has $\bigl|x-[x]\bigr|\leq{1\over2}$.
Assume that $z_1=(x_1,y_1)$, $\>z_2=(x_2,y_2)$ represent the first pair of given points. Put
$$x_2':=x_2-[x_2-x_1], \quad y_2':=y_2-[y_2-y_1]\ .$$
Then $z_2'=(x_2', y_2')\sim z_2$, and as $|x_2'-x_1|\leq{1\over2}$, $\>|y_2'-y_1|\leq{1\over2}$ we conclude that the segment $[z_1,z_2']\subset{\mathbb R}^2$ represents the shortest segment connecting $\hat z_1$ with $\hat z_2$ in $T$.
Do the same with the representatives $w_1=(u_1,v_1)$, $\>w_2=(u_2,v_2)$ of the second pair of points. You then obtain a segment $[w_1,w_2']\subset{\mathbb R}^2$ that represents the shortest segment connecting $\hat w_1$ with $\hat w_2$ in $T$.
Most probably the two segments  $[z_1,z_2']$ and  $[w_1,w_2']$ will lie far away from each other and will not intersect; but their projections to $T$ might intersect nevertheless. We shall now replace the segment $[w_1,w_2']$ by an equivalent segment $[w_1',w_2'']$ which intersects $[z_1,z_2']$ iff their projections do intersect on $T$. Note that both segments $[z_1,z_2']$ and  $[w_1,w_2']$ have an extension $\leq{1\over2}$  in both the horizontal and the vertical directions. We therefore align the midpoint of $[w_1',w_2'']$ as well as possible with the midpoint of $[z_1,z_2']$. To this end put
$$a:={x_1+x_2'\over2},\quad b:={y_1+y_2'\over2},\quad c:={u_1+u_2'\over2},\quad
d:={v_1+v_2'\over2}$$
and
$$w_1':=w_1-\bigl([c-a], [d-b]\bigr), \qquad w_2'':=w_2'-\bigl([c-a], [d-b]\bigr)\ .$$
Then $[w_1',w_2'']\sim [w_1,w_2']$, and the midpoints of $[z_1,z_2']$ and $[w_1',w_2'']$ differ by at most ${1\over2}$ in both directions. It follows that the boldface "iff" above is indeed satisfied, since no other segment equivalent to $[w_1,w_2']$ has the slightest chance to intersect $[z_1,z_2']$.
Consider now the two lines
$$g:\quad s\mapsto (1-s)z_1+s z_2'\quad (s\in{\mathbb R}),\qquad h:\quad t\mapsto (1-t)w_1'+t w_2''\quad (t\in{\mathbb R})$$
and intersect them, solving a linear system for $s$ and $t$. When the found solution $(s_*, t_*)$ lies in $[0,1]^2$ we finally know that the two  shortest segments on $T$ in question actually intersect.
