### Bookstore

 Computer Math and Games in Pascal (preview) Lazarus Handbook

### Author Topic: [SOLVED] "Close to track" detection with lat/long coordinates  (Read 1376 times)

#### MarkMLl

• Hero Member
• Posts: 7227
##### [SOLVED] "Close to track" detection with lat/long coordinates
« on: June 05, 2024, 02:32:25 pm »
This continues the discussion of determining whether a point is within a given perimeter at https://forum.lazarus.freepascal.org/index.php/topic,65082.msg495816.html#msg495816

Given two relatively-close points described by lat/long coordinates, believed to be good to around a second of arc, is there a way which is both readable and moderately accurate to determine whether a third point is within some distance (say 50m) either side of the line between them (/which/ side doesn't matter)?

The number of lines to be handled in this way is fairly small, so it would be feasible to precompute the offsets (in arcsecs) perpendicular to each which corresponded to the distance of interest. Or in extremis, it would be possible to expand each line to a rectangle and apply the algorithms discussed in the link above.

MarkMLl
« Last Edit: June 07, 2024, 01:08:57 pm by MarkMLl »
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

#### RayoGlauco

• Full Member
• Posts: 189
• Beers: 1567
##### Re: "Close to track" detection with lat/long coordinates
« Reply #1 on: June 05, 2024, 03:05:40 pm »
This is a geometry problem. You can take latitude as the Y axis and longitude as the X axis. Then the problem is reduced to calculating the distance of a given point (x,y) with respect to the line that passes through (x1,y1) and (x2,y2) .
To err is human, but to really mess things up, you need a computer.

#### RayoGlauco

• Full Member
• Posts: 189
• Beers: 1567
##### Re: "Close to track" detection with lat/long coordinates
« Reply #2 on: June 05, 2024, 03:13:01 pm »
To err is human, but to really mess things up, you need a computer.

#### MarkMLl

• Hero Member
• Posts: 7227
##### Re: "Close to track" detection with lat/long coordinates
« Reply #3 on: June 05, 2024, 03:24:05 pm »
Yes, but that assumes that the ordinate scales are equal: which isn't the case for geographic coordinates in most parts of the World.

With the coordinates given as lat/long, you need to work out the orientation of the original line (or, equivalently, the perpendicular): and then use that to resolve and re-scale the perpendicular distance to metres. I'm sure there's shortcuts for doing that.

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

#### RayoGlauco

• Full Member
• Posts: 189
• Beers: 1567
##### Re: "Close to track" detection with lat/long coordinates
« Reply #4 on: June 05, 2024, 04:12:23 pm »
I think that for small distances, the differences would be negligible. For longer distances, a coefficient based on latitude would possibly be needed. For example:

Code: Pascal  [Select][+][-]
1. distance := distance(x0,y0) * (1 + k * (lat0-lat2))

or something like that (k would depend on the inclination of the line and the distance between P1 and P2).
« Last Edit: June 05, 2024, 04:24:25 pm by RayoGlauco »
To err is human, but to really mess things up, you need a computer.

#### Dzandaa

• Sr. Member
• Posts: 343
• From C# to Lazarus
##### Re: "Close to track" detection with lat/long coordinates
« Reply #5 on: June 05, 2024, 04:52:58 pm »
Regards,
Dzandaa

#### MarkMLl

• Hero Member
• Posts: 7227
##### Re: "Close to track" detection with lat/long coordinates
« Reply #6 on: June 05, 2024, 05:11:47 pm »
I think that for small distances, the differences would be negligible. For longer distances, a coefficient based on latitude would possibly be needed. For example:

Code: Pascal  [Select][+][-]
1. distance := distance(x0,y0) * (1 + k * (lat0-lat2))

or something like that (k would depend on the inclination of the line and the distance between P1 and P2).

The difference is /not/ negligible. In Europe a degree of longitude is roughly 80km, while a degree of Latitude is roughly 111km. Therefore you /have/ to start applying transcendentals, the only question being the most effective way (i.e. possibly trading off readability against efficiency).

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

#### MarkMLl

• Hero Member
• Posts: 7227
##### Re: "Close to track" detection with lat/long coordinates
« Reply #7 on: June 05, 2024, 05:42:32 pm »
Look at:

https://www.movable-type.co.uk/scripts/latlong.html

What do you have in mind there? It appears to be very much oriented to relatively large distances where spherical geometry (i.e. as distinct from non-isotropic scaling) is significant.

I'm beginning to find various things relating to e.g. inshore navigation cross-track error which look useful.

Somewhat later: a number of discussions end up pointing at https://uknowledge.uky.edu/cgi/viewcontent.cgi?article=1040&context=bae_facpub, where it explicitly says

Quote
For calculating XTE, the discrete location samples representing the vehicle’s path must be represented in a localized Cartesian (X, Y) coordinate system. While some location recording equipment may directly provide this information, others (such as that used in this work) provide output in the form of latitude and longitude coordinates. These were simply transformed using the formula and methods described in ISO Standard 12188-1 (ISO, 2010). This provided inputs to the XTE calculation procedure that consisted of a list of points in Cartesian coordinates.

So for the situation I've got where I'm testing (numerous) points against (a small number of) lines, that suggests that the best approach would be to pre-convert to e.g. metres relative to Greenwich and then to use https://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line#Line_defined_by_two_points (credit to Roy, even if he was inclined to brush some of the problems under the carpet :-) which uses fairly basic maths which will be handled efficiently by most FPUs.

This does, of course, raise the question of whether I would be best off converting /everything/ to metres, i.e. including the earlier region handling. However on the balance I think probably not, since the overall question is related to (local, i.e. <15km) navigation and output is likely to include e.g. .gpx files.

MarkMLl
« Last Edit: June 05, 2024, 06:28:18 pm by MarkMLl »
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

#### Paolo

• Hero Member
• Posts: 529
##### Re: [SOLVED] "Close to track" detection with lat/long coordinates
« Reply #8 on: June 09, 2024, 12:29:55 am »
Hello,

a thought of mine. For geometrical, but also mathematical, problems, the solution is generally formulated for a "standard" case, so the real task is to reduce the current problem to a "standard" case. Specifically, if P1 and P2 are two points on the equator it is easy to know if a third point P3 is x-Km away from the point joining the two points. just do

Code: Pascal  [Select][+][-]
1. // Result is a boolean
2.   Result:=(P3.Lon >= P1.Lon) and (P3.Lon <= P2.Lon) and (Abs(P3.Lat) <= Lat_for_the_fixed_Distance)  //NB: P1.Lon < P2.Lon
3.

therefore, given the three points, the problem is to change the coordinate system, through appropriate rotations to transform all the 3 points such that  P1 and P2 are on the equeator, and carry out the test reported above in the final coordinate system.

Not implemented, but it has to work.

#### MarkMLl

• Hero Member
• Posts: 7227
##### Re: [SOLVED] "Close to track" detection with lat/long coordinates
« Reply #9 on: June 09, 2024, 09:59:09 am »
I added a couple more things relating to range and bearing yesterday evening, and the easiest thing appears to be an early coordinate transformation.

I already know that all points are within 15km groundrange, so for practical purposes can assume that the local coordinate system is flat. At that point converting to either relative coordinates in metres or km or to absolute coordinates relative to some distant point makes things much easier, and in practice can probably be done very early in the calculations.

Hence calculations of range, bearing (azimuth) and altitude may be computed with minimal transcendentals.

However I think it is also useful to be able to dump any program-generated regions in e.g. GPX format, so that their correctness can be checked in an external GIS (QGIS, Google Earth running locally on a PC, etc.).

MarkMLl
« Last Edit: June 09, 2024, 12:38:07 pm by MarkMLl »
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

#### Paolo

• Hero Member
• Posts: 529
##### Re: [SOLVED] "Close to track" detection with lat/long coordinates
« Reply #10 on: June 27, 2024, 03:33:39 pm »
Hello MarkMLI,

Just for my curiosity, you can check if the attached code works as expected (if you have time obviously, I don't want to waste your time).

I've spent a few time implementing such generic routines, but I have no real test cases (except trivial cases that seem to work).

In the code the coordinates of Milan and Rome are preset, and the third city is Florence, the calculated distance of Florence to the line Milan-Rome seems OK.

Ciao