Skip to content

Instantly share code, notes, and snippets.

@nikcorg
Last active February 5, 2019 00:02
Show Gist options
  • Save nikcorg/716813fa3cd246aaddc7bb55ab380406 to your computer and use it in GitHub Desktop.
Save nikcorg/716813fa3cd246aaddc7bb55ab380406 to your computer and use it in GitHub Desktop.
Summed-area Table
// https://en.wikipedia.org/wiki/Summed-area_table
type Point = { x: number; y: number };
type DefaultingGetter<T> = (x: number) => T;
type DefaultingGetterFactory = <T>(xs: T[], def: T) => DefaultingGetter<T>;
interface Mapper {
toxy: (n: number) => Point;
toi: (x: number, y: number) => number;
}
const makeGet: DefaultingGetterFactory = <T>(xs: T[], def: T) => (x: number): T =>
x < 0 || x >= xs.length ? def : xs[x];
const xymap = (w: number) => {
return {
toxy: (i: number) => ({ x: i % w, y: Math.floor(i / w) }),
toi: (x: number, y: number) => w * y + x,
};
};
const sumtable = (xs: number[], m: Mapper) =>
xs.reduce((acc, n, i) => {
const { x, y } = m.toxy(i);
const get = makeGet(acc, 0);
const a = get(m.toi(x, y - 1));
const b = get(m.toi(x - 1, y));
const c = get(m.toi(x - 1, y - 1));
const nn = n + a + b - c;
acc[i] = nn;
return acc;
}, []);
const areasum = (xs: number[], m: Mapper, get: DefaultingGetter<number>) => (
{ x: ax, y: ay }: Point,
{ x: bx, y: by }: Point,
) => {
const A = get(m.toi(ax - 1, ay - 1));
const B = get(m.toi(bx, ay - 1));
const C = get(m.toi(ax - 1, by));
const D = get(m.toi(bx, by));
return D - B - C + A;
};
// these are the example numbers from the wikipedia article
// prettier-ignore
const nums = [
31, 2, 4, 33, 5, 36,
12, 26, 9, 10, 29, 25,
13, 17, 21, 22, 20, 18,
24, 23, 15, 16, 14, 19,
30, 8, 28, 27, 11, 7,
1, 35, 34, 3, 32, 6
];
const w = 6;
const m = xymap(w);
const sumstable = sumtable(nums, m);
const getter = makeGet(sumstable, 0);
const summer = areasum(sumstable, m, getter);
const sum = summer({ x: 2, y: 3 }, { x: 4, y: 4 });
console.log(sum); // 111
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment