Является ли этот алгоритм хорошим способом определить, имеют ли два массива одинаковое содержимое в одном порядке?

Question

Итак, у меня есть два массива, каждый из которых представляет собой простой замкнутый многоугольник в виде пройденного массива точек. Последний элемент совпадает с первым элементом. Я реализую равный алгоритм для любых 2 простых замкнутых многоугольников.

Array A would be like this [pnt1, pnt2, pnt3, pnt4, pnt5, pnt6, pnt1] 
Array B would be like this [pnt2, pnt3, pnt4, pnt5, pnt6, pnt1, pnt2] 
Array C would be like this [pnt2, pnt1, pnt6, pnt5, pnt4, pnt3, pnt2] 
Array D would be like this [pnt1, pnt2, pnt3, pnt5, pnt6, pnt4, pnt1] 

Массивы A и B равны, потому что точки находятся в одном порядке и одинаковых точках. Массивы A и C равны, потому что точки находятся в одном порядке (но наоборот), а также B и C по той же причине.

Массив D не равен ни одному из других массивов, поскольку обход точки не соответствует порядку.

Так мой алгоритм выглядит следующим образом:

1) сравнивает длины массивов, должен содержать то же # элементов - постоянное время

2) найти [0] в B набора как K - линейный поиск , линейное время

3) увидеть, если а [1] = в [K + 1] и так далее до A [N], линейное время

естественно индексы будут обернуть вокруг конца массива, возможно, через оператор мод.

Есть ли алгоритм, который может сделать лучше, чем это?

Answer 1

Резюме:

1. Удалить повторную точку
2. Найти местоположение я минимального значения
3. Если значение в I-1 ниже, чем значения, при + 1 обратной строки (должно принять краевых случаев, то есть я = 0 или я = п-1)
4. Поворотом массив так, чтобы минимальное значение на голове

Общая сложность: о (п)

ПРИМЕЧАНИЕ. Этапы 3 и 4 не являются абсолютно необходимыми. С шага 2 вы можете получить место минимума и с шага 3 получить ориентацию. Сравнивая два разных массива, просто начинайте с сравнения с * местоположением * s минимумов и двигайтесь в соответствии с ориентацией.

Например:

[pnt1, pnt2, pnt3, pnt4, pnt5, pnt6, pnt1] -> [pnt1, pnt2, pnt3, pnt4, pnt5, pnt6] -> [pnt1, pnt2, pnt3, pnt4 , pnt5, pnt6]

[pnt2, pnt3, pnt4, pnt5, pnt6, pnt1, pnt2] -> [pnt2, pnt3, pnt4, pnt5, pnt6, pnt1] -> [pnt1, pnt2, pnt3, pnt4, pnt5, pnt6]

[pnt2, pnt1, pnt6, pnt5, pnt4, pnt3, pnt2] -> [pnt2, pnt1, pnt6, pnt5, pnt4, pnt3] -> [pnt3, pnt4, pnt5, pnt6, pnt1 , pnt2] -> [pnt1, pnt2, pnt3, pnt4, pnt5, pnt6]

[pnt1, pnt2, pnt3, pnt5, pnt6, pnt4, pnt1] -> [pnt1, pnt2, pnt3, pnt5, pnt6, pnt4] -> [pnt1, pnt2, pnt3, pnt5, pnt6, pnt4]

Answer 2

Чтобы сделать такое сравнение, вы можете проверить, является ли один массив вращением другого (за исключением последних элементов).

Прежде всего, удалите повторяющиеся элементы, как указал Элькамини. Тогда в принципе, вы хотите знать, если А можно получить путем вращения элементов В.

Когда A=[x1, x2, ..., xk], B будет иметь то же самое содержание в том же порядке, что и тогда и только тогда, когда B=[x3, x4, ..., xk, x1, x2] или что-то подобное. В этом случае B можно назвать rotation of A. Однако этого недостаточно, так как вы также хотите проверить, является ли порядок одинаковым, но наоборот. Затем вы можете применить ту же процедуру для оборотной стороны B или наоборот A.

