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.
Read more about this topic: Intersection Of A Polyhedron With A Line
Famous quotes containing the words general and/or solution:
“As a general rule, do not kick the shins of the opposite gentleman under the table, if personally unaquainted with him; your pleasantry is liable to be misunderstood—a circumstance at all times unpleasant.”
—Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)
“What is history? Its beginning is that of the centuries of systematic work devoted to the solution of the enigma of death, so that death itself may eventually be overcome. That is why people write symphonies, and why they discover mathematical infinity and electromagnetic waves.”
—Boris Pasternak (1890–1960)