Thread Subject: Distance from coast map

Suppose you have a vector of coordinates listing points around
the coastline of a country - or simply the borders of an inland
country. If you wanted to make a map (contour or heatmap) showing
the minimum distance of any point location from the coast/border,
what would be your approach to solving this problem in MATLAB?
I can think of a couple of 'obvious' ways: 1) construct a grid
of points and for each point do a bisection search for the radius
at which a circle centred on the point intersects the lines that
define the border, and 2) progressively dilate an image of the
coastline, assigning a distance measure (which would be mapped
to colour) at each iteration. The second method would likely be
much faster, but also less accurate because of truncations to
'pixel distance'. Are there better approaches?

I realize this is not a MATLAB-specific question, although I will
implement the solution in MATLAB. (Also, this is *not* homework!)

Looking forward to any suggestions or discussion.

Francis

On 20 Mai, 10:55, Francis Burton <fbur...@nyx.net> wrote:
> Suppose you have a vector of coordinates listing points around
> the coastline of a country - or simply the borders of an inland
> country. If you wanted to make a map (contour or heatmap) showing
> the minimum distance of any point location from the coast/border,
> what would be your approach to solving this problem in MATLAB?
> I can think of a couple of 'obvious' ways: 1) construct a grid
> of points and for each point do a bisection search for the radius
> at which a circle centred on the point intersects the lines that
> define the border, and 2) progressively dilate an image of the
> coastline, assigning a distance measure (which would be mapped
> to colour) at each iteration. The second method would likely be
> much faster, but also less accurate because of truncations to
> 'pixel distance'. Are there better approaches?
>
> I realize this is not a MATLAB-specific question, although I will
> implement the solution in MATLAB. (Also, this is *not* homework!)
>
> Looking forward to any suggestions or discussion.

The border or coastline is presumably represented as an ordered
list of points, or equivalently, a list of edges.

You might want to scan the list for the point or edge which
is closest to the specified point, and maybe refine from there.

You may also want to ask such questions on comp.graphics.algorithms.

Rune

On May 20, 10:13=A0pm, Rune Allnor <all...@tele.ntnu.no> wrote:
> On 20 Mai, 10:55, Francis Burton <fbur...@nyx.net> wrote:
>
>
>
>
>
> > Suppose you have a vector of coordinates listing points around
> > the coastline of a country - or simply the borders of an inland
> > country. If you wanted to make a map (contour or heatmap) showing
> > the minimum distance of any point location from the coast/border,
> > what would be your approach to solving this problem in MATLAB?
> > I can think of a couple of 'obvious' ways: 1) construct a grid
> > of points and for each point do a bisection search for the radius
> > at which a circle centred on the point intersects the lines that
> > define the border, and 2) progressively dilate an image of the
> > coastline, assigning a distance measure (which would be mapped
> > to colour) at each iteration. The second method would likely be
> > much faster, but also less accurate because of truncations to
> > 'pixel distance'. Are there better approaches?
>
> > I realize this is not a MATLAB-specific question, although I will
> > implement the solution in MATLAB. (Also, this is *not* homework!)
>
> > Looking forward to any suggestions or discussion.
>
> The border or coastline is presumably represented as an ordered
> list of points, or equivalently, a list of edges.
>
> You might want to scan the list for the point or edge which
> is closest to the specified point, and maybe refine from there.
>
> You may also want to ask such questions on comp.graphics.algorithms.
>
> Rune- Hide quoted text -
>
> - Show quoted text -

If it's a country, unless it's a pretty small country, you'll need to
use a map projection to get the right answer. Gnomonic projection is
a good one for this. It transforms curves on the Great Circle to
lines on a (distorted) map.

Francis Burton <fburton@nyx.net> wrote in message
<1211273718.794911@irys.nyx.net>...
> Suppose you have a vector of coordinates listing points around
> the coastline of a country - or simply the borders of an inland
> country. If you wanted to make a map (contour or heatmap) showing
> the minimum distance of any point location from the coast/border,
> what would be your approach to solving this problem in MATLAB?
> I can think of a couple of 'obvious' ways: 1) construct a grid
> of points and for each point do a bisection search for the radius
> at which a circle centred on the point intersects the lines that
> define the border, and 2) progressively dilate an image of the
> coastline, assigning a distance measure (which would be mapped
> to colour) at each iteration. The second method would likely be
> much faster, but also less accurate because of truncations to
> 'pixel distance'. Are there better approaches?
>
> I realize this is not a MATLAB-specific question, although I will
> implement the solution in MATLAB. (Also, this is *not* homework!)

Well, it was obvious that it was not homework.
Why would I have known? Because you actually
thought about a possible answer. ;-) Sad, but
true.

Think of the coastline as some smooth curve in
the plane, although in your case, you will just
have a list of points. So we would probably use
a piecewise linear (connect-the-dots) coastline
in practice. This coastline might have an
interesting shape, including a peninsula like
that of Italy or Cape Cod.

As a function of position offshore, you want to
define the function which is defined as the
distance to the nearest point on that coastline
"curve".

