package barneshut

import "gonum.org/v1/gonum/spatial/barneshut"

Package barneshut provides routines for calculating n-body force approximations using the Barnes-Hut algorithm.

See https://en.wikipedia.org/wiki/Barnes–Hut_simulation, http://arborjs.org/docs/barnes-hut and https://jheer.github.io/barnes-hut/ for details.

package main

import (
	"log"

	"golang.org/x/exp/rand"

	"gonum.org/v1/gonum/spatial/barneshut"
	"gonum.org/v1/gonum/spatial/r2"
)

type mass struct {
	d r2.Vec
	v r2.Vec
	m float64
}

func (m *mass) Coord2() r2.Vec { return m.d }
func (m *mass) Mass() float64  { return m.m }
func (m *mass) move(f r2.Vec) {
	m.v = r2.Add(m.v, r2.Scale(1/m.m, f))
	m.d = r2.Add(m.d, m.v)
}

func main() {
	rnd := rand.New(rand.NewSource(1))

	// Make 1000 stars in random locations.
	stars := make([]*mass, 1000)
	p := make([]barneshut.Particle2, len(stars))
	for i := range stars {
		s := &mass{
			d: r2.Vec{
				X: 100 * rnd.Float64(),
				Y: 100 * rnd.Float64(),
			},
			v: r2.Vec{
				X: rnd.NormFloat64(),
				Y: rnd.NormFloat64(),
			},
			m: 10 * rnd.Float64(),
		}
		stars[i] = s
		p[i] = s
	}
	vectors := make([]r2.Vec, len(stars))

	// Make a plane to calculate approximate forces
	plane := barneshut.Plane{Particles: p}

	// Run a simulation for 100 updates.
	for i := 0; i < 1000; i++ {
		// Build the data structure. For small systems
		// this step may be omitted and ForceOn will
		// perform the naive quadratic calculation
		// without building the data structure.
		err := plane.Reset()
		if err != nil {
			log.Fatal(err)
		}

		// Calculate the force vectors using the theta
		// parameter...
		const theta = 0.5
		// and an imaginary gravitational constant.
		const G = 10
		for j, s := range stars {
			vectors[j] = r2.Scale(G, plane.ForceOn(s, theta, barneshut.Gravity2))
		}

		// Update positions.
		for j, s := range stars {
			s.move(vectors[j])
		}

		// Rendering stars is left as an exercise for
		// the reader.
	}
}

Index ¶

• func Gravity2(_, _ Particle2, m1, m2 float64, v r2.Vec) r2.Vec
• func Gravity3(_, _ Particle3, m1, m2 float64, v r3.Vec) r3.Vec
• type Force2
• type Force3
• type Particle2
• type Particle3
• type Plane
• func NewPlane(p []Particle2) (*Plane, error)
• func (q *Plane) ForceOn(p Particle2, theta float64, f Force2) (force r2.Vec)
• func (q *Plane) Reset() (err error)
• type Volume
• func NewVolume(p []Particle3) (*Volume, error)
• func (q *Volume) ForceOn(p Particle3, theta float64, f Force3) (force r3.Vec)
• func (q *Volume) Reset() (err error)

Examples ¶

• package (Galaxy)

Functions ¶

func Gravity2 ¶

func Gravity2(_, _ Particle2, m1, m2 float64, v r2.Vec) r2.Vec

Gravity2 returns a vector force on m1 by m2, equal to (m1⋅m2)/‖v‖² in the directions of v. Gravity2 ignores the identity of the interacting particles and returns a zero vector when the two particles are coincident, but performs no other sanity checks.

func Gravity3 ¶

func Gravity3(_, _ Particle3, m1, m2 float64, v r3.Vec) r3.Vec

Gravity3 returns a vector force on m1 by m2, equal to (m1⋅m2)/‖v‖² in the directions of v. Gravity3 ignores the identity of the interacting particles and returns a zero vector when the two particles are coincident, but performs no other sanity checks.

