Published
Edited
Dec 5, 2019
1 star
function buildTree (dim, points, depth = 0) {
if (points.length == 0) return null
const ax = depth % dim
const [low, median, high] = medianPart(points, ax)
return {
low: buildTree(dim, low, depth + 1),
high: buildTree(dim, high, depth + 1),
value: median
}
}
{
const root = md`## Przeszukiwanie
Złożoność przeszukiwania w kd-drzewie wynosi`
root.append(tex`O(\sqrt n + k)`)
return root
}
pointInRange = (point, min, max) => point.every((val, ax) => min[ax] <= val && val <= max[ax])
function query(dim, tree, min, max) {
const points = []
const query = (tree, depth) => {
if (tree == null) return
const ax = depth % dim
if (tree.value[ax] < min[ax]) query(tree.high, depth + 1)
else if (tree.value[ax] > max[ax]) query(tree.low, depth + 1)
else {
if (pointInRange(tree.value, min, max)) points.push(tree.value)
query(tree.low, depth + 1)
query(tree.high, depth + 1)
}
}
query(tree, 0)
return points
}
function medianPart(arr, ax) {
arr.sort((a, b) => a[ax] - b[ax])
let split = arr.length / 2 | 0
const sp = arr[split][ax]
while (split > 1 && arr[split - 1][ax] == sp)
split--
return [arr.slice(0, split), arr[split], arr.slice(split + 1)]
}
color = ({
ax0: '#10a778',
ax1: 'orange',
empty: '#f1f1f1',
positiveQuery: '#228b22cc',
negativeQuery: '#ff000099',
lnegativeQuery: '#ff00004d',
lpositiveQuery: '#228b2280',
focus: '#d11919'
})
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
