[STATSGRASS] Questions on calculating minimum distance between polygons and map attributes after m.in.e00

Thu, Dec 18, 2003 10:50 PM

Hi,
I am not very familiar with the m.in.e00 command in GRASS. Is the point
to compute an all pairs min distance between all polygons in a set
or just the min distance between two polygons or something inbetween. If
it is an all pairs problem then the optimum is O((n*m)^2) as Denis White
states below. If it is inbetween we can do much better. A potentially
easier implementation than the Okabe Miller approach is to just use a
good data structure on the bounding boxes of the polygons and filter the
returned list from a range query with a bruteforce menthod. That may be
efficient enough. On calculating the min (or max) distance between two
polygons one could probably do much better than O((m1*m2)^2) with some
clever triangulation of the polygons. 

Nicholas

Message: 1
Date: Wed, 17 Dec 2003 12:23:52 +0100 (CET)
From: Roger Bivand <Roger.Bivand at nhh.no>
Subject: Re: [R-sig-Geo] FW: [STATSGRASS] Questions on calculating
	minimum	dista ncebetween polygons and map attributes after m.in.e00
To: White.Denis at epamail.epa.gov
Cc: r-sig-geo at stat.math.ethz.ch, kgleditsch at ucsd.edu
Message-ID: <Pine.LNX.4.44.0312171213570.1851-100000 at reclus.nhh.no>
Content-Type: TEXT/PLAIN; charset=ISO-8859-1

On Mon, 15 Dec 2003 White.Denis at epamail.epa.gov wrote:

I am a new member of r-sig-geo and saw your message in
the archives.  I don't know whether you already had
algorithms in mind, or received some responses on this,
but two publications with algorithms are:

Chin F, Wang CA.  1983.  Optimal algorithms for the
intersection and the minimum distance problems between
planar polygons.  IEEE Transactions on Computers,
Vol C-32(12):1203-1207.

Okabe A, Miller HJ.  1996.  Exact computation methods for
calculating distances between objects in a cartographic
database.  Cartography and Geographic Information Systems
Vol 23(4):180-195.

Thanks for interesting references. In other email (I think offlist, but
repeating here to get further response), the idea of using OpenGIS
functions on a database was floated:

http://www.mysql.com/doc/en/Functions_that_test_spatial_relationships_between_ge
ometries.html

(para 10.5.6 in MSQL Manual 4.1) describes a function:

Distance(g1,g2) Returns as a double-precision number the shortest
distance
between any two points in the two geometries.

I'm not sure whether this supports latlong. PostGIS also has the same
function as an OpenGIS function.  http://postgis.refractions.net/ has the
details:

Distance(geometry,geometry) Return the cartesian distance between two
geometries in projected units.

It also has:

distance_spheroid(point, point, spheroid) Returns linear distance between
two lat/lon points given a particular spheroid. See the explanation of
spheroids given for length_spheroid().  Currently only implemented for
points.

as a non-OpenGIS function. Kristian's question is about nation states, so 
latlong is an issue, I believe. This makes it non-trivial, of course!

Any other ideas?

Roger

What I would like to do is to try to use an algorithm
to determine the shortest distance between points on
two states??? outer boundaries, with each state defined
either as a polygon or union of polygons.

_______________________________________________
R-sig-Geo mailing list
R-sig-Geo at stat.math.ethz.ch
https://www.stat.math.ethz.ch/mailman/listinfo/r-sig-geo

-- 
Roger Bivand
Economic Geography Section, Department of Economics, Norwegian School of
Economics and Business Administration, Breiviksveien 40, N-5045 Bergen,
Norway. voice: +47 55 95 93 55; fax +47 55 95 93 93
e-mail: Roger.Bivand at nhh.no



------------------------------

Message: 2
Date: Wed, 17 Dec 2003 08:29:27 -0800
From: White.Denis at epamail.epa.gov
Subject: Re: [R-sig-Geo] FW: [STATSGRASS] Questions on calculating
	minimum	dista ncebetween polygons and map attributes after m.in.e00
To: Roger.Bivand at nhh.no
Cc: r-sig-geo at stat.math.ethz.ch, kgleditsch at ucsd.edu,
	r-sig-geo-bounces at stat.math.ethz.ch
Message-ID:
	<OF0C2BDB7D.E467E6AD-ON88256DFF.0058F5B5-88256DFF.005A959D at epamail.epa.gov>
	
Content-Type: text/plain; charset=UTF-8





Yes, spheroid distance is one issue; computational complexity is
another.  I looked into this when I had a problem of computing pairwise
distances between 10,000 polygons for an application in conservation
biology.  The brute force computational complexity, searching for the
closest pair of points across all pairs of polygons, would be about
O(m^2 * n^2), if there were n polygons with an average of m points, say.

In Kristian's case these numbers are not so prohibitive as the number of
countries is not so many, and he can cut down on the search space for
closest points by eye to some degree.  Using the MySQL function
"distance" may or may not be an efficient algorithm for the single pair
case (haven't looked at it carefully), but it would have to be embedded
in some outer algorithm for the many pairs situation.

I think that the Okabe and Miller approach with Voronoi methods is the
general way to go, but I didn't have time to program it, and couldn't
find an available implementation, so I punted and used a series of
buffered distances (I also had an exponential inverse distance relation
and therefore could set a reasonable maximum buffer size).

Denis

On Mon, 15 Dec 2003 White.Denis at epamail.epa.gov wrote:

I am a new member of r-sig-geo and saw your message in
the archives.  I don't know whether you already had
algorithms in mind, or received some responses on this,
but two publications with algorithms are:

Chin F, Wang CA.  1983.  Optimal algorithms for the
intersection and the minimum distance problems between
planar polygons.  IEEE Transactions on Computers,
Vol C-32(12):1203-1207.

Okabe A, Miller HJ.  1996.  Exact computation methods for
calculating distances between objects in a cartographic
database.  Cartography and Geographic Information Systems
Vol 23(4):180-195.

Thanks for interesting references. In other email (I think offlist,

but

repeating here to get further response), the idea of using OpenGIS
functions on a database was floated:

http://www.mysql.com/doc/en/Functions_that_test_spatial_relationships_between_ge

ometries.html

(para 10.5.6 in MSQL Manual 4.1) describes a function:

Distance(g1,g2) Returns as a double-precision number the shortest

distance

between any two points in the two geometries.

I'm not sure whether this supports latlong. PostGIS also has the same
function as an OpenGIS function.  http://postgis.refractions.net/ has

the

details:

Distance(geometry,geometry) Return the cartesian distance between two
geometries in projected units.

It also has:

distance_spheroid(point, point, spheroid) Returns linear distance

between

two lat/lon points given a particular spheroid. See the explanation of
spheroids given for length_spheroid().  Currently only implemented for
points.

as a non-OpenGIS function. Kristian's question is about nation states,

so

latlong is an issue, I believe. This makes it non-trivial, of course!

Any other ideas?

Roger

What I would like to do is to try to use an algorithm
to determine the shortest distance between points on
two states???????? outer boundaries, with each state defined
either as a polygon or union of polygons.

_______________________________________________
R-sig-Geo mailing list
R-sig-Geo at stat.math.ethz.ch
https://www.stat.math.ethz.ch/mailman/listinfo/r-sig-geo

_______________________________________________
R-sig-Geo mailing list
R-sig-Geo at stat.math.ethz.ch
https://www.stat.math.ethz.ch/mailman/listinfo/r-sig-geo


End of R-sig-Geo Digest, Vol 4, Issue 8
***************************************