Drawing Non-Overlapping Shapes in R

Question

I am working with the R Programming language.

Recently, I learned about the following problem: Suppose you have 100 coordinate points - what is the smallest shape that will enclose these 100 points?

To answer this question, I learned about something called the "Convex Hull" (https://en.wikipedia.org/wiki/Convex_hull) which is exactly this. Here is an example in R of how to determine the convex hull of a given set of points:

library(ggplot2)
library(sf)


# simulate data
set.seed(123)
n <- 100
df <- data.frame(longitude = runif(n, -180, 180),
                 latitude = runif(n, -90, 90))

# find the convex hull
hull <- chull(df$longitude, df$latitude)
hull <- c(hull, hull[1])

# visualize results
p <- ggplot(df, aes(x = longitude, y = latitude)) +
  geom_point() +
  geom_polygon(data = df[hull, ], aes(x = longitude, y = latitude), fill = "red", alpha = 0.5)


# optional : convert to shapefile 
hull_df <- df[hull, ]

# optional : convert to shapefile 
hull_sf <- st_as_sf(hull_df, coords = c("longitude", "latitude"), crs = 4326)

My Question: Suppose I have a similar problem - but now are there different "classes" of points (e.g. red class, blue class, green class). Now, I want to identify 3 convex hulls - but I want none of the convex hulls to overlap with each other.

When I tried to do this:

set.seed(123)
n <- 100
df <- data.frame(longitude = runif(n, -180, 180),
                 latitude = runif(n, -90, 90),
                 color = sample(c("red", "blue", "green"), n, replace = TRUE))

# Find the convex hull of the points for each color class
hulls <- lapply(unique(df$color), function(color) {
  chull(df[df$color == color, c("longitude", "latitude")])
})

# Create scatter plot with convex hulls
p <- ggplot(df, aes(x = longitude, y = latitude)) +
  geom_point(aes(color = color)) +
  lapply(seq_along(hulls), function(i) {
    geom_polygon(data = df[df$color == unique(df$color)[i], ][hulls[[i]], ],
                 aes(x = longitude, y = latitude), fill = unique(df$color)[i], alpha = 0.5)
  })


# optional steps
hull_sfs <- lapply(seq_along(hulls), function(i) {
  st_as_sf(df[df$color == unique(df$color)[i], ][hulls[[i]], ],
           coords = c("longitude", "latitude"), crs = 4326)
})


hull_sf_combined <- do.call(rbind, hull_sfs)


st_write(hull_sf_combined, "hulls.shp")

Problem: As we can see here - the convex hulls for the different color classes were identified, but they all overlap with each other now. d

Thanks!

Note: Is the "Concave Hull" a better choice for this kind of problem?

library(concaveman)

# find concave hull
concave_hull <- concaveman(as.matrix(df))
concave_hull_df <- as.data.frame(concave_hull)
names(concave_hull_df) <- c("x", "y")



# scatter plot with concave hull
p2 <- ggplot(df, aes(x = x, y = y)) +
  geom_point() +
  geom_polygon(data = concave_hull_df, aes(x = x, y = y), fill = "blue", alpha = 0.5) +
  ggtitle("Concave Hull")

Answer 1

If I understand you correctly, you are trying to identify areas according to the nearest points. You can do this via nearest in terra:

set.seed(123)
n <- 100
df <- data.frame(longitude = runif(n, -180, 180),
                 latitude = runif(n, -90, 90),
                 color = sample(c("red", "blue", "green"), n, replace = TRUE))

library(terra)
#> terra 1.7.3
library(ggplot2)
#> Warning: package 'ggplot2' was built under R version 4.2.3

v <- vect(df, geom = c("longitude", "latitude"))
grid <- vect(expand.grid(lon = seq(-180, 180), lat = seq(-90, 90)))

grid <- nearest(grid, v)
#> Warning: [perim] unknown CRS. Results can be wrong
grid$color <- v$color[grid$to_id]
grid <- as.data.frame(grid)

ggplot(df, aes(longitude, latitude, fill = color)) +
  geom_raster(aes(x = from_x, y = from_y, fill = color), data = grid,
              alpha = 0.2) +
  geom_point(shape = 21) +
  scale_fill_identity(guide = guide_legend())

^{Created on 2023-08-06 with reprex v2.0.2}