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 > > > > > > > -- > > 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 > *************************************** |
Free forum by Nabble | Edit this page |