npm package discovery and stats viewer.

Discover Tips

  • General search

    [free text search, go nuts!]

  • Package details

    pkg:[package-name]

  • User packages

    @[username]

Sponsor

Optimize Toolset

I’ve always been into building performant and accessible sites, but lately I’ve been taking it extremely seriously. So much so that I’ve been building a tool to help me optimize and monitor the sites that I build to make sure that I’m making an attempt to offer the best experience to those who visit them. If you’re into performant, accessible and SEO friendly sites, you might like it too! You can check it out at Optimize Toolset.

About

Hi, 👋, I’m Ryan Hefner  and I built this site for me, and you! The goal of this site was to provide an easy way for me to check the stats on my npm packages, both for prioritizing issues and updates, and to give me a little kick in the pants to keep up on stuff.

As I was building it, I realized that I was actually using the tool to build the tool, and figured I might as well put this out there and hopefully others will find it to be a fast and useful way to search and browse npm packages as I have.

If you’re interested in other things I’m working on, follow me on Twitter or check out the open source projects I’ve been publishing on GitHub.

I am also working on a Twitter bot for this site to tweet the most popular, newest, random packages from npm. Please follow that account now and it will start sending out packages soon–ish.

Open Software & Tools

This site wouldn’t be possible without the immense generosity and tireless efforts from the people who make contributions to the world and share their work via open source initiatives. Thank you 🙏

© 2024 – Pkg Stats / Ryan Hefner

quadtree-lib

v1.0.9

Published

Efficient quadtrees library written in CoffeeScript.

Downloads

1,651

Readme

If you are already familiar with quadtrees, then you should perfectly understand how to use this library.

Otherwise, there are many online articles (wikipedia does the job) which explain the advantages of using the quadtree datastructure in certain situations.

If you want to see the library in action :

Setup

Using npm / yarn

From the command line :

npm install quadtree-lib or yarn add quadtree-lib

Using bower

bower install quadtree-lib

Using gulp

In your favorite terminal :

# 1°clone the repo
git clone https://github.com/elbywan/quadtree-lib
# 2° change dir
cd quadtree-lib
# 3° build the library
gulp
# 4° build the documentation
gulp doc
# 5° run performance tests
gulp perf
# 6° profit

Usage

Import

This library is bundled in UMD format.

Examples :

  • Import using commonjs :
Quadtree = require("quadtree-lib")
  • Import globally with a script tag :
<script src="path/to/quadtree-lib.min.js"></script>

Init

First step is to initialize a new Quadtree object.

var quadtree = new Quadtree({
    width: 500,
    height: 500,
    maxElements: 5 //Optional
})

width and height are mandatory attributes.

maxElements (default 1) is the maximum number of elements contained in a leaf before it splits into child trees.

For typescript users

A set of declaration files (.d.ts) is included, which means that you have access to auto-completion and embedded documentation in your favorite IDE.

If you are using the library globally with a <script> tag, add the following declaration import :

/// <reference types="quadtree-lib" />

Otherwise, if you are using the commonjs way :

import * as Quadtree from "quadtree-lib"

Adding elements

Elements must be objects, with coordinates set.

Optionally, you can pass a boolean argument which, if set to true, will remove/push the object into the quadtree each time its coordinates or dimensions are set (ex: item.x = ... or item.width = ...).

Without this flag, x / y / width / height properties should not be changed after insertion.

quadtree.push({
    x: 10,      //Mandatory
    y: 10,      //Mandatory
    width: 1,   //Optional, defaults to 1
    height: 2   //Optional, defaults to 1
}, true) //Optional, defaults to false

To insert an array of elements, use the pushAll method which is faster than inserting each element with push.

quadtree.pushAll([
    {x: 1, y: 1},
    {x: 2, y: 2}
    // ... //
])

Removing elements

Removes an item by reference.

quadtree.remove(item)

Clearing the tree

Removes the tree contents and restores it to pristine state.

quatree.clear()

Filtering the tree

Filters the quadtree and returns a clone containing only the elements determined by a predicate function.

var filtered = quadtree.filter(function(element){
    return element.x > 50
})

Opposite: quadtree.reject

Retrieve colliding elements

Gets every element that collides with the parameter 2d object.

var colliding = quadtree.colliding({
    x: 10,
    y: 10,
    width: 5, //Optional
    height: 5 //Optional
})

The default collision function is a basic bounding box algorithm. You can change it by providing a function as a second argument.

var colliding = quadtree.colliding({
    x: 10,
    y: 10
}, function(element1, element2){
    return // Place collision algorithm here //
})

Perform an action on colliding elements

Performs an action on every element that collides with the parameter 2d object.

onCollision({
    x: 10,
    y: 20
}, function(item) {
    /* Action on colliding item */

    // As with all iterative methods, modifying the quadtree or its contents is discouraged. //
}, function(element1, element2){
    /* Optional custom collision algorithm */
    return // Place predicate here //
})

Retrieve by properties

Gets every element that match the parameter properties.

quadtree.push({x: 0, y: 0, animal: 'rabbit'})
var match = quadtree.where({
    animal: 'rabbit'
})

Alias : quadtree.get

Retrieve by predicate

Gets every element that validate the given predicate.

quadtree.find(function(element){
    return element.color === 'red' //Example
})

Iterate over the elements

Performs an action on each element of the Quadtree (breadth first traversal).

quadtree.each(function(element){
    console.log(element.color)

    // As with all iterative methods, modifying the quadtree or its contents is discouraged. //
})

Like some other data structures, it is strongly discouraged to update Quadtree elements (especially coordinates / dimensions) or the Quadtree itself while iterating on it.

Visit the tree nodes

Visits each node of the quadtree. (meaning subtrees)

quadtree.visit(function(){
    // This function is called once for each node.
    // *this* is a pointer to the current node.
    console.log(this.contents)

    // As with all iterative methods, modifying the quadtree or its contents is discouraged. //
})

Pretty print

Outputs the tree and its contents in an eye friendly format.

var quadtree = new Quadtree({
  width: 10,
  height: 10,
  maxElements: 1
});

var elementArray = [
  element0 = {
    x: 0,
    y: 0,
    toString: function() {
      return 0;
    }
  }, element1 = {
    x: 3,
    y: 3,
    toString: function() {
      return 1;
    }
  }
];

quadtree.pushAll(elementArray);

console.log(quadtree.pretty());

Console output :

| ROOT
| ------------
└──┐
   | NW
   | ------------
   └──┐
      | SE
      | ------------
      | * Leaf content *
      |   1
      | NW
      | ------------
      | * Leaf content *
      |   0

Further documentation

You can find the annotated source code here.

Generated with Docco.

License

The MIT License (MIT)

Copyright (c) 2015 Julien Elbaz

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.