quadtree-js - GitLite

KO | EN

gitlite — search

#javascript #typescript #llm #go #golang #rust #deep-learning #linux #nodejs #java #windows #awesome #kubernetes #vue

quadtree-js

(★ 640)

A lightweight quadtree implementation for javascript

파일 탐색기

최종 버전 다운로드 (.zip)

- dynamic.html
- index.html
- many.html
- quadtree.min.js
- retrieve-nodes.html
- simple.html
- style.css
- test-10000-1.1.3.html
- test-10000-1.2.0.html
- test-retrieve.html
.gitignore
LICENSE.md
package-lock.json
package.json
quadtree.d.ts
quadtree.js
quadtree.min.js
README.md

# 설치 가이드

1. 코드 내려받기

git clone https://github.com/timohausmann/quadtree-js

깃허브에서 프로젝트 코드 전체를 내 컴퓨터로 내려받습니다.

cd quadtree-js

방금 내려받은 프로젝트 폴더 안으로 이동합니다.

2. Node.js

쉬움 추천

사전 준비물

Git GitHub에서 프로젝트 코드를 내려받으려면 필요합니다.
Node.js npm 명령어를 쓰려면 Node.js가 설치되어 있어야 합니다. LTS(장기지원) 버전을 추천합니다.

npm i -D @timohausmann/quadtree-js

이 명령어를 터미널에 그대로 입력해 실행하세요.

<script src="https://cdn.jsdelivr.net/npm/@timohausmann/quadtree-js/quadtree.min.js"></script>

이 명령어를 터미널에 그대로 입력해 실행하세요.

