Detecting a Click on a Line Segment in XNA

Posted on by Stephane Beniak

So here I was prototyping a new game with XNA, when I ran into a little snag (for those who don’t know, I absolutely love XNA and I’m sad that its future is currently uncertain). I needed to detect if a user had clicked on (or close enough to) an arbitrary line of varying thickness in 2D space. This problem boils down to just finding the distance between a point and a line, but the line is confined to a segment.

Some Code

Now, my usual recourse is to abuse of the almighty Google, but having been an “Applied Linear Algebra” TA for most of my bachelor’s degree, it would have been a little embarrassing if I wasn’t able to come up with an adequate solution myself. So, after a little bit of thought, and slightly more work, here’s my tiny contribution to the betterment of the Internet:

public static float DistanceFromLineToPoint(Vector2 a, Vector2 b, Vector2 p)
{
	Vector2 pointVector = p - a;
	Vector2 lineVector = (b - a);
	lineVector.Normalize();
	float lineLength = (b - a).Length();
	float intersectDistanceFromA = Vector2.Dot(lineVector, pointVector);

	if (intersectDistanceFromA < 0f)
		return -1f;
	if (intersectDistanceFromA > lineLength)
		return -1f;

	lineVector *= intersectDistanceFromA;
	Vector2 intersectPoint = a + lineVector;

	return (p - intersectPoint).Length();
}

So if you’re looking for a quick and dirty solution to whatever it is you’re building, by all means copy paste the above and go on your merry way. But hopefully you’re a little curious about how it works, so please read on for an explanation.

Step 1: Setting Things Up

A line segment is most easily defined by two points, the beginning and the end, and a point is just a point, so that’s what we start with as input parameters, a triplet of points, which might look something like this:

spacer

Then, we need a few basic ingredients before cooking up our solution. We need to find any vector between the line segment and the point (line 3 in the code above), as well as the vector that represents the line segment itself (line 4). Luckily both are easy to do with just some basic vector subtraction. Then, we just need to normalize the line vector (line 5), so it has a length of exactly one unit, but remember its length for later (line 6) so we can get it back.

spacer

Step 2: Applying Magical Math

Now that we have all the pieces we need, this is the part where a (seemingly) magical math function comes and gives us the answer we want. In our case, it’s the dot product, which is simpler than it might seem, so go ahead and glance at the wiki article. In essence, it tells us “how much does the point vector overlap the line vector” by projecting the point vector onto the line vector, like so:

spacer

Note that it returns a number, not a vector, because it simply computes the ratio of how much they “travel in the same direction,” which is another handy way of looking at it. Anyways, after performing that operation (line 7), we now know how to find the intersection point, which is the short name we’ll use to denote “the point on the line at which the distance between the line and the point P is minimized.”

Step 3: Finding An Answer

Now that we have this ratio from the dot product, we can immediately detect if the point is within the ranges of the line segment. If the ratio is negative, it means the intersection point is behind the beginning of the line, and if the ratio is bigger than the line’s length (which we saved earlier), it means the intersection point is past the end of the line. You can choose how you want to handle this case, such as returning the distance from the ends of the line, but for my usage, I just wanted to detect clicks on the line, so I return an error code of a negative length, which means the click was too far (lines 9 through 12).

Finally, if we avoided the cases where the intersection point was beyond the ends of the line, we know that it lies somewhere along the line segment, so we can compute it simply multiplying the line vector by the ratio we found (because recall that the line vector was normalized, so its length was of just one unit), which is on line 14 in the code above. That gives us the offset from point A, so adding it to A (line 15) gives us the exact position of our intersection point. Then, at last, just subtract the intersect point from the original point to get the difference vector, and return its length, which looks something like this:

spacer

This entry was posted in Programming and tagged C#, Linear Algebra, Math, XNA by Stephane Beniak. Bookmark the permalink.

2 thoughts on “Detecting a Click on a Line Segment in XNA

  1. spacer Stepan on said:

    Inspired by a recent discussion on HN, I suggest that whenever you release code for people to use as they wish, you attribute a specific license to it. This is simply due to the fact that the default is copy right (all rights reserved), if no license appears.

    I highly recommend this one:
    sam.zoy.org/wtfpl/

    Reply
    • spacer Stephane Beniak on said:

      Hmm, good call, I wasn’t aware of that. If anyone else is curious, there’s more information in this thread:

      programmers.stackexchange.com/questions/26548/what-is-the-default-software-license

      In any case, I love your choice of license and I’m applying it now spacer

      Reply

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a class="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>