Qualquer método eficaz verdadeiramente de uso geral padronizará as representações das formas para que não sejam alteradas mediante rotação, translação, reflexão ou alterações triviais na representação interna.
Uma maneira de fazer isso é listar cada forma conectada como uma sequência alternada de comprimentos de arestas e ângulos (sinalizados), começando de uma extremidade. (A forma deve ser "limpa" no sentido de não ter arestas de comprimento zero ou ângulos retos.) Para tornar isso invariante sob reflexão, negue todos os ângulos se o primeiro diferente de zero for negativo.
(Como qualquer polilinha conectada de n vértices terá n -1 arestas separadas por n -2 ângulos, achei conveniente no Rcódigo abaixo usar uma estrutura de dados que consiste em duas matrizes, uma para os comprimentos das arestas $lengthse a outra para o ângulos, $angles. um segmento de linha não terá ângulos de todo, por isso é importante para manipular matrizes de comprimento zero, de tal estrutura de dados.)
Tais representações podem ser ordenadas lexicograficamente. Alguma permissão deve ser feita para erros de ponto flutuante acumulados durante o processo de padronização. Um procedimento elegante estimaria esses erros em função das coordenadas originais. Na solução abaixo, é usado um método mais simples, no qual dois comprimentos são considerados iguais quando diferem em uma quantidade muito pequena em uma base relativa. Os ângulos podem diferir apenas em uma quantidade muito pequena em uma base absoluta.
Para torná-los invariantes sob a reversão da orientação subjacente, escolha a representação lexicograficamente mais antiga entre a da polilinha e sua reversão.
Para lidar com polilinhas de várias partes, organize seus componentes em ordem lexicográfica.
Para encontrar as classes de equivalência sob transformações euclidianas ,
Crie representações padronizadas das formas.
Execute um tipo lexicográfico das representações padronizadas.
Faça um passe pela ordem classificada para identificar sequências de representações iguais.
O tempo de computação é proporcional a O (n * log (n) * N) em que n é o número de recursos e N é o maior número de vértices em qualquer recurso. Isso é eficiente.
Provavelmente, vale a pena mencionar de passagem que um agrupamento preliminar baseado em propriedades geométricas invariantes facilmente calculáveis, como comprimento da polilinha, centro e momentos sobre esse centro, geralmente pode ser aplicado para otimizar todo o processo. É preciso apenas encontrar subgrupos de características congruentes em cada um desses grupos preliminares. O método completo dado aqui seria necessário para formas que, de outra forma, seriam tão notavelmente semelhantes que tais invariantes simples ainda não as distinguiriam. Recursos simples construídos a partir de dados rasterizados podem ter essas características, por exemplo. No entanto, como a solução fornecida aqui é tão eficiente de qualquer maneira, que, se alguém se esforçar para implementá-la, ela poderá funcionar bem por si só.
Exemplo
A figura da esquerda mostra cinco polilinhas e mais 15 que foram obtidas através de translação aleatória, rotação, reflexão e reversão da orientação interna (que não é visível). A figura da direita os pinta de acordo com sua classe de equivalência euclidiana: todas as figuras de uma cor comum são congruentes; cores diferentes não são congruentes.
Rcódigo a seguir. Quando as entradas foram atualizadas para 500 formas, 500 formas extras (congruentes), com uma média de 100 vértices por forma, o tempo de execução nesta máquina foi de 3 segundos.
Esse código está incompleto: como Rnão possui uma classificação lexicográfica nativa e não senti vontade de codificá-lo do zero, simplesmente executei a classificação na primeira coordenada de cada forma padronizada. Isso será bom para as formas aleatórias criadas aqui, mas para o trabalho de produção, uma classificação lexicográfica completa deve ser implementada. A função order.shapeseria a única afetada por essa alteração. Sua entrada é uma lista de formas padronizadas se sua saída é a sequência de índices em sque a classificaria.
#
# 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)vez decbind(x,y)). É tudo o que você precisa: aspbiblioteca não é usada. Se você gostaria de acompanhar o que é feito em detalhes, eu sugiro que você começa com, digamos,n.shapes <- 2,n.shapes.new <- 3, ep.mean <- 1. Entãoshapes,shapes.stdetc. são todos pequenos o suficiente para serem facilmente inspecionados. A maneira elegante - e "correta" - de lidar com tudo isso seria criar uma classe de representações padronizadas de recursos.Você está pedindo muito com rotação e dilatação arbitrárias! Não tenho certeza de quão útil a distância de Hausdorff estaria lá, mas confira. Minha abordagem seria reduzir o número de casos a serem verificados através de dados baratos. Por exemplo, você pode pular comparações caras se o comprimento das duas cadeias de linhas não for uma proporção inteira ( assumindo a escala inteira / graduada ). Da mesma forma, você pode verificar se a área da caixa delimitadora ou suas áreas convexas do casco estão em uma boa proporção. Tenho certeza de que há muitos cheques baratos que você poderia fazer contra o centróide, como distâncias ou ângulos do início / fim.
Somente então, se você detectar a escala, desfaça-a e faça as verificações realmente caras.
Esclarecimento: Não conheço os pacotes que você está usando. Por razão de número inteiro, eu quis dizer que você deve dividir as duas distâncias, verificar se o resultado é um número inteiro, se não, inverter esse valor (pode ser que você tenha escolhido a ordem errada) e verificar novamente. Se você obtiver um número inteiro ou aproximar-se o suficiente, poderá deduzir que talvez houvesse dimensionamento em andamento. Ou poderia ser apenas duas formas diferentes.
Quanto à caixa delimitadora, você provavelmente obteve pontos opostos do retângulo que o representa, portanto, tirar a área deles é uma aritmética simples. O princípio por trás da comparação de proporção é o mesmo, apenas que o resultado seria ao quadrado. Não se preocupe com cascos convexos se você não conseguir tirá-los do pacote R com agrado, foi apenas uma ideia (provavelmente não é barata o suficiente).
fonte
Um bom método para comparar essas polilinhas seria confiar em uma representação como uma sequência de (distâncias, ângulos de virada) em cada vértice: Para uma linha composta de pontos
P1, P2, ..., PN, essa sequência seria:De acordo com seus requisitos, duas linhas são iguais se, e somente se, as seqüências correspondentes forem as mesmas (módulo a ordem e a direção do ângulo). Comparar sequências numéricas é trivial.
Calculando cada sequência de polilinha apenas uma vez e, como sugerido por lynxlynxlynx, testando a similaridade de sequência apenas para polilinha com as mesmas características triviais (comprimento, número de vértices ...), o cálculo deve ser muito rápido!
fonte