Voronois con distintas distancias

Especulando sobre la diferencia en la práctica entre distintas métricas ($latex l_1$, $latex l_2$, $latex l_\infty$, etc.), construi una serie de diagramas de Voronoi usado métricas arbitrarias.

En la Wikipedia se comparan gráficamente $latex l_1$, $latex l_2$ (o euclídea y Manhattan). Mi código,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
library(data.table)
library(reshape2)
library(grid)

n <- 20
dim.image <- 1000
puntos <- data.frame(id = 1:n,
                      x0 = runif(n) * dim.image,
                      y0 = runif(n) * dim.image)
colores <- rainbow(n)

voronoi <- function(p){
  tmp <- data.table(expand.grid(
      x = 1:dim.image,
      y = 1:dim.image, id = 1:n), key = "id")
  tmp <- merge(tmp, puntos, by = "id")

  distancia <- function(a, b, c, d, p)
    (abs(a-c)^p + abs(b-d)^p)^(1/p)

  tmp$distancia <- distancia(tmp$x,
    tmp$y, tmp$x0, tmp$y0, p)
  tmp[, rank := rank(distancia, ties = "random"),
    by = c("x", "y")]

  rejilla <- tmp[tmp$rank == 1,]
  rejilla$x0 <- rejilla$y0 <-
    rejilla$distancia <- rejilla$rank <- NULL

  rejilla$color <- colores[rejilla$id]

  imagen <- as.matrix(dcast(rejilla, x ~ y, value.var = "color")[,-1])

  grid.raster(imagen)
}

permite usar más en función del parámetro p.

Así, voronoi(1) da

vioronoi_p1

(nótese el ángulo de los segmentos de frontera) y voronoi(2),

voronoi_p2

donde las fronteras son segmentos (de mediatriz entre parejas de puntos). Con un valor de p alto (una aproximación a la norma $latex l_\infty$, voronoi(100), se obtiene

voronoi_p_infty

que tampoco difiere sustancialmente de las anteriores.

Y para los amigos de la experimentación, aquí va voronoi(0.8) (recuérdese que $latex l_{0.8}$ no es una métrica: no respeta la desigualdad triangular, genera bolas no convexas, etc.),

voronoi_p_08

donde se aprecian las consecuencias de lo antedicho.