CODEWITHSUNDEEP
c#mappingdistancetrigonometry
ConditionRacer
ConditionRacer

Reputation: 4498

Algorithm to determine is a point is along a line OR pretty close

Ok, I have an application that uses a mapping system to draw lines. Each line A,B is defined in lat/lon format. When a user clicks the map, all that is given to me is a single point, C, where the user clicked in lat/lon format. I want to give the user the ability to select lines on the map by clicking. The problem is, because of varying zoom levels, it is very difficult for a user to click exactly along the line. The best I can hope for is that they click within some threshold distance that I define. How can I figure out that the user has clicked on, or reasonably close to a line given only this information?

I have a rough idea for an algorithm but I haven't fleshed it out, and I'm not sure if it's the most efficient way to do it. Since there are potentially many lines on the screen at any time, the algorithm needs to be fairly quick.

What I've come up with so far is to first check the distance AC and BC. If either distance is greater than AB, then the user did not click on the line. If it passes this check, then I calculate angles CAB and CBA. If C is exactly on the line, then both angles should be 0, i think, my trig is kind of rusty. Otherwise, to determine if C is "close enough", I will select the smallest of the two calculated angles, and see if it falls below some predefined threshold.

Am I on the right track or way off? Any better ideas?

Upvotes: 1

Views: 867

Answers (1)

Howard
Howard

Reputation: 39177

You may also directly calculate the distance of your point to any line. The wikipedia article gives you the details and also some (pseudo)code.

In your case you also have to consider the end-points separately. I.e. you first have to calculate the parameter t (see article above) and check if it is within the range 0 to length of AB. Then if additionaly the distance lies below a pre-defined amount then the user did click on the line, otherwise not.

The formulas in your case look as follows: 

(C - (A + t * (B-A))) * (B-A) = 0

=> t = (C.x - A.x) * (B.x - A.x) + (C.y - A.y) * (B.y - A.y) / ((B.x - A.X) * (B.x - A.x) + (B.y - A.y) * (B.y - A.y))

If t is below 0 or above 1 the user did not click on the line. Otherwise (i.e. t is between zero and one) you can calculate the distance d using this value t:

d = dist(C, A+t*(B-A)) = sqrt( (C.x - A.x - t * (B.x - A.x))^2 + (C.y - A.y - t * (B.y - A.y))^2)

If d is below some pre-defined threshold you can assume that the user clicked on your line.

Upvotes: 6

Related Questions