Computer science student
Published
Edited
Dec 5, 2019
2 forks
class Point extends Array {
get x() { return this[0] }
get y() { return this[1] }
}
class RectangularRange {
constructor(bottomLeftPoint, topRightPoint) {
this.bottomLeftPoint = bottomLeftPoint
this.topRightPoint = topRightPoint
}
doesOverlapWith(other) {
return this.bottomLeftPoint.x < other.topRightPoint.x && this.topRightPoint.x > other.bottomLeftPoint.x
&& this.bottomLeftPoint.y < other.topRightPoint.y && this.topRightPoint.y > other.bottomLeftPoint.y
}
isPointIn(point) {
return point.x >= this.bottomLeftPoint.x && point.x < this.topRightPoint.x
&& point.y >= this.bottomLeftPoint.y && point.y < this.topRightPoint.y
}
}
class Node {
constructor(bottomLeftPoint, topRightPoint) {
this.point = null
this.range = new RectangularRange(bottomLeftPoint, topRightPoint)
this.hasBeenPopulated = false
this.topLeftQuad = null
this.topRightQuad = null
this.bottomLeftQuad = null
this.bottomRightQuad = null
this.vertialLine = null
this.horizontalLine = null
}
populateQuads() {
const tr = this.range.topRightPoint
const bl = this.range.bottomLeftPoint
const a = (tr.x - bl.x) / 2
this.hasBeenPopulated = true
this.topLeftQuad = new Node(new Point(bl.x, bl.y + a), new Point(bl.x + a, tr.y))
this.topRightQuad = new Node(new Point(bl.x + a, bl.y + a), tr)
this.bottomLeftQuad = new Node(bl, new Point(bl.x + a, bl.y + a))
this.bottomRightQuad = new Node(new Point(bl.x + a, bl.y), new Point(tr.x, bl.y + a))
this.vertialLine = [[this.bottomRightQuad.range.bottomLeftPoint.x,
this.bottomRightQuad.range.bottomLeftPoint.y],
[this.topRightQuad.range.bottomLeftPoint.x,
this.topRightQuad.range.topRightPoint.y]]
this.horizontalLine = [[this.topLeftQuad.range.bottomLeftPoint.x,
this.topLeftQuad.range.bottomLeftPoint.y],
[this.topRightQuad.range.topRightPoint.x,
this.topRightQuad.range.bottomLeftPoint.y]]
}
isPointInRange(point) {
return this.range.isPointIn(point, this.bottomLeftPoint, this.topRightPoint)
}
insertIntoQuad(point) {
if (!this.hasBeenPopulated) {
throw "Node is not populated."
}
if (this.topLeftQuad.isPointInRange(point)) {
insertPoint(this.topLeftQuad, point)
} else if (this.topRightQuad.isPointInRange(point)) {
insertPoint(this.topRightQuad, point)
} else if (this.bottomLeftQuad.isPointInRange(point)) {
insertPoint(this.bottomLeftQuad, point)
} else if (this.bottomRightQuad.isPointInRange(point)) {
insertPoint(this.bottomRightQuad, point)
}
}
}
function buildQuadTree(bottomLeftPoint, topRightPoint, points) {
const root = new Node(bottomLeftPoint, topRightPoint)
for (let point of points) {
insertPoint(root, point)
}
return root
}
function insertPoint(node, point) {
if (!node.isPointInRange(point)) {
return null
}
if (node.point == null && !node.hasBeenPopulated) {
node.point = point
return null
}
if (!node.hasBeenPopulated) {
let quads = node.populateQuads()
node.insertIntoQuad(node.point)
node.insertIntoQuad(point)
node.point = null
return quads
}
insertPoint(node.topLeftQuad, point)
insertPoint(node.topRightQuad, point)
insertPoint(node.bottomLeftQuad, point)
insertPoint(node.bottomRightQuad, point)
}
function *getPointsInRectangularRangeIter(rootNode, range) {
let queue = [rootNode]
let res = []
while (queue.length > 0) {
let node = queue.pop()
yield {
node,
event: 'OVERLAP'
}
if (node.point != null && range.isPointIn(node.point)) {
res.push(node.point)
yield {
point: node.point,
event: 'POINT'
}
}
if (node.hasBeenPopulated) {
let children = [node.topLeftQuad, node.topRightQuad, node.bottomLeftQuad, node.bottomRightQuad]
for (let child of children) {
if (!range.doesOverlapWith(child.range)) {
continue
}
queue.push(child)
}
}
}
//return res
}
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.
