# How to calculate the nearest point on a line to a given point

**URL:** <https://discourse.julialang.org/t/how-to-calculate-the-nearest-point-on-a-line-to-a-given-point/105743>\
**Category:** Geo\
**Tags:** linearalgebra, math, geometry, geospatial\
**Created:** [November 3, 2023, 7:03am UTC](https://discourse.julialang.org/t/how-to-calculate-the-nearest-point-on-a-line-to-a-given-point/105743 "2023-11-03T07:03:59Z")\
**Posts on this page:** 17\
**Page:** 1

<div class="post-metadata">

**Author:** ![Chamika\_Kasun](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chamika_kasun/32/202926_2.png) [@Chamika\_Kasun](https://discourse.julialang.org/u/Chamika_Kasun)\
**Post date:** [November 3, 2023, 7:03am UTC](https://discourse.julialang.org/t/how-to-calculate-the-nearest-point-on-a-line-to-a-given-point/105743/1 "2023-11-03T07:03:59Z")

</div>

I’ve a line string that has long/lat coordinates as follows:

```julia
[
          [
            146.54294815408372,
            -36.04985956921628
          ],
          [
            146.5457684472937,
            -36.04924988190973
          ],
          [
            146.54706548053542,
            -36.04879871026288
          ],
          [
            146.54919201177802,
            -36.047176909745176
          ],
          [
            146.55074543531066,
            -36.04585993436855
          ]
        ]

```

And a point input like this:

```julia
[
          146.54376257030356,
          -36.04616479173944
        ]

```

So, if we given these two input to a function, I need to calculate the nearest point on that line. As shown in the following picture, Black dots shows the line input and orange dot shows the expected output from the function.

 ![Screenshot 2023-11-03 at 5.54.09 pm](https://global.discourse-cdn.com/julialang/original/3X/8/7/87bccacf5f0feda4826f0efc14ea7e191183fcb6.png)

---

<div class="post-metadata">

**Author:** ![jaksaa](https://avatars.discourse-cdn.com/v4/letter/j/91b2a8/32.png) [@jaksaa](https://discourse.julialang.org/u/jaksaa)\
**Post date:** [November 3, 2023, 9:12am UTC](https://discourse.julialang.org/t/how-to-calculate-the-nearest-point-on-a-line-to-a-given-point/105743/2 "2023-11-03T09:12:21Z")

</div>

Calculate the [Euclidean distance - Wikipedia](https://en.wikipedia.org/wiki/Euclidean_distance)

---

<div class="post-metadata">

**Author:** ![barucden](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/barucden/32/26154_2.png) [@barucden](https://discourse.julialang.org/u/barucden)\
**Post date:** [November 3, 2023, 10:38am UTC](https://discourse.julialang.org/t/how-to-calculate-the-nearest-point-on-a-line-to-a-given-point/105743/3 "2023-11-03T10:38:27Z")

</div>

1. Parse your input to get a list of line segments (\vec{s}\_i, \vec{t}\_i).

2. Project your point \vec{p} onto each line segment to get \vec{q}\_i:

Let \vec{v}\_i = \vec{t}\_i - \vec{s}\_i and \vec{p}\_i = \vec{p} - \vec{s}\_i. Then \vec{s}\_i + t \vec{v}\_i, where t = \frac{\vec{v}^T \vec{p}\_i}{\vec{v}\_i^T \vec{v}\_i}, is the orthogonal projection onto _line_ (\vec{s}\_i, \vec{t}\_i). You are interested in _line segments_, so we need to clamp the parameter t. So, \vec{q}\_i = \vec{s}\_i + \min(1, \max(0, t)) \vec{v}\_i.

1. Use \vec{q}\_i with the minimum distance d\_i from \vec{p}:

You can use the squared euclidean distance, which is simply a dot product: d\_i = (\vec{p} - \vec{q}\_i)^T (\vec{p} - \vec{q}\_i).

In julia, the second point can be implemented like this

```julia
using LinearAlgebra
# given a point `p` and a line segment starting at point `s` and ending at point `t`, 
# find a point on that line that is closest to `p`
function nearest_point_on_line(p, s, t)
    @assert ndim(s) == ndim(t) == ndim(p)
    v = (t - s)
    t = clamp((v ⋅ (p - s)) / (v ⋅ v), 0, 1)
    return s + t * v
end

```

---

<div class="post-metadata">

**Author:** ![visr](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/visr/32/17204_2.png) [@visr](https://discourse.julialang.org/u/visr)\
**Post date:** [November 3, 2023, 10:34pm UTC](https://discourse.julialang.org/t/how-to-calculate-the-nearest-point-on-a-line-to-a-given-point/105743/4 "2023-11-03T22:34:24Z")

</div>

Just to add a solution using [GEOS](https://libgeos.org/) `nearestPoints`, which works between a larger set of geometries and is battle-tested:

```julia
import LibGEOS

linestring = LibGEOS.LineString([
    [146.54294815408372, -36.04985956921628],
    [146.5457684472937, -36.04924988190973],
    [146.54706548053542, -36.04879871026288],
    [146.54919201177802, -36.047176909745176],
    [146.55074543531066, -36.04585993436855],
])
point = LibGEOS.Point(146.54376257030356, -36.04616479173944)

on_linestring, on_point = LibGEOS.nearestPoints(linestring, point)

```

We can check the result visually:

```julia
using CairoMakie, GeoInterfaceMakie
# enable plotting LibGEOS geometries
GeoInterfaceMakie.@enable LibGEOS.AbstractGeometry

fig, ax, p = plot(linestring; axis=(aspect=DataAspect(),))
plot!(ax, point)
plot!(ax, on_linestring)
fig

```

 ![plot](https://global.discourse-cdn.com/julialang/original/3X/e/2/e2cd96c2eaa395146ddf774b34304e73b6e97054.png)

---

<div class="post-metadata">

**Author:** ![Chamika\_Kasun](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chamika_kasun/32/202926_2.png) [@Chamika\_Kasun](https://discourse.julialang.org/u/Chamika_Kasun)\
**Post date:** [November 4, 2023, 12:27am UTC](https://discourse.julialang.org/t/how-to-calculate-the-nearest-point-on-a-line-to-a-given-point/105743/5 "2023-11-04T00:27:30Z")

</div>

Amazing @visr , You’re a lifesaver. This is exactly what I needed.

Just a small question along the same, Since these line strings are on the earth’s surface, how would it affect the accuracy of the returning on\_linestring value?

---

<div class="post-metadata">

**Author:** ![joa-quim](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/joa-quim/32/227_2.png) [@joa-quim](https://discourse.julialang.org/u/joa-quim)\
**Post date:** [November 4, 2023, 12:36am UTC](https://discourse.julialang.org/t/how-to-calculate-the-nearest-point-on-a-line-to-a-given-point/105743/6 "2023-11-04T00:36:54Z")

</div>

The problem of the GEOS solution is … it’s not correct because GEOS is a Cartesian library. When working with geographical coordinates you want the point to be along a great circle. In this case the difference is small, but it is no zero. GMT computes it though I find some issues that need to be ironed up. Namely, to compute this one need to save the lines segments in a file first

```julia
using GMT

gmtwrite("line.dat", [146.54294815408372 -36.04985956921628; 146.5457684472937 -36.04924988190973; 146.54706548053542 -36.04879871026288; 146.54919201177802 -36.047176909745176; 146.55074543531066 -36.04585993436855])

pt2 = mapproject([146.54376257030356 -36.04616479173944], dist2line="line.dat")

1×5 GMTdataset{Float64, 2}
 Row │ col.1 col.2 col.3 col.4 col.5
─────┼───────────────────────────────────────────────
   1 │ 146.544 -36.0462 376.851 146.545 -36.0495

```

The the result is in columns 4 & 5 (column 3 is the distance in meters).  
Also PrettyTables is not printing enough decimals in this case, so we need to

```julia
julia> pt2[4]
146.544839684871

julia> pt2[5]
-36.049450668819865

```

For reference, the GEOS solution is

```julia
julia> on_linestring
POINT (146.54448928065796 -36.04952641048415)

```

If the line segment was longer, the difference between Cartesian and Geographic would be larger.

---

<div class="post-metadata">

**Author:** ![visr](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/visr/32/17204_2.png) [@visr](https://discourse.julialang.org/u/visr)\
**Post date:** [November 4, 2023, 6:56am UTC](https://discourse.julialang.org/t/how-to-calculate-the-nearest-point-on-a-line-to-a-given-point/105743/7 "2023-11-04T06:56:14Z")

</div>

Indeed it’s good to stress that GEOS assumes a plane. I added the answer by @joa-quim to my plot as a red dot to show the difference.

 ![plot_2](https://global.discourse-cdn.com/julialang/original/3X/6/e/6e7008322f13db6ef805bc8a41ff7d6ea74fd5dd.png)

You could also project your points first using e.g. [Proj.jl](https://github.com/JuliaGeo/Proj.jl). In time it would also be nice to be able to use [S2 Geometry](https://s2geometry.io/), which assumes a sphere.

---

<div class="post-metadata">

**Author:** ![Chamika\_Kasun](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chamika_kasun/32/202926_2.png) [@Chamika\_Kasun](https://discourse.julialang.org/u/Chamika_Kasun)\
**Post date:** [November 4, 2023, 9:33am UTC](https://discourse.julialang.org/t/how-to-calculate-the-nearest-point-on-a-line-to-a-given-point/105743/8 "2023-11-04T09:33:41Z")

</div>

> [@joa-quim](#):
>
> ```julia
> gmtwrite("line.dat", [146.54294815408372 -36.04985956921628; 146.5457684472937 -36.04924988190973; 146.54706548053542 -36.04879871026288; 146.54919201177802 -36.047176909745176; 146.55074543531066 -36.04585993436855])
> 
> ```

Oh nice @joa-quim , This is exactly what I needed. Appreciate the help mate. Just wondering are you by any chance familiar with this error ? I’m using Mac with M1 processor.

Failed to precompile GMT [5752ebe1-31b9-557e-87aa-f909b540aa54] to /Users/cbandara/.julia/compiled/v1.6/GMT/jl\_rcWYt7.  
ERROR: LoadError: SystemError: opening file “/Users/cbandara/.julia/packages/GMT/1kBBX/deps/deps.jl”: No such file or directory

When I tried to install this libaray, it keeps giving me this error. I’m using Mac with M1 processor.

---

<div class="post-metadata">

**Author:** ![Chamika\_Kasun](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chamika_kasun/32/202926_2.png) [@Chamika\_Kasun](https://discourse.julialang.org/u/Chamika_Kasun)\
**Post date:** [November 4, 2023, 9:34am UTC](https://discourse.julialang.org/t/how-to-calculate-the-nearest-point-on-a-line-to-a-given-point/105743/9 "2023-11-04T09:34:38Z")

</div>

Thanks @visr, Appreciate the help on this.

Btw, by any chance are you familiar with this error ? I got this when I try to add the library ?

Failed to precompile GMT [5752ebe1-31b9-557e-87aa-f909b540aa54] to /Users/cbandara/.julia/compiled/v1.6/GMT/jl\_rcWYt7.  
ERROR: LoadError: SystemError: opening file “/Users/cbandara/.julia/packages/GMT/1kBBX/deps/deps.jl”: No such file or directory

---

<div class="post-metadata">

**Author:** ![joa-quim](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/joa-quim/32/227_2.png) [@joa-quim](https://discourse.julialang.org/u/joa-quim)\
**Post date:** [November 4, 2023, 11:31am UTC](https://discourse.julialang.org/t/how-to-calculate-the-nearest-point-on-a-line-to-a-given-point/105743/10 "2023-11-04T11:31:30Z")

</div>

Hmm, that file (`deps.jl`) is generated by the build process. Don’t know why it was not in your case.  
Try to run `import Pkg; Pkg.build("GMT")`. If it doesn’t solve it better to move this into a GMT.jl issue

---

<div class="post-metadata">

**Author:** ![Dan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dan/32/42581_2.png) [@Dan](https://discourse.julialang.org/u/Dan)\
**Post date:** [November 4, 2023, 12:34pm UTC](https://discourse.julialang.org/t/how-to-calculate-the-nearest-point-on-a-line-to-a-given-point/105743/11 "2023-11-04T12:34:24Z")

</div>

There is the issue of multiple results with the same (or almost the same distance). Perhaps an `eps` parameter will help to determine closest points, and a vector/set returned. Or a `findfirst` logic, or return the closest point and the gap to the next closest point.  
The simplest example to think of is the middle of an equilatral triangle.

---

<div class="post-metadata">

**Author:** ![Chamika\_Kasun](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chamika_kasun/32/202926_2.png) [@Chamika\_Kasun](https://discourse.julialang.org/u/Chamika_Kasun)\
**Post date:** [November 4, 2023, 10:28pm UTC](https://discourse.julialang.org/t/how-to-calculate-the-nearest-point-on-a-line-to-a-given-point/105743/13 "2023-11-04T22:28:06Z")

</div>

You mean using the mapproject function from GMT ?

---

<div class="post-metadata">

**Author:** ![Dan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dan/32/42581_2.png) [@Dan](https://discourse.julialang.org/u/Dan)\
**Post date:** [November 4, 2023, 10:34pm UTC](https://discourse.julialang.org/t/how-to-calculate-the-nearest-point-on-a-line-to-a-given-point/105743/14 "2023-11-04T22:34:13Z")

</div>

I mean, when the input is something like this:

 ![equilateral](https://global.discourse-cdn.com/julialang/original/3X/e/3/e353494d5ebbb1778e078f793db8b2ef39128bd1.png)

The result could be any of the red points. And it isn’t clear how to choose which one, or to return them all.

---

<div class="post-metadata">

**Author:** ![joa-quim](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/joa-quim/32/227_2.png) [@joa-quim](https://discourse.julialang.org/u/joa-quim)\
**Post date:** [November 4, 2023, 11:02pm UTC](https://discourse.julialang.org/t/how-to-calculate-the-nearest-point-on-a-line-to-a-given-point/105743/15 "2023-11-04T23:02:20Z")

</div>

Tried a case like that (a rectangle to make it simple) in GMT and it returned only one point. Presumably the first it found.

---

<div class="post-metadata">

**Author:** ![rafael.guerra](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rafael.guerra/32/216610_2.png) [@rafael.guerra](https://discourse.julialang.org/u/rafael.guerra)\
**Post date:** [November 4, 2023, 11:31pm UTC](https://discourse.julialang.org/t/how-to-calculate-the-nearest-point-on-a-line-to-a-given-point/105743/16 "2023-11-04T23:31:05Z")

</div>

To output multiple nearest points within a specified tolerance:

![Closest_point_to_equilateral_triangle_path](https://global.discourse-cdn.com/julialang/original/3X/b/9/b9083e4b3d0bbfc4121e35708a109a3d0080d4ee.png)

> **Code**
>
> ```julia
> # Assumes that the input line nodes are spatially ordered
> 
> distance(P1, P2) = hypot(P1[1] - P2[1], P1[2] - P2[2])
> 
> dot(x,y) = sum(a*b for (a,b) in zip(x,y))
> 
> # Adapted from @barucden
> # Given a line segment starting at point S[1] and ending at point S[2], 
> # find a point on that line that is closest to P0
> function nearest_point_on_segment(S, P0)
> V = S[2] - S[1]
> t = clamp(dot(V, P0 - S[1]) / dot(V, V), 0., 1.)
> return S[1] + t * V
> end
> 
> # Input data
> P = [[0.0, 0.0], [1.0, 0.0], [0.5, sqrt(3)/2], [0.0, 0.0] ]
> P0 = [0.5, sqrt(3)/6]
> 
> # Find the closest points on each of the segments
> S = [[P[i], P[i+1]] for i in 1:length(P)-1]
> Pn = nearest_point_on_segment.(S, Ref(P0))
> d = distance.(Pn, Ref(P0))
> dmin = minimum(d)
> ϵ = 1e-3 * dmin # tolerance on distance
> ix = findall(x -> abs(x - dmin) < ϵ, d)
> 
> # Plot results
> using Plots
> p = plot(first.(P), last.(P), m=:o, ms=3, ratio=1, lims=(-0.1,1.1))
> scatter!((P0[1], P0[2]), c=:red, label="P0")
> for i in ix; scatter!((Pn[i][1], Pn[i][2]), c=:red, m=:x, label="P$i"); end
> p
> 
> ```

---

<div class="post-metadata">

**Author:** ![Chamika\_Kasun](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chamika_kasun/32/202926_2.png) [@Chamika\_Kasun](https://discourse.julialang.org/u/Chamika_Kasun)\
**Post date:** [November 7, 2023, 8:56am UTC](https://discourse.julialang.org/t/how-to-calculate-the-nearest-point-on-a-line-to-a-given-point/105743/17 "2023-11-07T08:56:28Z")

</div>

@Dan Ahh, Yes that makes sense. This is the issue with LibGEOS library, based on the answer provided by @visr , does that mean on\_linestring can have multiple values when the line string is almost a triangle?

---

<div class="post-metadata">

**Author:** ![juliohm](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/juliohm/32/215266_2.png) [@juliohm](https://discourse.julialang.org/u/juliohm)\
**Post date:** [November 7, 2023, 11:45am UTC](https://discourse.julialang.org/t/how-to-calculate-the-nearest-point-on-a-line-to-a-given-point/105743/18 "2023-11-07T11:45:59Z")

</div>

> [@Chamika\_Kasun](#):
>
> @Dan Ahh, Yes that makes sense. This is the issue with LibGEOS library, based on the answer provided by @visr , does that mean on\_linestring can have multiple values when the line string is almost a triangle?

@Chamika_Kasun if you ever feel the need to modify these algorithms or use a different combination of functions without reaching out to external libraries not written in Julia, consider reading the source code of Meshes.jl.

Regarding distance calculations, we plan to add more methods [here](https://github.com/JuliaGeometry/Meshes.jl/blob/master/src/distances.jl) after we finish the implementation of a related set of features. Regarding nearest neighbors, take a look at the examples [here](https://juliageometry.github.io/MeshesDocs/stable/algorithms/neighborsearch.html).