I am not very familiar with the m.in.e00 command in GRASS. Is the point

or just the min distance between two polygons or something inbetween. If

states below. If it is inbetween we can do much better. A potentially

returned list from a range query with a bruteforce menthod. That may be

efficient enough. On calculating the min (or max) distance between two

clever triangulation of the polygons.

> 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> > >

> >

> > --

> > 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

> >

> >

>

>

>

> ------------------------------

>

> _______________________________________________

> 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

> ***************************************