如何在R语言中获取不规则细长多边形的两个端点？

首先，我完全理解你遇到的困扰：你手头有个闭合的细长多边形（顶点按顺序排列），想找到视觉上的两个端点，还要算出这两个点沿环的两条路径长度，同时需要O(n)复杂度的高效方案。

问题分析 #

你之前的思路是找沿环距离为周长一半的点对，但这种方法针对的是“半周长匹配点”，而非视觉上的端点——后者本质是多边形中欧氏距离最远的点对，所以才会得到不符合预期的结果。我们需要调整方向，先定位到最远点对（也就是你说的24和74），再计算对应的环路径长度。

O(n)解决方案步骤 #

1. 预处理：计算累积路径距离数组

首先快速计算每个顶点到起点的沿环累积距离，这一步是严格O(n)复杂度：

# 计算相邻顶点间的线段距离
n <- nrow(x)
seg_dist <- sqrt((x[-1,1] - x[-n,1])^2 + (x[-1,2] - x[-n,2])^2)
# 补上最后一个顶点到第一个顶点的闭合距离
seg_dist <- c(seg_dist, sqrt((x[1,1]-x[n,1])^2 + (x[1,2]-x[n,2])^2))

# 预分配累积距离数组，cum_dist[i]表示从点1到点i的沿环距离（点1到自身为0）
cum_dist <- numeric(n+1)
cum_dist[1] <- 0
for (i in 2:(n+1)) {
  cum_dist[i] <- cum_dist[i-1] + seg_dist[i-1]
}
perimeter <- cum_dist[n+1]  # 多边形总周长

这里用预分配数组代替你原代码里的rbind，避免了重复复制数据的开销，效率更高。

2. O(n)寻找最远点对（欧氏距离）

对于简单闭合多边形（你的数据看起来属于这类），旋转卡壳算法可以在O(n)时间内找到欧氏距离最远的点对，也就是你要的视觉端点：

# 旋转卡壳实现（要求顶点按顺时针/逆时针顺序排列）
max_dist <- 0
best_p1 <- 1
best_p2 <- 2

# 复制顶点数组处理闭合边界
x_ext <- rbind(x, x[1,])

for (i in 1:n) {
  # 移动指针p2，直到下一个点的距离不再增大
  while (sqrt((x_ext[i+1,1]-x_ext[best_p2+1,1])^2 + (x_ext[i+1,2]-x_ext[best_p2+1,2])^2) > 
         sqrt((x_ext[i+1,1]-x_ext[best_p2,1])^2 + (x_ext[i+1,2]-x_ext[best_p2,2])^2)) {
    best_p2 <- best_p2 %% n + 1
  }
  # 计算当前点对的欧氏距离，更新最远点对
  current_dist <- sqrt((x[i,1]-x[best_p2,1])^2 + (x[i,2]-x[best_p2,2])^2)
  if (current_dist > max_dist) {
    max_dist <- current_dist
    final_p1 <- i
    final_p2 <- best_p2
  }
}

cat("找到的端点索引：", final_p1, final_p2, "\n")
cat("端点间欧氏距离：", max_dist, "\n")

这个算法通过双指针遍历，每个指针最多移动n次，总时间复杂度为O(n)，针对你的数据应该能精准定位到24和74。

3. 计算两点在环上的两条路径长度

有了累积距离数组，计算两条路径长度就是O(1)的操作：

# 确保索引小的在前，方便计算
if (final_p1 > final_p2) {
  temp <- final_p1
  final_p1 <- final_p2
  final_p2 <- temp
}

# 路径1：从final_p1到final_p2的沿环正向距离
path_length1 <- cum_dist[final_p2] - cum_dist[final_p1]
# 路径2：反向环路径距离，即总周长减去正向距离
path_length2 <- perimeter - path_length1

cat("环上两条路径长度：", path_length1, path_length2, "\n")

为什么你的原代码会出错？ #

你原代码的思路是寻找“沿环距离为半周长”的点对，但这种点对的欧氏距离不一定是最大的——尤其是当多边形不是正圆形或凸多边形时，半周长对应的点对和视觉上的端点（最远点对）可能完全不重合。而视觉上的端点本质是整个多边形中欧氏距离最远的两个点，所以用旋转卡壳找最远点对才是正确的方向。

内容的提问来源于stack exchange，提问作者Peter.k