Cómo se mide la similitud de objetos SpatialLines

Question

He creado dos SpatialLines objetos en R: .

Estos objetos fueron creados de esta manera:

library(sp)
xy <- cbind(x,y)
xy.sp = sp::SpatialPoints(xy)
spl1 <- sp::SpatialLines(list(Lines(Line(xy.sp), ID="a")))

Ahora quiero de alguna manera a la conclusión de que esta es la misma línea de girar y se volcó, y que la diferencia entre ellos es igual a 0 (es decir, la forma es igual).

Para hacer eso, uno puede usar maptools paquete y rotar la línea #1, por ejemplo:

spl180 <- maptools::elide(spl1, rotate=180)

Cada girado línea, a continuación, debe comprobarse frente a la línea #2 usando rgeos paquete, por ejemplo:

hdist <- rgeos::gDistance(spl180, spl2, byid=FALSE, hausdorff=TRUE)

Sin embargo, esto es tan costosas computacionalmente forma para que coincida SpatialLines objetos, especialmente si el número de objetos es de alrededor de 1000.

Hay alguna forma inteligente de hacer este trabajo?

P. S. por otra parte, el método descrito anteriormente no garantiza que todos los posibles giros y volteretas.

P. S2. Si la línea #1 es ampliada con respecto a la línea #2, la diferencia entre la línea #1 y #2 aún debe ser igual a 0.

ACTUALIZACIÓN:

Answer 1

Cualquier verdaderamente de propósito general eficaz método de estandarizar la representación de las formas , de modo que no cambiarán después de la rotación, traslación, reflexión o trivial cambios en la representación interna.

Una manera de hacer esto es hacer una lista de cada uno de ellos conectado forma como una secuencia alternante de borde y longitudes (firmado) los ángulos, desde uno de los extremos. (La forma debe ser "limpio", en el sentido de no tener longitud cero bordes o ángulos rectos.) Para hacer esta invariante bajo la reflexión, niega todos los ángulos si el primer cero uno es negativo.

(Debido a que cualquier conectados polilínea de n vértices tiene n-1 bordes separados por n-2 ángulos, he encontrado que es conveniente en la R código a continuación para usar una estructura de datos que consta de dos matrices, una para el borde longitudes $lengths y el otro para los ángulos, $angles. Un segmento de línea no tendrá ningún ángulos en todos, por lo que es importante tratar de longitud cero matrices en una estructura de datos.)

Tales representaciones pueden ser ordenados lexicográficamente. Algunos asignación debe ser hecha por errores de punto flotante acumulada durante el proceso de normalización. Un elegante procedimiento de estimación de los errores como una función de las coordenadas originales. En la solución a continuación, un método más simple que se utiliza en el cual dos longitudes son considerados iguales cuando difieren por una cantidad muy pequeña en términos relativos. Los ángulos pueden diferir sólo por una cantidad muy pequeña en forma absoluta.

Para hacerlos invariantes bajo la inversión de la orientación subyacente, elija el lexicográficamente representación más antigua entre la de la polilínea y su reversión.

Manejar multi-parte polilíneas, arreglar sus componentes en orden lexicographic.

Para encontrar las clases de equivalencia bajo Euclidiana transformaciones, a continuación,

• Crear estandarizada de las representaciones de las formas.

• Realizar un lexicográfica de ordenación de la normalización de las representaciones.

• Hacer un pase a través de la orden para identificar las secuencias de la igualdad de las representaciones.

El tiempo de cálculo es proporcional a O(n*log(n)*N), donde n es el número de características y N es el número más grande de los vértices de cualquier característica. Esto es eficiente.

Es probablemente vale la pena mencionar de paso que una agrupación preliminar basado en fácilmente calculada invariante propiedades geométricas, tales como la polilínea de longitud, centro, y momentos alrededor de ese centro, a menudo puede ser aplicado a agilizar todo el proceso. Uno sólo necesita encontrar subgrupos de congruencia de las características dentro de cada grupo preliminar. El método completo que se dan aquí sería necesario para las formas que de otra manera sería tan extraordinariamente similar que estas simples invariantes todavía no los distinguen. Características simples construido a partir de una trama de datos podría tener tales características, por ejemplo. Sin embargo, ya que la solución que aquí es tan eficiente de todos modos, que si uno se va a ir al esfuerzo de implementación, se puede trabajar bien por sí mismo.

