## Line-line collision detection investigation (part two)

July 29th, 2016 7:11 am

I recently rebooted development of a project I tried to develop for the Ludum Dare 20 contest held in April 2011, the theme of which was “It’s dangerous to go alone! Take this!”

As the project will require a function for performing line-line collision detection, and as I’m interested in whether it is possible to program that function using the knowledge I’ve gained-, and the abilities I’ve developed-, studying the Introductory Algebra Review (MA004) and Visualizing Algebra (MA006) courses offered by Udacity, I’ve begun an investigation into programming that function.

In the second part of the investigation – posted to my blog – I investigate programming a function for performing line-line collision detection when the two lines are finite in length.

### 6 Responses to “Line-line collision detection investigation (part two)”

1. varuns says:

Where are you from? Even non-Asians cover the math for this in high school, so how could you have missed it?

• sealfin says:

I’m from England, where the mathematics pertaining to this topic isn’t (as far as I’m aware) taught at GCSE level, and I’ve not (hopefully “not yet“) been able to (formally) study mathematics beyond GCSE level.

• sorceress says:

It is encountered at GCSE as crossing lines, (not line segments). See simultaneous linear equations in two variables.

• sealfin says:

I’m aware that line-line intersection is taught at GCSE level (I used it in part one of this investigation) – I meant that as far as I’m aware line segment-line segment intersection isn’t taught at GCSE level..? (Sorry for the confusion!)

• sorceress says:

Line segment intersection is not usually studied in mathematics, perhaps because it’s too specific a problem. Mathematics likes to focus on general principles upon which we can build more advanced mathematics.

The mathematics is essentially the same for infinite lines, but with additional testing to make sure that the intersection point is part of each line segment. One way is to parameterise the line segments by lerping between their end points:

L1(λ)= seg1pt1 + λ * (seg1pt2 – seg1pt1)
L2(μ)= seg2pt1 + μ * (seg2pt2 – seg2pt1)

Then letting L1(λ) = L2(μ) (= intersection point), and solving for parameters λ and μ. Finally make sure these are both in the interval [0,1].

Hope that helps

2. QualityCatGames says:

there goes my brain…

Not quite sure if it’s ever been attempted to each me this stuff before

And sadly, I would benefit from learning it…

oh well, maybe another time.

[cache: storing page]