Intersection of A Polyhedron With A Line - General Solution

General Solution

To this end, we would like to find such that, which is equivalent to finding a such that

for .

Thus, we can bound as follows:

The last two lines follow from the cases when the direction vector is parallel to the halfplane defined by the row of : . In the second to last case, the point is on the inside of the halfspace; in the last case, the point is on the outside of the halfspace, and so will always be infeasible.

As such, we can find as all points in the region (so long as we do not have the fourth case from above)

which will be empty if there is no intersection.