Skip to content

GitLab

Open
Created by Joseph Siddons@josiddOwner
Report abuse

Resolve "Improve documentation"

1 unresolved thread
Viewing commit 8e9bae21
Prev Next
19 files
+ 2684
- 251
Show latest version
GeoSpat‎ialTools‎
great_c‎ircle.py‎ +5 -4
kdtr‎ee.py‎ +2 -2
util‎s.py‎ +1 -1
note‎books‎
kdtree‎.ipynb‎ +315 -46
octtre‎e.ipynb‎ +550 -167
te‎st‎
test_kd‎tree.py‎ +1 -1
test_neig‎hbours.py‎ +2 -2
test_oc‎ttree.py‎ +4 -4
test_qua‎dtree.py‎ +4 -4
.codes‎pellrc‎ +6 -0
.giti‎gnore‎ +2 -1
.gitlab‎-ci.yml‎ +52 -0
.pre-commit‎-config.yaml‎ +16 -0
CHANG‎ES.md‎ +1 -0
CONTRIB‎UTING.md‎ +99 -0
LIC‎ENSE‎ +0 -2
READ‎ME.md‎ +8 -8
pyproje‎ct.toml‎ +11 -9
uv.‎lock‎ +1605 -0
GeoSpatialTools/great_circle.py
+ 5
- 4
Show all unchanged lines Show 20 lines
"""
import numpy as np
from typing import Optional, Tuple
from .distance_metrics import bearing, gcd_slc
Show 20 lines Show all unchanged lines Show 20 lines
y: float,
z: float,
to_radians: bool = False,
) -> tuple[float, float]:
) -> Tuple[float, float]:
"""
Get lon, and lat from cartesian coordinates.
Show 20 lines Show all unchanged lines Show 20 lines
R: float = 6371,
to_radians: bool = True,
normalised: bool = True,
) -> tuple[float, float, float]:
) -> Tuple[float, float, float]:
"""
Convert from polars coordinates to cartesian.
Show 20 lines Show all unchanged lines Show 20 lines
def intersection(
self, other: object, epsilon: float = 0.01
) -> tuple[float, float] | None:
) -> Optional[Tuple[float, float]]:
"""
Determine intersection position with another GreatCircle.
Show 20 lines Show all unchanged lines Show 20 lines
self,
other: object,
epsilon: float = 0.01,
) -> float | None:
) -> Optional[float]:
"""
Get angle of intersection with another GreatCircle.
Show 20 lines Show all unchanged lines
GeoSpatialTools/kdtree.py
+ 2
- 2
Show all unchanged lines Show 20 lines
This implementation is a _balanced_ KDTree, each leaf node should have the
same number of points (or differ by 1 depending on the number of points
the KDTree is intialised with).
the KDTree is initialised with).
The KDTree partitions in each of the lon and lat dimensions alternatively
in sequence by splitting at the median of the dimension of the points
Show 20 lines Show all unchanged lines Show 20 lines
The current depth of the KDTree, you should set this to 0, it is used
internally.
max_depth : int
The maximium depth of the KDTree. The leaf nodes will have depth no
The maximum depth of the KDTree. The leaf nodes will have depth no
larger than this value. Leaf nodes will not be created if there is
only 1 point in the branch.
"""
Show 20 lines Show all unchanged lines
GeoSpatialTools/utils.py
+ 1
- 1
Show all unchanged lines Show 20 lines
class DateWarning(Warning):
"""Warnning for Datetime Value"""
"""Warning for Datetime Value"""
pass
notebooks/kdtree.ipynb
+ 315
- 46
{
"cells": [
{
"cell_type": "markdown",
"id": "f7143f08-1d06-4e94-bbf6-ef35ddd11556",
"metadata": {},
"source": [
"# KDTree\n",
"\n",
"Testing the time to look-up nearby records with the `KDTree` implementation. Note that this implementation is actually a `2DTree` since it can only compute a valid distance comparison between longitude and latitude positions.\n",
"\n",
"The `KDTree` object is used for finding the closest neighbour to a position, in this implementation we use the Haversine distance to compare positions."
]
},
{
"cell_type": "code",
"execution_count": 1,
Show 20 lines Show all unchanged lines Show 20 lines
"outputs": [],
"source": [
"import os\n",
"import gzip\n",
"\n",
"os.environ[\"POLARS_MAX_THREADS\"] = \"4\"\n",
"\n",
"from datetime import datetime, timedelta\n",
"from random import choice\n",
"from datetime import datetime\n",
"from string import ascii_letters, digits\n",
"import random\n",
"import inspect\n",
Show 20 lines Show all unchanged lines Show 20 lines
"import polars as pl\n",
"import numpy as np\n",
"\n",
"from GeoSpatialTools import Record, haversine, KDTree"
"from GeoSpatialTools import Record, KDTree"
]
},
{
"cell_type": "markdown",
"id": "ec6c6e7f-8eee-47ea-a5e9-12537bb3412d",
"metadata": {},
"source": [
"## Set-up functions\n",
"\n",
"Used for generating data, or for comparisons by doing brute-force approach."
]
},
{
Show 20 lines Show all unchanged lines Show 20 lines
"outputs": [],
"source": [
"def randnum() -> float:\n",
" \"\"\"Get a random number between -1 and 1\"\"\"\n",
" return 2 * (np.random.rand() - 0.5)"
]
},
Show 20 lines Show all unchanged lines Show 20 lines
"outputs": [],
"source": [
"def generate_uid(n: int) -> str:\n",
" \"\"\"Generates a pseudo uid by randomly selecting from characters\"\"\"\n",
" chars = ascii_letters + digits\n",
" return \"\".join(random.choice(chars) for _ in range(n))"
]
Show 20 lines Show all unchanged lines Show 20 lines
{
"cell_type": "code",
"execution_count": 4,
"id": "9e647ecd-abdc-46a0-8261-aa081fda2e1d",
"metadata": {
"jupyter": {
"source_hidden": true
},
"scrolled": true
},
"outputs": [],
"source": [
"def check_cols(\n",
" df: pl.DataFrame | pl.LazyFrame,\n",
" cols: list[str],\n",
" var_name: str = \"dataframe\",\n",
") -> None:\n",
" \"\"\"\n",
" Check that a dataframe contains a list of columns. Raises an error if not.\n",
"\n",
" Parameters\n",
" ----------\n",
" df : polars Frame\n",
" Dataframe to check\n",
" cols : list[str]\n",
" Required columns\n",
" var_name : str\n",
" Name of the Frame - used for displaying in any error.\n",
" \"\"\"\n",
" calling_func = inspect.stack()[1][3]\n",
" if isinstance(df, pl.DataFrame):\n",
" have_cols = df.columns\n",
" elif isinstance(df, pl.LazyFrame):\n",
" have_cols = df.collect_schema().names()\n",
" else:\n",
" raise TypeError(\"Input Frame is not a polars Frame\")\n",
"\n",
" cols_in_frame = intersect(cols, have_cols)\n",
" missing = [c for c in cols if c not in cols_in_frame]\n",
"\n",
" if len(missing) > 0:\n",
" err_str = f\"({calling_func}) - {var_name} missing required columns. \"\n",
" err_str += f\"Require: {', '.join(cols)}. \"\n",
" err_str += f\"Missing: {', '.join(missing)}.\"\n",
" raise ValueError(err_str)\n",
"\n",
" return\n",
"\n",
"\n",
"def haversine_df(\n",
" df: pl.DataFrame | pl.LazyFrame,\n",
" lon: float,\n",
" lat: float,\n",
" R: float = 6371,\n",
" lon_col: str = \"lon\",\n",
" lat_col: str = \"lat\",\n",
") -> pl.DataFrame | pl.LazyFrame:\n",
" \"\"\"\n",
" Compute haversine distance on earth surface between lon-lat positions\n",
" in a polars DataFrame and a lon-lat position.\n",
"\n",
" Parameters\n",
" ----------\n",
" df : polars.DataFrame\n",
" The data, containing required columns:\n",
" * lon_col\n",
" * lat_col\n",
" * date_var\n",
" lon : float\n",
" The longitude of the position.\n",
" lat : float\n",
" The latitude of the position.\n",
" R : float\n",
" Radius of earth in km\n",
" lon_col : str\n",
" Name of the longitude column\n",
" lat_col : str\n",
" Name of the latitude column\n",
"\n",
" Returns\n",
" -------\n",
" polars.DataFrame\n",
" With additional column specifying distances between consecutive points\n",
" in the same units as 'R'. With colname defined by 'out_colname'.\n",
" \"\"\"\n",
" required_cols = [lon_col, lat_col]\n",
"\n",
" check_cols(df, required_cols, \"df\")\n",
" return (\n",
" df.with_columns(\n",
" [\n",
" pl.col(lat_col).radians().alias(\"_lat0\"),\n",
" pl.lit(lat).radians().alias(\"_lat1\"),\n",
" (pl.col(lon_col) - lon).radians().alias(\"_dlon\"),\n",
" (pl.col(lat_col) - lat).radians().alias(\"_dlat\"),\n",
" ]\n",
" )\n",
" .with_columns(\n",
" (\n",
" (pl.col(\"_dlat\") / 2).sin().pow(2)\n",
" + pl.col(\"_lat0\").cos()\n",
" * pl.col(\"_lat1\").cos()\n",
" * (pl.col(\"_dlon\") / 2).sin().pow(2)\n",
" ).alias(\"_a\")\n",
" )\n",
" .with_columns(\n",
" (2 * R * (pl.col(\"_a\").sqrt().arcsin())).round(2).alias(\"_dist\")\n",
" )\n",
" .drop([\"_lat0\", \"_lat1\", \"_dlon\", \"_dlat\", \"_a\"])\n",
" )\n",
"\n",
"\n",
"def intersect(a, b) -> set:\n",
" \"\"\"Intersection of a and b, items in both a and b\"\"\"\n",
" return set(a) & set(b)\n",
"\n",
"\n",
"def nearest_ship(\n",
" lon: float,\n",
" lat: float,\n",
" df: pl.DataFrame,\n",
" lon_col: str = \"lon\",\n",
" lat_col: str = \"lat\",\n",
") -> pl.DataFrame:\n",
" \"\"\"\n",
" Find the observation nearest to a position in space.\n",
"\n",
" Get a frame with only the records that is closest to the input point.\n",
"\n",
" Parameters\n",
" ----------\n",
" lon : float\n",
" The longitude of the position.\n",
" lat : float\n",
" The latitude of the position.\n",
" df : polars.DataFrame\n",
" The pool of records to search. Can be pre-filtered and filter_datetime\n",
" set to False.\n",
" lon_col : str\n",
" Name of the longitude column in the pool DataFrame\n",
" lat_col : str\n",
" Name of the latitude column in the pool DataFrame\n",
"\n",
" Returns\n",
" -------\n",
" polars.DataFrame\n",
" Containing only records from the pool within max_dist of the input\n",
" point, optionally at the same datetime if filter_datetime is True.\n",
" \"\"\"\n",
" required_cols = [lon_col, lat_col]\n",
" check_cols(df, required_cols, \"df\")\n",
"\n",
" return (\n",
" df.pipe(\n",
" haversine_df,\n",
" lon=lon,\n",
" lat=lat,\n",
" lon_col=lon_col,\n",
" lat_col=lat_col,\n",
" )\n",
" .filter(pl.col(\"_dist\").eq(pl.col(\"_dist\").min()))\n",
" .drop([\"_dist\"])\n",
" )"
]
},
{
"cell_type": "markdown",
"id": "287bdc1d-1ecf-4c59-af95-d2dc639c6894",
"metadata": {},
"source": [
"## Initialise random data"
]
},
{
"cell_type": "code",
"execution_count": 5,
"id": "c60b30de-f864-477a-a09a-5f1caa4d9b9a",
"metadata": {},
"outputs": [
Show 20 lines Show all unchanged lines Show 20 lines
"text": [
"(16000, 2)\n",
"shape: (5, 2)\n",
"┌──────┬─────┐\n",
"│ lon ┆ lat │\n",
"│ --- ┆ --- │\n",
"│ i64 ┆ i64 │\n",
"╞══════╪═════╡\n",
"│ 127 ┆ 21 │\n",
"│ -148 ┆ 36 │\n",
"│ -46 ┆ -15 │\n",
"│ 104 ┆ 89 │\n",
"│ -57 ┆ -31 │\n",
"└──────┴─────┘\n"
"┌─────┬─────┐\n",
"│ lon ┆ lat │\n",
"│ --- ┆ --- │\n",
"│ i64 ┆ i64 │\n",
"╞═════╪═════╡\n",
"│ -26 ┆ -42 │\n",
"│ 109 ┆ -33 │\n",
"│ -87 ┆ -18 │\n",
"│ -94 ┆ -81 │\n",
"│ -94 ┆ 0 │\n",
"└─────┴─────┘\n"
]
}
],
Show 20 lines Show all unchanged lines Show 20 lines
"N = 16_000\n",
"lons = pl.int_range(-180, 180, eager=True)\n",
"lats = pl.int_range(-90, 90, eager=True)\n",
"dates = pl.datetime_range(datetime(1900, 1, 1, 0), datetime(1900, 1, 31, 23), interval=\"1h\", eager=True)\n",
"dates = pl.datetime_range(\n",
" datetime(1900, 1, 1, 0),\n",
" datetime(1900, 1, 31, 23),\n",
" interval=\"1h\",\n",
" eager=True,\n",
")\n",
"\n",
"lons_use = lons.sample(N, with_replacement=True).alias(\"lon\")\n",
"lats_use = lats.sample(N, with_replacement=True).alias(\"lat\")\n",
Show 20 lines Show all unchanged lines Show 20 lines
},
{
"cell_type": "code",
"execution_count": 5,
"execution_count": 6,
"id": "875f2a67-49fe-476f-add1-b1d76c6cd8f9",
"metadata": {},
"outputs": [],
Show 20 lines Show all unchanged lines Show 20 lines
"records = [Record(**r) for r in df.rows(named=True)]"
]
},
{
"cell_type": "markdown",
"id": "bd83330b-ef2c-478e-9a7b-820454d198bb",
"metadata": {},
"source": [
"## Initialise the `KDTree`\n",
"\n",
"There is an overhead to constructing a `KDTree` object, so performance improvement is only for multiple comparisons."
]
},
{
"cell_type": "code",
"execution_count": 6,
"execution_count": 7,
"id": "1e883e5a-5086-4c29-aff2-d308874eae16",
"metadata": {},
"outputs": [
Show 20 lines Show all unchanged lines Show 20 lines
"name": "stdout",
"output_type": "stream",
"text": [
"CPU times: user 151 ms, sys: 360 ms, total: 511 ms\n",
"Wall time: 57.3 ms\n"
"CPU times: user 35 ms, sys: 1.5 ms, total: 36.5 ms\n",
"Wall time: 32.1 ms\n"
]
}
],
Show 20 lines Show all unchanged lines Show 20 lines
"kt = KDTree(records)"
]
},
{
"cell_type": "markdown",
"id": "0a37ef06-2691-4e01-96a9-1c1ecd582599",
"metadata": {},
"source": [
"## Compare with brute force approach"
]
},
{
"cell_type": "code",
"execution_count": 7,
"execution_count": 8,
"id": "365bbf30-7a93-438d-92b2-a3471f1e9249",
"metadata": {},
"outputs": [],
"source": [
"test_record = Record(\n",
" random.choice(range(-179, 180)) + randnum(),\n",
" random.choice(range(-89, 90)) + randnum(),\n",
")"
]
},
{
"cell_type": "code",
"execution_count": 9,
"id": "69022ad1-5ec8-4a09-836c-273ef452451f",
"metadata": {},
"outputs": [
Show 20 lines Show all unchanged lines Show 20 lines
"name": "stdout",
"output_type": "stream",
"text": [
"203 μs ± 4.56 μs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)\n"
"101 μs ± 3.52 μs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)\n"
]
}
],
"source": [
"%%timeit\n",
"test_record = Record(random.choice(range(-179, 180)) + randnum(), random.choice(range(-89, 90)) + randnum())\n",
"kt.query(test_record)"
]
},
{
"cell_type": "code",
"execution_count": 8,
"execution_count": 10,
"id": "28031966-c7d0-4201-a467-37590118e851",
"metadata": {},
"outputs": [
Show 20 lines Show all unchanged lines Show 20 lines
"name": "stdout",
"output_type": "stream",
"text": [
"8.87 ms ± 188 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
"8.17 ms ± 38.6 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
]
}
],
"source": [
"%%timeit\n",
"test_record = Record(random.choice(range(-179, 180)) + randnum(), random.choice(range(-89, 90)) + randnum())\n",
"np.argmin([test_record.distance(p) for p in records])"
]
},
{
"cell_type": "code",
"execution_count": 9,
"execution_count": 11,
"id": "09e0f923-ca49-47bf-8643-e0b3a6d0467c",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"8.22 ms ± 95.3 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
]
}
],
"source": [
"%%timeit\n",
"nearest_ship(lon=test_record.lon, lat=test_record.lat, df=df)"
]
},
{
"cell_type": "markdown",
"id": "f0359950-942d-45ea-8676-b22c8ce9e296",
"metadata": {},
"source": [
"## Verify that results are correct"
]
},
{
"cell_type": "code",
"execution_count": 12,
"id": "0d10b2ba-57b2-475c-9d01-135363423990",
"metadata": {},
"outputs": [
Show 20 lines Show all unchanged lines Show 20 lines
"name": "stdout",
"output_type": "stream",
"text": [
"CPU times: user 17.4 s, sys: 147 ms, total: 17.6 s\n",
"Wall time: 17.6 s\n"
"CPU times: user 16.3 s, sys: 74.7 ms, total: 16.4 s\n",
"Wall time: 16.4 s\n"
]
}
],
Show 20 lines Show all unchanged lines Show 20 lines
"%%time\n",
"n_samples = 1000\n",
"tol = 1e-8\n",
"test_records = [Record(random.choice(range(-179, 180)) + randnum(), random.choice(range(-89, 90)) + randnum()) for _ in range(n_samples)]\n",
"test_records = [\n",
" Record(\n",
" random.choice(range(-179, 180)) + randnum(),\n",
" random.choice(range(-89, 90)) + randnum(),\n",
" )\n",
" for _ in range(n_samples)\n",
"]\n",
"kd_res = [kt.query(r) for r in test_records]\n",
"kd_recs = [_[0][0] for _ in kd_res]\n",
"kd_dists = [_[1] for _ in kd_res]\n",
"tr_recs = [records[np.argmin([r.distance(p) for p in records])] for r in test_records]\n",
"tr_recs = [\n",
" records[np.argmin([r.distance(p) for p in records])] for r in test_records\n",
"]\n",
"tr_dists = [min([r.distance(p) for p in records]) for r in test_records]\n",
"assert all([abs(k - t) < tol for k, t in zip(kd_dists, tr_dists)]), \"NOT MATCHING?\""
"\n",
"if not all([abs(k - t) < tol for k, t in zip(kd_dists, tr_dists)]):\n",
" raise ValueError(\"NOT MATCHING?\")"
]
},
{
"cell_type": "code",
"execution_count": 10,
"execution_count": 13,
"id": "a6aa6926-7fd5-4fff-bd20-7bc0305b948d",
"metadata": {},
"outputs": [
Show 20 lines Show all unchanged lines Show 20 lines
"└──────────┴──────────┴─────────┴────────┴────────┴─────────┴────────┴────────┘"
]
},
"execution_count": 10,
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
Show 20 lines Show all unchanged lines Show 20 lines
"tr_lons = [r.lon for r in tr_recs]\n",
"tr_lats = [r.lat for r in tr_recs]\n",
"\n",
"df = pl.DataFrame({\n",
" \"test_lon\": test_lons, \n",
" \"test_lat\": test_lats,\n",
" \"kd_dist\": kd_dists,\n",
" \"kd_lon\": kd_lons,\n",
" \"kd_lat\": kd_lats,\n",
" \"tr_dist\": tr_dists,\n",
" \"tr_lon\": tr_lons,\n",
" \"tr_lat\": tr_lats, \n",
"}).filter((pl.col(\"kd_dist\") - pl.col(\"tr_dist\")).abs().ge(tol))\n",
"df = pl.DataFrame(\n",
" {\n",
" \"test_lon\": test_lons,\n",
" \"test_lat\": test_lats,\n",
" \"kd_dist\": kd_dists,\n",
" \"kd_lon\": kd_lons,\n",
" \"kd_lat\": kd_lats,\n",
" \"tr_dist\": tr_dists,\n",
" \"tr_lon\": tr_lons,\n",
" \"tr_lat\": tr_lats,\n",
" }\n",
").filter((pl.col(\"kd_dist\") - pl.col(\"tr_dist\")).abs().ge(tol))\n",
"df"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "GeoSpatialTools",
"display_name": "geospatialtools",
"language": "python",
"name": "geospatialtools"
},
Show 20 lines Show all unchanged lines Show 20 lines
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.12.7"
"version": "3.11.11"
}
},
"nbformat": 4,
Show 20 lines Show all unchanged lines
notebooks/octtree.ipynb
+ 550
- 167

Files with large changes are collapsed by default.

test/test_kdtree.py
+ 1
- 1
test/test_neighbours.py
+ 2
- 2
test/test_octtree.py
+ 4
- 4
test/test_quadtree.py
+ 4
- 4
.codespellrc
+ 6
- 0
.gitignore
+ 2
- 1
.gitlab-ci.yml
+ 52
- 0
.pre-commit-config.yaml
+ 16
- 0
CHANGES.md
+ 1
- 0
CONTRIBUTING.md
+ 99
- 0
LICENSE
+ 0
- 2
README.md
+ 8
- 8
pyproject.toml
+ 11
- 9
uv.lock
+ 1605
- 0