1"""
  2# GeoKDTree
  3[![PyPI version](https://badge.fury.io/py/geokdtree.svg)](https://badge.fury.io/py/geokdtree)
  4[![License: MIT](https://img.shields.io/badge/License-MIT-yellow.svg)](https://opensource.org/licenses/MIT)
  5[![PyPI Downloads](https://pepy.tech/badge/geokdtree)](https://pypi.org/project/geokdtree/)
  6<!-- [![PyPI Downloads](https://img.shields.io/pypi/dm/geokdtree.svg?label=PyPI%20downloads)](https://pypi.org/project/geokdtree/) -->
  7
  8# GeoKDTree
  9
 10## Ultra-fast nearest-neighbor lookup for latitude/longitude data
 11
 12**GeoKDTree** is a lightweight, high-performance spatial indexing library for Python designed to find the *nearest geographic coordinate* from massive datasets in nanoseconds.
 13
 14It wraps a highly optimized KD-Tree with a geographic interface, allowing you to work directly with `(latitude, longitude)` pairs. No projections, no external dependencies, and no heavy GIS stacks.
 15
 16![geokdtree](https://raw.githubusercontent.com/connor-makowski/geokdtree/main/static/geokdtree.png)
 17
 18### Documentation
 19
 20- Docs: https://connor-makowski.github.io/geokdtree/geokdtree.html
 21- Git Repo: https://github.com/connor-makowski/geokdtree
 22
 23## Installation
 24
 25```bash
 26pip install geokdtree
 27```
 28
 29## Getting Started
 30
 31```python
 32from geokdtree import GeoKDTree
 33
 34example_points = [
 35    (34.0522, -118.2437),  # Los Angeles
 36    (40.7128, -74.0060),   # New York
 37    (37.7749, -122.4194),  # San Francisco
 38    (51.5074, -0.1278),    # London
 39    (48.8566, 2.3522),     # Paris
 40]
 41
 42geo_kd_tree = GeoKDTree(points=example_points)
 43
 44test_point = (47.6062, -122.3321)  # Seattle
 45# Find the index of the closest point in the original dataset
 46closest_idx = geo_kd_tree.closest_idx(test_point) #=> 2
 47# Find the closest point itself
 48closest_point = geo_kd_tree.closest_point(test_point) #=> (37.7749, -122.4194)
 49```
 50
 51## Why Use GeoKDTree?
 52
 53GeoKDTree is designed to solve one focused problem extremely well:
 54
 55**Fast nearest-neighbor lookup for latitude/longitude data at scale.**
 56
 57It is worth noting that the closest point found may not be the true closest point, but should be very close for most practical applications. See KD-Tree limitations for more details.
 58
 59### Extremely Fast Lookups
 60
 61Once constructed, nearest-neighbor queries consistently complete in **tens of nanoseconds**, even with very large datasets.
 62
 63Typical benchmark results from the included tests:
 64
 65| Number of Points | Build Time | Query Time |
 66| ---------------: | ---------: | ---------: |
 67|            1,000 |    ~1.7 ms |   ~0.02 ms |
 68|           10,000 |     ~25 ms |   ~0.05 ms |
 69|          100,000 |    ~350 ms |   ~0.05 ms |
 70|        1,000,000 |     ~6.8 s |   ~0.07 ms |
 71
 72This makes GeoKDTree well-suited for:
 73
 74* Real-time proximity queries
 75* Matching incoming coordinates against large reference datasets
 76* High-throughput geospatial APIs
 77* Pre-filtering before more expensive geospatial calculations
 78
 79> Exact timings depend on hardware, Python version, and data distribution. These values reflect typical results from the repository’s benchmarks.
 80
 81### Built for Geographic Coordinates
 82
 83GeoKDTree works directly with `(latitude, longitude)` pairs.
 84
 85You do **not** need to:
 86
 87* Project coordinates into planar space
 88* Use heavyweight GIS libraries
 89* Maintain custom spatial indexing code
 90
 91Just pass geographic coordinates and query.
 92
 93### Simple API, Minimal Overhead
 94
 95GeoKDTree intentionally keeps the API small and focused.
 96
 97* Build once from a list of coordinates
 98* Query nearest neighbors with a single method call
 99* Retrieve indices or points directly from your original dataset
100
101There are no external C extensions or heavy dependencies, keeping installation and deployment simple.
102
103### Deterministic and Predictable Performance
104
105* Tree construction scales at approximately `O(n log n)`
106* Query performance scales at approximately `O(log n)`
107* No probabilistic approximations
108* No background indexing or caching
109
110This predictability is valuable for production systems where latency and reproducibility matter.
111
112## Supported Features
113
114See: https://connor-makowski.github.io/geokdtree/geokdtree.html
115
116## Contributing
117
118Issues, feature requests, and pull requests are welcome.
119Please open an issue to discuss changes or enhancements.
120
121# Development
122## Running Tests, Prettifying Code, and Updating Docs
123
124Make sure Docker is installed and running on a Unix system (Linux, MacOS, WSL2).
125
126- Create a docker container and drop into a shell
127    - `./run.sh`
128- Run all tests (see ./utils/test.sh)
129    - `./run.sh test`
130- Prettify the code (see ./utils/prettify.sh)
131    - `./run.sh prettify`
132- Update the docs (see ./utils/docs.sh)
133    - `./run.sh docs`
134
135- Note: You can and should modify the `Dockerfile` to test different python versions.
136
137"""
138
139try:
140    from geokdtree.cpp import GeoKDTree, KDTree
141except ImportError:
142    from geokdtree.geokdtree import GeoKDTree
143    from geokdtree.kdtree import KDTree