Types ¶

type Force2 ¶

type Force2 func(p1, p2 Particle2, m1, m2 float64, v r2.Vec) r2.Vec

Force2 is a force modeling function for interactions between p1 and p2, m1 is the mass of p1 and m2 of p2. The vector v is the vector from p1 to p2. The returned value is the force vector acting on p1.

In models where the identity of particles must be known, p1 and p2 may be compared. Force2 may be passed nil for p2 when the Barnes-Hut approximation is being used. A nil p2 indicates that the second mass center is an aggregate.

type Force3 ¶

type Force3 func(p1, p2 Particle3, m1, m2 float64, v r3.Vec) r3.Vec

Force3 is a force modeling function for interactions between p1 and p2, m1 is the mass of p1 and m2 of p2. The vector v is the vector from p1 to p2. The returned value is the force vector acting on p1.

In models where the identity of particles must be known, p1 and p2 may be compared. Force3 may be passed nil for p2 when the Barnes-Hut approximation is being used. A nil p2 indicates that the second mass center is an aggregate.

type Particle2 ¶

type Particle2 interface {
	Coord2() r2.Vec
	Mass() float64
}

Particle2 is a particle in a plane.

type Particle3 ¶

type Particle3 interface {
	Coord3() r3.Vec
	Mass() float64
}

Particle3 is a particle in a volume.

type Plane ¶

type Plane struct {
	Particles []Particle2
	// contains filtered or unexported fields
}

Plane implements Barnes-Hut force approximation calculations.

func NewPlane ¶

func NewPlane(p []Particle2) (*Plane, error)

NewPlane returns a new Plane. If the plane is too large to allow particle coordinates to be distinguished due to floating point precision limits, NewPlane will return a non-nil error.

func (*Plane) ForceOn ¶

func (q *Plane) ForceOn(p Particle2, theta float64, f Force2) (force r2.Vec)

ForceOn returns a force vector on p given p's mass and the force function, f, using the Barnes-Hut theta approximation parameter.

Calls to f will include p in the p1 position and a non-nil p2 if the force interaction is with a non-aggregate mass center, otherwise p2 will be nil.

It is safe to call ForceOn concurrently.

func (*Plane) Reset ¶

func (q *Plane) Reset() (err error)

Reset reconstructs the Barnes-Hut tree. Reset must be called if the Particles field or elements of Particles have been altered, unless ForceOn is called with theta=0 or no data structures have been previously built. If the plane is too large to allow particle coordinates to be distinguished due to floating point precision limits, Reset will return a non-nil error.

type Volume ¶

type Volume struct {
	Particles []Particle3
	// contains filtered or unexported fields
}

Volume implements Barnes-Hut force approximation calculations.

func NewVolume ¶

func NewVolume(p []Particle3) (*Volume, error)

NewVolume returns a new Volume. If the volume is too large to allow particle coordinates to be distinguished due to floating point precision limits, NewVolume will return a non-nil error.

func (*Volume) ForceOn ¶

func (q *Volume) ForceOn(p Particle3, theta float64, f Force3) (force r3.Vec)

ForceOn returns a force vector on p given p's mass and the force function, f, using the Barnes-Hut theta approximation parameter.

Calls to f will include p in the p1 position and a non-nil p2 if the force interaction is with a non-aggregate mass center, otherwise p2 will be nil.

It is safe to call ForceOn concurrently.

func (*Volume) Reset ¶

func (q *Volume) Reset() (err error)

Reset reconstructs the Barnes-Hut tree. Reset must be called if the Particles field or elements of Particles have been altered, unless ForceOn is called with theta=0 or no data structures have been previously built. If the volume is too large to allow particle coordinates to be distinguished due to floating point precision limits, Reset will return a non-nil error.

Source Files ¶

barneshut2.go barneshut3.go doc.go no_bounds.go