lair.geo.points_along_line#

lair.geo.points_along_line(multiline, spacing, resolution_factor=None, decimals=None)[source]#

Generate points spaced along a line or a network of lines.

Every pair of points is at least spacing apart (Euclidean distance, in the units of the coordinates), across the whole network, including between disconnected lines. Distances within float rounding of spacing count as spacing, so points on a straight line come out evenly spaced.

The algorithm works as follows:

  1. Topology fixing: union_all splits the lines where they cross, so every intersection becomes a node, then line_merge stitches simple paths back together.

  2. Graph construction: each line is segmentized into steps of at most spacing * resolution_factor, and the vertices become the nodes of a graph whose edges follow the lines. Node coordinates are rounded to decimals places, which snaps microscopic gaps between lines together.

  3. Point placement: each connected component is walked breadth-first from an endpoint (any node for a closed loop), visiting each node once. The walk carries the last point placed behind it as its “origin”. A node at least spacing from its origin gets a point, which becomes the new origin. A node closer than spacing to any other placed point is skipped, and the walk keeps going, still measuring from the old origin.

  4. Global spacing: placed points are kept in a grid of square cells, so checking a node against every placed point only looks at nearby cells. Runtime is close to linear in the number of graph nodes.

Parameters:
  • multiline (shapely.LineString | shapely.MultiLineString) – The line, or network of lines.

  • spacing (float) – The minimum Euclidean distance between generated points.

  • resolution_factor (float, optional) – Graph step size as a fraction of spacing, by default 0.1. Smaller values make a denser graph, which follows curves more closely and places points closer to exactly spacing apart, but is slower.

  • decimals (int, optional) – Number of decimal places node coordinates are rounded to. By default two places finer than the step size (spacing * resolution_factor), and at least 5.

Returns:

list[shapely.Point] – Points along the network, in the order they were placed, each at least spacing from every other.

Raises:

ValueError – If spacing is not positive.

Return type:

list[Point]

See also

haversine

A distance in km, where this one is in the coordinates’ units.

Examples

>>> from shapely import LineString
>>> from lair.geo import points_along_line
>>> points = points_along_line(LineString([(0, 0), (10, 0)]), 2.5)
>>> [(p.x, p.y) for p in points]
[(0.0, 0.0), (2.5, 0.0), (5.0, 0.0), (7.5, 0.0), (10.0, 0.0)]