Tell me more ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.
up vote 10 down vote favorite
3

I have a set of points as a shapefile and I want to find (the coordinates) of a new point which will have the longest possible distance from each of the existing points. Is that possible? If yes, is there any sample VB code? Thanks Demetris

share|improve this question
Do you mean you want a new point for each already-existing point, or one point that is somehow "farthest" from all of them? And by farthest, do you mean "the other side of the globe"? If so, you can just multiply the latitude by -1, and add 180 to the longitude (subtracting 360 if the resultant value is > 180) if you have them in decimal degrees. – nmpeterson Nov 29 '11 at 14:43
I think the interesting question would be: given existing points scattered across the globe, find a new point on the globe farthest from all existing points. – Kirk Kuykendall Nov 29 '11 at 14:54
It would, effectively be the point at the end of an isosceles triangle, at which the distance is limited only by how far out you wish to go. If I have read the question properly, you want the point furthest from both of them? Equally? – Hairy Nov 29 '11 at 14:56
1  
Oh!My post created a fantastic discussion and material! NMpeterson:Firstly, I have to say that my points are within a small flat area; so no need for globe calculations. I am looking for the second issue raised; i.e.one point that is somehow "farthest" from all of the existing points. So, please focus on this. – Demetris Nov 29 '11 at 20:13

4 Answers

up vote 5 down vote accepted

Kirk Kukendall's recommendation to construct a spherical Voronoi diagram (Thiessen polygons) is a good one, but might have some technical hitches to work out. In the meantime, as an alternative, one can apply the standard raster solution as described on another thread. Use spherical distances instead of Euclidean distances.

Here is an example using five points, here given as (lat, lon):

 82.7051   -145.256
 60.3321     81.2881
-17.076     105.125
-38.792    -122.686
  0.000     180.000

Distance map

On this spherical shortest distance map (which spans the entire globe from -180 to 180 degrees longitude and -90 to 90 degrees latitude) the points are shown with large red dots, the distances increase with brightness, and the small black dot near (-15.3268, -2.04352) marks the point of maximum distance of 11,227 km. (Distances were computed in the ITRF00 ellipsoidal datum.)

The resolution of this grid is one degree. To get a more precise solution, one can zoom into such a point (and into any other local maximum with a sufficiently close value to the global maximum) and repeat the calculation on a smaller but higher-resolution grid.

share|improve this answer
much prettier than vectors. Not sure why I thought rasters required a flat earth model. – Kirk Kuykendall Nov 29 '11 at 18:15
Pretty, yes, but inefficient. It would be nice to see the vector-based spherical Voronoi solution work out. – whuber♦ Nov 29 '11 at 18:17
@Whuber:How can you get automatically the coordinates of the black point?" – Demetris Dec 1 '11 at 10:47
@Demetris One way is to compute the maximum value on the grid, select all cells equal to that value, and use the coordinates of that cell's center. – whuber♦ Dec 1 '11 at 15:46
@Whuber: Many thanks. This is a good idea. However, I have to clip the output raster based on a feature class (a uniques polygon). Can I do this? – Demetris Dec 1 '11 at 19:09
show 3 more comments
up vote 5 down vote

enter image description here

I've never tried this but it seems like this would work:

Create a 3D voronoi diagram of the sphere. This resulting polygons will be roughly centered on the original existing (seed) points.

Loop through each resulting vertex to find the one that is farthest from its closest existing point. This point should be the most remote point on the globe.

share|improve this answer
This is a great idea (+1). But what does the spherical Voronoi diagram look like when all the points lie within a common hemisphere? The code you refer to obtains it with a convex hull, but it seems that will not work. – whuber♦ Nov 29 '11 at 17:24
hmm, yeah, I guess even if they aren't all in a common hemisphere there will be one polygon that lacks a seed point. What if you constructed a point for it by using the antipodal point of the convex hulls' centroid? Then, in addition to looping through each vertex, this convex-antipode-point would be examined to see if it is further from its neighbors than the max vertex distance. – Kirk Kuykendall Nov 29 '11 at 17:42
That was my initial thought, but the antipodal points will create artifactual polygons. Think about what would happen in your illustration if the antipode to every point were included, for instance! There's probably a solution of this nature, but it seems like it's not straightforward. – whuber♦ Nov 29 '11 at 17:53
up vote 1 down vote

You could use a Cost-Weighted Distance Function to identify how far away every cell in your raster is from all other points.

share|improve this answer
What cost would you use? – whuber♦ Nov 29 '11 at 17:03
If you set the cost to be one unit; you could identify what the furthest point would be based on distance. – djq Nov 29 '11 at 17:14
@whuber Though perhaps this is no different to calculating the euclidean distance approach already mentioned. – djq Nov 29 '11 at 17:21
That's Euclidean distance. Actually, it's not even that: it's a weird kind of octagonal distance (circles are actually octagons). In this situation (distances from points only, with no barriers), it's much more accurate and much faster to compute either a Euclidean distance or spherical distance grid directly, rather than trying to exploit CostDistance for this. – whuber♦ Nov 29 '11 at 17:22
I am not sure that cost weighted distance fucntion would help because I need the coordinates of just one point and I have an exsiting vector set of points;but I will try. Thanks. – Demetris Nov 29 '11 at 20:17
show 2 more comments
up vote 1 down vote

As far as I know, this "Pole of Inaccessability" analysis has to be done iteratively.

An iterative raster approach would be appropriate as long as you are looking at a small area with minimal distortion from projection. For each cell, compute the distance to all points, then take the minimum distance. The cell with the highest value is the pole. You can also use Euclidean Distance in Spatial Analyst to accomplish this.

An iterative vector approach is more complicated. Garcia-Castellanos et al 2007 describe an iterative method based on a spherical earth. It appears that they have made their C code available online. I can imagine ways of doing this in Arc with buffers, but it would still iterative and slow.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.