If all you want is the nearest neighbor from the
set of search points, then its a nearest neighbor
search. My own ipdm on the file exchange does
this, although I think there is now a kd-tree
based tool on the FEX that will do it faster. You
could also probably do this more elegantly with
a Voronoi tool, but it might not be worth the
time to program it.

If the coastline were really a smooth function,
perhaps a spline that cscvn might produce,
then finding the nearest point on that coastline
would require an optimization tool, that could
find the global minimum of a general smooth
function. This is a more difficult issue to deal
with than you probably want to bother with.

If you wanted to use the piecewise linear
approximation to the coastline, then you need
to find the distance to a list of (connected)
line segments in the plane. Again, its probably
more work than you need.

So simplest and most direct is just to use a
nearest neighbor approach. Build a gridded
surface that defines the distance to the
nearest pixel on the coastline. Define the
elements in the grid that are inshore of the
coastline as NaNs. Then if you want contours,
use contour. Its simple and easy to do. All you
need to do is use meshgrid to generate the
grid, then do a nearest neighbor search for
each point on that grid.

HTH,
John

On 20 Mai, 12:26, NZTideMan <mul...@gmail.com> wrote:
> On May 20, 10:13=A0pm, Rune Allnor <all...@tele.ntnu.no> wrote:
>
>
>
>
>
> > On 20 Mai, 10:55, Francis Burton <fbur...@nyx.net> wrote:
>
> > > Suppose you have a vector of coordinates listing points around
> > > the coastline of a country - or simply the borders of an inland
> > > country. If you wanted to make a map (contour or heatmap) showing
> > > the minimum distance of any point location from the coast/border,
> > > what would be your approach to solving this problem in MATLAB?
> > > I can think of a couple of 'obvious' ways: 1) construct a grid
> > > of points and for each point do a bisection search for the radius
> > > at which a circle centred on the point intersects the lines that
> > > define the border, and 2) progressively dilate an image of the
> > > coastline, assigning a distance measure (which would be mapped
> > > to colour) at each iteration. The second method would likely be
> > > much faster, but also less accurate because of truncations to
> > > 'pixel distance'. Are there better approaches?
>
> > > I realize this is not a MATLAB-specific question, although I will
> > > implement the solution in MATLAB. (Also, this is *not* homework!)
>
> > > Looking forward to any suggestions or discussion.
>
> > The border or coastline is presumably represented as an ordered
> > list of points, or equivalently, a list of edges.
>
> > You might want to scan the list for the point or edge which
> > is closest to the specified point, and maybe refine from there.
>
> > You may also want to ask such questions on comp.graphics.algorithms.
>
> > Rune- Hide quoted text -
>
> > - Show quoted text -
>
> If it's a country, unless it's a pretty small country,

Or Colorado... I was always amused by the outline of Colorado
when I was a kid. These days I'm more annoyed by borders that
obviously were established by drawing with a straight-edge
on some map.

> you'll need to
> use a map projection to get the right answer. =A0Gnomonic projection is
> a good one for this. =A0It transforms curves on the Great Circle to
> lines on a (distorted) map.

Divide and conquer - solve the problem in trivial coordinate
systems first; then refine to whatever geographical system
concerning the problem.

Rune

On May 20, 4:55=A0am, Francis Burton <fbur...@nyx.net> wrote:
> Suppose you have a vector of coordinates listing points around
> the coastline of a country - or simply the borders of an inland
> country. If you wanted to make a map (contour or heatmap) showing
> the minimum distance of any point location from the coast/border,
> what would be your approach to solving this problem in MATLAB?
> I can think of a couple of 'obvious' ways: 1) construct a grid
> of points and for each point do a bisection search for the radius
> at which a circle centred on the point intersects the lines that
> define the border, and 2) progressively dilate an image of the
> coastline, assigning a distance measure (which would be mapped
> to colour) at each iteration. The second method would likely be
> much faster, but also less accurate because of truncations to
> 'pixel distance'. Are there better approaches?
>
> I realize this is not a MATLAB-specific question, although I will
> implement the solution in MATLAB. (Also, this is *not* homework!)
>
> Looking forward to any suggestions or discussion.
>
> Francis

----------------------------------------------------
MATLAB's been there and done that - you're right. What you want to do
is to create a binary image of your map. Perhaps if you have the
boundary, you can use the poly2mask() function. Then simply call the
bwdist function. This is their strange name for the concept which is
more generally called the "Euclidean Distance Map."
Regards,
ImageAnalyst

In article <g0u9b2$dck$1@fred.mathworks.com>,
John D'Errico <woodchips@rochester.rr.com> wrote:
>> I realize this is not a MATLAB-specific question, although I will
>> implement the solution in MATLAB. (Also, this is *not* homework!)
>
>Well, it was obvious that it was not homework.
>Why would I have known? Because you actually
>thought about a possible answer. ;-) Sad, but
>true.

Maybe also the fact that I didn't ask for complete MATLAB code. ;-)

Thanks, guys - you've given me several good ideas.

Francis