Cualquier método efectivo verdaderamente de propósito general estandarizará las representaciones de las formas para que no cambien con la rotación, traslación, reflexión o cambios triviales en la representación interna.
Una forma de hacerlo es enumerar cada forma conectada como una secuencia alterna de longitudes de borde y ángulos (con signo), comenzando desde un extremo. (La forma debe ser "limpia" en el sentido de que no tiene bordes de longitud cero o ángulos rectos). Para hacer que esta invariante bajo reflexión, niegue todos los ángulos si el primero que no es cero es negativo.
(Debido a que cualquier polilínea conectada de n vértices tendrá n -1 aristas separadas por n -2 ángulos, he encontrado conveniente en el Rsiguiente código utilizar una estructura de datos que consta de dos matrices, una para las longitudes de los bordes $lengthsy la otra para las ángulos,. $anglesUn segmento de línea no tendrá ángulos, por lo que es importante manejar matrices de longitud cero en dicha estructura de datos).
Dichas representaciones se pueden ordenar lexicográficamente. Se debe tener en cuenta algunos errores de coma flotante acumulados durante el proceso de estandarización. Un procedimiento elegante estimaría esos errores en función de las coordenadas originales. En la solución a continuación, se usa un método más simple en el que dos longitudes se consideran iguales cuando difieren en una cantidad muy pequeña en una base relativa. Los ángulos pueden diferir solo en una cantidad muy pequeña sobre una base absoluta.
Para hacerlos invariables bajo la inversión de la orientación subyacente, elija la representación lexicográfica más temprana entre la de la polilínea y su inversión.
Para manejar polilíneas de varias partes, organice sus componentes en orden lexicográfico.
Para encontrar las clases de equivalencia en transformaciones euclidianas, entonces,
Crea representaciones estandarizadas de las formas.
Realizar un tipo lexicográfico de las representaciones estandarizadas.
Pase por el orden ordenado para identificar secuencias de representaciones iguales.
El tiempo de cálculo es proporcional a O (n * log (n) * N) donde n es el número de entidades y N es el mayor número de vértices en cualquier entidad. Esto es eficiente
Probablemente vale la pena mencionar de pasada que una agrupación preliminar basada en propiedades geométricas invariantes fácilmente calculadas, como la longitud de la polilínea, el centro y los momentos sobre ese centro, a menudo se puede aplicar para simplificar todo el proceso. Uno solo necesita encontrar subgrupos de características congruentes dentro de cada grupo preliminar. El método completo dado aquí sería necesario para formas que, de lo contrario, serían tan notablemente similares que tales invariantes simples aún no las distinguirían. Las características simples construidas a partir de datos ráster pueden tener tales características, por ejemplo. Sin embargo, dado que la solución dada aquí es tan eficiente de todos modos, que si uno se va a esforzar por implementarla, podría funcionar bien por sí sola.
Ejemplo
La figura de la izquierda muestra cinco polilíneas más 15 más que se obtuvieron de ellas mediante traducción aleatoria, rotación, reflexión e inversión de orientación interna (que no es visible). La figura de la derecha los colorea según su clase de equivalencia euclidiana: todas las figuras de un color común son congruentes; Los diferentes colores no son congruentes.
REl código sigue. Cuando las entradas se actualizaron a 500 formas, 500 formas adicionales (congruentes), con una media de 100 vértices por forma, el tiempo de ejecución en esta máquina fue de 3 segundos.
Este código está incompleto: debido a Rque no tiene una clasificación lexicográfica nativa y no tenía ganas de codificar una desde cero, simplemente realizo la clasificación en la primera coordenada de cada forma estandarizada. Eso estará bien para las formas aleatorias creadas aquí, pero para el trabajo de producción se debe implementar un tipo lexicográfico completo. La función order.shapesería la única afectada por este cambio. Su entrada es una lista de formas estandarizadas sy su salida es la secuencia de índices en los sque se ordenaría.
#
# 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)))
.
rbind(x,y)lugar decbind(x,y)). Eso es todo lo que necesitas: laspbiblioteca no se usa. Si desea seguir lo que se hace en detalle, le sugiero que comience con, digamos,n.shapes <- 2,n.shapes.new <- 3, yp.mean <- 1. Entoncesshapes,shapes.stdetc. son lo suficientemente pequeños como para ser inspeccionados fácilmente. La forma elegante y "correcta" de lidiar con todo esto sería crear una clase de representaciones de características estandarizadas.¡Estás pidiendo mucho con rotación arbitraria y dilatación! No estoy seguro de cuán útil sería la distancia de Hausdorff, pero échale un vistazo. Mi enfoque sería reducir el número de casos para verificar a través de datos baratos. Por ejemplo, podría omitir comparaciones costosas si la longitud de las dos cadenas de líneas no es una relación de enteros ( suponiendo una escala de enteros / graduada ). De manera similar, puede verificar si el área del cuadro delimitador o sus áreas de casco convexo están en una buena relación. Estoy seguro de que hay muchas comprobaciones baratas que podrías hacer contra el centroide, como distancias o ángulos desde el inicio / final.
Solo entonces, si detecta escala, deshaga y realice las comprobaciones realmente costosas.
Aclaración: no sé los paquetes que está utilizando. Por relación de enteros quise decir que debe dividir ambas distancias, verificar si el resultado es un entero, si no, invertir ese valor (podría elegir el orden incorrecto) y volver a verificar. Si obtienes un número entero o lo suficientemente cerca, puedes deducir que quizás estaba ocurriendo una escala. O podría ser solo dos formas diferentes.
En cuanto al cuadro delimitador, probablemente obtuviste puntos opuestos del rectángulo que lo representa, por lo que sacar el área de ellos es simple aritmética. El principio detrás de la comparación de razones es el mismo, solo que el resultado sería al cuadrado. No te molestes con los cascos convexos si no puedes sacarlos de ese paquete R muy bien, fue solo una idea (de todos modos, probablemente no sea lo suficientemente barato).
fuente
Un buen método para comparar estas polilíneas sería confiar 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, dicha secuencia sería:De acuerdo con sus requisitos, dos líneas son iguales si y solo si sus secuencias correspondientes son las mismas (módulo de orden y dirección del ángulo). Comparar secuencias de números es trivial.
Al calcular cada secuencia de polilínea solo una vez y, como lo sugiere lynxlynxlynx, probar la similitud de secuencia solo para polilíneas que tienen las mismas características triviales (longitud, número de vértices ...), ¡el cálculo debería ser realmente rápido!
fuente