 |
 |
|
|
Input Description: A point \(p\) and a line segment \(l\), or two line segments \(l_1\) and \(l_2\).
Problem: Does \(p\) lie over, under, or on \(l\)? Does \(l_1\) intersect \(l_2\)?
Excerpt from The Algorithm Design Manual: Implementing basic geometric primitives is a task fraught with peril, even for such simple tasks as returning the intersection point of two lines. What should you return if the two lines are parallel, meaning they don't intersect at all? What if the lines are identical, so the intersection is not a point but the entire line?
What if one of the lines is horizontal, so that in the course of solving the equations for the intersection point you are likely to divide by zero? What if the two lines are almost parallel, so that the intersection point is so far from the origin as to cause arithmetic overflows? These issues become even more complicated for intersecting line segments, since there are a bunch of other special cases that must be watched for and treated specially.
  Determinants and Permanents |
  Intersection Detection |
  Maintaining Line Arrangements |
As an Amazon affiliate, I earn from qualifying purchases if you buy from links on this website.
.jpg)
Algorithms in Java, Third Edition (Parts 1-4) by Robert Sedgewick and Michael Schidlowsky
Computational Geometry in C by Joseph O'Rourke
Algorithms from P to NP, Vol. I: Design and Efficiency by B. Moret and H. Shapiro