Last active
November 1, 2021 07:21
-
-
Save hmmhmmhm/699779ac2f73a349dad5af44d6112321 to your computer and use it in GitHub Desktop.
typescript grid item sort & align algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
export interface PackNode { | |
w: number | |
h: number | |
x?: number | |
y?: number | |
used?: boolean | |
right?: PackNode | |
down?: PackNode | |
fit?: PackNode | |
} | |
export interface InputNode { | |
w: number | |
h: number | |
} | |
export interface ResultNode { | |
x: number | |
y: number | |
w: number | |
h: number | |
} | |
export const rectanglePack = <T>(props: { | |
w: number | |
h: number | |
nodes: (InputNode & T)[] | |
}) => { | |
const root: PackNode = { x: 0, y: 0, w: props.w, h: props.h } | |
const findNode = (node: PackNode | undefined, w: number, h: number) => { | |
if (node) { | |
if (node.used) | |
return findNode(node.right, w, h) || findNode(node.down, w, h) | |
else if (w <= node.w && h <= node.h) return node | |
else return null | |
} else { | |
return null | |
} | |
} | |
const splitNode = (node: PackNode | undefined, w: number, h: number) => { | |
if (node) { | |
node.used = true | |
node.down = { x: node.x, y: node.y! + h, w: node.w, h: node.h - h } | |
node.right = { x: node.x! + w, y: node.y, w: node.w - w, h: h } | |
} | |
return node | |
} | |
const blocks = [...props.nodes] | |
let node: PackNode | |
let block: PackNode | |
for (let n = 0; n < blocks.length; n++) { | |
block = blocks[n] | |
if ((node = findNode(root, block.w, block.h))) | |
block.fit = splitNode(node, block.w, block.h) | |
} | |
const result: (ResultNode & T)[] = blocks.map((block) => { | |
return { | |
...block, | |
x: block.fit!.x!, | |
y: block.fit!.y!, | |
w: block.w, | |
h: block.h | |
} | |
}) | |
return result | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment