Любой действительно эффективный метод общего назначения будет стандартизировать представления форм, чтобы они не изменялись при вращении, перемещении, отражении или тривиальных изменениях во внутреннем представлении.
Один из способов сделать это - перечислить каждую соединенную фигуру в виде чередующейся последовательности длин ребер и (подписанных) углов, начиная с одного конца. (Форма должна быть «чистой» в том смысле, что она не имеет ребер нулевой длины или прямых углов.) Чтобы сделать этот инвариант при отражении, отрицательными являются все углы, если первый ненулевой является отрицательным.
(Поскольку любая соединенная ломаная из n вершин будет иметь n -1 ребер, разделенных n -2 углами, я посчитал удобным в приведенном Rниже коде использовать структуру данных, состоящую из двух массивов, один для длин ребер $lengthsи другой для углы $angles. У линейного сегмента вообще не будет углов, поэтому важно обрабатывать массивы нулевой длины в такой структуре данных.)
Такие представления можно заказать лексикографически. Некоторый учет должен быть сделан для ошибок с плавающей запятой, накопленных в процессе стандартизации. Элегантная процедура оценила бы эти ошибки как функцию исходных координат. В приведенном ниже решении используется более простой метод, в котором две длины считаются равными, когда они отличаются на очень небольшую величину на относительной основе. Углы могут отличаться только на очень небольшую величину в абсолютном выражении.
Чтобы сделать их инвариантными при обращении базовой ориентации, выберите лексикографически раннее представление между представлением ломаной и ее обращением.
Для обработки многокомпонентных полилиний расположите их компоненты в лексикографическом порядке.
Чтобы найти классы эквивалентности при евклидовых преобразованиях, тогда
Создайте стандартизированные представления форм.
Выполните лексикографическую сортировку стандартизированных представлений.
Сделайте проход через отсортированный порядок, чтобы идентифицировать последовательности равных представлений.
Время вычислений пропорционально O (n * log (n) * N), где n - количество объектов, а N - наибольшее количество вершин в любом объекте. Это эффективно.
Вероятно, стоит попутно упомянуть, что предварительная группировка, основанная на легко вычисляемых инвариантных геометрических свойствах, таких как длина полилинии, центр и моменты вокруг этого центра, часто может применяться для рационализации всего процесса. Нужно только найти подгруппы конгруэнтных признаков в каждой такой предварительной группе. Полный метод, приведенный здесь, был бы необходим для форм, которые в противном случае были бы настолько удивительно похожи, что такие простые инварианты до сих пор не различали бы их. Простые объекты, построенные из растровых данных, могут иметь такие характеристики, например. Однако, поскольку приведенное здесь решение в любом случае настолько эффективно, что, если кто-то собирается приложить усилия для его реализации, оно само по себе может работать просто отлично.
пример
На рисунке слева показаны пять полилиний плюс еще 15, которые были получены из них путем случайного перемещения, поворота, отражения и изменения внутренней ориентации (которая не видна). Фигура правой руки окрашивает их в соответствии с их евклидовым классом эквивалентности: все фигуры общего цвета являются конгруэнтными; разные цвета не совпадают.
Rкод следует. Когда входные данные были обновлены до 500 фигур, 500 дополнительных (конгруэнтных) форм со средним значением 100 вершин на форму, время выполнения на этом компьютере составляло 3 секунды.
Этот код неполон: поскольку Rне имеет нативной лексикографической сортировки, и мне не хотелось кодировать ее с нуля, я просто выполняю сортировку по первой координате каждой стандартизированной формы. Это будет хорошо для случайных фигур, созданных здесь, но для производственных работ должна быть реализована полная лексикографическая сортировка. Функция order.shapeбудет единственной, затронутой этим изменением. Его входные данные представляют собой список стандартизированной формы, sа выходные данные представляют собой последовательность индексов, в sкоторую можно было бы их отсортировать.
#
# 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)вместоcbind(x,y)). Это все, что вам нужно:spбиблиотека не используется. Если вы хотите следовать тому , что делается в деталях, я предлагаю вам начать с, скажем,n.shapes <- 2,n.shapes.new <- 3, иp.mean <- 1. Тогдаshapes,shapes.stdи т.д., все достаточно малы , чтобы быть легко проверены. Элегантный и «правильный» способ - справиться со всем этим - создать класс стандартизированных представлений функций.Вы просите много с произвольным вращением и расширением! Не уверен, насколько полезным будет расстояние Хаусдорфа, но проверьте это. Мой подход заключается в сокращении количества проверяемых случаев с помощью дешевых данных. Например, вы можете пропустить дорогостоящие сравнения, если длина двух строк не является целочисленным отношением ( при условии целочисленного / градуированного масштабирования ). Вы также можете проверить, находятся ли ограничивающие области или их выпуклые области корпуса в хорошем соотношении. Я уверен, что есть много дешевых проверок, которые вы могли бы сделать против центроида, таких как расстояния или углы от начала / конца.
Только тогда, если вы обнаружите масштабирование, отмените его и сделайте действительно дорогие проверки.
Уточнение: я не знаю, какие пакеты вы используете. Под целочисленным соотношением я подразумевал, что вы должны разделить оба расстояния, проверить, является ли результат целым числом, если нет, инвертировать это значение (может быть, вы выбрали неправильный порядок) и перепроверить. Если вы получили целое число или достаточно близко, вы можете сделать вывод, что, возможно, происходило масштабирование. Или это могут быть две разные формы.
Что касается ограничивающего прямоугольника, вы, вероятно, получили противоположные точки прямоугольника, который представляет его, поэтому получение области из них является простой арифметикой. Принцип сравнения коэффициентов тот же, только результат будет в квадрате. Не беспокойтесь о выпуклых оболочках, если вы не можете вытащить их из этого пакета R, это была просто идея (скорее всего, недостаточно дешевая).
источник
Хороший метод сравнения этих полилиний заключается в том, чтобы полагаться на представление в виде последовательности (расстояния, углы поворота) в каждой вершине: для линии, состоящей из точек
P1, P2, ..., PN, такая последовательность будет иметь вид:Согласно вашим требованиям, две линии равны тогда и только тогда, когда их соответствующие последовательности одинаковы (по модулю порядка и направления угла). Сравнение числовых последовательностей тривиально.
Вычисляя каждую последовательность полилиний только один раз и, как предполагает lynxlynxlynx, проверяя сходство последовательностей только для полилиний, имеющих одинаковые тривиальные характеристики (длина, число вершин ...), вычисление должно быть действительно быстрым!
источник