# Trace with 2D terrain

I currently have some 2D terrain in my game defined by 2D coordinates with lines drawn in between them (linear interpolation too keep it simple).

Now I want to cast a ray from anywhere above the terrain and see if it collides with the terrain for drawing bullet tracers.

Here is a quickly drawn example: https://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect

Here is the exact text of the most popular answer at the time that I'm posting this, posted by user Gareth Rees:

There’s a nice approach to this problem that uses vector cross products. Define the 2-dimensional vector cross product v × w to be vxwy − vywx (this is the magnitude of the 3-dimensional cross product).

Suppose the two line segments run from p to p + r and from q to q + s. Then any point on the first line is representable as p + tr (for a scalar parameter t) and any point on the second line as q + us (for a scalar parameter u).

The two lines intersect if we can find t and u such that:

p + tr = q + us

Cross both sides with s, getting

(p + tr) × s = (q + us) × s

And since s×s = 0, this means

t(r × s) = (q − p) × s

And therefore, solving for t:

t = (q − p) × s / (r × s)

In the same way, we can solve for u:

u = (q − p) × r / (r × s)

Now if r × s = 0 then the two lines are parallel. (There are two cases: if (q − p) × r = 0 too, then the lines are collinear, otherwise they never intersect.)

Otherwise the intersection point is on the original pair of line segments if 0 ≤ t ≤ 1 and 0 ≤ u ≤ 1.

(Credit: this method is the 2-dimensional specialization of the 3D line intersection algorithm from the article "Intersection of two lines in three-space" by Ronald Graham, published in Graphics Gems, page 304. In three dimensions, the usual case is that the lines are skew (neither parallel nor intersecting) in which case the method gives the points of closest approach of the two lines.)

• In case that question ever gets deleted (since it was closed as off topic), it would be useful to copy a good answer to this site to preserve it. – Tetrad Feb 9 '12 at 16:59
• Good idea, consider it done. – Nic Foster Feb 9 '12 at 17:19
• Thats not the problem, the problem is that I don't know with which line it intersects and since this equition solves even non intersecting lines I have a problem. – Quincy Tynes Feb 9 '12 at 19:33
• You have to run this query with the line segment you're testing against every other line in your game. That may sound inefficient, and it likely will be. To optimize you will need an implementation of spatial partitioning, which will let you determine which line segments for terrain are in the nearby vicinity, at which point you only have to test against those lines. This article covers the basic idea (it covers many types of shapes though), cg.informatik.uni-freiburg.de/course_notes/sim_08_sp.pdf. – Nic Foster Feb 9 '12 at 19:37
• Thx so much for this, really helped me solving a problem! :) – Ben Feb 10 '12 at 19:31

I guess you can handle the rest, but the main idea is written in this wiki page. using the formula above you can find the intersection point of a ray and a segment; note that ray is defined by (x1,y1) and (x2,y2) and the line segment is between (x3,y3) and(x4,y4).

• Can you post at least the main idea behind what you linked to. If that link goes dead this post is of absolutely no help. :( – Richard Marskell - Drackir Feb 9 '12 at 23:25
• @RichardMarskell-Drackir added, though I doubt this question lasts longer than wikipage! – Ali1S232 Feb 10 '12 at 10:34