Background
While implementing a 2D LiDAR simulator, the calculation of the LiDAR measurement was a bottleneck for performance improvement. For example, in a particle filter with 1024 particles and each particle represents a 256-line LiDAR, running in a map was represented by line segments. For a map with 16 line segments, the estimator have to calculate intersection for \(1024 \times 256 \times 16 = 4194304\) times each update. Therefore, an effective method which determines the intersection of line segments is necessary.
Statement of Problem
Given two line segments defined by points: \(AB\) and \(CD\), check whether two segments intersect.
Intersection of a line and line segment
Given line \(l\), line segment \(AB\) and its correspondent line \(l_{AB}\). The intersection \(K\) of \(l\) and \(l_{AB}\). Then point \(K\) can be expressed as:
\[ K = A + t \overrightarrow{AB} \tag{3-1} \]Here is the relationship between \(t\) and \(l\), \(AB\):
\[ \begin{cases} l \ \text{intersects} \ AB, & t \in (0, 1) \\ l \ \text{touches} \ AB, & t = 0 \ \text{or} \ t = 1 \\ l \ \text{misses} \ AB, & t \in (-\infty, 0) \cup (1, \infty) \end{cases} \]
Fig. 3-1: Intersect
Fig. 3-2: Touch
Fig. 3-2: Miss
Therefore, the sufficient and necessary condition of \(l\) intersecting \(AB\) is:
\[ K = A + t \overrightarrow{AB}, \ t \in (0, 1) \tag{3-2} \]Lemma A. Determine if Two Line Segments Intersect
Given line segments \(AB\), \(CD\) and their correspondent line \(l_{AB}\), \(l_{CD}\). It is obvious if and only if \(l_{AB}\) intersects \(CD\) and \(l_{CD}\) intersects \(AB\), these two line segments intersect.
A Rapid Method
Line segments \(AB\) intersects \(CD\) if and only if:
\[ (\overrightarrow{AC} \times \overrightarrow{AB}) \cdot (\overrightarrow{AB} \times \overrightarrow{AD}) > 0 \\ \text{and} \\ (\overrightarrow{CA} \times \overrightarrow{CD}) \cdot (\overrightarrow{CD} \times \overrightarrow{CB}) > 0 \tag{4-1} \]Proof:
According to formula (3-2)
\[ m \overrightarrow{AB} = \overrightarrow{AK} = \overrightarrow{AC} + t \overrightarrow{CD} = \overrightarrow{AD} + (1-t) \overrightarrow{DC} \tag{4-2} \]\(m\) is random none-zero constant. Then we have:
\[ \overrightarrow{AB} = \frac{1}{m}(\overrightarrow{AC} + t \overrightarrow{CD}) \tag{4-3} \] \[ \overrightarrow{AB} = \frac{1}{m}(\overrightarrow{AD} + t \overrightarrow{DC}) \tag{4-4} \]Then the first term of (4-1) becomes:
\[ \frac{t(1-t)}{m^2} (\overrightarrow{AC} \times \overrightarrow{CD}) \cdot (\overrightarrow{DC} \times \overrightarrow{AD}) > 0 \tag{4-5} \]For any triangle \(ACD\)：
\[( \overrightarrow{AC} \times \overrightarrow{CD}) \cdot (\overrightarrow{DC} \times \overrightarrow{AD}) = |AC||CD|\sin \alpha \cdot |DC||AD| \sin \beta \tag{4-6} \]There are two cases listed in Fig. 4-1 and Fig. 4-2. No matter in which case, \(\sin \alpha \sin \beta > 0\).
Fig. 4-1: \(\alpha \in (0, \pi)\), \(\beta \in (0, \pi)\), therefore, \(\sin \alpha \sin \beta > 0\).
Fig. 4-2: \(\alpha \in (\pi, 2\pi)\), \(\beta \in (\pi, 2 \pi)\), \(\sin \alpha \sin \beta > 0\) as well.
Becasue \(m^2 > 0\), formula (4-5) becomes:
\[ t(1-t) > 0 \] \[ 0 < t < 1 \tag{4-7} \]Therefore, the first term of formula (3-1) means \(l_{AB}\) intersects \(CD\). Similarly, the second term means \(l_{CD}\) intersects \(AB\). According to Lemma A., \(AB\) intersects \(CD\).