---

Ejemplo

La mano izquierda de la figura muestra cinco polilíneas, además de 15 más que se obtuvieron a partir de los a través de random traslación, rotación, reflexión, y la reversión de la orientación interna (que no es visible). La mano derecha de la figura colores de acuerdo a sus Euclidiana equivalencia de la clase: todas las cifras de un color común son congruentes; diferentes colores no son congruentes.

R código de la siguiente manera. Cuando las entradas se han actualizado para 500 formas, 500 extra (congruentes) las formas, con una media de 100 vértices por la forma, el tiempo de ejecución en esta máquina fue de 3 segundos.

Este código es incompleta: porque R no tiene una unidad de ordenación lexicográfica, y yo no tenía ganas de codificación uno desde cero, yo simplemente realizar la clasificación en la primera coordenada de cada forma estandarizada. Que estará bien por el azar de las formas creadas aquí, pero para el trabajo de producción de un total de ordenación lexicográfica debe ser implementado. La función order.shape sería el único afectado por este cambio. Su entrada es una lista de forma estandarizada s , y su salida es la secuencia de los índices en s que tipo es.

#
# Create random shapes.
#
n.shapes <- 5      # Unique shapes, up to congruence
n.shapes.new <- 15 # Additional congruent shapes to generate
p.mean <- 5        # Expected number of vertices per shape
set.seed(17)       # Create a reproducible starting point
shape.random <- function(n) matrix(rnorm(2*n), nrow=2, ncol=n)
shapes <- lapply(2+rpois(n.shapes, p.mean-2), shape.random)
#
# Randomly move them around.
#
move.random <- function(xy) {
  a <- runif(1, 0, 2*pi)
  reflection <- sign(runif(1, -1, 1))
  translation <- runif(2, -8, 8)
  m <- matrix(c(cos(a), sin(a), -sin(a), cos(a)), 2, 2) %*%
    matrix(c(reflection, 0, 0, 1), 2, 2)
  m <- m %*% xy + translation
  if (runif(1, -1, 0) < 0) m <- m[ ,dim(m)[2]:1]
  return (m)
}
i <- sample(length(shapes), n.shapes.new, replace=TRUE)
shapes <- c(shapes, lapply(i, function(j) move.random(shapes[[j]])))
#
# Plot the shapes.
#
range.shapes <- c(min(sapply(shapes, min)), max(sapply(shapes, max)))
palette(gray.colors(length(shapes)))
par(mfrow=c(1,2))
plot(range.shapes, range.shapes, type="n",asp=1, bty="n", xlab="", ylab="")
invisible(lapply(1:length(shapes), function(i) lines(t(shapes[[i]]), col=i, lwd=2)))
#
# Standardize the shape description.
#
standardize <- function(xy) {
  n <- dim(xy)[2]
  vectors <- xy[ ,-1, drop=FALSE] - xy[ ,-n, drop=FALSE]
  lengths <- sqrt(colSums(vectors^2))
  if (which.min(lengths - rev(lengths))*2 < n) {
    lengths <- rev(lengths)
    vectors <- vectors[, (n-1):1]
  }
  if (n > 2) {
    vectors <- vectors / rbind(lengths, lengths)
    perps <- rbind(-vectors[2, ], vectors[1, ])
    angles <- sapply(1:(n-2), function(i) {
      cosine <- sum(vectors[, i+1] * vectors[, i])
      sine <- sum(perps[, i+1] * vectors[, i])
      atan2(sine, cosine)
    })
    i <- min(which(angles != 0))
    angles <- sign(angles[i]) * angles
  } else angles <- numeric(0)
  list(lengths=lengths, angles=angles)
}
shapes.std <- lapply(shapes, standardize)
#
# Sort lexicographically.  (Not implemented: see the text.)
#
order.shape <- function(s) {
  order(sapply(s, function(s) s$lengths[1]))
}
i <- order.shape(shapes.std)
#
# Group.
#
equal.shape <- function(s.0, s.1) {
  same.length <- function(a,b) abs(a-b) <= (a+b) * 1e-8
  same.angle <- function(a,b) min(abs(a-b), abs(a-b)-2*pi) < 1e-11
  r <- function(u) {
    a <- u$angles
    if (length(a) > 0) {
      a <- rev(u$angles)
      i <- min(which(a != 0))
      a <- sign(a[i]) * a
    }
    list(lengths=rev(u$lengths), angles=a)
  }
  e <- function(u, v) {
    if (length(u$lengths) != length(v$lengths)) return (FALSE)
    all(mapply(same.length, u$lengths, v$lengths)) &&
      all(mapply(same.angle, u$angles, v$angles))
    }
  e(s.0, s.1) || e(r(s.0), s.1)
}
g <- rep(1, length(shapes.std))
for (j in 2:length(i)) {
  i.0 <- i[j-1]
  i.1 <- i[j]
  if (equal.shape(shapes.std[[i.0]], shapes.std[[i.1]])) 
    g[j] <- g[j-1] else g[j] <- g[j-1]+1
}
palette(rainbow(max(g)))
plot(range.shapes, range.shapes, type="n",asp=1, bty="n", xlab="", ylab="")
invisible(lapply(1:length(i), function(j) lines(t(shapes[[i[j]]]), col=g[j], lwd=2)))

