Module

Hylograph.Forces.Quadtree

Package
purescript-hylograph-forces
Repository
afcondon/purescript-hylograph-forces

The part of d3-quadtree that d3-force uses: build a tree from a set of points, once, and hand it to a force to walk.

Ported from d3-quadtree 3.0.1 (ISC, Copyright 2010-2021 Mike Bostock); see LICENSE.

d3 inserts the points one at a time into a mutable tree. This builds the same tree from the top down, without mutation: a square that holds no point is Empty, one that holds a single location is a Leaf, and any other is a Branch of its four quarters. That is the tree d3's insertion arrives at whatever the order, because d3 splits a square exactly when a second location lands in it. Two things do depend on insertion order and are kept: the points of a leaf run newest first, as d3's next chain does, and the extent starts from the unit square at the floor of the smallest coordinates and doubles until it covers the largest.

The squares themselves are not stored. A force recomputes them as it walks, halving from the root's extent with the same (x0 + x1) / 2 that d3's visit uses, so the bounds agree to the bit.

#Point Source

type Point item = { item :: item, x :: Number, y :: Number }

A location and whatever the force keeps there.

#Quadtree Source

data Quadtree item

A quadtree. The quarters of a Branch are in d3's order: top-left, top-right, bottom-left, bottom-right, where "right" is x >= middle and "bottom" is y >= middle. A Leaf holds its newest point and then the older points at the same location, newest first.

Constructors

#Extent Source

type Extent = { x0 :: Number, x1 :: Number, y0 :: Number, y1 :: Number }

The square a tree covers.

#Planted Source

type Planted item = { extent :: Extent, root :: Quadtree item }

A tree and the square its root covers.

#build Source

build :: forall item. List (Point item) -> Planted item

d3's quadtree(nodes, x, y): the tree of the given points. They are listed newest first, that is, in the reverse of the order d3 would insert them, which is how a list comes out when it is built by adding each node to the front. Points with a NaN coordinate are left out, as d3 leaves them out.