Quadtree

 1type Point struct {
 2    X, Y float64
 3}
 4
 5type Rectangle struct {
 6    X, Y, Width, Height float64
 7}
 8
 9func (r *Rectangle) Contains(p Point) bool {
10    return p.X >= r.X && p.X < r.X+r.Width &&
11           p.Y >= r.Y && p.Y < r.Y+r.Height
12}
13
14func (r *Rectangle) Intersects(other *Rectangle) bool {
15    return !(other.X > r.X+r.Width ||
16             other.X+other.Width < r.X ||
17             other.Y > r.Y+r.Height ||
18             other.Y+other.Height < r.Y)
19}
20
21type QuadTree struct {
22    boundary  *Rectangle
23    capacity  int
24    points    []Point
25    divided   bool
26    
27    // Four quadrants
28    northwest *QuadTree
29    northeast *QuadTree
30    southwest *QuadTree
31    southeast *QuadTree
32}
33
34func NewQuadTree(boundary *Rectangle, capacity int) *QuadTree {
35    return &QuadTree{
36        boundary: boundary,
37        capacity: capacity,
38        points:   make([]Point, 0, capacity),
39    }
40}

 1func (qt *QuadTree) Insert(p Point) bool {
 2    // Point not in boundary
 3    if !qt.boundary.Contains(p) {
 4        return false
 5    }
 6    
 7    // If not at capacity, add point
 8    if len(qt.points) < qt.capacity {
 9        qt.points = append(qt.points, p)
10        return true
11    }
12    
13    // Subdivide if not already divided
14    if !qt.divided {
15        qt.subdivide()
16    }
17    
18    // Insert into appropriate quadrant
19    if qt.northwest.Insert(p) {
20        return true
21    }
22    if qt.northeast.Insert(p) {
23        return true
24    }
25    if qt.southwest.Insert(p) {
26        return true
27    }
28    if qt.southeast.Insert(p) {
29        return true
30    }
31    
32    return false
33}
34
35func (qt *QuadTree) subdivide() {
36    x := qt.boundary.X
37    y := qt.boundary.Y
38    w := qt.boundary.Width / 2
39    h := qt.boundary.Height / 2
40    
41    qt.northwest = NewQuadTree(&Rectangle{x, y, w, h}, qt.capacity)
42    qt.northeast = NewQuadTree(&Rectangle{x + w, y, w, h}, qt.capacity)
43    qt.southwest = NewQuadTree(&Rectangle{x, y + h, w, h}, qt.capacity)
44    qt.southeast = NewQuadTree(&Rectangle{x + w, y + h, w, h}, qt.capacity)
45    
46    qt.divided = true
47}

 1func (qt *QuadTree) Query(searchRange *Rectangle) []Point {
 2    found := []Point{}
 3    
 4    // If range doesn't intersect boundary, return empty
 5    if !qt.boundary.Intersects(searchRange) {
 6        return found
 7    }
 8    
 9    // Check points in this node
10    for _, p := range qt.points {
11        if searchRange.Contains(p) {
12            found = append(found, p)
13        }
14    }
15    
16    // If divided, check children
17    if qt.divided {
18        found = append(found, qt.northwest.Query(searchRange)...)
19        found = append(found, qt.northeast.Query(searchRange)...)
20        found = append(found, qt.southwest.Query(searchRange)...)
21        found = append(found, qt.southeast.Query(searchRange)...)
22    }
23    
24    return found
25}
26
27// Example
28func main() {
29    qt := NewQuadTree(&Rectangle{0, 0, 100, 100}, 4)
30    
31    qt.Insert(Point{25, 25})
32    qt.Insert(Point{75, 25})
33    qt.Insert(Point{25, 75})
34    qt.Insert(Point{75, 75})
35    
36    // Query points in region
37    searchRange := &Rectangle{20, 20, 60, 60}
38    points := qt.Query(searchRange)
39    fmt.Println("Found points:", points)
40}

 1type LODQuadTree struct {
 2    boundary *Rectangle
 3    level    int
 4    maxLevel int
 5    
 6    // Mesh data for this LOD level
 7    vertices  []Point
 8    indices   []int
 9    
10    // Children for higher detail
11    children [4]*LODQuadTree
12}
13
14func NewLODQuadTree(boundary *Rectangle, level, maxLevel int) *LODQuadTree {
15    qt := &LODQuadTree{
16        boundary: boundary,
17        level:    level,
18        maxLevel: maxLevel,
19    }
20    
21    // Generate mesh for this level
22    qt.generateMesh()
23    
24    return qt
25}
26
27func (qt *LODQuadTree) generateMesh() {
28    // Generate vertices based on level
29    // Higher level = more detail
30    detail := 1 << uint(qt.level) // 2^level
31    
32    for i := 0; i <= detail; i++ {
33        for j := 0; j <= detail; j++ {
34            x := qt.boundary.X + float64(i)*qt.boundary.Width/float64(detail)
35            y := qt.boundary.Y + float64(j)*qt.boundary.Height/float64(detail)
36            qt.vertices = append(qt.vertices, Point{x, y})
37        }
38    }
39    
40    // Generate indices for triangles
41    // ... (triangle strip or indexed triangles)
42}
43
44func (qt *LODQuadTree) GetLODForDistance(cameraPos Point, distance float64) *LODQuadTree {
45    // Calculate distance from camera to quad center
46    centerX := qt.boundary.X + qt.boundary.Width/2
47    centerY := qt.boundary.Y + qt.boundary.Height/2
48    
49    dx := cameraPos.X - centerX
50    dy := cameraPos.Y - centerY
51    dist := math.Sqrt(dx*dx + dy*dy)
52    
53    // Determine LOD level based on distance
54    if dist < distance && qt.level < qt.maxLevel {
55        // Need higher detail, subdivide
56        if qt.children[0] == nil {
57            qt.subdivide()
58        }
59        
60        // Return appropriate child
61        // ... (determine which child based on camera position)
62    }
63    
64    return qt
65}
66
67func (qt *LODQuadTree) subdivide() {
68    x := qt.boundary.X
69    y := qt.boundary.Y
70    w := qt.boundary.Width / 2
71    h := qt.boundary.Height / 2
72    
73    qt.children[0] = NewLODQuadTree(&Rectangle{x, y, w, h}, qt.level+1, qt.maxLevel)
74    qt.children[1] = NewLODQuadTree(&Rectangle{x + w, y, w, h}, qt.level+1, qt.maxLevel)
75    qt.children[2] = NewLODQuadTree(&Rectangle{x, y + h, w, h}, qt.level+1, qt.maxLevel)
76    qt.children[3] = NewLODQuadTree(&Rectangle{x + w, y + h, w, h}, qt.level+1, qt.maxLevel)
77}
78
79func (qt *LODQuadTree) Render(cameraPos Point, lodDistance float64) {
80    lod := qt.GetLODForDistance(cameraPos, lodDistance)
81    
82    // Render mesh at appropriate LOD
83    // ... (OpenGL/Vulkan rendering code)
84}

 1type Frustum struct {
 2    planes [6]Plane // 6 planes defining view frustum
 3}
 4
 5type Plane struct {
 6    normal Point
 7    distance float64
 8}
 9
