Geometry question (mapping)

estebanrey

estebanrey

estebanrey

Soldato
Joined
8 Mar 2007
Posts
10,938
Hi all, probably a simple problem for anyone with a decent knowledge of geometry.

Long story short I'm writing a small application and want to mimic a Sat Navs ability to tell you what road you are on at any given time.

Here's my problem.....

210h7x3.jpg


I know the coordinates of all three points; let's call them 'Ax & Ay', 'Bx & By' and 'Cx & Cy'. For my purposes 'A' is the end of the road, 'B' is the start of the road and 'C' is the vehicle.

So I guess the question is, mathematically how do I test if coordinate 'C' is on the line of a joined to 'B'?

* Ignore bends, I will always be using straight lines.
* The angle of the road/line used above is just an example, the road/line could be in * any orientation, 360 degrees round including 'A' being at the bottom and 'B' being at the top.
* 'C' can obviously be on any part of the line between 'A' and 'B'.
 
Last edited:
Participant said:
But that determines if it falls anywhere on an infinite straight line, not necessarily whether it falls within A and B.
Click to expand...

Then he is writing an application which I presume implies code then it is a simple test to check if the x and y are above and below the A and B coordinates.

If Cx > Ax and Cx > Bx then not between
If Cx < Ax and Cx < Bx then not between
etc
 
Haircut said:
If (cy-ay)/(cx-ax) = (by-cy)/(bx-cx) then c is on the line ab
Click to expand...

Participant said:
But that determines if it falls anywhere on an infinite straight line, not necessarily whether it falls within A and B.
Click to expand...

Not only that but a horizontal line breaks it because you can't divide by zero (with a horizontal line cy is equal to ay producing '0' as the first divider. so it fails the any orientation stipulation.

Thanks for the starter though, I sure we're on the right line here (see what I did there).
 
Last edited:
for the whole division by zero thing you could always put in special cases that first check if the line is horizontal, vertical, or just a dot. It isn't exactly efficient but it would work. i think i did that in one of the programs i wrote at uni that needed a function to check angles of some sort when i was pressed for time

How accurate are the coordinates that you are getting? I know that GPS coordinates can be a little off, so if the coordinates that are being sent to your program are also a little off then you might have to alter the equation Haircut gave you a little bit to determine if it is on the line or not to something like this

If 0.98 < [(cy-ay)/(cx-ax)] / [(by-cy)/(bx-cx)] < 1.02 then its on the line

Makes the division by zero thing a bit harder to solve but its a simple and adjustable way of getting around inaccurate coordinates
 
By Jove I think I got it.....

If (ay = by and by = cy) and ((cx > ax and cx < bx) or (cx < ax and cx > bx) then
'on line (horizontal line) and between points a & b
ElseIf (ax = bx and bx = cy) and ((cy > ay and cy < by) or (cy < ay and cy > by) then
'on line (vertical line) and between points a & b
ElseIf ((cy-ay)/(cx-ax) = (by-cy)/(bx-cx) and ((cy > ay and cy < by) or (cy < ay and cy > by) ) then
'on line (any diagonal) and between points a & b
Else
'Not on line
End if

Reaper 392 said:
How accurate are the coordinates that you are getting? I know that GPS coordinates can be a little off, so if the coordinates that are being sent to your program are also a little off then you might have to alter the equation Haircut gave you a little bit to determine if it is on the line or not to something like this
Click to expand...

Yeah you are right but building in a margin of error is pretty simple (albeit a longer code) I figured once I had the main maths bit down.
 
Last edited:
Here's my final pseudo code to work with, it checks that C is on the line (or near it within a +/- 5% margin of error) and that it is between the two other points for any orientation.

If (ax = bx and (ax/cx => 0.95 and <= 1.05)) and ((cy => ay and cy <= by) or (cy <= ay and cy >= by) then
'on line (vertical line) and between points a & b
ElseIf (ay = by and (ay/cy => 0.95 and <= 1.05)) and ((cx => ax and cx <= bx) or (cx <= ax and cx >= bx) then
'on line (horizontal line) and between points a & b
Elseif (((ay-cy)/(cx-ax)) / ((by-cy)/(cx-bx)) >= 0.95 and <=1.05) and ((cy >= ay and cy <= by) or (cy <= ay and cy >= by) ) then
'on line (any diagonal) and between points a & b
Else
'Not on line
End If

Think that works. Thanks to everyone that helped!
 
Last edited:
I thought there was a nice way to incorporate inaccuracy to this problem somewhere. This method I found needs separate (and pretty trivial) cases when AB is horizontal or vertical, but it shouldn't be too bad. I'm basing it off of what i found here (mostly because of the adjustable diagram which i found very helpful): http://www.mathopenref.com/coordpointdist.html

an added bonus of this is that if the input point C is slightly off of the line AB, the point on the line where C should be is already worked out

first, work out the equation of the line that passes through AB
Then find the equation of the line that is perpendicular to line AB that passes through point C.

If the point where both lines meet is between A and B, then find the distance between that meeting point and C.
If that distance is within your range of error then you are on the line.

If that meeting point is not between A and B then find the distance from A to C and the distance from A to B. Whichever is the smallest value is the distance to the line.
If that smallest distance is within your error range then the point is on the line. If it is outside the error range then it is not on the line.

In the case of AB being a horizontal line, check if the x coordinate is between A and B and if the Y coordinate is within your error range. if this is the case the point is on the line
If this is not the case, check the distance from A to C and the distance from B to C. If the lowest of these distances is within your error range then the point is on the line.
If both of the above are not the case then the point is not on the line.

It should be trivial to convert the above to the case for a vertical line


in programming terms you should be able to reuse a function for "get distance between two points" quite a lot, which should help speed things up a bit

hope that helps (and that i haven't made a stupid mistake as i usually do)

If there's anything you need help with in that method, or if you need me to explain anything in more detail then let me know
 
Last edited:
Mapping GPS measurements to atlas segments is part of what I do professionally.
One important thing to bear in mind is that GPS locations are in spherical coordinates so Cartesian geometry won't work natively, e.g. For distance between 2 points you will need to use the Haversine function. In general to reduce complexity you can transform the geometry to a local Cartesian reference frame (Equatorial ref frame). Also, atlas segments are typically polylines so you will have to iterate over over each linear subline.

After that you have to realise that GPS data is extremely noisy, the points won't lie anywhere close to the atlas and will have a relatively large scatter. Worse still smartphone apply low pass filters that greatly distort the true measurements. Furthermore, atlases contain many errors and are somewhat topological in nature (e.g. Divided high way will often be a single segment for both directions).

To map a stream of GPS points to positions along atlas segments you will need to apply some kind of estimation and localisation algorithm. Typically you would define a multivariate scoring function for possible states , e.g. Distance to segment, velocity and heading matches, hysterises weighting. You also have to check connectivity, i use an A* shortest path on a custom coded digraph (spent today optimisgn the graph code). You then have to apply a state estimate filter, in house we have used things like EKFs and HMM (google the,). My preference is to use a variant on Monte Carlo techniques. In general for efficiency reasons it is wise to treat localisation as a Markov process, I.e the estimatation of the current state is dependent only upon the prior estimate of the last state and the current sensor measurements, but not on previous estimates. Matching polylines geometry when crossing segments is important and there are some fun tricks that speed things up (sadly can't share)

Lastly, finding candidates atlas segments to map a GpS point to in a large atlas will require some kind of spatial index for efficient querying. I use a various trees, quad trees for some uniform point data but atlas data is best served by an R*Tree algorithm.

In summary, GPS nav is nothing like projecting a point to a line....

Can't go into any more details or help, I am under NDA and some of the stuff is under patent application.
 
Last edited:
Thanks DP, looks like I may have some reading to do.

For my purposes I will be using Lats and Longs, which through my job I have access to, including lats/longs for every turn in a round (so every route breaks down into straight lines).

My application is only needed to cover one small city, it doesn't need to work globally so hopefully the curvature issue shouldn't cause too many problems. I'm going to have a play and do a few tests, my immediate thought is to apply a function that takes the input lats and longs and converts that to a coordinate that would be true if you were to take the square area I'm interested in then flattening it.

Thanks for all the input guys
 
You must log in or register to reply here.
Back
Top Bottom