| Name | e-pyquadtree JSON |
| Version |
0.1.1
JSON |
| download |
| home_page | |
| Summary | |
| upload_time | 2023-09-24 18:39:46 |
| maintainer | |
| docs_url | None |
| author | Ethan Anderson |
| requires_python | |
| license | |
| keywords |
|
| VCS |
|
| bugtrack_url |
|
| requirements |
No requirements were recorded.
|
| Travis-CI |
No Travis.
|
| coveralls test coverage |
No coveralls.
|
# PyQuadTree
A simple pure Python quadtree implementation.
Supports fast query, insertion, deletion, and nearest neighbor search.
## Installation
```bash
pip install e-pyquadtree
```
## Usage
### 1. Creating a QuadTree
`bbox` is a tuple of the form `(x1, y1, x2, y2)` where `(x1, y1)` is the top left corner of the bounding box and
`(x2, y2)` is the bottom right corner of the bounding box.
`max_elements` is the maximum number of elements that can be stored in a node before it splits.
`max_depth` is the maximum depth of the quadtree.
```python
from pyquadtree import QuadTree
quadtree = QuadTree(bbox=(0, 0, 1000, 500), max_elements=10, max_depth=5)
```
### 2. Adding elements to the QuadTree
The first argument can be any object you want to store in the quadtree.
The second argument is a tuple of the form `(x, y)` where `(x, y)` is the location of the object.
```python
quadtree.add("apple", (100, 100))
```
### 3. Deleting elements from the QuadTree
The first argument is the object you want to delete from the quadtree.
It performs a lookup on the object and deletes it from the quadtree.
```python
quadtree.delete("apple")
```
### 4. Querying the QuadTree
The first argument is a tuple of the form `(x1, y1, x2, y2)` where `(x1, y1)` is the top left corner of the bounding box and
`(x2, y2)` is the bottom right corner of the bounding box.
Returns a list of elements within the bounding box.
Each element has an `item` and a `point` attribute.
These are the same as the arguments passed to `quadtree.add()`
when this element was added to the quadtree.
```python
found_elements = quadtree.query((50, 50, 150, 150))
```
### 5. Finding the nearest neighbor
Allows you to find the nearest n neighbors to a point.
The first argument is the point of interest.
There are a couple of optional arguments:
- `condition` is a function that takes in an item and returns a boolean.
If the function returns `True`, the item is considered a valid neighbor.
If the function returns `False`, the item is not considered a valid neighbor.
- `max_distance` is the maximum distance from the point of interest to a neighbor.
If the distance between the point of interest and a neighbor is greater than `max_distance`,
the neighbor is not considered a valid neighbor.
- `number_of_neighbors` is the number of neighbors to return.
If `number_of_neighbors` is 1 by default.
```python
condition = lambda x: x == "apple"
neighbors = quadtree.nearest_neighbors((200, 100), condition=condition, max_distance=100, number_of_neighbors=3)
```
### 6. Drawing the tree
Calling `get_all_bbox()` on the root node will return a flat list of all bounding boxes that make up the tree.
These can then be drawn using your favorite drawing library.
```python
from pyquadtree import QuadTree
import random
import matplotlib.pyplot as plt
from matplotlib.patches import Rectangle
quadtree = QuadTree(bbox=(0, 0, 1000, 500), max_elements=10, max_depth=5)
for i in range(100):
quadtree.add(i, (random.randint(0, 100), random.randint(0, 500)))
all_bbox = quadtree.get_all_bbox()
fig, ax = plt.subplots()
ax.set_xlim(0, 1000)
ax.set_ylim(0, 500)
for bbox in all_bbox:
print(bbox)
rectangle = Rectangle((bbox[0], bbox[1]), bbox[2] - bbox[0], bbox[3] - bbox[1], fill=False,
edgecolor="r", linewidth=1)
ax.add_patch(rectangle)
plt.show()
```
## Example
```python
from pyquadtree import QuadTree
# Creating a quadtree from (0, 0) to (1000, 500)
# It will have a maximum depth of 5 and a maximum number of 10 objects per node
quadtree = QuadTree(bbox=(0, 0, 1000, 500), max_elements=10, max_depth=5)
# Inserting a string object with a location of (100, 100)
quadtree.add("apple", (100, 100))
# Inserting another string object with a location of (200, 50)
quadtree.add("orange", (200, 50))
# Querying the quadtree for all objects in the bounding box (50, 50, 150, 150)
# Returns the list of elements within the bounding box
found_elements = quadtree.query((50, 50, 150, 150))
for element in found_elements:
print(element.point, element.item) # (100, 100) apple
# Finding the element nearest to (200, 100)
nearest_neighbor = quadtree.nearest_neighbors((200, 100))[0]
print(nearest_neighbor.point, nearest_neighbor.item) # (200, 50) orange
# Getting a list all elements in the quadtree
all_elements = quadtree.get_all_elements()
for element in all_elements:
print(element.point, element.item) # (100, 100) apple, (200, 50) orange
```
## Performance
The following performance tests were run on a quadtree with a maximum depth of 10 and
a maximum number of 20 elements per node.
The values are the number of seconds needed to both build the tree and then do 500 random queries.
pyqtree is an alternative pure Python quadtree implementation which can be found
[here](https://pypi.org/project/Pyqtree/). It was a big part in the inspiration
for this project.
| Number of elements | Brute Force | pyquadtree | pyqtree |
|--------------------|-------------|------------|---------|
| 2000 | 0.057 | 0.029 | 0.032 |
| 4000 | 0.112 | 0.052 | 0.061 |
| 6000 | 0.165 | 0.097 | 0.1 |
| 8000 | 0.222 | 0.108 | 0.132 |
| 10000 | 0.273 | 0.13 | 0.163 |
| 12000 | 0.334 | 0.177 | 0.197 |
| 14000 | 0.405 | 0.2 | 0.241 |
| 16000 | 0.457 | 0.216 | 0.314 |
| 18000 | 0.504 | 0.282 | 0.334 |
| 20000 | 0.564 | 0.278 | 0.41 |
| 22000 | 0.623 | 0.359 | 0.458 |
| 24000 | 0.681 | 0.35 | 0.557 |
| 26000 | 0.73 | 0.425 | 0.592 |
| 28000 | 0.792 | 0.493 | 0.657 |
----------------------------------------------------------------
At 28000 elements, pyquadtree is 25% faster than pyqtree and 38% faster than brute force.
Raw data
{
"_id": null,
"home_page": "",
"name": "e-pyquadtree",
"maintainer": "",
"docs_url": null,
"requires_python": "",
"maintainer_email": "",
"keywords": "",
"author": "Ethan Anderson",
"author_email": "telan4892@gmail.com",
"download_url": "https://files.pythonhosted.org/packages/ae/eb/468e682fa0d1da7df90c5fe6ae93bb11a6a0d017e7905ed6a75e98a3e4ff/e_pyquadtree-0.1.1.tar.gz",
"platform": null,
"description": "# PyQuadTree \r\nA simple pure Python quadtree implementation. \r\nSupports fast query, insertion, deletion, and nearest neighbor search.\r\n\r\n\r\n## Installation\r\n```bash\r\npip install e-pyquadtree\r\n```\r\n\r\n## Usage\r\n\r\n### 1. Creating a QuadTree\r\n\r\n`bbox` is a tuple of the form `(x1, y1, x2, y2)` where `(x1, y1)` is the top left corner of the bounding box and\r\n`(x2, y2)` is the bottom right corner of the bounding box. \r\n\r\n`max_elements` is the maximum number of elements that can be stored in a node before it splits. \r\n\r\n`max_depth` is the maximum depth of the quadtree.\r\n```python\r\nfrom pyquadtree import QuadTree\r\nquadtree = QuadTree(bbox=(0, 0, 1000, 500), max_elements=10, max_depth=5)\r\n```\r\n\r\n### 2. Adding elements to the QuadTree\r\n\r\nThe first argument can be any object you want to store in the quadtree.\r\nThe second argument is a tuple of the form `(x, y)` where `(x, y)` is the location of the object.\r\n```python\r\nquadtree.add(\"apple\", (100, 100))\r\n```\r\n\r\n### 3. Deleting elements from the QuadTree\r\n\r\nThe first argument is the object you want to delete from the quadtree.\r\nIt performs a lookup on the object and deletes it from the quadtree.\r\n```python\r\nquadtree.delete(\"apple\")\r\n```\r\n\r\n### 4. Querying the QuadTree\r\n\r\nThe first argument is a tuple of the form `(x1, y1, x2, y2)` where `(x1, y1)` is the top left corner of the bounding box and\r\n`(x2, y2)` is the bottom right corner of the bounding box.\r\n\r\nReturns a list of elements within the bounding box.\r\nEach element has an `item` and a `point` attribute.\r\nThese are the same as the arguments passed to `quadtree.add()`\r\nwhen this element was added to the quadtree.\r\n```python\r\nfound_elements = quadtree.query((50, 50, 150, 150))\r\n```\r\n\r\n### 5. Finding the nearest neighbor\r\nAllows you to find the nearest n neighbors to a point.\r\nThe first argument is the point of interest.\r\n\r\nThere are a couple of optional arguments:\r\n- `condition` is a function that takes in an item and returns a boolean.\r\n If the function returns `True`, the item is considered a valid neighbor.\r\n If the function returns `False`, the item is not considered a valid neighbor.\r\n- `max_distance` is the maximum distance from the point of interest to a neighbor.\r\n If the distance between the point of interest and a neighbor is greater than `max_distance`,\r\n the neighbor is not considered a valid neighbor.\r\n- `number_of_neighbors` is the number of neighbors to return.\r\n If `number_of_neighbors` is 1 by default.\r\n\r\n\r\n```python\r\ncondition = lambda x: x == \"apple\"\r\nneighbors = quadtree.nearest_neighbors((200, 100), condition=condition, max_distance=100, number_of_neighbors=3)\r\n```\r\n\r\n### 6. Drawing the tree\r\nCalling `get_all_bbox()` on the root node will return a flat list of all bounding boxes that make up the tree.\r\nThese can then be drawn using your favorite drawing library.\r\n```python\r\nfrom pyquadtree import QuadTree\r\nimport random\r\nimport matplotlib.pyplot as plt\r\nfrom matplotlib.patches import Rectangle\r\n\r\nquadtree = QuadTree(bbox=(0, 0, 1000, 500), max_elements=10, max_depth=5)\r\nfor i in range(100):\r\n quadtree.add(i, (random.randint(0, 100), random.randint(0, 500)))\r\n\r\nall_bbox = quadtree.get_all_bbox()\r\nfig, ax = plt.subplots()\r\nax.set_xlim(0, 1000)\r\nax.set_ylim(0, 500)\r\nfor bbox in all_bbox:\r\n print(bbox)\r\n rectangle = Rectangle((bbox[0], bbox[1]), bbox[2] - bbox[0], bbox[3] - bbox[1], fill=False,\r\n edgecolor=\"r\", linewidth=1)\r\n ax.add_patch(rectangle)\r\nplt.show()\r\n```\r\n\r\n## Example\r\n```python\r\nfrom pyquadtree import QuadTree\r\n\r\n# Creating a quadtree from (0, 0) to (1000, 500)\r\n# It will have a maximum depth of 5 and a maximum number of 10 objects per node\r\nquadtree = QuadTree(bbox=(0, 0, 1000, 500), max_elements=10, max_depth=5)\r\n\r\n# Inserting a string object with a location of (100, 100)\r\nquadtree.add(\"apple\", (100, 100))\r\n\r\n# Inserting another string object with a location of (200, 50)\r\nquadtree.add(\"orange\", (200, 50))\r\n\r\n# Querying the quadtree for all objects in the bounding box (50, 50, 150, 150)\r\n# Returns the list of elements within the bounding box\r\nfound_elements = quadtree.query((50, 50, 150, 150))\r\n\r\nfor element in found_elements:\r\n print(element.point, element.item) # (100, 100) apple\r\n\r\n# Finding the element nearest to (200, 100)\r\nnearest_neighbor = quadtree.nearest_neighbors((200, 100))[0]\r\nprint(nearest_neighbor.point, nearest_neighbor.item) # (200, 50) orange\r\n\r\n# Getting a list all elements in the quadtree\r\nall_elements = quadtree.get_all_elements()\r\nfor element in all_elements:\r\n print(element.point, element.item) # (100, 100) apple, (200, 50) orange\r\n```\r\n\r\n## Performance\r\nThe following performance tests were run on a quadtree with a maximum depth of 10 and\r\na maximum number of 20 elements per node.\r\nThe values are the number of seconds needed to both build the tree and then do 500 random queries.\r\n\r\npyqtree is an alternative pure Python quadtree implementation which can be found\r\n[here](https://pypi.org/project/Pyqtree/). It was a big part in the inspiration\r\nfor this project. \r\n\r\n\r\n| Number of elements | Brute Force | pyquadtree | pyqtree |\r\n|--------------------|-------------|------------|---------|\r\n| 2000 | 0.057 | 0.029 | 0.032 |\r\n| 4000 | 0.112 | 0.052 | 0.061 |\r\n| 6000 | 0.165 | 0.097 | 0.1 |\r\n| 8000 | 0.222 | 0.108 | 0.132 |\r\n| 10000 | 0.273 | 0.13 | 0.163 |\r\n| 12000 | 0.334 | 0.177 | 0.197 |\r\n| 14000 | 0.405 | 0.2 | 0.241 |\r\n| 16000 | 0.457 | 0.216 | 0.314 |\r\n| 18000 | 0.504 | 0.282 | 0.334 |\r\n| 20000 | 0.564 | 0.278 | 0.41 |\r\n| 22000 | 0.623 | 0.359 | 0.458 |\r\n| 24000 | 0.681 | 0.35 | 0.557 |\r\n| 26000 | 0.73 | 0.425 | 0.592 |\r\n| 28000 | 0.792 | 0.493 | 0.657 |\r\n----------------------------------------------------------------\r\n\r\nAt 28000 elements, pyquadtree is 25% faster than pyqtree and 38% faster than brute force.\r\n",
"bugtrack_url": null,
"license": "",
"summary": "",
"version": "0.1.1",
"project_urls": null,
"split_keywords": [],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "9c39c2b44956a87f22f714365e8f5c3bf426f02951c002b819fd0f020118997a",
"md5": "27b71c12bb4413f71ac76084b9695ba1",
"sha256": "c887e81378cd1b81a1a0e51d7f4b6f23c30478b9b246baeb568f606d0e694c34"
},
"downloads": -1,
"filename": "e_pyquadtree-0.1.1-py3-none-any.whl",
"has_sig": false,
"md5_digest": "27b71c12bb4413f71ac76084b9695ba1",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": null,
"size": 8164,
"upload_time": "2023-09-24T18:39:44",
"upload_time_iso_8601": "2023-09-24T18:39:44.698102Z",
"url": "https://files.pythonhosted.org/packages/9c/39/c2b44956a87f22f714365e8f5c3bf426f02951c002b819fd0f020118997a/e_pyquadtree-0.1.1-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "aeeb468e682fa0d1da7df90c5fe6ae93bb11a6a0d017e7905ed6a75e98a3e4ff",
"md5": "0c236bb547807f2236b5bf745d4d6dc1",
"sha256": "bbbea6668c4029a5f2b884fc8f9f5889cea075ff499c34de93bf08cc8df86b21"
},
"downloads": -1,
"filename": "e_pyquadtree-0.1.1.tar.gz",
"has_sig": false,
"md5_digest": "0c236bb547807f2236b5bf745d4d6dc1",
"packagetype": "sdist",
"python_version": "source",
"requires_python": null,
"size": 7405,
"upload_time": "2023-09-24T18:39:46",
"upload_time_iso_8601": "2023-09-24T18:39:46.331120Z",
"url": "https://files.pythonhosted.org/packages/ae/eb/468e682fa0d1da7df90c5fe6ae93bb11a6a0d017e7905ed6a75e98a3e4ff/e_pyquadtree-0.1.1.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2023-09-24 18:39:46",
"github": false,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"lcname": "e-pyquadtree"
}
