資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用Golang實現空間索引四叉樹的程式
空間索引是一種有效組織和查詢空間資料的關鍵技術。四叉樹是一種用於空間索引的流行資料結構，它將二維空間劃分為更小的區域。在本文中，我們將探討使用Golang實現四叉樹的兩個不同示例。下面演示的示例將執行諸如初始化、插入、顯示和視覺化四叉樹資料等操作。
解釋
四叉樹作為一種樹形資料結構，確保每個節點最多可以有四個子節點，這是一種通常用於將二維空間劃分為更小區域的屬性，從而可以有效地索引和查詢空間資料。這使得四叉樹非常適合地理資訊系統 (GIS)、遊戲中的碰撞檢測等場景。
語法
func NewQuadTree(b Boundary, c int) *QuadTree
該語法表示一個名為NewQuadTree的方法，該方法初始化並返回QuadTree結構的新例項，並以表示矩形區域的Boundary和表示容量的整數作為輸入引數。
func (qt *QuadTree) subdivide()
該語法表示一個名為subdivide的方法，該方法將當前的QuadTree節點拆分為四個子節點，每個子節點代表邊界的一個象限。它計算當前邊界的中心。
演算法
首先定義四叉樹節點結構。
實現節點插入邏輯。
定義拆分條件。
實現查詢邏輯。
建立示例場景並查詢四叉樹。
示例 1
在這個示例中，我們使用Go語言實現了一個四叉樹，使用Point和Boundary結構體分別表示二維點和矩形區域。NewQuadTree函式初始化一個QuadTree，Insert方法新增點並在容量達到時細分節點。在主函式中，建立了一個具有邊界和容量的QuadTree。
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結構體定義了一個矩形區域，其方法檢查點包含關係以及與其他邊界的相交關係。主函式初始化並演示了QuadTree結構體，使用displayQuadTree函式，最後查詢一定範圍內的點。
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實現四叉樹的兩種不同方法。第一種方法側重於插入點和使用基於文字的輸出進行查詢，突出了QuadTree的內部結構。第二種方法透過縮排視覺化結構來增強此功能，從而更清晰地描繪了細分和資料分佈。
185 次瀏覽