Псевдокод

def isSamePolygon(A, B): 
    remove the last element of A and last element of B 
    return isRotation(A, B) or isRotation(A, reverse(B)) 

def isRotation(A, B): // returns true if A is a rotation of B 
    // create an array which has two copies of A. 
    // e.g [a1, a2, ..., ai, a1, a2, ..., ai] 
    if (size(A) != size(B)) 
     return false 
    temp_array = concat(A, A) 
    return true if temp_array contains the elements of B in the exact same order, 
     false otherwise 

Анализ

Ходовой времени и пространства сложности isRotation является линейным размером макс (размер (A), размер (B)). Это связано с тем, что создание temp_array занимает линейное время и линейное пространство в размере A. Аналогично, проверка того, содержит ли B в A, также требует линейного времени для запуска.

Исправьте меня, если я ошибаюсь, но используя этот алгоритм, вы не можете уменьшить асимптотические сложности. Однако, хотя вы можете оптимизировать его, чтобы работать быстрее. Возможно, вы захотите обменять A и B, если size(A)>size(B). Более того; вы можете проверить обратное в одно и то же время, вместо этого выполните два вызова.

Answer 3

Если препроцессор не разрешен, эта проблема является наихудшим случаем Omega (N) только потому, что найти одну вершину одного многоугольника среди вершин другого можно с помощью N сравнений.

Так что не намного лучше, чем ваш алгоритм, который работает в оптимальное время O (N). [Вставить шаг между 2 и 3, чтобы определить порядок обхода.)

Если разрешена препроцессия, для каждого многоугольника вы можете идентифицировать первую вершину в лексикографическом порядке (X, Y). Назовем его главной вершиной. Делая это, вы сделаете шаг 1 вашего алгоритма бесполезным, потому что два равных многоугольника имеют одну и ту же главную вершину и сохраняют линейный поиск.

Еще лучше, вы могли бы связать подпись с полигонами, вычислив CRC в координатах, начиная с основной вершины. Затем вы обнаружите различные полигоны с высокой вероятностью во времени O (1), просто сравнивая сигнатуры.

Answer 4

Я предполагаю, что под «простым» подразумевается многоугольник без отверстий или самопересечений, но это может касаться только вершин. Например, следующее:

Такого рода сценарий может не имеет значения в вашем случае, но некоторые polygon algorithms полагаться на такие формы, чтобы сформировать контуры, составляющие сложный многоугольник, так что это удобно, чтобы быть в состоянии справиться с ними.

В этом случае эти два многоугольника должны сравнить равны:

P = ABCADEAFGAHIAJKA 
Q = FGAHIAJKABCADEAF 

Некоторые из приведенных алгоритмов может игнорировать это, потому что первый (и лексикографически минимальный) вершина А в Р повторяется. Тем не менее, до тех пор, как мы знаем, что нет края повторяется, мы можем адаптировать алгоритм без особых проблем:

1. Поиска P[0] в Q.
2. Обнаружив матч по номеру Q[i], сравните P[1] по номеру Q[i-1] и Q[i+1] (с соответствующей упаковкой).
3. Если ни один из них не возвращается к 1 и Продолжить поиск P[0] в Q, начиная с Q[i+1].
4. Как только матч будет найден на шаге 2, продолжите сравнение, продвигаясь вперед по P и в том же направлении через Q. Будет обнаружено несоответствие, и в этом случае полигоны будут разными, и вы можете немедленно остановиться (нет необходимости продолжать поиск другого соответствия для P[0]), или вы пройдете весь путь, и они будут идентичными.

Как и в стороне, если вы хотите использовать алгоритм, который должен определить лексикографический минимальную вершину в контуре, но где вершины могут повторяться, вы можете разорвать связи, рассматривая либо минимальную соседнюю вершину или по часовой стрелке (или против часовой стрелки, до тех пор, пока вы согласуетесь) соседней вершины. Опять же, это зависит от того, что ребра не повторяются.