✅ 명령어 실행 후 터미널에 나타나는 주소(보통 http://localhost:3000 형태)를 브라우저에서 열어보세요.

이 레포의 README에 적힌 실제 명령어를 그대로 가져왔습니다.

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# quadtree-js

This is a JavaScript Quadtree implementation based on the Java Methods described on [gamedevelopment.tutsplus.com by Steven Lambert](https://gamedevelopment.tutsplus.com/tutorials/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space--gamedev-374):

> Many games require the use of collision detection algorithms to determine when two objects have collided, but these algorithms are often expensive operations and can greatly slow down a game. One way to speed things up is to reduce the number of checks that have to be made. Two objects that are at opposite ends of the screen can not possibly collide, so there is no need to check for a collision between them. This is where a quadtree comes into play.

This implementation can store and retrieve rectangles in a recursive 2D Quadtree. Every Quadtree node can hold a maximum number of objects before it splits into four subnodes. Objects are only stored on leaf nodes (the lowest level). If an object overlaps into multiple leaf nodes, a reference to the object is stored in each node.

*Only 639 Bytes! (Compressed + Gzipped)*

----

### checkout "2.0": [quadtree-ts](https://github.com/timohausmann/quadtree-ts/) with multiple primitives, Typescript and more.

----

## Demos

* [Simple Demo](https://timohausmann.github.io/quadtree-js/simple.html) – add static objects and see the Quadtree split
* [Dynamic Demo](https://timohausmann.github.io/quadtree-js/dynamic.html) – continuously track moving objects
* [Many to many Demo](https://timohausmann.github.io/quadtree-js/many.html) – check all objects against each other
* [Benchmark v1.2.6](https://timohausmann.github.io/quadtree-js/test-retrieve.html) - Performance test with 1.000.000 objects

## Install

Install this module via [npm](https://www.npmjs.com/package/@timohausmann/quadtree-js) and import or require it:

```bash
npm i -D @timohausmann/quadtree-js
```

```javascript
import Quadtree from '@timohausmann/quadtree-js';
```

```javascript
const Quadtree = require('@timohausmann/quadtree-js');
```

Alternatively, [download the source](https://github.com/timohausmann/quadtree-js/archive/master.zip) and include it the old-fashioned way:

```html
<script src="quadtree.min.js"></script>
```

Or use an awesome CDN like [jsdelivr](https://www.jsdelivr.com/package/npm/@timohausmann/quadtree-js) or [unpkg](https://unpkg.com/browse/@timohausmann/quadtree-js@latest/):

```html
<script src="https://cdn.jsdelivr.net/npm/@timohausmann/quadtree-js/quadtree.min.js"></script>
```

```html
<script src="https://unpkg.com/@timohausmann/quadtree-js/quadtree.min.js"></script>
```

## How to use

Create a new Quadtree (with default values for `max_objects` (10) and `max_levels` (4)).

```javascript
var myTree = new Quadtree({
    x: 0,
    y: 0,
    width: 400,
    height: 300
});
```

> MAX_OBJECTS defines how many objects a node can hold before it splits and MAX_LEVELS defines the deepest level subnode.

If you want to specify `max_objects` and `max_levels` on your own, you can pass them as a 2nd and 3rd argument. I recommend using low values for `max_levels` because each level will quadruple the possible amount of nodes. Using lower values for `max_levels` increases performance but may return more candidates. Finetuning these values depends on your 2D space, the amount and size of the objects and your retrieving areas.

```javascript
var myTree = new Quadtree({
    x: 0,
    y: 0,
    width: 800,
    height: 600
}, 15, 6);
```

Insert an element in the Quadtree
```javascript
myTree.insert({
    x: 100,
    y: 100,
    width: 100,
    height: 100
});
```

Retrieve elements from nodes that intersect with the given bounds
```javascript
var elements = myTree.retrieve({
    x: 150,
    y: 150,
    width: 100,
    height: 100
});
```

Clear the Quadtree
```javascript
myTree.clear();
```

Check out the examples for more information.

## Typescript

Type definitions are included. Inserted objects need to conform to the `Quadtree.Rect` interface.

```javascript
import Quadtree, { Rect } from '@timohausmann/quadtree-js';

/*
 * interface Rect {
 *     x: number
 *     y: number
 *     width: number
 *     height: number
 * }
 */

interface Player extends Rect {
    name: string;
    health: number;
}

const hero:Player = {
    name: 'Shiffman',
    health: 100,
    x: 100,
    y: 100,
    width: 32,
    height: 32
}

myTree.insert(hero);
```

## Update single objects

This was often requested and is now supported in [quadtree-ts](https://timohausmann.github.io/quadtree-ts/examples/update/). 
This might be handy when most of the objects in your Quadtree are static.

## Browser Support

This library is supported in all modern browsers and runtimes.
2023 Update: now using ES6 (`new Set()`) which breaks IE9 compatibility. For IE9 support, use [1.2.5](https://github.com/timohausmann/quadtree-js/releases/tag/1.2.5).

## Development scripts

* `npm run build` to minify the source

## Changelog

### 1.2.6

* Performance improvement of `retrieve()` (was O(n^2), now O(n)) (thanks to [xixileng](https://github.com/timohausmann/quadtree-ts/pull/8)) Pushing the retrieval on a tree with 1.000.000 objects from ~160ms to ~5ms (MacBook M1 Pro).
* New example: <a href="https://timohausmann.github.io/quadtree-js/test-retrieve.html" target="_blank">test-retrieve</a>
* Local copy of `quadtree.min.js` for the docs folder so it's always up to date

### 1.2.5

Typescript Definition File Bugfix (thanks to [pietrovismara](https://github.com/timohausmann/quadtree-js/pull/18))

### 1.2.4

Added definition files for Typescript support

JSDoc Fixes

### 1.2.3

Using github.io for examples (docs), CDN URLs

### 1.2.2

Removed `grunt` dev dependency, now using `uglify-js` to minifiy

### 1.2.1

Allow float boundaries for Quads

Simplified getIndex function

### 1.2.0

This implementation now stores objects exclusively on leaf nodes and thus differs from the tutorial it's based on. Objects, that overlap into multiple subnodes are now referenced in each matching subnode instead of their parent node. This drastically reduces the collision candidates. Prior to 1.2.0, overlapping objects were stored in parent nodes.

### 1.1.3

Support for npm and `module.exports`