Precise imprecision

Have you ever thought about how many types of intersections exist for two lines? Just two straight lines, either in 2D or 3D, bounded by two points (not infinite). And only counting the intersections that fall on one of the two lines, including their end points. You probably didn't, because it sounds pointless.


Well, I had to think about that one seriously while working on a problem back in 2001. It looks simple at first. You start imagining the type of intersections:

• The two lines crossing in the middle


• One end of a line touching the other one


• One end of both lines touching each other

Then you think about that one:

• The two lines completely overlapping

And that gets you to:

• The two lines partly overlapping
  
• And both overlapping combinations with a short and a long line...

In that completed list, you arrive at 7 types of intersections. That would be OK in a perfect world where everything is on a nice grid and points are either on or off the line.
In the real world, lines don't fall perfectly on each other. Many times, two points will be really, really, really close but not touching. That's when you start working with an allowance for imprecision. Doing that, you round up numbers for which the difference is smaller than the allowed precision. So in a 3D world, you would consider two points that are close enough together as one point. This then creates a perfect world with 7 types of intersections... or does it?

Not really, if you're picky like me. Because, with this approach, the data changes with each correction created by the precision rounding. So I asked myself: what would happened if I didn't move the rounded points? What kind of intersection types would that create? After a lot of work, I finished a new list of intersection types. Starting with the original 7 types of intersections, I identified variations for almost each of them. And because of the imprecision allowance, I also found a whole set of sub-cases with each of them acting as a multiplication factor on the base types. This brought the grand total to 129 types of intersections.

129, Ouch!

So, next time you think something is simple... think twice.