## Don't Make Me Cross

A very common task in graphics is computing the point where two line segments meet. This computation might be needed, for instance, to clip a triangle against the edges of the screen, or check if two shapes overlap in a physical simulation. But how do we find an intersection, concretely?

In particular, let's consider two line segments with endpoints (**a0**,**a1**) and (**b0**,**b1**) in the plane. We'll consider three different ways to compute the intersection point **x** (if it exists).

### Implicit approach.

One way to interpret a system of linear equations is that you're looking for the point where a collection of lines (or planes, etc.) intersect. But how do you turn lines into equations?

- Write down an affine equation that characterizes all points
**x**on the line through**a0**and**a1**. Now do the same for**b0**,**b1**. - Write down a linear system A
**x**=**b**for the intersection point**x**. You do not need to solve this system, but should give explicit expressions for the entries of the matrix**A**and the vector**b**(so that you could in principle hand it off to a linear solver). - What does it mean geometrically if the system does not have full rank?
- Suppose the linear system has full rank, and the solver produces the intersection point
**x**. How can we check whether it is contained in the two segments?

### Explicit approach.

A different way to describe a line is to think of it as a ray **r**(t) = **o** + t**d** that starts at some origin **o** and travels in some direction *d* for time *t*. (To trace out the rest of the line, we can just go in the opposite direction -t.)

- Write down a ray
**f**(t) along the segment (**a0**,**a1**), and another ray**g**(s) along the segment (**b0**,**b1**). - What linear system can you solve to determine the intersection? Give the entries of this system explicitly. To obtain the final intersection point
**x**, what else do you have to do beyond just solving the linear system? - How do you know if the intersection point is contained in the segments?

### Homogeneous approach.

There's a much simpler way to compute the intersection of two lines, using this "one weird trick" called *homogeneous coordinates*. The basic idea is to turn every point in 2D into a whole line in 3D. Certain computations on these 3D lines are then much easier than the corresponding calculations on points in 2D. More precisely, any point **x** in 2D gets associated with all points of the form **X** = (c**x**,c), where c is any nonzero constant. If we vary c, we see that these points trace out a line in 3D. Often, we let c=1 and use (**x**,1) as the canonical representative, corresponding to a point in the 2D plane at height 1 above the origin.

- If we consider all 2D points along the 2D line through
**a0**and**a1**, what shape do all the corresponding 3D points describe in 3D? How about**b0**and**b1**? - Geometrically, which line in 3D corresponds to our 2D intersection point
**x**? - How can we compute this line explicitly, using only the homogeneous coordinates
**A0**,**A1**,**B0**, and**B1**? [Hint: your final expression for the intersection point should be*really*simple!]