Hylograph.Forces.RectCollide
- Package
- purescript-hylograph-forces
- Repository
- afcondon/purescript-hylograph-forces
Rectangle collision: push overlapping axis-aligned rectangles apart along the axis on which they overlap least.
Not in d3. The rule is the Rust kernel's (apply_rect_collide in
force-kernel/src/forces.rs), and the two are held to each other bit
for bit by test/differential.mjs.
Node i is a rectangle of half-width w_i and half-height h_i centred
on its anticipated position a_i = position + velocity. A node is HELD
on an axis if it cannot be moved along it: it is pinned there (fx for
x, fy for y; here, whatever the config's heldX and heldY say). One
iteration:
Take
a_ifor every node that takes part, all at once, before anything moves.For every node i that takes part, and every other node j that takes part and may collide with it (see "Who collides"), both
afinite, taking j in ascending order:dx = a_i.x - a_j.x dy = a_i.y - a_j.y ox = (w_i + w_j) - |dx| oy = (h_i + h_j) - |dy|The pair overlaps when
ox > 0andoy > 0. If it does, the push is along x ifox <= oyand along y otherwise. If i is held on that axis, nothing more happens for this pair. Otherwiseshare = 1 if j is held on that axis = A_j / (A_i + A_j) otherwise, with A = w * h (1/2 if A_i + A_j is not above 0) push = s * overlap * strength * share v_i[axis] += pushwhere
sis the sign of dx (or dy): +1 if positive, -1 if negative, and if exactly zero, -1 when i < j and +1 when i > j.
So a held rectangle is never moved, and what overlaps it takes the whole correction; two free rectangles share it, the smaller moving more.
THE SQUEEZE. A wide rectangle nearly always overlaps another least
vertically, so it is only ever pushed up or down; caught between two
things that do not give way (two pinned dots, a dot and a packed row of
other labels) the pushes cancel and it sits on both for ever. With
squeezed: goesThrough, after the last iteration of one application of
the force, for each node i and each axis it is not held on: let up be
the sum of the positive pushes step 2 gave it on that axis over all the
iterations, and down the sum of the negative ones, as a magnitude. If
both are above 0 the node is squeezed, and it goes with one side and
ignores the other:
v_i[axis] += down if it goes up (the downward pushes are undone)
v_i[axis] -= up if it goes down
It goes the way it was already moving, if it was moving: with w its
velocity on that axis as it was when the force was applied, if
|w| > 0.001 * (up + down) it goes up when w > 0 and down when
w < 0. Otherwise (a velocity that small is what is left of a movement
long over, or the last of a pull dying away) it goes with the stronger
side: up if up > down, down if up < down, and if they are equal, up
when i is odd and down when it is even.
Going the way it is moving is what makes this resolve: the rectangle
keeps on through whatever was squeezing it, a dot or another rectangle,
until it is clear, where a rule that only compared the two sides would
turn round as soon as it went deeper into the weaker one. It suits
rectangles that nothing else is pressing together. Under a force that
keeps pressing (a pull to a point that a pinned body is standing on) a
squeeze is permanent and the rectangle will be walked through its
neighbour, so let such a pull die away before expecting rest. With
squeezed: staysPut, the default, step 2 is all there is.
Who collides. A node left out by include collides with nothing and
nothing collides with it. With groups, pairs restricts the pairs: only
two nodes of the same group (withinGroups), or only two nodes not of
the same group (betweenGroups; a node in no group is in a different
group from everyone).
Every correction in an iteration comes from the same anticipated positions, so no node is favoured by its index. Not scaled by alpha, as d3's collide is not.
The quadtree only finds the rectangles that overlap a given one. They are then put in index order before their corrections are added, which makes the result the same, bit for bit, as the loop over all pairs.
#Config Source
type Config :: Row Type -> Typetype Config row = { group :: Node row -> Membership, halfHeight :: Node row -> Number, halfWidth :: Node row -> Number, heldX :: Node row -> Boolean, heldY :: Node row -> Boolean, include :: Node row -> Boolean, iterations :: Int, pairs :: Pairs, squeezed :: Squeezed, strength :: Number }
halfWidth, halfHeight, include and group are asked once per node
when the force is initialized; a half-extent of NaN counts as zero.
heldX and heldY say whether a node cannot be moved along an axis,
and are asked every time the force is applied, since pins come and go:
Node.pinnedX and Node.pinnedY are the ones to give for nodes with
fx and fy.
#defaultConfig Source
defaultConfig :: forall row. Config rowUnit squares, full strength, one iteration, every node, every pair, nothing held, a squeezed rectangle stays put.
#RectCollide Source
newtype RectCollide :: Row Type -> Typenewtype RectCollide row
An initialized rectangle collision: the nodes that take part.
#initialize Source
initialize :: forall row. Config row -> Array (Node row) -> RectCollide row- Modules
- Hylograph.
Forces - Hylograph.
Forces. Center - Hylograph.
Forces. Cohesion - Hylograph.
Forces. Collide - Hylograph.
Forces. Contain - Hylograph.
Forces. Directional - Hylograph.
Forces. Group - Hylograph.
Forces. Link - Hylograph.
Forces. Linkage - Hylograph.
Forces. ManyBody - Hylograph.
Forces. Measure - Hylograph.
Forces. Node - Hylograph.
Forces. Position - Hylograph.
Forces. Quadtree - Hylograph.
Forces. Radial - Hylograph.
Forces. Random - Hylograph.
Forces. RectCollide - Hylograph.
Forces. Snapshot - Hylograph.
Forces. Tick - Hylograph.
Forces. Towards