Path: news.mathworks.com!not-for-mail
From: "John D'Errico" <woodchips@rochester.rr.com>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Distance from coast map
Date: Tue, 20 May 2008 10:32:02 +0000 (UTC)
Organization: John D'Errico (1-3LEW5R)
Lines: 73
Message-ID: <g0u9b2$dck$1@fred.mathworks.com>
References: <1211273718.794911@irys.nyx.net>
Reply-To: "John D'Errico" <woodchips@rochester.rr.com>
NNTP-Posting-Host: webapp-02-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1211279522 13716 172.30.248.37 (20 May 2008 10:32:02 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Tue, 20 May 2008 10:32:02 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 869215
Xref: news.mathworks.com comp.soft-sys.matlab:469433


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