Вычисление перекрытий сеток

Question

Скажем, у меня есть две карты, каждая из которых представлена ​​в виде двумерного массива. Каждая карта содержит несколько отличительных особенностей (камни, трава, растения, деревья и т. Д.). Я знаю, что две карты относятся к одному и тому же общему региону, но я хотел бы выяснить: 1.) перекрываются ли они и 2.) если да, то где происходит это перекрытие. Кто-нибудь знает какие-либо алгоритмы, которые помогли бы мне сделать это?

[EDIT] Каждая функция полностью содержится в индексе массива. Хотя, возможно, можно отличить (например) камень от клочка травы, невозможно отличить один камень от другого (или один участок травы от другого).

Answer 1

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

match( A on B ):
    for each i in length(A):
        see if A[i..] matches B[0..]
    if no match found: do the same for B on A.

Для 2D вы делаете то же самое, в основном: находите «ребро» A, которое перекрывается с противоположным ребром B. Только ребра не 1D, но 2D:

for each point xa,ya in A:
    find a row yb in B that has a match( A[ya] on B[yb] )
        see if A[ya..] matches B[yb..]

Вы должны сделать это для 2 диагоналей, в каждом смысле.

Answer 2

Для одной карты, просмотрите каждую функцию и найдите ближайшую другую функцию к ней. Запишите их в список, сохранив тип каждой из двух функций и dx dy между ними. Хранить в хеш-таблице или отсортированном списке. Теперь они не зависят от местоположения, поскольку записывают только относительные расстояния.

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

Answer 3

Похоже на регистрация изображения (википедия), находя преобразование (в вашем случае только перевод), которое может выровнять два изображения. Существует куча программного обеспечения, которая делает подобные вещи, связанные со страницей википедии.