Checking if a pair of segments intersects in an n-dimensional Euclidean space (in Lisp)

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, (a1 a2), where a1 and a2 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.

Advertisements
Published in: on 05/01/2013 at 20:27  Leave a Comment  

The URI to TrackBack this entry is: https://burubaxair.wordpress.com/2013/01/05/checking-if-a-pair-of-segments-intersects-in-an-n-dimensional-euclidean-space-in-lisp/trackback/

RSS feed for comments on this post.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: