如何找到与坐标集相关的点？

Question

我有一个包含大约5000个地理（WGS84）坐标的集合，它们都在40 km²的范围内。

是否有算法/ R函数可以找到集合外、方形内距离任何给定点最远的点？

我的意思是如何在正方形内找到距离最近点的距离最长的点？

现在，我通过生成等间隔坐标网格，并计算每个网格点到最近集合点的距离来实现这一目标。是否有更少依赖数字计算/非暴力方法？

编辑： 之前提出的问题存在错误。或许这会对你有所帮助：

店铺的坐标集合是该城市中5000家商店的位置。我想找到距离最近商店最远的城市中某个位置。

- mefju

---

方框内的很容易。其他的我不太确定你在问什么。你想要最离群值中最离群的吗？ - Ari B. Friedman

请查看栅格库中的distanceFromPoints函数。 - Jesse Anderson

Answer 1

我认为，如果你要找的点不在盒子的边缘上，则它必须位于点的Voronoi图形的顶点处。如果它在盒子的边缘上，则它必须位于盒子和Voronoi图形边缘的交点上。

因此，如果您计算Voronoi图并使用rgeos将其与盒子相交，那么这将为您提供一组可能的点。然后，您可以使用FNN包计算从这些可能的点到数据点的邻居距离，进行排序，并找到具有最大最近邻的可能点。

这样就可以得到一个精确的点，而不需要进行任何网格化操作。如果现在还没有睡觉，我可以整理出一些代码来做这件事。您可能需要使用deldir包或Voronoi图形。它甚至可能已经做了盒子相交...

好吧，现在还没到睡觉时间。以下是解决方案:

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])
}

编辑版本现在返回一个点，并将角点添加为可能性。

- Spacedman

---

聪明！谢谢你。我相信你说的最远点在 Voronoi 图块的一个顶点上是正确的，但还有一个小细节：它也可能在盒子的四个角之一。为了检查这些角落，你可以在初始分配给 vpts 后添加以下内容：vpts <- rbind(vpts, as.matrix(expand.grid(c(xmin, xmax), c(ymin, ymax))))。 - Josh O'Brien

完成了，而且还将矩阵去重了。我不知道duplicated()函数也可以用于行。太棒了。 - Spacedman

Answer 2

这是一个使用raster包中的多个函数(distanceFromPoints(), maxValue(), Which(), 和 xyFromCell())进行关键计算的示例:

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

- Josh O'Brien