Documentation ¶
Overview ¶
Heap methods
Author: Benjamin Frölich
This packacke should provide methods for heapification of arrays.
TODOs:
Goals: - [x] Min-Heap - [ ] Max-Heap - Maybe Fibonacci Heap - Maybe Binomial Heap - ... Functionality: - [x] BuildHeap - [ ] DecreaseKey - [x] Insert - [ ] Remove - [x] Replace - [x] Find Min/Max - [x] Extract Min/Max Linear Algebra functions and types Visualization stuff for Simulations
Index ¶
- Constants
- Variables
- func Abs(x int) int
- func AccelerationAndEDot2D(p *Particle, sim *Simulation, kernel Kernel)
- func BuildHeap[T cmp.Ordered](array []T)
- func ConfigMakeError(token Token, msg string) error
- func ConfigParseError(t Tokenizer, msg string) error
- func Density2D(p *Particle, sim *Simulation, kernel Kernel) float64
- func DensityMonahan3D(p *Particle) float64
- func DensityTopHat2D(p *Particle) float64
- func DensityTopHat3D(p *Particle) float64
- func Dist(a, b Vec2) float64
- func DistSq(a, b Vec2) float64
- func DumpHeap[T cmp.Ordered](array []T)
- func DumpHeap1[T cmp.Ordered](array []T)
- func ExtractMin[T cmp.Ordered](array []T) ([]T, T, error)
- func FindMin[T cmp.Ordered](array []T) (T, error)
- func GenerateDefaultConfigFile(filePath string)
- func GenerateTextFile(filePath string, source string)
- func Heapify[T cmp.Ordered](array []T, i int)
- func HeapifyRec[T cmp.Ordered](array []T, i int)
- func InitUniformly(particles []Particle)
- func Insert[T cmp.Ordered](array []T, element T) []T
- func MakeTreePlot(root *Cell, w, h int) gfx.Canvas
- func Max(x, y int) int
- func Min(x, y int) int
- func PlotBoundingCircles(c gfx.Canvas, root *Cell, max_depth int, color gfx.Color)
- func PlotCells(canvas gfx.Canvas, root *Cell, color_index, max_color_index int)
- func QuickSort(particles []*Particle, cmpValue func(*Particle) int)
- func ReadEntireFile(fname string) []rune
- func Replace[T cmp.Ordered](array []T, element T) ([]T, T, error)
- type Animator
- type Cell
- type Kernel
- type Orientation
- type Param
- type Particle
- func (particle *Particle) FindNearestNeighbours(root *Cell)
- func (particle *Particle) FindNearestNeighboursPeriodic(root *Cell, HorPeriodic, VertPeriodic [2]float64)
- func (p *Particle) NNQueueInitSentinel()
- func (p *Particle) NNQueueInsert(dist float64, neighbour *Particle, realPos Vec2)
- func (p *Particle) NNQueuePeekKey() float64
- type ParticleSource
- type Reflection
- type Simulation
- type SphConfig
- type Token
- type TokenType
- type Tokenizer
- type UniformRectSpawner
- type Vec2
- type Vec2i
Constants ¶
const ( MAX_PARTICLES_PER_CELL = 8 SPLIT_FRACTION = 0.5 // Fraction of left to total space for Treebuild(), usually 0.5. USE_RANDOM_SEED = false // for generating randomly distributed particles in init_uniformly() NN_SIZE = 32 // Nearest Neighbour Size )
Configuration
Variables ¶
var Monahan2D = Kernel{ F: func(q float64) float64 { if q < 0.5 { return q*q*q - q*q + 1.0/6 } return (1 - q) * (1 - q) * (1 - q) / 3 }, FPrefactor: 6 * 40 / (math.Pi * 7), DF: func(q float64) float64 { if q < 0.5 { return (3*q*q - 2*q) } return -(1 - q) * (1 - q) }, DFPrefactor: 6 * 40 / (math.Pi * 7), }
var Wendtland2D = Kernel{ F: func(q float64) float64 { if q <= 1 { return (1 - q) * (1 - q) * (1 - q) * (1 - q) * (1 + 4*q) } else { panic("not good..") } }, FPrefactor: 4 * 7 / (math.Pi * 4), DF: func(q float64) float64 { if q <= 1 { return -10 * q * (1 - q) * (1 - q) * (1 - q) } else { panic("not good..") } }, DFPrefactor: 8 * 7 / (math.Pi * 4), }
Functions ¶
func AccelerationAndEDot2D ¶
func AccelerationAndEDot2D(p *Particle, sim *Simulation, kernel Kernel)
- Sum [ (Pa/rhoa^2 + Pb/rhob^2 + PIab )] contribution A + contributionB
func ConfigMakeError ¶
func ConfigParseError ¶
func DensityMonahan3D ¶
lets assume mass 1 per particle, so the density is just the 1/volume of sphere
func DensityTopHat2D ¶
lets assume mass 1 per particle, so the density is just the 1/volume of sphere
func DensityTopHat3D ¶
lets assume mass 1 per particle, so the density is just the 1/volume of sphere
func ExtractMin ¶
func GenerateDefaultConfigFile ¶
func GenerateDefaultConfigFile(filePath string)
func GenerateTextFile ¶
func HeapifyRec ¶
func InitUniformly ¶
func InitUniformly(particles []Particle)
func PlotBoundingCircles ¶
Draw Bounding Circles of leaf nodes in Cell max_depth should be >= 1
func PlotCells ¶
draws rectangles for each cell. the higher the level, the color of the rect is more towards violet in rainbow
func ReadEntireFile ¶
Types ¶
type Animator ¶
type Animator struct { //frames for rendering Frames []image.Image // as refernce to simulation variables Simulation *Simulation // contains filtered or unexported fields }
func MakeAnimator ¶
func MakeAnimator(simulation *Simulation) Animator
func (*Animator) CurrentFrame ¶
type Cell ¶
type Cell struct { Particles []Particle // Bounds of Cell LowerLeft Vec2 UpperRight Vec2 // Minimum Bounding Sphere BCenter Vec2 BRadius float64 // Children Lower *Cell Upper *Cell }
Tree structure every leaf holds at most MAX_PARTICLES_PER_CELL
func MakeCells ¶
func MakeCells(particles []Particle, ori Orientation) *Cell
func MakeCellsUniform ¶
func MakeCellsUniform(n int, orientation Orientation) *Cell
func (*Cell) BoundingSpheres ¶
func (root *Cell) BoundingSpheres()
Adapted idea from: (might be worse) 1990, Jack Ritter proposed a simple algorithm to find a non-minimal bounding sphere. https://en.wikipedia.org/wiki/Bounding_sphere, 2024
func (*Cell) DistSquared ¶
not used/ not sure if it is correct? dist squared to cell
func (*Cell) Treebuild ¶
func (root *Cell) Treebuild(orientation Orientation)
type Particle ¶
type Particle struct { Pos Vec2 Vel Vec2 Rho float64 // Density C float64 // Speed of sound E float64 // Specific internal energy // Temporary values filled by Simulation EDot float64 // specific internal energy change de/dt VDot Vec2 // Acceleration EPred float64 // Predicted internal energy VPred Vec2 // Predicted Velicty // TODO: move this out of particles so we have smaller particle size! -> cache locality // @Speed might be bad because we have a big particle size now // should rather keep it seperate to prevent cache misses? // for now we just naively implement it like this // 32*(8+8) = 512 bytes NearestNeighbours [NN_SIZE]*Particle NNDists [NN_SIZE]float64 NNPos [NN_SIZE]Vec2 // keep track of position, we need to know because of periodic b.c. // visualisation trick for depth rendering Z int }
func Partition ¶
func Partition(ps []Particle, orientation Orientation, middle float64) (a, b []Particle)
func (*Particle) FindNearestNeighbours ¶
recursively find all nearest neighbors of a particle based on position make sure you call it on the top/root Cell!!
TODO: implement it using a loop
func (*Particle) FindNearestNeighboursPeriodic ¶
func (particle *Particle) FindNearestNeighboursPeriodic(root *Cell, HorPeriodic, VertPeriodic [2]float64)
Periodic version assuming particles are between x = HorPeriodic, y = VertPeriodic check for min/max float -> Open Boundaries
func (*Particle) NNQueueInitSentinel ¶
func (p *Particle) NNQueueInitSentinel()
func (*Particle) NNQueueInsert ¶
This is actually faster than the heapque. it's probably beacuse we only have 32 NN's TODO: compare for other NN_SIZEs than 32
using copy() is actually slower, because it is not inlined anymore by the compiler
func (*Particle) NNQueuePeekKey ¶
type ParticleSource ¶
type Reflection ¶
type Simulation ¶
type Simulation struct { Config SphConfig Root *Cell // Tree structure for keeping track of spatial cells of particles Particles []Particle CurrentStep int IsBusy sync.Mutex }
func MakeSimulation ¶
func MakeSimulation() Simulation
func MakeSimulationFromConf ¶
func MakeSimulationFromConf(conf SphConfig) Simulation
func MakeSimulationFromConfig ¶
func MakeSimulationFromConfig(configFilePath string) (error, Simulation)
func (*Simulation) CalculateForces ¶
func (sim *Simulation) CalculateForces()
func (*Simulation) Run ¶
func (sim *Simulation) Run()
func (*Simulation) TotalDensity ¶
func (sim *Simulation) TotalDensity() float64
func (*Simulation) TotalEnergy ¶
func (sim *Simulation) TotalEnergy() float64
func (*Simulation) TotalMomentum ¶
func (sim *Simulation) TotalMomentum() float64
type SphConfig ¶
type SphConfig struct { NSteps int DeltaTHalf float64 Gamma float64 ParticleMass float64 Acceleration Vec2 Kernel Kernel HorPeriodicity [2]float64 // -math.MaxFloat64, math.MaxFloat64 is open VertPeriodicity [2]float64 // -math.MaxFloat64, math.MaxFloat64 is open Reflections []Reflection Sources []ParticleSource Start []ParticleSource Viewport [2]Vec2 // upperleft and lower right }
func MakeConfig ¶
func MakeConfig() SphConfig
default values conifg all valuues are zero or empty arrays except defined in this function:
func MakeConfigFromFile ¶
type Token ¶
type Tokenizer ¶
type Tokenizer struct {
// contains filtered or unexported fields
}
func MakeTokenizer ¶
type UniformRectSpawner ¶
func (UniformRectSpawner) Spawn ¶
func (spwn UniformRectSpawner) Spawn(t float64) []Particle
spawn once uniformely in this rect