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
       isDeviatingFromSegment[S] = True

for item in isDeviatingFromSegment:
     if item is False:
         answer = Q_IS_NOT_DEVIATING

As you can see, for each query I iterate the whole path which is linear. I am wondering if I'm dealing right with the problem or if I should use a data structure to reduce query time, or maybe study another theory that will fit better for this problem.

Thanks in advance.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.