如何找到R投影上不规则多边形的最小外接圆？

Question

我想知道如何找到不规则多边形的最小外接圆。我已经在R中处理了空间多边形。

我想在矢量模式下重现某些fragstats指标，因为我很难使用“ landscapemetrics”软件包来处理大量数据。具体来说，我想实现圆圈（http://www.umass.edu/landeco/research/fragstats/documents/Metrics/Shape%20Metrics/Metrics/P11%20-%20CIRCLE.htm）。到目前为止，我找不到最小外接圆的公式或脚本。

非常欢迎您发表所有评论。

谢谢

Answer 1

正如我在评论中提到的那样，我不知道现有的R代码，但是如果您不需要在圆中圈太多的点，则蛮力搜索应该足够快。我刚刚写了这个。 center()函数基于Wikipedia的代码，用于在三角形周围绘制圆； circumcircle()是您想要的功能，可以通过蛮力搜索遍历集合中2或3点的所有圆找到。在我的笔记本电脑上，处理100分需要大约4秒钟。如果您有更大的集合，可以通过转换为C ++来获得可容忍的结果，但这是n^4的增长率，因此您需要一个更好的解决方案对于一个很大的集合。

center <- function(D) {
  if (NROW(D) == 0)
    matrix(numeric(), ncol = 2)
  else if (NROW(D) == 1)
    D
  else if (NROW(D) == 2) {
    (D[1,] + D[2,])/2
  } else if (NROW(D) == 3) {
    B <- D[2,] - D[1,]
    C <- D[3,] - D[1,]
    Dprime <- 2*(B[1]*C[2] - B[2]*C[1])
    c((C[2]*sum(B^2) - B[2]*sum(C^2))/Dprime,
      (B[1]*sum(C^2) - C[1]*sum(B^2))/Dprime) + D[1,]
  } else 
    center(circumcircle(D))
}

radius <- function(D, U = center(D))
  sqrt(sum((D[1,] - U)^2))

circumcircle <- function(P) {
  n <- NROW(P)
  if (n < 3) 
    return(P)
  P <- P[sample(n),]
  bestset <- NULL
  bestrsq <- Inf
  # Brute force search
  for (i in 1:(n-1)) {
    for (j in (i+1):n) {
      D <- P[c(i,j),]
      U <- center(D)
      rsq <- sum((D[1,] - U)^2)
      if (rsq >= bestrsq)
        next
      failed <- FALSE
      for (k in (1:n)[-j][-i]) {
        Pk <- P[k,,drop = FALSE]
        if (sum((Pk - U)^2) > rsq) {
          failed <- TRUE
          break
        }
      }
      if (!failed) {
        bestset <- c(i,j)
        bestrsq <- rsq
      }
    }
  }
  # Look for the best 3 point set
  for (i in 1:(n-2)) {
    for (j in (i+1):(n-1)) {
      for (l in (j+1):n) {
        D <- P[c(i,j,l),]
        U <- center(D)
        rsq <- sum((D[1,] - U)^2)
        if (rsq >= bestrsq)
          next
        failed <- FALSE
        for (k in (1:n)[-l][-j][-i]) {
          Pk <- P[k,,drop = FALSE]
          if (sum((Pk - U)^2) > rsq) {
            failed <- TRUE
            break
          }
        }
        if (!failed) {
          bestset <- c(i,j,l)
          bestrsq <- rsq
        }
      }
    }  
  }
  P[bestset,]
}

showP <- function(P, ...) {
  plot(P, asp = 1, type = "n", ...)
  text(P, labels = seq_len(nrow(P)))
}

showD <- function(D) {
  U <- center(D)
  r <- radius(D, U)
  theta <- seq(0, 2*pi, len = 100)
  lines(U[1] + r*cos(theta), U[2] + r*sin(theta))
}

n <- 100
P <- cbind(rnorm(n), rnorm(n))
D <- circumcircle(P)
showP(P)
showD(D)

这显示输出