Resolve "Improve documentation"

Closes #10 (closed)

GeoSpatialTools/octtree.py

 neighbours.
 """
 
-from typing import Optional
+from typing import List, Optional
 import datetime
 from .distance_metrics import haversine
-from .record import SpaceTimeRecord, SpaceTimeRecords
+from .record import SpaceTimeRecord
 from .shape import SpaceTimeEllipse, SpaceTimeRectangle
 
 
         self.capacity = capacity
         self.depth = depth
         self.max_depth = max_depth
-        self.points = SpaceTimeRecords()
+        self.points: list[SpaceTimeRecord] = list()
         self.divided: bool = False
         return None
 
     def query(
         self,
         rect: SpaceTimeRectangle,
-        points: Optional[SpaceTimeRecords] = None,
-    ) -> SpaceTimeRecords:
-        """Get points that fall in a SpaceTimeRectangle"""
+        points: Optional[List[SpaceTimeRecord]] = None,
+    ) -> List[SpaceTimeRecord]:
+        """
+        Get SpaceTimeRecords contained within the OctTree that fall in a
+        SpaceTimeRectangle
+
+        Parameters
+        ----------
+        rect : SpaceTimeRectangle
+
+        Returns
+        -------
+        List[SpaceTimeRecord]
+            The SpaceTimeRecord values contained within the OctTree that fall
+            within the bounds of rect.
+        """
         if not points:
-            points = SpaceTimeRecords()
+            points = list()
         if not self.boundary.intersects(rect):
             return points
 
     def query_ellipse(
         self,
         ellipse: SpaceTimeEllipse,
-        points: Optional[SpaceTimeRecords] = None,
-    ) -> SpaceTimeRecords:
-        """Get points that fall in an ellipse."""
+        points: Optional[List[SpaceTimeRecord]] = None,
+    ) -> List[SpaceTimeRecord]:
+        """
+        Get SpaceTimeRecords contained within the OctTree that fall in a
+        SpaceTimeEllipse
+
+        Parameters
+        ----------
+        ellipse : SpaceTimeEllipse
+
+        Returns
+        -------
+        List[SpaceTimeRecord]
+            The SpaceTimeRecord values contained within the OctTree that fall
+            within the bounds of ellipse.
+        """
         if not points:
-            points = SpaceTimeRecords()
+            points = list()
         if not ellipse.nearby_rect(self.boundary):
             return points
 
         point: SpaceTimeRecord,
         dist: float,
         t_dist: datetime.timedelta,
-        points: Optional[SpaceTimeRecords] = None,
-    ) -> SpaceTimeRecords:
+        points: Optional[List[SpaceTimeRecord]] = None,
+    ) -> List[SpaceTimeRecord]:
         """
-        Get all points that are nearby another point.
+        Get all SpaceTimeRecords contained in the OctTree that are nearby
+        another query SpaceTimeRecord.
 
         Query the OctTree to find all SpaceTimeRecords within the OctTree that
         are nearby to the query SpaceTimeRecord. This search should be faster
             query SpaceTimeRecord. Can be numeric if the OctTree boundaries,
             SpaceTimeRecords, and query SpaceTimeRecord have numeric datetime
             values and ranges.
-        points : SpaceTimeRecords | None
+        points : List[SpaceTimeRecord] | None
             List of SpaceTimeRecords already found. Most use cases will be to
             not set this value, since it's main use is for passing onto the
             children OctTrees.
 
         Returns
         -------
