Computing overlaps of grids

Question

Say I have two maps, each represented as a 2D array. Each map contains several distinct features (rocks, grass, plants, trees, etc.). I know the two maps are of the same general region but I would like to find out: 1.) if they overlap and 2.) if so, where does this overlap occur. Does anyone know of any algorithms which would help me do this?

[EDIT] Each feature is contained entirely inside an array index. Although it is possibly to discern (for example) a rock from a patch of grass, it is not possible to discern one rock from another (or one patch of grass from another).

Answer 1

For one map, go through each feature and find the nearest other feature to it. Record these in a list, storing the type of each of the two features and the dx dy between them. Store in a hash table or sorted list. These are now location invariant, since they record only relative distances.

Now for your second map, start doing the same: pick any feature, find its closest neighbor, find the delta. Look for the same correspondence in the original map list. If the features are shared between the maps, you'll find it in the list and you now know one correspondence between the maps. Repeat for many features if necessary. The results will give you a decent answer of if the maps overlap, and if so, at what offset.

Answer 2

When doing this in 1D, I would for each index in the first collection (a string, really), try find the largest match in the second collection. If the match goes to the end, I have an overlap (like in act*ion* and 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.

For 2D, you do the same thing, basically: find an 'edge' of A that overlaps with the opposite edge of B. Only the edges aren't 1D, but 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..]

You need to do this for the 2 diagonals, in each sense.

Answer 3

Sounds like image registration (wikipedia), finding a transformation (translation only, in your case) which can align two images. There's a pile of software that does this sort of thing linked off the wikipedia page.