Każda skuteczna metoda prawdziwie ogólnego zastosowania ustandaryzuje reprezentacje kształtów , aby nie ulegały zmianie po obrocie, translacji, odbiciu lub trywialnych zmianach reprezentacji wewnętrznej.
Jednym ze sposobów na to jest wyszczególnienie każdego połączonego kształtu jako naprzemiennej sekwencji długości krawędzi i (podpisanych) kątów, zaczynając od jednego końca. (Kształt powinien być „czysty” w tym sensie, że nie ma krawędzi zerowych ani prostych kątów.) Aby ten niezmiennik był odbijany, zaneguj wszystkie kąty, jeśli pierwszy niezerowy jest ujemny.
(Ponieważ jakakolwiek połączona polilinia n wierzchołków będzie miała n- 1 krawędzi oddzielonych n- kątami 2, w Rponiższym kodzie uznałem za wygodne użycie struktury danych składającej się z dwóch tablic, jednej dla długości krawędzi, $lengthsa drugiej dla kąty $angles,. Segment linii w ogóle nie będzie miał kątów, dlatego ważne jest, aby obsługiwać tablice o zerowej długości w takiej strukturze danych.)
Takie przedstawienia można uporządkować leksykograficznie. Należy uwzględnić pewne błędy zmiennoprzecinkowe nagromadzone podczas procesu normalizacji. Elegancka procedura oszacowałaby te błędy w funkcji pierwotnych współrzędnych. W poniższym rozwiązaniu zastosowano prostszą metodę, w której dwie długości są uważane za równe, gdy różnią się względnie bardzo małą ilością . Kąty mogą się różnić tylko bardzo małą wartością bezwzględną.
Aby stały się niezmiennikami przy odwróceniu orientacji leżącej u podstaw, wybierz najwcześniejsze leksykograficznie przedstawienie między polilinią a jej odwróceniem.
Aby obsługiwać polilinie wieloczęściowe, ustaw ich komponenty w porządku leksykograficznym.
Aby znaleźć klasy równoważności w transformacjach euklidesowych ,
Twórz standardowe reprezentacje kształtów.
Wykonaj leksykograficzny typ znormalizowanych reprezentacji.
Przejdź przez posortowaną kolejność, aby zidentyfikować sekwencje równych reprezentacji.
Czas obliczania jest proporcjonalny do O (n * log (n) * N), gdzie n to liczba cech, a N to największa liczba wierzchołków w dowolnej funkcji. To jest wydajne.
Prawdopodobnie warto wspomnieć mimochodem, że wstępne grupowanie oparte na łatwo obliczalnych niezmiennych właściwościach geometrycznych, takich jak długość polilinii, środek i momenty wokół tego środka, często można zastosować w celu usprawnienia całego procesu. Wystarczy znaleźć podgrupy przystających funkcji w każdej takiej wstępnej grupie. Podana tutaj pełna metoda byłaby potrzebna dla kształtów, które w przeciwnym razie byłyby tak niezwykle podobne, że takie proste niezmienniki wciąż by ich nie rozróżniały. Proste funkcje zbudowane z danych rastrowych mogą mieć na przykład takie cechy. Ponieważ jednak podane tutaj rozwiązanie jest tak wydajne, że jeśli ktoś podejmie wysiłek jego wdrożenia, może samo w sobie działać dobrze.
Przykład
Rysunek po lewej stronie pokazuje pięć polilinii plus 15 innych, które zostały uzyskane z nich przez losowe tłumaczenie, obrót, odbicie i odwrócenie orientacji wewnętrznej (która nie jest widoczna). Prawa figura koloruje je zgodnie z klasą równoważności euklidesowej: wszystkie figury tego samego koloru są zgodne; różne kolory nie są zgodne.
Rkod następuje. Kiedy dane wejściowe zostały zaktualizowane do 500 kształtów, 500 dodatkowych (przystających) kształtów, ze średnią 100 wierzchołków na kształt, czas wykonania na tym komputerze wynosił 3 sekundy.
Ten kod jest niekompletny: ponieważ Rnie ma rodzimego sortowania leksykograficznego i nie miałem ochoty kodować go od zera, po prostu wykonuję sortowanie według pierwszej współrzędnej każdego znormalizowanego kształtu. Będzie to dobrze w przypadku tworzonych tutaj losowych kształtów, ale do prac produkcyjnych należy wdrożyć pełny rodzaj leksykograficzny. Ta funkcja order.shapemiałaby wpływ tylko na tę funkcję . Jego dane wejściowe to lista znormalizowanych kształtów, sa dane wyjściowe to sekwencja indeksów, sktóre by je posortowały.
#
# 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)))
.