-        SpaceTimeRecords : A list of SpaceTimeRecords whose distance to the
-        query SpaceTimeRecord is <= dist, and the datetimes of the
-        SpaceTimeRecords fall within the datetime range of the query
-        SpaceTimeRecord.
+        list[SpaceTimeRecord]
+            A list of SpaceTimeRecords whose distance to the
+            query SpaceTimeRecord is <= dist, and the datetimes of the
+            SpaceTimeRecords fall within the datetime range of the query
+            SpaceTimeRecord.
         """
         if not points:
-            points = SpaceTimeRecords()
+            points = list()
         if not self.boundary.nearby(point, dist, t_dist):
             return points
 

GeoSpatialTools/quadtree.py

         return out
 
     def len(self, _current_len: int = 0) -> int:
-        """Get the number of points in the OctTree"""
+        """Get the number of points in the QuadTree"""
         _current_len += len(self.points)
         if not self.divided:
             return _current_len
         rect: Rectangle,
         points: Optional[List[Record]] = None,
     ) -> List[Record]:
-        """Get points that fall in a rectangle"""
+        """
+        Get Records contained within the QuadTree that fall in a
+        Rectangle
+
+        Parameters
+        ----------
+        rect : Rectangle
+
+        Returns
+        -------
+        list[Record]
+            The Record values contained within the QuadTree that fall
+            within the bounds of rect.
+        """
         if not points:
             points = list()
         if not self.boundary.intersects(rect):
         ellipse: Ellipse,
         points: Optional[List[Record]] = None,
     ) -> List[Record]:
-        """Get points that fall in an ellipse."""
+        """
+        Get Records contained within the QuadTree that fall in a
+        Ellipse
+
+        Parameters
+        ----------
+        ellipse : Ellipse
+
+        Returns
+        -------
+        list[Record]
+            The Record values contained within the QuadTree that fall
+            within the bounds of ellipse.
+        """
         if not points:
             points = list()
         if not ellipse.nearby_rect(self.boundary):
         dist: float,
         points: Optional[List[Record]] = None,
     ) -> List[Record]:
-        """Get all points that are nearby another point"""
+        """
+        Get all Records contained in the QuadTree that are nearby
+        another query Record.
+
+        Query the QuadTree to find all Records within the QuadTree that
+        are nearby to the query Record. This search should be faster
+        than searching through all records, since only QuadTree children whose
+        boundaries are close to the query Record are evaluated.
+
+        Parameters
+        ----------
+        point : Record
+            The query point.
+        dist : float
+            The distance for comparison. Note that Haversine distance is used
+            as the distance metric as the query Record and QuadTree are
+            assumed to lie on the surface of Earth.
+        points : Records | None
+            List of Records already found. Most use cases will be to
+            not set this value, since it's main use is for passing onto the
+            children QuadTrees.
+
+        Returns
+        -------
+        list[Record]
+            A list of Records whose distance to the
+            query Record is <= dist, and the datetimes of the
+            Records fall within the datetime range of the query
+            Record.
+        """
         if not points:
             points = list()
         if not self.boundary.nearby(point, dist):

GeoSpatialTools/record.py

         if not isinstance(other, SpaceTimeRecord):
             raise TypeError("Argument other must be an instance of Record")
         return haversine(self.lon, self.lat, other.lon, other.lat)
-
-
-class SpaceTimeRecords(List[SpaceTimeRecord]):
-    """List of SpaceTimeRecords"""

docs/authors.rst

-=======
 Credits
 =======
 

docs/bisection.rst

+================
+Bisection Search
+================
+
+Bisection can be used to find the nearest neighbour in a sorted one-dimensional list of search values in
+:math:`O(\log(n))` time complexity.
+
+The implementation in `GeoSpatialTools` makes use of the `bisect` library, which is part of the Python standard library.
+The input types are numeric types, which can include ``int``, ``float``, or ``datetime.datetime`` values.
+
+The bisection approach repeatedly splits the list of search values in two at the mid-index. The query value is compared
+to the search value at the mid-index. If the query value is larger than the search value at the mid-index, then the
+search values after the mid-index become the new search values. If the query value is smaller than the search value at
+the mid-index then the search values before the mid-index become the new search values. This bisecting is repeated
+(succesively halving the number of search values) until one values remain. The nearest neighbour is either the value at
+the remaining index, or the value at the index one above.
+
+.. note:: The above assumes that the list of search values is sorted in increasing order. The opposite applies if the
+   list is sorted in reverse.
+
+.. warning:: The input values must be sorted
+
+Example
+=======
+
+.. code-block:: python
+
+   from GeoSpatialTools import find_nearest
+   import numpy as np
+   
+   search_values: list[float] = list(np.random.randn(50))
+   search_values.sort()
+
+   query_value: float = 0.45
+   neighbour_index: int = find_nearest(
+        vals=search_values,
+        test=query_value,
+   )
+   neighbour_value: float = search_values[neighbour_index]
+
+neighbours Module
+=================
+
+.. automodule:: GeoSpatialTools.neighbours
+   :members:

docs/hyperlinks.rst

 .. _uv: https://docs.astral.sh/uv
 
 .. _haversine: https://en.wikipedia.org/wiki/Haversine_formula
+
+.. _NumPy: https://numpy.org/
+
+.. _polars: https://pola.rs/
+
+.. _Jupyter: https://jupyter.org/
+
+.. _NOC: https://noc.ac.uk

docs/index.rst

-.. module:: GeoSpatialTools
+===============
+GeoSpatialTools
+===============
 
 .. PyCOADS documentation master file, created by
    sphinx-quickstart on Fri Jul  5 11:49:36 2024.
    You can adapt this file completely to your liking, but it should at least
    contain the root `toctree` directive.
 
-``GeoSpatialTools`` documentation
----------------------------------
-
-``GeoSpatialTools`` is a python3_ library for identifying neighbours in a geo-spatial context. This is designed to solve
-problems where one needs to identify data within a spatial range on the surface of the Earth. The library provides
-implementations of standard tools for neighbourhood searching, such as k-d-tree_ and Quadtree_ that have been
-adapted to account for spherical geometry, using a haversine_ distance metric. 
-
-The tool allows for spatial look-ups with :math:`O(\log(n))` complexity in time. Additionally, a simple 1-d nearest
-neighbours look-up is provided for sorted data using bisection_ search.
-
-``GeoSpatialTools`` also provides functionality for working with great-circle_ objects, for example intersecting
-great-circles.
-
 .. toctree::
    :maxdepth: 4
    :caption: Contents:
     
-   authors
+   introduction
    installation
+   bisection
    record
+   shape
    quadtree
    octtree
+   kdtree
    users_guide
 
-   
 .. include:: hyperlinks.rst
 
 ..

docs/installation.rst

 ============
 
 ``GeoSpatialTools`` is not currently available on PyPI so must be installed either from source or directly from the
-GitLab repository.
+GitLab repository. Versions of python between 3.9 and 3.13, inclusive, are supported, however the recommended version of
+python is 3.12.
 
 We recommend the installation of ``GeoSpatialTools`` using the uv_ package manager, however it can be installed using
 pip_.
 
+The only required dependency of the project is NumPy_. Additional dependency polars_ is required to run the Jupyter_
+notebooks.
+
 Via UV
 ======
 
 
 .. code-block:: bash
 
+   # Get the code
    git clone git@git.noc.ac.uk/nocsurfaceprocesses/geospatialtools.git
    cd geospatialtools
-   uv sync --all-extras --dev --python 3.12  # Install with all dependencies and create an environment with python 3.12
-   source .venv/bin/activate                 # Load the environment
 
-The recommended python version is python 3.12. By default, uv creates a virtual environment in ``.venv``.
+   # Install with all dependencies and create an environment with python 3.12
+   uv sync --all-extras --dev --python 3.12 
+
+   # Load the environment
+   source .venv/bin/activate
+
+   # Run the unit tests
+   uv run pytest test
+
+.. note:: The recommended python version is python 3.12. By default, uv creates a virtual environment in ``.venv``.
 
 Via Pip
 =======

docs/introduction.rst

+============
+Introduction
+============
+
+GeoSpatialTools
+===============
+
+``GeoSpatialTools`` is a python3_ library developed at NOC_ (National Oceanography Centre, Southampton, UK) for
+identifying neighbours in a geo-spatial context. This is designed to solve problems where one needs to identify
+data within a spatial range on the surface of the Earth. The library provides implementations of standard tools
+for neighbourhood searching, such as k-d-tree_ and Quadtree_ that have been adapted to account for spherical
+geometry, using a haversine_ distance metric.
+
+The tool allows for spatial look-ups with :math:`O(\log(n))` complexity in time. Additionally, a simple 1-d nearest
+neighbours look-up is provided for sorted data using bisection_ search.
+
+``GeoSpatialTools`` also provides functionality for working with great-circle_ objects, for example intersecting
+great-circles.
+
+.. include:: authors.rst
+
+.. include:: hyperlinks.rst

docs/kdtree.rst

+========
+K-D-Tree
+========
+
+A K-D-Tree is a data structure that operates in a similar way to bisection or a binary tree, and can be used to find the
+nearest neighbour. For :math:`k`-dimensional data (i.e. the data has :math:`k` features), a binary tree is constructed
+by bisecting the data along each of the :math:`k` dimensions in sequence. The first layer bisects the data along the
+first dimension, the second layer bisects each of the previous bisection results along the 2nd dimension (the data is
+now partitioned into 4), and so on. The pattern repeats after the :math:`k`-th layer, until a single point of data 
+remains in each leaf node. A K-D-Tree that bisects data and results in each leaf node containing a single value is
+called referred to as a balanced K-T-Tree.
+
+To find the data point that is closest to a point in the tree, one descends the tree comparing the query point to the
+partition value in each dimension. The final leaf node should be the closest point, however there may be a point closer
+if the query point is close to a previous partition value, so some back tracking is performed to either confirm, or
+update, the closest point.
+
+A K-D-Tree can typically find the nearest neighbour in :math:`O(\log(n))` time complexity, and the data structure has
+:math:`O(n)` space-complexity.
+
+Most implementations of K-D-Tree assume that the coordinates use a cartesian geometry and therefore use a simple
+Euclidean distance to identify the nearest neighbour. The implementation in ``GeoSpatialTools.kdtree`` assumes a
+spherical geometry on the surface of the Earth and uses the Haversine distance to identify neighbours. The
+implementation has been designed to account for longitude wrapping at -180, 180 degrees. The
+``GeoSpatialTools.kdtree.KDTree`` class is a 2-D-Tree, the dimensions are longitude and latitude. The object is
+initialised with data in the form of a list of ``GeoSpatialTools.quadtree.Record`` objects. A maximum depth value
+(``max_depth``) can be provided, if this is set then the partitioning will stop after ``max_depth`` partitionings,
+the leaf nodes may contain more than one ``Record``.
+
+Example
+=======
+
+.. code-block:: python
+
+   from GeoSpatialTools import KDTree, Record
+   from random import choice
+
+   lon_range = list(range(-180, 180))
+   lat_range = list(range(-90, 90))
+   N_samples = 1000
+
+   records: list[Record] = [Record(choice(lon_range), choice(lat_range)) for _ in range(N_samples)]
+   # Construct Tree
+   kdtree = KDTree(records)
+
+   test_value: Record = Record(lon=47.6, lat=-31.1)
+   neighbours, dist = kdtree.query(test_value)
+
+Documentation
+=============
+
+.. note:: Insertion and deletion operations may cause the ``KDTree`` to become un-balanced.
+
+Inserting Records
+-----------------
+
+A ``Record`` can be inserted in to a ``KDTree`` with the ``KDTree.insert`` method. The method will return ``True`` if
+the ``Record`` was inserted into the ``KDTree``, ``False`` otherwise. A ``Record`` will not be added if it is already
+contained within the ``KDTree``, to add the ``Record`` anyway use the ``KDTree._insert`` method.
+
+Removing Records
+----------------
+
+A ``Record`` can be removed from a ``KDTree`` with the ``KDTree.delete`` method. The method will return ``True`` if the
+``Record`` was successfully removed, ``False`` otherwise (for example if the ``Record`` is not contained within the
+``KDTree``).
+
+Querying
+--------
+
+The nearest neighbour ``Record`` contained within a ``KDTree`` to a query ``Record`` can be found with the
+``KDTree.query`` method. This will return a tuple containing the list of ``Record`` objects from the ``KDTree`` with
+minimum distance to the query ``Record``, and the minimum distance.
+
+kdtree Module
+=============
+
+.. automodule:: GeoSpatialTools.kdtree
+   :members:

docs/octtree.rst

 Whilst the Quadtree divides into 4 children after the capacity is reached, the Octtree divides into 8 children. The
 divisions are at the longitude midpoint, the latitude midpoint, and the datetime midpoint of the boundary.
 
+The implementation of Octtree within this library, the ``OctTree`` class, utilises the Haversine distance as a metric
+for indentifying records within the queried region. This allows the Octtree to account for the spherical geometry of the
+Earth. Boundary checks with query regions also account for the wrapping of longitude at -180, 180 degrees.
+
+The ``OctTree`` object is defined by a bounding box in space and time, i.e. boundaries at the western, eastern,
+southern, and northern edges as well as the start and end datetimes of the data that will be inserted into the ``OctTree``.
+Additionally, a capacity and maximum depth can be provided. If the capacity is exceeded whilst inserting records the
+``OctTree`` will divide and new records will be inserted into the appropriate child ``OctTree``. The maxium depth is the
+maximum height of the ``OctTree``, if capacity is also specified then this will be overridden if the ``OctTree`` is at this
+depth, and the ``OctTree`` will not divide.
+
 Documentation
 =============
 
 -----------------
 
 A ``SpaceTimeRecord`` can be added to an ``OctTree`` with ``OctTree.insert`` which will return ``True`` if the operation
-was successful, ``False`` otherwise. The ``OctTree`` is modified in place.
+was successful, ``False`` otherwise. The ``OctTree`` is modified in place. Records that fall outside the bounds of the
+``OctTree`` will not be inserted as the boundary is fixed.
 
 Removing Records
 ----------------
 
 .. code-block:: python
 
-   from GeoSpatialTools.octtree import OctTree, SpaceTimeRecord, SpaceTimeRectangle
+   from GeoSpatialTools import OctTree, SpaceTimeRecord, SpaceTimeRectangle
    from datetime import datetime, timedelta
    from random import choice
    from polars import datetime_range

docs/quadtree.rst

 Quadtree
 ========
 
+A Quadtree is a data-structure where each internal node has exactly four children, and are used to recursively partition
+a two-dimensional spatial domain. Each child note is itself a Quadtree, whose spatial domain represents one of the
+quadrants (north-west, north-east, south-west, south-east) of its parent's domain. The partitioning of data in this way
+is dependent on the spatial density of data inserted into the Quadtree. The Quadtree is typically initialised with a
+capacity value, once the capacity is reached (by inserting data points), the Quadtree divides and subsequent data points
+are added to the appropriate child-node.
+
+Quadtree structures allow for fast identification of data within some query region. The structure of the tree ensures
+that only nodes whose domain boundary intersects (or contains or is contained by) the query region are evaluated. The
+time-complexity of these query operations is :math:`O(\log(n))`, the space-complexity of a Quadtree is :math:`O(n)`.
+
+Typically, it is assumed that the data uses a cartesian coordinate system, so comparisons between boundaries and query
+shapes utilise cartesian geometry and euclidean distances. The implementation of Quadtree within this library, the
+``QuadTree`` class, utilises the Haversine distance as a metric for indentifying records within the queried region.
+This allows the Quadtree to account for the spherical geometry of the Earth. Boundary checks with query regions also
+account for the wrapping of longitude at -180, 180 degrees.
+
+The ``QuadTree`` object is defined by a bounding box, i.e. boundaries at the western, eastern, southern, and northern edges of
+the data that will be inserted into the ``QuadTree``. Additionally, a capacity and maximum depth can be provided. If the
+capacity is exceeded whilst inserting records the ``QuadTree`` will divide and new records will be inserted into the appropriate
+child ``QuadTree``. The maxium depth is the maximum height of the ``QuadTree``, if capacity is also specified then this will be
+overridden if the ``QuadTree`` is at this depth, and the ``QuadTree`` will not divide.
+
 Documentation
 =============
 
 
 .. code-block:: python
 
-   from GeoSpatialTools.quadtree import QuadTree, Record, Rectangle
+   from GeoSpatialTools import QuadTree, Record, Rectangle
    from random import choice
 
    lon_range = list(range(-180, 180))

docs/record.rst

 ==============
 Record Classes
 ==============
+
+``Record`` classes in ``GeoSpatialTools`` form the back-bone of the data structures within the library. They represent a
+consistent input data-type across all classes in the library.
+
+There are two classes of ``Record``:
+
+* ``GeoSpatialTools.record.Record`` for two-dimensional data structures defined by ``lon`` (longitude) and ``lat``
+  (latitude). Optionally, one can pass ``datetime`` and ``uid``, as well as additional data attributes with keyword
+  arguments.
+* ``GeoSpatialTools.record.SpaceTimeRecord`` for three-dimensional data structures defined by ``lon`` (longitude),
+  ``lat`` (latitude), and ``datetime``. Optionally, one can pass ``uid``, as well as additional data attributes with
+  keyword arguments.
+
+Only the positional, datetime, and uid attributes are used for equality tests. ``Record`` objects are used for
+``QuadTree`` and ``KDTree`` objects, whereas ``SpaceTimeRecord`` objects must be used for ``OctTree``.
+
+.. note:: ``Record`` and ``SpaceTimeRecord`` are exposed at the ``GeoSpatialTools`` level.
+
+Example
+=======
+
+.. code-block:: python
+
+   from GeoSpatialTools import Record
+
+   record: Record = Record(lon=-151.2, lat=42.7, uid="foo")
+   dist: float = record.distance(Record(-71.1, -23.2, uid="bar"))
+
+record Module
+=============
+
+.. automodule:: GeoSpatialTools.record
+   :members:
+

docs/shape.rst

+=============
+Shape Classes
+=============
+
+The ``GeoSpatialTools.shape`` module defines various classes that can be used to define the boundary for ``QuadTree``
+and ``OctTree`` classes, or query regions for the same.
+
+``Rectangle`` and ``SpaceTimeRectangle`` classes are used to define the boundaries for ``QuadTree`` and ``OctTree``
+classes respectively. They are defined by the bounding box in space (and time for a ``SpaceTimeRectangle``).
+
+``Ellipse`` and ``SpaceTimeEllipse`` classes are defined by ``lon`` and ``lat`` indicating the centre of the ellipse, ``a``
+and ``b`` indicating the length of the semi-major and semi-minor axes respectively, and ``theta`` indicating the angle
+of the ellipse. ``SpaceTimeEllipse`` classes also require ``start`` and ``end`` datetime values. The
+``SpaceTimeEllipse`` is an elliptical cylinder where the height is represented by the time dimension.
+
+``Rectangle`` and ``Ellipse`` classes can be used to define a query shape for a ``QuadTree``, using ``QuadTree.query``
+and ``QuadTree.query_ellipse`` respectively.
+
+``SpaecTimeRectangle`` and ``SpaceTimeEllipse`` classes can be used to define a query shape for a ``OctTree``, using
+``OctTree.query`` and ``OctTree.query_ellipse`` respectively.
+
+Example
+=======
+
+.. code-block:: python
+
+   from GeoSpatialTools.shape import Rectangle, SpaceTimeEllipse
+   from datetime import datetime
+   from math import pi
+
+   rectangle: Rectangle = Rectangle(
+       west=-180,
+       east=180,
+       south=-90,
+       north=90,
+   )
+
+   ellipse: SpaceTimeEllipse = SpaceTimeEllipse(
+       lon=23.4,
+       lat=-17.9,
+       a=103,
+       b=71,
+       theta=pi/3,
+       start=datetime(2009, 2, 13, 19, 30),
+       end=datetime(2010, 7, 2, 3, 45),
+   )
+
+shape Module
+============
+
+.. automodule:: GeoSpatialTools.shape
+   :members:
+

docs/users_guide.rst

-===========
-Users Guide
-===========
-
-.. automodule:: GeoSpatialTools.neighbours
-   :members:
-
-.. automodule:: GeoSpatialTools.quadtree
-   :members:
-
-.. automodule:: GeoSpatialTools.octtree
-   :members:
-
-.. automodule:: GeoSpatialTools.kdtree
-   :members:
+==================
+Additional Modules
+==================
 
 .. automodule:: GeoSpatialTools.great_circle
    :members:
 
 .. automodule:: GeoSpatialTools.distance_metrics
    :members:
+
+.. automodule:: GeoSpatialTools.utils
+   :members:

CHANGES.md

 
 ### Breaking Changes
 
+* Removed `SpaceTimeRecords` class, favour `list[SpaceTimeRecord]` (!27).
 * `Record` and `SpaceTimeRecord` classes moved to `GeoSpatialTools.record` module (!27).
 * `Rectangle`, `Ellipse`, `SpaceTimeRectangle`, `SpaceTimeEllipse` classes moved to `GeoSpatialTools.shape` module (!27).
 
 ### Internal changes
 
+* Added complete documentation (!27).
 * Added changelog (!26).
 
 ## 0.11.2 (2025-02-27)

[Joseph Siddons]

@ricorne : please have a look at docs/Documentation.pdf and let me know if you have any suggestions.

[Joseph Siddons]

https://git.noc.ac.uk/nocsurfaceprocesses/geospatialtools/-/blob/0bb2e0e603aef49e789188a1c7a8097a22fb8421/docs/Documentation.pdf

edit: update file to latest commit