R语言技术问询：如何强制凹包形状无重叠？

已完成的操作步骤 #

1. 模拟数据集并绘制散点图 #

使用ggplot2、sf和concaveman包完成数据模拟与散点图绘制，代码如下：

library(ggplot2)
library(sf)
library(concaveman)

# simulate data
set.seed(123)

df1 <- data.frame(longitude = rnorm(100,10,1),
                 latitude = rnorm(100,10,1), color = "red")

df2 <- data.frame(longitude = rnorm(100,8,1),
                 latitude = rnorm(100,8,1), color = "blue")

df = rbind(df1, df2)

ggplot(df, aes(x=longitude, y=latitude, color=color)) +
  geom_point()

2. 绘制Concave Hulls（凹包）并可视化 #

基于上述数据绘制两类点的凹包，代码如下：

hull_red_df <- data.frame(longitude = hull_red[, 1], latitude = hull_red[, 2], color = "red")

hull_blue_df <- data.frame(longitude = hull_blue[, 1], latitude = hull_blue[, 2], color = "blue")

hull_df <- rbind(hull_red_df, hull_blue_df)

ggplot() +
  geom_point(data = df, aes(x = longitude, y = latitude, color = color)) +
  geom_polygon(data = hull_df, aes(x = longitude, y = latitude, group = color, fill = color), alpha = 0.4) +
  scale_color_manual(values = c("red", "blue")) +
  scale_fill_manual(values = c("red", "blue"))

核心问题 #

能否在绘制形状前、绘制过程中或绘制完成后，添加条件强制多个形状（2个及以上）不重叠？例如，检测某类点是否处于另一类形状范围内，通过循环调整直至无重叠；或是否存在更适合的形状/算法便于实现该条件？

解决方案 #

一、基于现有凹包的重叠修正方案 #

如果要基于已有的凹包调整，核心思路是检测重叠区域→裁剪重叠部分→循环修正直到无重叠，可以借助sf包的空间运算功能实现：

1. 将凹包转为sf对象：先把hull_red和hull_blue转为sf多边形，方便进行空间计算

# 假设hull_red是concaveman生成的矩阵，先转为sf多边形
hull_red_sf <- st_polygon(list(hull_red)) %>% st_sfc() %>% st_sf(color = "red")
hull_blue_sf <- st_polygon(list(hull_blue)) %>% st_sfc() %>% st_sf(color = "blue")

2. 检测并裁剪重叠区域：使用st_intersection找到重叠部分，再用st_difference减去重叠区域，设置迭代次数直到重叠面积小于阈值：

# 计算初始重叠
overlap <- st_intersection(hull_red_sf, hull_blue_sf)
overlap_area <- st_area(overlap)

# 设置阈值，比如面积小于0.01时停止迭代
threshold <- units::set_units(0.01, "m^2") # 单位根据数据调整

while (overlap_area > threshold) {
  # 对红色凹包裁剪重叠部分
  hull_red_sf <- st_difference(hull_red_sf, overlap)
  # 重新计算重叠
  overlap <- st_intersection(hull_red_sf, hull_blue_sf)
  overlap_area <- ifelse(nrow(overlap) > 0, st_area(overlap), 0)
}

3. 可视化修正后的无重叠凹包：把修正后的sf对象转为数据框再用ggplot绘制

# 转为数据框
hull_red_new_df <- st_coordinates(hull_red_sf) %>% as.data.frame() %>% rename(longitude = X, latitude = Y) %>% mutate(color = "red")
hull_blue_new_df <- st_coordinates(hull_blue_sf) %>% as.data.frame() %>% rename(longitude = X, latitude = Y) %>% mutate(color = "blue")
hull_new_df <- rbind(hull_red_new_df, hull_blue_new_df)

ggplot() +
  geom_point(data = df, aes(x = longitude, y = latitude, color = color)) +
  geom_polygon(data = hull_new_df, aes(x = longitude, y = latitude, group = color, fill = color), alpha = 0.4) +
  scale_color_manual(values = c("red", "blue")) +
  scale_fill_manual(values = c("red", "blue"))

二、更适合无重叠需求的替代算法/形状 #

如果不想事后修正，也可以直接生成天然无重叠的形状，推荐两种方式：

1. Voronoi图（泰森多边形）：基于点集生成的Voronoi图天然保证区域无重叠，每个区域对应点的影响范围，适合严格无重叠的场景。用sf包的st_voronoi实现：

# 将所有点转为sf对象
points_sf <- st_as_sf(df, coords = c("longitude", "latitude"))
# 生成Voronoi图
voronoi <- st_voronoi(st_union(points_sf)) %>% st_collection_extract("POLYGON")
# 关联原始点的颜色属性
voronoi_sf <- st_sf(geometry = voronoi, color = df$color[st_nearest_feature(points_sf, voronoi)])

# 可视化
ggplot() +
  geom_sf(data = voronoi_sf, aes(fill = color), alpha = 0.4) +
  geom_point(data = df, aes(x = longitude, y = latitude, color = color)) +
  scale_color_manual(values = c("red", "blue")) +
  scale_fill_manual(values = c("red", "blue"))

2. 基于距离的缓冲区调整：先为每类点生成缓冲区，通过类中心点距离调整缓冲区半径，确保缓冲区不重叠：

# 计算每类点的中心
center_red <- df1 %>% summarise(longitude = mean(longitude), latitude = mean(latitude))
center_blue <- df2 %>% summarise(longitude = mean(longitude), latitude = mean(latitude))
# 计算中心距离
center_dist <- sqrt((center_red$longitude - center_blue$longitude)^2 + (center_red$latitude - center_blue$latitude)^2)
# 设置缓冲区半径为距离的一半（加余量避免相切）
buffer_radius <- center_dist / 2.1

# 生成缓冲区
red_buffer <- st_as_sf(center_red, coords = c("longitude", "latitude")) %>% st_buffer(buffer_radius)
blue_buffer <- st_as_sf(center_blue, coords = c("longitude", "latitude")) %>% st_buffer(buffer_radius)

# 可视化
ggplot() +
  geom_sf(data = red_buffer, fill = "red", alpha = 0.4) +
  geom_sf(data = blue_buffer, fill = "blue", alpha = 0.4) +
  geom_point(data = df, aes(x = longitude, y = latitude, color = color)) +
  scale_color_manual(values = c("red", "blue"))

内容的提问来源于stack exchange，提问作者stats_noob