from collections.abc import Callable
from typing import Any, Literal
from warnings import warn
import numpy as np
from shapely import is_valid_reason
from shapely.geometry import LineString, MultiLineString, MultiPolygon, Polygon
# ======== Messages and constants ======== #
# Pre-defined DGGS with WGS84 ellipsoid, coordinates in degrees, n == 3 to subdivide
# cell sides, and both N and S polar cube face attached to O equatorial cube face:
# N
# O P Q R
# S
# List of resolution 0 cell addresses (i.e. cube faces)
from rhealpixdggs.cell import Cell, _ring_step_neighbors
from rhealpixdggs.conversion import cells_from_linestring, cells_from_polygon
from rhealpixdggs.dggs import WGS84_003, LineSemantics, RHEALPixDGGS
# Warnings
PARENT_RESOLUTION_WARNING = "WARNING: You requested a parent resolution that is higher than the cell resolution. Returning the cell address itself."
CHILD_RESOLUTION_WARNING = "WARNING: You requested a child resolution that is lower than the cell resolution. Returning the cell address itself."
CELL_CENTRE_WARNING = "WARNING: You requested a centre cell for a DGGS that has an even number of cells on a side. Returning None."
POLYFILL_GEOMETRY_WARNING = "WARNING: Empty or missing geometry, unsupported geometry type (not Polygon or MultiPolygon), or geometry with no area. Returning None."
LINETRACE_GEOMETRY_WARNING = "WARNING: Empty or missing line geometry, unsupported line type (not LineString or MultiLineString), or line with no length. Returning None."
# ======== Main API ======== #
[docs]
def geo_to_rhp(
lat: float,
lng: float,
resolution: int,
plane: bool = True,
dggs: RHEALPixDGGS = WGS84_003,
) -> str | None:
"""
Turn a latitute and longitude (in degrees) into an rHEALPix cell address at
the requested resolution.
Mostly passes through the parameters to the function turning coordinate points
into cells, but converts the address tuple from the resulting cell into a
string.
Returns None if no cell matching the coordinates is found.
EXAMPLES::
>>> geo_to_rhp(-43.738058, -176.260506, 9, plane=False)
'S001450634'
>>> geo_to_rhp(-43.738379,-176.258807, 9, plane=False)
'S001450635'
"""
dggs._require_index_strings()
cell = dggs.cell_from_point(resolution, (lng, lat), plane)
# Bail out if there's no matching cell
if cell is None:
return None
return dggs.format_index(cell.suid)
[docs]
def rhp_to_geo(
rhpindex: str,
geo_json: bool = True,
plane: bool = True,
dggs: RHEALPixDGGS = WGS84_003,
) -> tuple[float, float] | None:
"""
Look up the centroid (in degrees) of the cell identified by rhpindex:
the cell's direct position in the sense of OGC Topic 21 (see
``Cell.centroid``). With `plane` = True, the default, that is the
centre of the planar square, which is also the cell's nucleus; with
`plane` = False it is the area-weighted centroid on the ellipsoid.
Returns None if the cell index is invalid.
If geojson is requested as the output format:
- Will return a (longitude, latitude) coordinate pair.
if geojson is NOT requested as the output format:
- Will return a (latitude, longitude) coordinate pair in order to be consistent with
h3 coordinate ordering.
EXAMPLES::
>>> rhp_to_geo('S001450634', True, False)
(-176.2606635452476, -43.7365450535837)
>>> rhp_to_geo('S001450635', True, False)
(-176.25592420875034, -43.7365450535837)
>>> rhp_to_geo('NotACellId', True, False)
"""
suid = dggs.parse_index(rhpindex)
if suid is None:
return None
cell = dggs.cell(suid)
centroid = cell.centroid(plane=plane)
# rhealpix coordinates come out natively as lng/lat, h3 ones as lat/lng
if not geo_json:
# lng/lat -> lat/lng to make it consistent with h3
centroid = centroid[::-1]
return (float(centroid[0]), float(centroid[1]))
[docs]
def rhp_to_parent(
rhpindex: str,
res: int | None = None,
verbose: bool = True,
dggs: RHEALPixDGGS = WGS84_003,
) -> str | None:
"""
Returns parent of rhpindex at resolution res (immediate parent if res == None).
Returns None if the cell index is invalid.
EXAMPLES::
>>> rhp_to_parent('S001450634', res=0)
'S'
>>> rhp_to_parent('S001450634')
'S00145063'
>>> rhp_to_parent('INVALID')
"""
suid = dggs.parse_index(rhpindex)
if suid is None:
return None
# Top-level cells are their own parent, regardless of the requested resolution (by convention)
child_res = len(suid) - 1
if child_res < 1:
return rhpindex
# res == None returns the first address up (by convention)
elif res is None:
return dggs.index_ancestor(rhpindex, child_res - 1)
# Handle mismatch between cell resolution and requested parent resolution
elif res > child_res:
if verbose:
warn(PARENT_RESOLUTION_WARNING, stacklevel=2)
return rhpindex
# Standard case (including child_res == res)
else:
return dggs.index_ancestor(rhpindex, res)
[docs]
def rhp_to_center_child(
rhpindex: str,
res: int | None = None,
verbose: bool = True,
dggs: RHEALPixDGGS = WGS84_003,
) -> str | None:
"""
Returns central child of rhpindex at resolution res (immediate central
child if res == None).
Returns None if the cell index is invalid.
Returns None if the DGGS has an even number of cells on a side.
EXAMPLES::
>>> rhp_to_center_child('S001450634')
'S0014506344'
>>> rhp_to_center_child('S001450634', res=13)
'S0014506344444'
>>> rhp_to_center_child('S001450634', res=9)
'S001450634'
>>> rhp_to_center_child('S001450634', res=10)
'S0014506344'
>>> rhp_to_center_child('INVALID')
"""
suid = dggs.parse_index(rhpindex)
if suid is None:
return None
# DGGSs with even numbers of cells on a side never have a cell at the centre
if (dggs.N_side % 2) == 0:
if verbose:
warn(CELL_CENTRE_WARNING, stacklevel=2)
return None
# Handle mismatch between cell resolution and requested child resolution
parent_res = len(suid) - 1
if res is not None and res < parent_res:
if verbose:
warn(CHILD_RESOLUTION_WARNING, stacklevel=2)
return rhpindex
# Standard case (including parent_res == res)
else:
# res == None returns the central child from one level down (by convention)
added_levels = 1 if res is None else res - parent_res
# Derive index of centre child and append that to rhpindex
# NOTE: only works for odd values of N_side
c_index = int((dggs.N_side**2 - 1) / 2)
return dggs.format_index(suid + (c_index,) * added_levels)
[docs]
def rhp_to_geo_boundary(
rhpindex: str,
geo_json: bool = True,
plane: bool = True,
dggs: RHEALPixDGGS = WGS84_003,
) -> tuple[tuple[float, float], ...] | None:
"""
Extract the corner coordinates of a cell at a given cell ID and returns them as
a tuple of coordinate pairs (in degrees).
Returns None if the cell index is invalid.
If geojson is requested as the output format:
- Will return (longitude, latitude) coordinate pairs.
- Will repeat the first vertex and insert it at the end if geojson is requested as
the output format.
If geojson is NOT requested as the output format:
- Will return (latitude, longitude) coordinate pairs in order to be consistent with
rHEALPix coordinate ordering.
EXAMPLES::
>>> rhp_to_geo_boundary('S001450634', False, False)
((-43.73395872598705, -176.26086040756147), (-43.73395872598705, -176.25612132062557), (-43.73913136381169, -176.26046658591815), (-43.73913136381169, -176.2652061719943))
>>> rhp_to_geo_boundary('S001450634', True, False)
((-176.26086040756147, -43.73395872598705), (-176.25612132062557, -43.73395872598705), (-176.26046658591815, -43.73913136381169), (-176.2652061719943, -43.73913136381169), (-176.26086040756147, -43.73395872598705))
>>> rhp_to_geo_boundary('INVALID')
"""
suid = dggs.parse_index(rhpindex)
if suid is None:
return None
# Grab the cell vertices (includes non-corner point in darts if plane == False)
cell = dggs.cell(suid)
verts = tuple(cell.vertices(plane=plane))
# rhealpix coordinates come out natively as lng/lat, h3 ones as lat/lng
# Neither has the repeated vertex that geo_json wants so it's inserted here when needed
if not geo_json:
# lng/lat -> lat/lng to make it consistent with h3
verts = tuple(v[::-1] for v in verts)
else:
# last point same as first
verts += (verts[0],)
return tuple((float(v[0]), float(v[1])) for v in verts)
[docs]
def rhp_get_resolution(rhpindex: str, dggs: RHEALPixDGGS = WGS84_003) -> int | None:
"""
Returns the resolution of a given cell index (or None if invalid).
EXAMPLES::
>>> rhp_get_resolution('S001450634')
9
>>> rhp_get_resolution('INVALID')
"""
if dggs.parse_index(rhpindex) is None:
return None
return dggs.index_resolution(rhpindex)
[docs]
def rhp_get_base_cell(rhpindex: str, dggs: RHEALPixDGGS = WGS84_003) -> str | None:
"""
Returns the resolution 0 cell id of a given cell index (or None if invalid).
EXAMPLES::
>>> rhp_get_base_cell('S001450634')
'S'
>>> rhp_get_base_cell('INVALID')
"""
suid = dggs.parse_index(rhpindex)
if suid is None:
return None
return str(suid[0])
[docs]
def rhp_to_uint64(rhpindex: str, dggs: RHEALPixDGGS = WGS84_003) -> int | None:
"""
Returns the uint64 zone identifier of a cell index (or None if invalid);
see ``Cell.uint64``.
EXAMPLES::
>>> rhp_to_uint64('R553110')
3458765673461713695
>>> rhp_to_uint64('INVALID')
"""
suid = dggs.parse_index(rhpindex)
if suid is None:
return None
return dggs.cell(suid).uint64
[docs]
def rhp_from_uint64(value: int, dggs: RHEALPixDGGS = WGS84_003) -> str | None:
"""
Returns the cell index with a uint64 zone identifier (or None if it names
no cell); see ``Cell.uint64``.
EXAMPLES::
>>> rhp_from_uint64(3458765673461713695)
'R553110'
>>> rhp_from_uint64(1 << 30)
'O'
>>> rhp_from_uint64(1)
"""
try:
return str(dggs.cell_from_uint64(value))
except ValueError:
return None
[docs]
def rhp_is_valid(rhpindex: str, dggs: RHEALPixDGGS = WGS84_003) -> bool:
"""
Checks if the given cell address is valid within the DGGS, i.e. whether
``dggs.parse_index`` accepts it. Like every function taking an index
string, raises ValueError if `dggs` has no index strings (``N_side``
other than 2 or 3).
EXAMPLES::
>>> rhp_is_valid('S001450634')
True
>>> rhp_is_valid('N')
True
>>> rhp_is_valid('INVALID')
False
>>> rhp_is_valid(None)
False
>>> rhp_is_valid(123456)
Traceback (most recent call last):
...
TypeError: object of type 'int' has no len()
"""
if rhpindex is None or len(rhpindex) == 0:
return False
return dggs.parse_index(rhpindex) is not None
[docs]
def cell_area(
rhpindex: str,
unit: Literal["km^2", "m^2"] = "km^2",
plane: bool = True,
dggs: RHEALPixDGGS = WGS84_003,
) -> float | None:
"""
Returns the area of a cell in the requested unit (or None if rhpindex is invalid).
TODO: investigate use case where unit is 'rads^2'
EXAMPLES::
>>> cell_area('S001450634', unit='m^2', plane=False)
219428.08748562282
>>> cell_area('S001450635', unit='m^2', plane=False)
219428.08748562282
>>> cell_area('S00145063', unit='km^2', plane=False)
1.9748527873706059
>>> cell_area('INVALID', unit='km^2', plane=False)
"""
suid = dggs.parse_index(rhpindex)
if suid is None:
return None
cell = dggs.cell(suid)
area = float(cell.area(plane=plane))
# Scale area if needed
if unit == "km^2":
area = area / 10**6
return float(area)
[docs]
def cell_ring(
rhpindex: str, k: int = 1, dggs: RHEALPixDGGS = WGS84_003
) -> list[str] | None:
"""
Returns the ring of cell indices around rhpindex at distance k (in graph
distance -- shortest number of edge/corner hops -- not straight-line
distance), or None if rhpindex is invalid.
Also returns None if k < 0.
Returns [ rhpindex ] if k == 0 (by convention).
Built by growing the ring outward one shell at a time from `neighbor()`
(edge-adjacent) and `diagonal_neighbor()` (corner-adjacent) steps, so
this is correct near a cube corner too: exactly 3 cells meet at each of
the cube's 8 corners rather than 4, so a ring passing near one has fewer
cells there than the usual 8*k for an interior ring, rather than an
incorrect or duplicate cell.
EXAMPLES::
>>> cell_ring('S001450634')
['S001450631', 'S001450632', 'S001450635', 'S001450638', 'S001450637', 'S001450636', 'S001450633', 'S001450630']
>>> cell_ring('S001450634', k=2)
['S001450607', 'S001450608', 'S001450606', 'S001450616', 'S001450640', 'S001450643', 'S001450646', 'S001450670', 'S001450662', 'S001450661', 'S001450660', 'S001442882', 'S001442858', 'S001442855', 'S001442852', 'S001442828']
>>> cell_ring('S001450634', k=0)
['S001450634']
>>> cell_ring('S', k=1)
['O', 'P', 'Q', 'R']
>>> cell_ring('S', k=-1)
"""
suid = dggs.parse_index(rhpindex)
if suid is None or k < 0:
return None
if k == 0:
return [rhpindex]
center = dggs.cell(suid)
return [str(cell) for cell in _rings_up_to(center, k)[k]]
[docs]
def k_ring(
rhpindex: str, k: int = 1, dggs: RHEALPixDGGS = WGS84_003
) -> list[str] | None:
"""
Returns the k-ring (the centre cell together with every ring out to
distance k, in graph distance -- see cell_ring()) of cell indices around
rhpindex, or None if rhpindex is invalid.
Also returns None if k < 0.
EXAMPLES::
>>> k_ring('S001450634')
['S001450634', 'S001450631', 'S001450632', 'S001450635', 'S001450638', 'S001450637', 'S001450636', 'S001450633', 'S001450630']
>>> k_ring('S001450634', k=2)
['S001450634', 'S001450631', 'S001450632', 'S001450635', 'S001450638', 'S001450637', 'S001450636', 'S001450633', 'S001450630', 'S001450607', 'S001450608', 'S001450606', 'S001450616', 'S001450640', 'S001450643', 'S001450646', 'S001450670', 'S001450662', 'S001450661', 'S001450660', 'S001442882', 'S001442858', 'S001442855', 'S001442852', 'S001442828']
>>> k_ring('S001450634', k=0)
['S001450634']
>>> k_ring('S001450634', k=-1)
>>> k_ring('INVALID')
"""
suid = dggs.parse_index(rhpindex)
if suid is None or k < 0:
return None
if k == 0:
return [rhpindex]
center = dggs.cell(suid)
return [str(cell) for ring in _rings_up_to(center, k) for cell in ring]
[docs]
def polyfill(
geometry: Polygon | MultiPolygon,
res: int,
plane: bool = True,
compress: bool = False,
verbose: bool = False,
dggs: RHEALPixDGGS = WGS84_003,
containment: Literal["center", "full", "overlapping"] = "center",
min_res: int = 0,
) -> set[str] | None:
"""
Turns the area contained in a shapely polygon or multipolygon into a set of cell
indices at the requested resolution: ``conversion.cells_from_polygon``
as a set, with None where that function raises or finds nothing to fill.
Which cells count is chosen by
`containment`, following H3's modes:
- ``"center"`` (default): a cell is included if its centroid is inside the
geometry defined by the boundaries and holes.
- ``"full"``: a cell is included if the whole cell lies within the geometry
(its boundary may touch the geometry's).
- ``"overlapping"``: a cell is included if any part of it meets the
geometry, so the result covers the geometry.
``full`` and ``overlapping`` test the cell's boundary polygon. In the plane
that polygon is exact. On the ellipsoid, equatorial cells are
longitude-latitude aligned and exact too; polar cells have curved edges,
which are represented by ``6`` points per edge (``Cell.boundary(n=6)``), so
a decision there is made against that piecewise-linear approximation. A
cap cell, which spans every longitude, is fully inside only a geometry
that covers the whole latitude band from the cap's boundary to the pole,
and overlaps any geometry reaching that latitude.
The candidate cells are those of the geometry's bounding box
(``RHEALPixDGGS.cells_in_box``), and every test runs on all candidates
at once: centroids from ``RHEALPixDGGS.centroids``, boundaries from
``RHEALPixDGGS.boundary_array``, predicates from shapely's vectorised
functions.
Returns an empty set if no cell centroids fall within the input geometry.
Returns None if the geom_type field in the input geometry is anything other than
'Polygon' or 'MultiPolygon'.
Returns None if the geometry is empty, or if it has no area.
Returns None if no cells match the geometry for some reason.
Returns None if the geometry is invalid in other ways, e.g. if a point on a hole
boundary is outside the exterior boundary of its polygon, or if two polygons in a
multipolygon overlap.
Polygon edges are straight in the input coordinate space (shapely
geometries are planar) and do not wrap around the antimeridian; a
region straddling it must be split into a MultiPolygon along the
antimeridian by the caller first, as is standard for planar GIS
geometry.
The fill descends the hierarchy from resolution `min_res`: a cell wholly
inside the geometry is kept whole, a cell missing it is dropped, and only
the cells the boundary passes through are split, down to resolution
`res`, where the remaining cells are decided by `containment`. So the
work grows with the length of the boundary, not the area. With
`compress` = False every kept coarse cell is expanded into its
resolution-`res` descendants, giving exactly the cells a cell-by-cell
test at `res` would give. With `compress` = True the coarse cells are
returned as they are, a mixed-resolution cover with no cell coarser than
`min_res` and no complete group of siblings left unmerged; so every cell
of the result has exactly one ancestor at resolution `min_res`, which
suits partitioning by that resolution. "Wholly inside" is judged by the
cell's boundary polygon for ``full`` and ``overlapping`` where that is
exact (the plane, equatorial cells), and otherwise by the cell's
longitude-latitude bounding box, which contains the cell: for polar
cells, whose 6-point polygon is only approximate, and for ``center``,
where the box also contains every descendant's centroid, so the centroid
rule is kept exactly.
``polyfill_array`` returns the same cells as a sorted numpy string array,
which costs less than half the memory per cell for large fills.
EXAMPLES::
>>> from shapely import Polygon
>>> coords = ((0., 0.), (0., 1.), (1., 1.), (1., 0.), (0., 0.))
>>> polygon = Polygon(coords)
>>> polyfill(polygon, res=1, plane=False)
set()
>>> polyfill(polygon, res=2, plane=False)
set()
>>> polyfill(polygon, res=3, plane=False)
set()
>>> polyfill(polygon, res=4, plane=False)
{'Q3330'}
>>> sorted(polyfill(polygon, res=5, plane=False))
['Q33303', 'Q33304', 'Q33305', 'Q33306', 'Q33307', 'Q33308', 'Q33330', 'Q33331', 'Q33332']
>>> sorted(polyfill(polygon, res=6, plane=False))
['Q333033', 'Q333034', 'Q333035', 'Q333036', 'Q333037', 'Q333038', 'Q333043', 'Q333044', 'Q333045', 'Q333046', 'Q333047', 'Q333048', 'Q333053', 'Q333054', 'Q333056', 'Q333057', 'Q333060', 'Q333061', 'Q333062', 'Q333063', 'Q333064', 'Q333065', 'Q333066', 'Q333067', 'Q333068', 'Q333070', 'Q333071', 'Q333072', 'Q333073', 'Q333074', 'Q333075', 'Q333076', 'Q333077', 'Q333078', 'Q333080', 'Q333081', 'Q333083', 'Q333084', 'Q333086', 'Q333087', 'Q333300', 'Q333301', 'Q333302', 'Q333303', 'Q333304', 'Q333305', 'Q333306', 'Q333307', 'Q333308', 'Q333310', 'Q333311', 'Q333312', 'Q333313', 'Q333314', 'Q333315', 'Q333316', 'Q333317', 'Q333318', 'Q333320', 'Q333321', 'Q333323', 'Q333324', 'Q333326', 'Q333327', 'Q333330', 'Q333331', 'Q333332', 'Q333333', 'Q333334', 'Q333335', 'Q333340', 'Q333341', 'Q333342', 'Q333343', 'Q333344', 'Q333345', 'Q333350', 'Q333351', 'Q333353', 'Q333354']
Four of those res-6 groups have all 9 siblings present (Q33306x, Q33307x,
Q33330x, Q33331x), so compress=True collapses them one level to res-5 parents.
The remaining partial groups stay at res-6, giving a mixed-resolution result:
>>> sorted(c for c in polyfill(polygon, res=6, plane=False, compress=True) if len(c) < 7)
['Q33306', 'Q33307', 'Q33330', 'Q33331']
At res=7 the same four cells are again fully covered (all 81 of each cell's
res-7 grandchildren fall inside the polygon), so compaction runs two levels:
res-7 siblings collapse to res-6 parents, those in turn collapse to res-5:
>>> result7 = polyfill(polygon, res=7, plane=False, compress=True)
>>> 'Q33306' in result7 # res-5 cell present despite res=7 request
True
>>> 'Q333060' not in result7 # intermediate res-6 cell absorbed
True
>>> 'Q3330600' not in result7 # original res-7 cell absorbed
True
"""
dggs._require_index_strings()
if _warn_if_malformed(
geometry, verbose, _malformed_geometry, POLYFILL_GEOMETRY_WARNING
):
return None
return set(
cells_from_polygon(
geometry, res, plane, containment, compress, min_res, dggs
).tolist()
)
[docs]
def polyfill_array(
geometry: Polygon | MultiPolygon,
res: int,
plane: bool = True,
compress: bool = False,
verbose: bool = False,
dggs: RHEALPixDGGS = WGS84_003,
containment: Literal["center", "full", "overlapping"] = "center",
min_res: int = 0,
) -> np.ndarray | None:
"""
``polyfill`` returning the cell indices as a numpy string array instead of
a set: the same cells for the same arguments, sorted (by base cell, then
digit by digit, the order ``Cell`` objects sort in; with `compress` a
coarse cell comes where its descendants would) and without duplicates,
or ``None`` where ``polyfill`` returns ``None``. An empty array means no
cell qualified.
The array costs about ``4 * (res + 2)`` bytes per cell against roughly a
hundred for a set entry, and feeds array-based callers such as
``RHEALPixDGGS.boundary_array``, ``RHEALPixDGGS.centroids`` or a data
frame column directly.
EXAMPLES::
>>> from shapely import Polygon
>>> polygon = Polygon(((0., 0.), (0., 1.), (1., 1.), (1., 0.), (0., 0.)))
>>> polyfill_array(polygon, res=5, plane=False).tolist()
['Q33303', 'Q33304', 'Q33305', 'Q33306', 'Q33307', 'Q33308', 'Q33330', 'Q33331', 'Q33332']
>>> polyfill_array(polygon, res=2, plane=False).size
0
>>> polyfill_array(Polygon(), res=2, plane=False) is None
True
"""
if _warn_if_malformed(
geometry, verbose, _malformed_geometry, POLYFILL_GEOMETRY_WARNING
):
return None
return cells_from_polygon(
geometry, res, plane, containment, compress, min_res, dggs
)
[docs]
def linetrace(
geometry: LineString | MultiLineString,
res: int,
plane: bool = True,
verbose: bool = False,
dggs: RHEALPixDGGS = WGS84_003,
wrap_antimeridian: bool = False,
line: LineSemantics | None = None,
) -> list[str] | None:
"""
Returns the list of cell indices touched by a shapely linestring or multilinestring
at the requested resolution: ``conversion.cells_from_linestring``, with None
where that function raises or finds nothing to trace. Removes internal sequences
of duplicate cells before returning result.
Returns None if the geom_type field in the input geometry is anything other than
'LineString' or 'MultiLineString'.
Returns None if the geometry is empty, or if it has no length.
Returns None if no cells match the geometry for some reason.
Returns None if the geometry is invalid in other ways, e.g. if a linestring contains
self intersecting segments.
A linestring's segments are straight in the input coordinate space
(shapely geometries are planar): planar rHEALPix coordinates if
`plane` = True, longitude-latitude coordinates otherwise -- so
longitude-latitude segments are plate carree lines, not geodesics,
and by default do not wrap around the antimeridian (a segment from
longitude 179 to -179 runs the long way around, through longitude 0
-- the literal planar reading). Splitting inputs at the antimeridian,
as GeoJSON's RFC 7946 prescribes for data producers, avoids the
ambiguity entirely; alternatively pass `wrap_antimeridian` = True to
trace segments spanning more than half a turn of longitude the short
way, across the antimeridian, which traces the same cells as
splitting them there. To trace a geodesic, densify it into short
segments first (e.g. with pyproj.Geod). See
RHEALPixDGGS.cells_from_line, which traces each segment exactly, for
the details.
EXAMPLES::
>>> from shapely import LineString
>>> line = LineString([[-176.260506, -43.738058], [-176.258807, -43.738379]])
>>> linetrace(line, res=9, plane=False)
['S001450634', 'S001450635']
"""
if _warn_if_malformed(
geometry, verbose, _malformed_lines, LINETRACE_GEOMETRY_WARNING
):
return None
return cells_from_linestring(geometry, res, plane, wrap_antimeridian, line, dggs)
# ======== Helper functions ======== #
def _rings_up_to(center: Cell, k: int) -> list[list[Cell]]:
"""
Return `[ring_0, ring_1, ..., ring_k]`, where `ring_0 == [center]` and
`ring_i` (`i` >= 1) is the list of cells at graph distance exactly `i`
from `center` -- the shortest number of edge/corner hops, via
`_ring_step_neighbors()` -- computed by growing the ring outward one
shell at a time.
Each ring's cells are visited in a stable order: each cell in the
previous ring is expanded via `_ring_step_neighbors()`'s fixed
clockwise order, in previous-ring order, keeping the first occurrence
of any cell reachable from more than one previous-ring cell. Cells
already seen in an earlier ring (tracked cumulatively, not just the
immediately preceding one, so this is a proper breadth-first search)
are skipped, so a ring near a genuine cube corner naturally comes out
with fewer cells than the usual 8*i for an interior ring, rather than
a duplicate or incorrect cell.
"""
rings = [[center]]
seen_suids = {center.suid}
for _ in range(k):
next_ring = []
seen_this_ring = set()
for cell in rings[-1]:
for neighbor in _ring_step_neighbors(cell):
if neighbor.suid in seen_suids or neighbor.suid in seen_this_ring:
continue
seen_this_ring.add(neighbor.suid)
next_ring.append(neighbor)
seen_suids.update(seen_this_ring)
rings.append(next_ring)
return rings
def _warn_if_malformed(
geometry: Any, verbose: bool, malformed: Callable[[Any], bool], fallback: str
) -> bool:
"""Whether `geometry` is malformed, warning why if `verbose`."""
if not malformed(geometry):
return False
if verbose:
message = is_valid_reason(geometry)
if not message or message == "Valid Geometry":
warn(fallback, stacklevel=3)
else:
warn(str.format("WARNING: {0}. Returning None.", message), stacklevel=3)
return True
def _malformed_geometry(geometry: Polygon | MultiPolygon) -> bool:
# Geometry has to have things in it
if geometry is None or geometry.is_empty:
return True
# Geometry needs to be of the correct type
if geometry.geom_type != "Polygon" and geometry.geom_type != "MultiPolygon":
return True
# This catches e.g. self intersecting hulls and holes, or overlapping polygons
if not geometry.is_valid:
return True
# Geometry has to have an area, i.e. not be collapsed to a line
return geometry.area == 0
def _malformed_lines(lines: LineString | MultiLineString) -> bool:
# There have to be lines
if lines is None or lines.is_empty:
return True
# Lines need to be of the correct type
if lines.geom_type != "LineString" and lines.geom_type != "MultiLineString":
return True
if not lines.is_valid:
return True
# Lines need to have a length, i.e. not be collapsed into points
return lines.length == 0