🥮 mooncakes.io

    Quadtree

    Download zip
    Version
    0.1.0
    License
    Apache-2.0
    Repository
    Last updated
    last year
    Downloads
    39

    No dependencies

    #Quadtree

    English | 简体中文

    A high-performance spatial data structure implementation in MoonBit, providing efficient point storage and complex geometric queries for 2D spatial data.

    #🚀 Key Features

    • 🌳 Quadtree Creation – Create quadtrees with custom boundaries and capacity settings.
    • ➕ Point Management – Insert, update, remove, and find points with associated values.
    • 🔍 Advanced Queries – Support for rectangular, circular, polygonal, ray, and sector queries.
    • 📊 Spatial Analysis – K-nearest neighbors, density hotspots, and spatial autocorrelation.
    • 🔄 Tree Operations – Merge, intersection, difference, and filtering operations.
    • 🧹 Memory Management – Automatic node compression and memory optimization.
    • 📈 Performance – Iterative algorithms to prevent stack overflow with large datasets.
    • 🎯 Clustering – DBSCAN clustering algorithm for point cloud analysis.
    • 🔧 Adaptive Insertion – Density-based capacity adjustment for optimal tree structure.
    • 💾 Serialization – JSON serialization support for data persistence.

    #📥 Installation

    moon add moonbit-community/Quadtree

    #🚀 Usage Guide

    #🔨 Create

    You can create a quadtree with a specified boundary rectangle.

    fn example_create_quadtree() {
        let boundary = Rect::{ x: 0.0, y: 0.0, width: 100.0, height: 100.0 }
        let tree = new(boundary)
    }

    #➕ Insert & 🔍 Query

    Insert points with associated values and query them efficiently.

    fn example_insert_and_query() {
        let boundary = Rect::{ x: 0.0, y: 0.0, width: 100.0, height: 100.0 }
        let mut tree = new(boundary)

        // Insert points
        tree = insert(tree, Point::{ x: 10.0, y: 20.0 }, "point1", 4)
        tree = insert(tree, Point::{ x: 30.0, y: 40.0 }, "point2", 4)

        // Rectangular query
        let result = Array::new()
        query(tree, Rect::{ x: 0.0, y: 0.0, width: 50.0, height: 50.0 }, result)
        assert_eq(result.length(), 2)
    }

    #🔍 Advanced Geometric Queries

    Perform complex geometric queries with high performance.

    fn example_advanced_queries() {
        let boundary = Rect::{ x: 0.0, y: 0.0, width: 100.0, height: 100.0 }
        let mut tree = new(boundary)

        // Insert points
        tree = insert(tree, Point::{ x: 15.0, y: 25.0 }, "point1", 4)
        tree = insert(tree, Point::{ x: 50.0, y: 50.0 }, "point2", 4)

        // Circular query
        let center = Point::{ x: 15.0, y: 25.0 }
        let radius : Float = 10.0
        let circle_result = Array::new()
        query_circle(tree, center, radius, circle_result)

        // Polygonal query
        let polygon = Array::new()
        polygon.push(Point::{ x: 0.0, y: 0.0 })
        polygon.push(Point::{ x: 50.0, y: 0.0 })
        polygon.push(Point::{ x: 25.0, y: 50.0 })
        let polygon_result = Array::new()
        query_polygon(tree, polygon, polygon_result)

        // Ray query
        let origin = Point::{ x: 0.0, y: 0.0 }
        let direction = Point::{ x: 1.0, y: 1.0 }
        let ray_result = Array::new()
        query_ray(tree, origin, direction, 100.0, ray_result)

        // Sector query
        let sector_center = Point::{ x: 0.0, y: 0.0 }
        let start_angle : Float = 0.0
        let end_angle = @math.PI.to_float() / 2.0
        let sector_radius : Float = 50.0
        let sector_result = Array::new()
        query_sector(tree, sector_center, start_angle, end_angle, sector_radius, sector_result)
    }

    #📊 Spatial Analysis

    Perform advanced spatial analysis operations.

        fn example_spatial_analysis() {
        let boundary = Rect::{ x: 0.0, y: 0.0, width: 100.0, height: 100.0 }
        let mut tree = new(boundary)

        // Insert test points
        tree = insert(tree, Point::{ x: 10.0, y: 20.0 }, 5.0, 4)
        tree = insert(tree, Point::{ x: 15.0, y: 25.0 }, 7.0, 4)
        tree = insert(tree, Point::{ x: 20.0, y: 30.0 }, 6.0, 4)
        tree = insert(tree, Point::{ x: 80.0, y: 80.0 }, 8.0, 4)
        tree = insert(tree, Point::{ x: 85.0, y: 85.0 }, 9.0, 4)

        // K-nearest neighbors
        let target = Point::{ x: 12.0, y: 22.0 }
        let nearest = find_nearest(tree, target, 3)
        assert_eq(nearest.length(), 3)
        // nearest contains the 3 closest points to target

        // Find density hotspot
        let (hotspot_rect, count) = find_hotspot(tree, 10)
        assert_true(count > 0)
        // hotspot_rect contains the area with highest point density

        // Spatial autocorrelation (Moran's I)
        let autocorr = spatial_autocorrelation(tree)
        assert_true(autocorr >= -1.0 && autocorr <= 1.0)
        // autocorr indicates spatial clustering: >0 = clustered, <0 = dispersed

        // Get tree statistics
        let point_count = count(tree)
        let tree_depth = depth(tree)
        let (leaf_count, internal_count) = count_nodes(tree)

        assert_eq(point_count, 5)
        assert_true(tree_depth > 0)
        assert_eq(leaf_count, 1)
        assert_eq(internal_count, 0)
    }

    #🔄 Tree Operations

    Perform set-like operations on quadtrees.

    fn example_tree_operations() {
        let boundary = Rect::{ x: 0.0, y: 0.0, width: 100.0, height: 100.0 }
        let tree1 = new(boundary)
        let tree2 = new(boundary)

        // Merge two trees
        let merged = merge(tree1, tree2, 4)

        // Find intersection
        let intersect = intersection(tree1, tree2, 4)

        // Find difference
        let diff = difference(tree1, tree2, 4)

        // Filter points
        let filtered = filter(tree1, fn(pt, val) -> Bool { pt.x > 10.0 }, 4)
    }

    #🎯 Clustering

    Use DBSCAN algorithm for point cloud clustering.

    fn example_clustering() {
      let boundary = Rect::{ x: 0.0, y: 0.0, width: 100.0, height: 100.0 }
      let mut tree = new(boundary)

      // Insert points
      tree = insert(tree, Point::{ x: 10.0, y: 20.0 }, "point1", 4)
      tree = insert(tree, Point::{ x: 30.0, y: 40.0 }, "point2", 4)
      tree = insert(tree, Point::{ x: 50.0, y: 60.0 }, "point3", 4)

      // DBSCAN clustering
      let clusters = dbscan_cluster(tree, 5.0, 3)
      // Note: With these points, clusters.length() will be 0 because 
      // the points are too far apart (distance > 5.0)
      assert_eq(clusters.length(), 0)
    }

    #💾 Serialization

    Serialize and deserialize quadtrees for data persistence.

    fn example_serialization() {
        let boundary = Rect::{ x: 0.0, y: 0.0, width: 100.0, height: 100.0 }
        let mut tree = new(boundary)

        // Insert points
        tree = insert(tree, Point::{ x: 10.0, y: 20.0 }, "point1", 4)

        // Serialize to JSON
        let json = serialize(tree)
        assert_true(json.contains("\"type\""))
        assert_true(json.contains("\"boundary\""))
    }

    #🧹 Memory Management

    Automatic memory optimization and cleanup.

    fn example_memory_management() {
        let boundary = Rect::{ x: 0.0, y: 0.0, width: 100.0, height: 100.0 }
        let mut tree = new(boundary)

        // Remove points
        tree = remove(tree, Point::{ x: 10.0, y: 20.0 }, 4)

        // Remove range
        tree = remove_range(tree, Rect::{ x: 0.0, y: 0.0, width: 25.0, height: 25.0 }, 4)

        // Compress empty nodes
        tree = compress_node(tree)

        // Clear all points
        tree = clear(boundary)
    }

    #📜 License

    This project is licensed under the Apache-2.0 License. See LICENSE for details.

    ToFloat

    source
    pub trait ToFloat {
      to_float(Self) -> Float
    }

    定义一个 ToFloat trait，用于将类型转换为 Float
    impl ToFloat for Int
    impl ToFloat for Float
    impl ToFloat for Double

    Point

    source
    pub(all) struct Point {
      x : Float
      y : Float
    }

    二维点结构
    impl Eq for Point
    impl Show for Point

    QuadtreeNode

    source
    pub(all) enum QuadtreeNode[T] {
      Leaf(Array[(Point, T)], Rect)
      Internal(Array[QuadtreeNode[T]], Rect)
    }

    四叉树节点

    Rect

    source
    pub(all) struct Rect {
      x : Float
      y : Float
      width : Float
      height : Float
    }

    区域边界
    impl Eq for Rect
    impl Show for Rect

    batch_update

    source
    fn[T] batch_update(node : QuadtreeNode[T], updates : Array[(Point, T)], capacity : Int) -> QuadtreeNode[T]

    批量更新

    clear

    source
    fn[T] clear(boundary : Rect) -> QuadtreeNode[T]

    清空四叉树，返回空树

    compress_node

    source
    fn[T] compress_node(node : QuadtreeNode[T]) -> QuadtreeNode[T]

    节点合并与压缩：如果所有子节点都是空Leaf，则合并为一个空Leaf

    count

    source
    fn[T] count(node : QuadtreeNode[T]) -> Int

    统计四叉树中所有点的数量

    count_nodes

    source
    fn[T] count_nodes(node : QuadtreeNode[T]) -> (Int, Int)

    统计 Leaf 和 Internal 节点数量

    dbscan_cluster

    source
    fn[T] dbscan_cluster(node : QuadtreeNode[T], eps : Float, min_points : Int) -> Array[Array[Point]]

    使用DBSCAN算法进行点云聚类

    depth

    source
    fn[T] depth(node : QuadtreeNode[T]) -> Int

    统计四叉树的最大深度

    difference

    source
    fn[T] difference(tree1 : QuadtreeNode[T], tree2 : QuadtreeNode[T], capacity : Int) -> QuadtreeNode[T]

    差集操作 - 从tree1中移除tree2中存在的点

    filter

    source
    fn[T] filter(node : QuadtreeNode[T], predicate : (Point, T) -> Bool, capacity : Int) -> QuadtreeNode[T]

    根据条件筛选点

    find

    source
    fn[T : Eq] find(node : QuadtreeNode[T], point : Point) -> T?

    查找某个点的内容

    find_hotspot

    source
    fn[T] find_hotspot(node : QuadtreeNode[T], grid_size : Int) -> (Rect, Int)

    查找密度最高的区域

    find_nearest

    source
    fn[T] find_nearest(node : QuadtreeNode[T], target : Point, k : Int) -> Array[(Point, T, Float)]

    找出最近的 K 个点 (K-Nearest Neighbors)

    insert

    source
    fn[T] insert(node : QuadtreeNode[T], point : Point, value : T, capacity : Int) -> QuadtreeNode[T]

    insert_adaptive

    source
    fn[T] insert_adaptive(node : QuadtreeNode[T], point : Point, value : T, min_capacity : Int, max_capacity : Int, density_threshold : Float) -> QuadtreeNode[T]

    基于点的分布密度自适应划分

    insert_many

    source
    fn[T] insert_many(node : QuadtreeNode[T], points : Array[Point], values : Array[T], capacity : Int) -> QuadtreeNode[T]

    批量插入多个点及内容

    intersection

    source
    fn[T] intersection(tree1 : QuadtreeNode[T], tree2 : QuadtreeNode[T], capacity : Int) -> QuadtreeNode[T]

    相交操作 - 找出两个四叉树共有的点

    merge

    source
    fn[T] merge(tree1 : QuadtreeNode[T], tree2 : QuadtreeNode[T], capacity : Int) -> QuadtreeNode[T]

    合并两个四叉树

    move_point

    source
    fn[T : Eq] move_point(node : QuadtreeNode[T], old_point : Point, new_point : Point, capacity : Int) -> QuadtreeNode[T]

    移动点（保持引用）

    new

    source
    fn[T] new(boundary : Rect) -> QuadtreeNode[T]

    创建一个空四叉树

    point_in_rect

    source
    fn point_in_rect(p : Point, rect : Rect) -> Bool

    判断点是否在矩形范围内

    query

    source
    fn[T] query(node : QuadtreeNode[T], range : Rect, result : Array[(Point, T)]) -> Unit

    query_circle

    source
    fn[T] query_circle(node : QuadtreeNode[T], center : Point, radius : Float, result : Array[(Point, T)]) -> Unit

    圆形范围查询（迭代版本）

    query_many

    source
    fn[T] query_many(node : QuadtreeNode[T], ranges : Array[Rect]) -> Array[(Point, T)]

    批量查询多个区域

    query_polygon

    source
    fn[T] query_polygon(node : QuadtreeNode[T], polygon : Array[Point], result : Array[(Point, T)]) -> Unit

    多边形范围查询（迭代版本）

    query_ray

    source
    fn[T] query_ray(node : QuadtreeNode[T], origin : Point, direction : Point, max_distance : Float, result : Array[(Point, T)]) -> Unit

    射线查询（迭代版本）

    query_sector

    source
    fn[T] query_sector(node : QuadtreeNode[T], center : Point, start_angle : Float, end_angle : Float, radius : Float, result : Array[(Point, T)]) -> Unit

    扇形范围查询（迭代版本）

    rect_intersect

    source
    fn rect_intersect(a : Rect, b : Rect) -> Bool

    判断两个矩形是否相交

    remove

    source
    fn[T] remove(node : QuadtreeNode[T], point : Point, capacity : Int) -> QuadtreeNode[T]

    删除四叉树中的指定点

    remove_range

    source
    fn[T] remove_range(node : QuadtreeNode[T], range : Rect, capacity : Int) -> QuadtreeNode[T]

    删除某一区域内的所有点

    serialize

    source
    fn[T : Show] serialize(node : QuadtreeNode[T]) -> String

    序列化四叉树为JSON格式字符串

    spatial_autocorrelation

    source
    fn[T : ToFloat] spatial_autocorrelation(node : QuadtreeNode[T]) -> Float

    计算空间自相关性（类似Moran's I）

    subdivide

    source
    fn subdivide(rect : Rect) -> Array[Rect]

    将矩形分为四个子区域

    to_array

    source
    fn[T] to_array(node : QuadtreeNode[T], result : Array[(Point, T)]) -> Unit

    遍历四叉树所有点及内容，收集到数组

    update

    source
    fn[T] update(node : QuadtreeNode[T], point : Point, new_value : T, capacity : Int) -> QuadtreeNode[T]

    更新四叉树中指定点的内容

    update_incremental

    source
    fn[T] update_incremental(node : QuadtreeNode[T], old_point : Point, new_point : Point, value : T, capacity : Int) -> QuadtreeNode[T]

    Source Files

    Powered by MoonBit

    Site sourceReport issueModulesSkillsCLIBuild queueStatistics

    © 2026 mooncakes.io