Golang 程序实现四叉树用于空间索引
go programmingserver side programmingprogramming
空间索引是高效组织和查询空间数据的关键技术。四叉树是一种用于空间索引的流行数据结构，将二维空间划分为更小的区域。在本文中，我们将探讨两个不同的示例，以在 Golang 中实现四叉树。下面演示的示例将执行四叉树数据的初始化、插入、显示和可视化等操作。
解释
四叉树作为一种树形数据结构，可确保每个节点最多可以有四个子节点，这是将二维空间划分为更小区域通常需要的属性，从而可以高效地索引和查询空间数据。它使四叉树非常适合地理信息系统 (GIS)、游戏中的碰撞检测等场景。
语法
func NewQuadTree(b Boundary, c int) *QuadTree
该语法表示一种名为 NewQuadTree 的方法，该方法初始化并返回 QuadTree 结构的新实例，以表示矩形区域的 Boundary 和表示容量的整数作为输入参数。
func (qt *QuadTree) subdivide()
该语法表示一种名为 subdivide 的方法，该方法将当前 QuadTree 拆分为四个子节点，计算当前边界的中心，每个子节点代表边界的一个象限。
算法
从定义四叉树节点结构。
实现节点插入逻辑。
定义拆分条件。
实现查询逻辑。
创建示例场景并查询四叉树。
示例 1
在此示例中，我们用 Go 实现四叉树，使用 Point 和 Boundary 结构体表示二维点和矩形区域。NewQuadTree 函数初始化四叉树，Insert 方法在达到容量时添加点并细分节点。在主函数中，创建具有边界和容量的四叉树。
package main
import (
"fmt"
"strings"
)
type Point struct{ x, y float64 }
type Boundary struct{ xMin, yMin, xMax, yMax float64 }
type QuadTree struct {
boundary Boundary
capacity int
points []Point
}
func NewQuadTree(b Boundary, c int) *QuadTree {
return &QuadTree{boundary: b, capacity: c}
}
func (qt *QuadTree) Insert(p Point) {
if qt.boundary.containsPoint(p) && len(qt.points) < qt.capacity {
qt.points = append(qt.points, p)
}
}
func (b *Boundary) containsPoint(p Point) bool {
return p.x >= b.xMin && p.x <= b.xMax && p.y >= b.yMin && p.y <= b.yMax
}
func main() {
qt := NewQuadTree(Boundary{0, 0, 100, 100}, 4)
points := []Point{{25, 75}, {60, 40}, {10, 20}, {80, 90}, {45, 60}, {70, 30}, {15, 85}, {90, 10}, {30, 30}, {70, 70}}
for _, p := range points {
qt.Insert(p)
}
fmt.Println("Quadtree after insertion:")
displayQuadTree(qt, 0)
}
func displayQuadTree(qt *QuadTree, d int) {
fmt.Printf("\n%sBoundary: (%.2f, %.2f, %.2f, %.2f), Points: %d", getIndent(d), qt.boundary.xMin, qt.boundary.yMin, qt.boundary.xMax, qt.boundary.yMax, len(qt.points))
}
func getIndent(d int) string {
return strings.Repeat(" ", d)
}
输出
Quadtree after insertion: Boundary: (0.00, 0.00, 100.00, 100.00), Points: 4
示例 2
在此示例中，为了在 Go 中实现四叉树，我们定义了一个 QuadTree 结构，该结构具有边界、容量、点和子节点，并支持插入点和查询给定边界内的点。Insert 方法将点添加到 QuadTree 中，如果超出容量，则细分节点，而 QueryRange 函数检索指定边界内的点。Boundary 结构定义一个矩形区域，其方法检查点的包含和与其他边界的相交。主函数使用 displayQuadTree 函数初始化并演示 QuadTree 结构，最后查询范围内的点。
package main
import "fmt"
type Point struct{ x, y float64 }
type Boundary struct{ xMin, yMin, xMax, yMax float64 }
type QuadTree struct {
boundary Boundary
capacity int
points []Point
divided bool
nw, ne, sw, se *QuadTree
}
func NewQuadTree(b Boundary, c int) *QuadTree { return &QuadTree{boundary: b, capacity: c} }
func (qt *QuadTree) Insert(p Point) {
if !qt.boundary.containsPoint(p) { return }
if len(qt.points) < qt.capacity { qt.points = append(qt.points, p); return }
if !qt.divided { qt.subdivide() }
qt.nw.Insert(p); qt.ne.Insert(p); qt.sw.Insert(p); qt.se.Insert(p)
}
func (qt *QuadTree) QueryRange(rb Boundary) []Point {
var foundPoints []Point
if !qt.boundary.intersectsBoundary(rb) { return foundPoints }
for _, p := range qt.points { if rb.containsPoint(p) { foundPoints = append(foundPoints, p) } }
if qt.divided {
foundPoints = append(foundPoints, qt.nw.QueryRange(rb)...)
foundPoints = append(foundPoints, qt.ne.QueryRange(rb)...)
foundPoints = append(foundPoints, qt.sw.QueryRange(rb)...)
foundPoints = append(foundPoints, qt.se.QueryRange(rb)...)
}
return foundPoints
}
func (b *Boundary) containsPoint(p Point) bool {
return p.x >= b.xMin && p.x <= b.xMax && p.y >= b.yMin && p.y <= b.yMax
}
func (b *Boundary) intersectsBoundary(rb Boundary) bool {
return !(rb.xMax < b.xMin || rb.xMin > b.xMax || rb.yMax < b.yMin || rb.yMin > b.yMax)
}
func (qt *QuadTree) subdivide() {
cx, cy := (qt.boundary.xMin+qt.boundary.xMax)/2, (qt.boundary.yMin+qt.boundary.yMax)/2
qt.nw, qt.ne, qt.sw, qt.se = NewQuadTree(Boundary{qt.boundary.xMin, qt.boundary.yMin, cx, cy}, qt.capacity), NewQuadTree(Boundary{cx, qt.boundary.yMin, qt.boundary.xMax, cy}, qt.capacity), NewQuadTree(Boundary{qt.boundary.xMin, cy, cx, qt.boundary.yMax}, qt.capacity), NewQuadTree(Boundary{cx, cy, qt.boundary.xMax, qt.boundary.yMax}, qt.capacity)
qt.divided = true
}
func main() {
qt := NewQuadTree(Boundary{0, 0, 100, 100}, 4)
points := []Point{{25, 75}, {60, 40}, {10, 20}, {80, 90}, {45, 60}, {70, 30}}
fmt.Println("Inserting points:")
for _, p := range points { qt.Insert(p); fmt.Printf("(%v, %v) ", p.x, p.y) }
fmt.Println("\nQuadtree structure:")
displayQuadTree(qt, 0)
queryRange := Boundary{20, 70, 30, 80}
foundPoints := qt.QueryRange(queryRange)
fmt.Println("\nQuery Range:", queryRange)
fmt.Println("Points within query range:", foundPoints)
}
func displayQuadTree(qt *QuadTree, d int) {
fmt.Printf("\n%sBoundary: (%.2f, %.2f, %.2f, %.2f), Points: %d", getIndent(d), qt.boundary.xMin, qt.boundary.yMin, qt.boundary.xMax, qt.boundary.yMax, len(qt.points))
if qt.divided { displayQuadTree(qt.nw, d+1); displayQuadTree(qt.ne, d+1); displayQuadTree(qt.sw, d+1); displayQuadTree(qt.se, d+1) }
}
func getIndent(d int) string { i := ""; for j := 0; j < d; j++ { i += " " }; return i }
输出
Inserting points:
(25, 75) (60, 40) (10, 20) (80, 90) (45, 60) (70, 30)
Quadtree structure:
Boundary: (0.00, 0.00, 100.00, 100.00), Points: 4
Boundary: (0.00, 0.00, 50.00, 50.00), Points: 0
Boundary: (50.00, 0.00, 100.00, 50.00), Points: 1
Boundary: (0.00, 50.00, 50.00, 100.00), Points: 1
Boundary: (50.00, 50.00, 100.00, 100.00), Points: 0
Query Range: {20 70 30 80}
Points within query range: [{25 75}]
实际实施
物理模拟:碰撞检测是物理模拟和视频游戏的重要组成部分，四叉树的使用已被证明是一种有效的方法。在模拟中，对象被放置在树结构的节点之间，通过选择检查与当前场景相关的节点，可以有效地检测碰撞。此解决方案成功减少了成对碰撞测试的数量，同时提高了模拟性能。
分形生成和地形建模:四叉树通常用于创建分形景观和地形模型。基于四叉树的算法可以通过反复将其划分为较小的部分来生成详细而逼真的景观表示。
结论
四叉树在用于空间索引时为管理和查询空间数据提供了一种有效的解决方案。在本文中，我们探讨了在 Golang 中实现四叉树的两种不同方法。第一种方法侧重于插入点并使用基于文本的输出进行查询，突出显示四叉树的内部结构。第二种方法通过缩进可视化结构来增强这一点，提供更清晰的细分和数据分布描述。
