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

[Nicholas Lewin-Koh]

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: [phone]; fax [phone]
> 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: [phone]; fax [phone]
> > 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
> ***************************************