How to find point related to set of coordinates?

问题:

I have a set of about 5000 geographical (WGS84) coordinates. All of them are inside 40km square.

Is there any algorithm / R function to find point, inside square and not in the given set, farthest from any point from set?

I mean how to find point in the square where the distance to the nearest point from set is longest?

Now I do it by generating grid of coordinates equally spaced and finding distance from each grid point to the nearest set point. Is there any less numerical / not brute force method?

EDIT: I made mistake in previous version of the question. Maybe this will help:

Set of points are coordinates of the 5000 shops in the city. I want to find place in the city where distance to the nearest shop is the longest.

回答1:

Here's an example that uses several functions (distanceFromPoints(), maxValue(), Which(), and xyFromCell()) from the raster package to perform the key calculations:

# Load required libraries
library(sp)
library(rgdal)
library(raster)

# Create a SpatialPoints object with 10 points randomly sampled from
# the area lying between longitudes 0 and 1 and latitudes 0 and 1
bbox <- matrix(c(0,0,1,1), ncol=2, dimnames = list(NULL, c("min", "max")))
PRJ4 <- CRS("+proj=longlat +datum=WGS84 +ellps=WGS84")
S <- Spatial(bbox = bbox, proj4string = PRJ4)
SP <- spsample(S, 10, type="random")

# Create a raster object covering the same area
R <- raster(extent(bbox), nrow=100, ncol=100, crs=PRJ4)

# Find the coordinates of the cell that is farthest from all of the points
D <- distanceFromPoints(object = R, xy = SP) 
IDmaxD <- Which(D == maxValue(D), cells=TRUE)
(XY <- xyFromCell(D, IDmaxD))
#          x     y
# [1,] 0.005 0.795

# Plot the results
plot(D, main = "Distance map, with most distant cell in red")
points(SP)
points(XY, col="red", pch=16, cex=2)

回答2:

I think that if the point you seek isn't on the edge of the box then it has to be at a vertex of the voronoi tesselation of the points. If it is on the edge of the box then it has to be on the intersection of the box and an edge of the voronoi tesselation.

So if you compute the voronoi tesselation and then use rgeos to intersect it with the box, that gives you a set of possible points. You can then use the FNN package to compute the neighbour distances from those possible points to the data points, sort, and find the possible point with the biggest nearest neighbour.

That gives you an exact point without any of this gridding business. If it wasn't so close to bedtime I'd sort out some code to do it. You probably want the deldir package or voronoi tesselations. It might even already do the box intersection...

Okay, not quite bedtime. Here's the solution:

findM <- function(pts,xmin,xmax,ymin,ymax){
  require(deldir)
  require(FNN)
  d = deldir(pts[,1],pts[,2],rw=c(xmin,xmax,ymin,ymax))

  vpts = rbind(as.matrix(d$dirsgs[,1:2]),as.matrix(d$dirsgs[,3:4]))
  vpts = rbind(vpts,cbind(c(xmin,xmax,xmin,xmax),c(ymin,ymin,ymax,ymax)))
  vpts = vpts[!duplicated(vpts),]

  nn = get.knnx(pts,vpts,k=1)
  ptmin = which(nn$nn.dist==max(nn$nn.dist))

  list(point = vpts[ptmin,,drop=FALSE], dist = nn$nn.dist[ptmin])
}

Edited version now returns one point and adds the corner points as possibles.