Answer 2

Estás pidiendo mucho con rotación arbitraria y la dilatación! No estoy seguro de lo útil de la distancia de Hausdorff estaría allí, pero échale un vistazo. Mi enfoque sería reducir el número de casos de comprobar a través de hoteles de datos. Por ejemplo, usted podría saltar caro comparaciones si la longitud de los dos linestrings no es una relación entero (suponiendo entero/graduado de escala). Usted podría asimismo comprobar si el cuadro delimitador de la zona o sus convex hull áreas están en una buena relación. Estoy seguro de que hay un montón de hoteles de cheques que usted puede hacer contra el centro de gravedad, como las distancias o ángulos de inicio/fin.

Sólo entonces, si usted detecta escala, deshacer y hacer lo que realmente caro cheques.

Aclaración: No sé los paquetes que están utilizando. Por relación entero quiero decir que usted debe dividir ambas distancias, compruebe si el resultado es un número entero, si no, invertir ese valor (podría ser elegido el orden equivocado) y vuelva a comprobar. Si usted recibe un entero o lo suficientemente cerca, se puede deducir que tal vez había escalado pasando. O simplemente podría ser de dos formas diferentes.

Como para el cuadro delimitador, usted probablemente tiene puntos opuestos del rectángulo que representa, por lo que el área de ellos es simple aritmética. El principio detrás de la relación de comparación es el mismo, sólo que el resultado sería elevada al cuadrado. No te molestes con cascos convexos si usted no puede conseguir fuera de ese paquete de R muy bien, era solo una idea (probablemente no lo suficientemente barato como para que de todos modos).

Answer 3

Un buen método para comparar estas polilíneas sería la de basarse en una representación como una secuencia de (distancias, ángulos de giro) en cada vértice: Para una línea compuesta de puntos P1, P2, ..., PN, la secuencia sería:

(distancia(P1P2), ángulo(P1,P2,P3), la distancia(P2P3),... ,ángulo(P(N-2),P(N-1),PN), la distancia(P(N-1)PN)).

De acuerdo a sus requerimientos, dos líneas son iguales si y sólo si sus correspondientes secuencias son las mismas (modulo el orden y el ángulo de dirección). Comparando el número de secuencias es trivial.

Mediante el cálculo de cada polilínea secuencia sólo una vez y, según lo sugerido por lynxlynxlynx, las pruebas de la similitud de secuencia sólo para polilínea con el mismo trivial características (longitud, número de vértices...), el cálculo debe ser muy rápido!