algorithm - 计算网格重叠

Question

假设我有两张 map ，每张都表示为一个二维数组。每张 map 都包含几个不同的特征(岩石、草地、植物、树木等)。我知道这两张 map 属于同一区域，但我想知道:1.) 它们是否重叠以及 2.) 如果重叠，重叠发生在哪里。有谁知道可以帮助我做到这一点的算法吗？

[编辑]每个功能都完全包含在一个数组索引中。尽管有可能从一片草丛中辨别出(例如)一 block 岩石，但不可能将一 block 岩石与另一 block 辨别出来(或者一片草丛与另一片草丛)。

Answer 1

在 1D 中执行此操作时，我会为第一个集合中的每个索引(实际上是一个字符串)尝试在第二个集合中找到最大的匹配项。如果比赛进行到最后，我就会有重叠(比如在 action 和 ionbeam 中)。

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，基本上做同样的事情:找到与 B 的相对边缘重叠的 A 的“边缘”。只有边缘不是一维的，而是二维的:

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 条对角线执行此操作。