10func (qt *LODQuadTree) FrustumCull(frustum *Frustum) []*LODQuadTree {
11    visible := []*LODQuadTree{}
12    
13    // Check if boundary intersects frustum
14    if !qt.boundary.IntersectsFrustum(frustum) {
15        return visible
16    }
17    
18    // If leaf or all children visible, add this node
19    if qt.children[0] == nil {
20        visible = append(visible, qt)
21    } else {
22        // Recursively check children
23        for _, child := range qt.children {
24            if child != nil {
25                visible = append(visible, child.FrustumCull(frustum)...)
26            }
27        }
28    }
29    
30    return visible
31}

 1type TerrainQuadTree struct {
 2    boundary  *Rectangle
 3    heightmap [][]float64
 4    level     int
 5    maxLevel  int
 6    
 7    // Mesh data
 8    vertices []Vertex
 9    normals  []Point
10    
11    children [4]*TerrainQuadTree
12}
13
14type Vertex struct {
15    pos    Point
16    height float64
17}
18
19func (tqt *TerrainQuadTree) GenerateTerrainMesh() {
20    detail := 1 << uint(tqt.level)
21    
22    for i := 0; i <= detail; i++ {
23        for j := 0; j <= detail; j++ {
24            // Sample heightmap
25            x := tqt.boundary.X + float64(i)*tqt.boundary.Width/float64(detail)
26            y := tqt.boundary.Y + float64(j)*tqt.boundary.Height/float64(detail)
27            
28            height := tqt.sampleHeightmap(x, y)
29            
30            tqt.vertices = append(tqt.vertices, Vertex{
31                pos:    Point{x, y},
32                height: height,
33            })
34        }
35    }
36    
37    // Calculate normals for lighting
38    tqt.calculateNormals()
39}
40
41func (tqt *TerrainQuadTree) sampleHeightmap(x, y float64) float64 {
42    // Bilinear interpolation from heightmap
43    // ... (implementation)
44    return 0.0
45}
46
47func (tqt *TerrainQuadTree) calculateNormals() {
48    // Calculate normals from vertices for smooth shading
49    // ... (implementation)
50}

 1type CollisionObject struct {
 2    pos    Point
 3    radius float64
 4}
 5
 6func (qt *QuadTree) CheckCollisions(obj *CollisionObject) []Point {
 7    // Create search range based on object's bounding box
 8    searchRange := &Rectangle{
 9        X:      obj.pos.X - obj.radius,
10        Y:      obj.pos.Y - obj.radius,
11        Width:  obj.radius * 2,
12        Height: obj.radius * 2,
13    }
14    
15    // Query potential collisions
16    candidates := qt.Query(searchRange)
17    
18    // Precise collision check
19    collisions := []Point{}
20    for _, p := range candidates {
21        dx := p.X - obj.pos.X
22        dy := p.Y - obj.pos.Y
23        dist := math.Sqrt(dx*dx + dy*dy)
24        
25        if dist < obj.radius {
26            collisions = append(collisions, p)
27        }
28    }
29    
30    return collisions
31}

 1type ImageQuadTree struct {
 2    boundary *Rectangle
 3    color    [3]uint8 // RGB
 4    error    float64
 5    
 6    children [4]*ImageQuadTree
 7}
 8
 9func CompressImage(img [][]color.RGBA, threshold float64) *ImageQuadTree {
10    boundary := &Rectangle{0, 0, float64(len(img[0])), float64(len(img))}
11    return compressRegion(img, boundary, threshold)
12}
13
14func compressRegion(img [][]color.RGBA, boundary *Rectangle, threshold float64) *ImageQuadTree {
15    qt := &ImageQuadTree{boundary: boundary}
16    
17    // Calculate average color
18    avgColor, colorError := calculateAverageColor(img, boundary)
19    qt.color = avgColor
20    qt.error = colorError
21    
22    // If error is below threshold, don't subdivide
23    if colorError < threshold || boundary.Width <= 1 || boundary.Height <= 1 {
24        return qt
25    }
26    
27    // Subdivide
28    x := boundary.X
29    y := boundary.Y
30    w := boundary.Width / 2
31    h := boundary.Height / 2
32    
33    qt.children[0] = compressRegion(img, &Rectangle{x, y, w, h}, threshold)
34    qt.children[1] = compressRegion(img, &Rectangle{x + w, y, w, h}, threshold)
35    qt.children[2] = compressRegion(img, &Rectangle{x, y + h, w, h}, threshold)
36    qt.children[3] = compressRegion(img, &Rectangle{x + w, y + h, w, h}, threshold)
37    
38    return qt
39}
40
41func calculateAverageColor(img [][]color.RGBA, boundary *Rectangle) ([3]uint8, float64) {
42    var sumR, sumG, sumB uint32
43    count := 0
44    
45    for y := int(boundary.Y); y < int(boundary.Y+boundary.Height); y++ {
46        for x := int(boundary.X); x < int(boundary.X+boundary.Width); x++ {
47            c := img[y][x]
48            sumR += uint32(c.R)
49            sumG += uint32(c.G)
50            sumB += uint32(c.B)
51            count++
52        }
53    }
54    
55    avgR := uint8(sumR / uint32(count))
56    avgG := uint8(sumG / uint32(count))
57    avgB := uint8(sumB / uint32(count))
58    
59    // Calculate error (variance)
60    var errorSum float64
61    for y := int(boundary.Y); y < int(boundary.Y+boundary.Height); y++ {
62        for x := int(boundary.X); x < int(boundary.X+boundary.Width); x++ {
63            c := img[y][x]
64            dr := float64(c.R) - float64(avgR)
65            dg := float64(c.G) - float64(avgG)
66            db := float64(c.B) - float64(avgB)
67            errorSum += dr*dr + dg*dg + db*db
68        }
69    }
70    
71    return [3]uint8{avgR, avgG, avgB}, errorSum / float64(count)
72}

 1type Octree struct {
 2    boundary *Cube
 3    capacity int
 4    points   []Point3D
 5    divided  bool
 6    
 7    // Eight octants
 8    children [8]*Octree
 9}
10
11type Point3D struct {
12    X, Y, Z float64
13}
14
15type Cube struct {
16    X, Y, Z, Size float64
17}