Table Pattern Matching

[schme16]

I'm stumped as to how the heck I can accomplish this feat.
What I'm trying to do is find a way to text one table against another.
(this is so I can see if one image contains another one, wholly or in part; all data is made into table[y][x] as per the Pixel Perfect Collision Library)

Example:

Code: Select all

--This is the `haystack` table
table1 = {}
	table1[y][x] = 1233
	table1[y][x] = 234
	table1[y][x] = 3451 --
	table1[y][x] = 34224
	table1[y][x] = 12345
	table1[y][x] = 12123
	table1[y][x] = 345345
	table1[y][x] = 3452
	table1[y][x] = 613 --
	table1[y][x] = 134
	table1[y][x] = 12123
	table1[y][x] = 909
	table1[y][x] = 2712
	table1[y][x] = 93286
	
	
	
--This is the `needle` table
table2 = {}
	table2[y][x] = 3451 --
	table2[y][x] = 34224
	table2[y][x] = 12345
	table2[y][x] = 12123
	table2[y][x] = 345345
	table2[y][x] = 3452
	table2[y][x] = 613 --
	

as you can see table 2 matches table one starting at entry 3 and ending at entry 9

as for actually figuring out how to do this automatically; Stumped.

any help (or alternatives) VERY welcome!

[vrld]

The fastest way of how to test for intersections is to create a new table with the values as key and the keys as values and then test the second table against it.
Something like this (untested):

Code: Select all

function intersection(table1, table2)
    local values = {}
    for y, xtable in pairs(table1) do -- use ipairs when tables are arrays
        for x,v in pairs(xtable) do
            values[v] = {x,y}
        end
    end
    
    local matches = {}
    for y, xtable in pairs(table2) do
        for x,v in pairs(xtable) do
            if values[v] then
                matches[#matches+1] = {t1 = values[v], t2 = {x,y}, value = v}
            end
        end
    end

    return matches
end

This will give you the intersection points and values of table1 and table2 using very few comparisons.