Code: line-segment-intersection.lisp

I treat intersection here in an engineering rather than a strict mathematical sense.

If two aeroplanes pass each other just one metre apart then formally their paths don’t intersect but you don’t want your software to optimise air traffic like that.

This is taken into account: if two segments approach each other closer than the user-defined `tolerance`

value, the program concludes that they intersect and returns approximate coordinates of the intersection point.

I didn’t use vector cross products, so the space doesn’t have to be three-dimensional.

The line segments are defined in an *n*-dimensional Euclidean space for arbitrary *n*.

The segments are entered as lists of their end points, (a_{1} a_{2}), where a_{1} and a_{2} are lists containing *n* Euclidean coordinates.

The program chooses a point at one of the segments’ ends and then slides along the segment towards the opposite end. At each step it compares the sum of the distances from the sliding point to the end-points of the other segment.

If the sum of the distances from the sliding point to the end points of the other segment becomes equal (within tolerance) to the length of that (other) segment, the intersection point is found.

Otherwise, the program returns `NIL`

when the sliding point reaches the opposite end of its own segment.

### Like this:

Like Loading...

*Related*

## Leave a Reply