# Check if a point is deviating from a path made by a set of line segments

I'd like to know or have other ideas --other than my solution-- about how to check if a car on a given position (lat, lng) is getting away (let's say a distance D away) from the path where the car should go over. Another condition for my problem is that there will be queries with different points (positions of the car) to the same path.

I proposed this problem as:

Given a path P defined as a set of continuous line segments i.e. {(x1,y1);{(x2,y2)};{(x2,y2);(x3,y3)}; and so on. Where x and y are supposed to be latitude and longitude; a query point Q=(x,y) and a distance D which is the maximum distance Q can deviate from path P. Check if a point Q is deviating from P on a distance greater than D.

My approach is using basic geometry.

As Q will always be different my idea is to create a triangle between Q and all segments in path P and check what kind of triangle it is (right, acute or obtuse) if the triangle is obtuse I don't consider it and mark as Q is deviating from that segment; if the triangule is acute or right I compute the perpendicular distance between Q and the segment. Then I compare this distance with D and save whether or not Q is deviating from S (based on the computed distance). Finally I say there is no deviation if there is at least one segment from which Q is not deviating i.e. the distance between Q and a segment is not greater than D.

Here is a pseudo-code for my approach:

``````isDeviatingFromSegment = [all False]
for each segment S in P:
if triangule between S and Q is right or acute:
tempDistance = PerpendicularDistanceB(Q, S)
if tempDistance > D:
isDeviatingFromSegment[S] = True
else
isDeviatingFromSegment[S] = True

• Why would it matter whether the triangle is acute or obtuse? Consider drawing some examples where `D > |S|` and `D < |S|/2`. Consider also the case that Q is on the line, but outside of the segment – you don't have a triangle in that case. Also read Distance from a point to a line. Note that you can avoid calculating the square root and the absolute value by computing the square of the distance, which is sufficient for your comparisons. – amon Oct 20 '16 at 9:18