Line Processing

Purpose and Scope

This document covers line processing operations in Turf.js, which manipulate LineString geometries through splitting, segmentation, intersection detection, and chunking. These operations enable dividing lines at specific points, finding where lines cross, extracting individual segments, and partitioning lines into measured chunks.

For boolean spatial relationship tests involving lines (e.g., booleanParallel, booleanCrosses), see Boolean Predicates. For polygon manipulation operations, see Polygon Operations. For distance calculations and coordinate transformations along lines, see Distance and Bearing.

Module Overview

The line processing category includes six primary modules that operate on LineString and MultiLineString geometries:

Module	Package	Primary Function	Key Dependencies
Line Split	@turf/line-split	Splits a LineString by another feature	@turf/geojson-rbush, @turf/line-intersect, @turf/line-segment
Line Intersect	@turf/line-intersect	Finds intersection points between lines	sweepline-intersections
Line Segment	@turf/line-segment	Creates segments from line coordinates	@turf/meta
Line Chunk	@turf/line-chunk	Divides lines into distance-based chunks	@turf/length, @turf/line-slice-along
Line Overlap	@turf/line-overlap	Finds overlapping segments	@turf/line-segment
Line Offset	@turf/line-offset	Offsets lines perpendicular to direction	@turf/meta

Line Processing Module Dependencies

100%

Line Split Operation

Overview

The lineSplit function divides a LineString into multiple segments at intersection points with a splitter feature. The splitter can be a Point, MultiPoint, LineString, MultiLineString, Polygon, or MultiPolygon.

Entry Point: packages/turf-line-split/index.js29-62

Input Validation and Type Handling

100%

The function performs type checking to ensure the line parameter is a LineString and rejects FeatureCollections and GeometryCollections as splitters packages/turf-line-split/index.js33-40 The splitter is truncated to 7 decimal places to avoid floating-point precision issues in the spatial index packages/turf-line-split/index.js44

For non-Point splitters, the function first uses lineIntersect to find all intersection points, then splits the line at those points packages/turf-line-split/index.js55-60

Split Algorithm with Single Point

100%

The single point split algorithm uses an R-tree spatial index (rbush) for efficient segment lookup. It follows these steps:

1. Endpoint Handling: Returns the original line unchanged if the split point exactly matches either endpoint packages/turf-line-split/index.js126-130
2. Segmentation: Converts the line into individual two-vertex segments using lineSegment packages/turf-line-split/index.js134
3. Spatial Indexing: Loads segments into an rbush tree for fast spatial queries packages/turf-line-split/index.js133-135
4. Proximity Search: Searches for segments within the point's bounding box packages/turf-line-split/index.js138
5. Closest Match: Uses nearestPointOnLine to find the closest segment when multiple candidates exist packages/turf-line-split/index.js144
6. Coordinate Accumulation: Uses featureReduce to iterate segments, accumulating coordinates until reaching the split segment packages/turf-line-split/index.js148-170
7. Split Construction: Creates two LineStrings at the intersection point, avoiding coordinate duplication packages/turf-line-split/index.js159-161

Split Algorithm with Multiple Points

100%

The multi-point split algorithm maintains a dynamic spatial index as it processes each point sequentially:

1. Initialization: Creates an empty rbush tree to track intermediate line segments packages/turf-line-split/index.js74
2. First Point: Splits the original line and loads results into the tree with unique IDs packages/turf-line-split/index.js78-84
3. Subsequent Points: For each remaining point:
   • Searches the tree for candidate lines within the point's bbox packages/turf-line-split/index.js88
   • Finds the closest line using nearestPointOnLine packages/turf-line-split/index.js92
   • Removes the closest line from both results array and tree packages/turf-line-split/index.js96-99
   • Splits the closest line into two new segments packages/turf-line-split/index.js102
   • Inserts both new segments back into results and tree packages/turf-line-split/index.js103-105

The algorithm assigns unique IDs to features for efficient filtering and removal packages/turf-line-split/index.js78-80

Helper Functions

The lineSplit module includes utility functions:

findClosestFeature(point, lines) packages/turf-line-split/index.js186-202

• Selects the closest feature from a set of candidates
• Uses nearestPointOnLine to calculate distance from point to each line
• Returns the feature with minimum distance
• Handles single-feature collections as optimization

pointsEquals(pt1, pt2) packages/turf-line-split/index.js212-214

• Compares two coordinate arrays for exact equality
• Used to detect endpoint matches and avoid duplicate coordinates
• Performs simple coordinate comparison: pt1[0] === pt2[0] && pt1[1] === pt2[1]

Line Intersect Operation

Overview

The @turf/line-intersect module finds all intersection points between two line or polygon features using the Bentley-Ottmann sweepline algorithm via the sweepline-intersections library.

Key Features:

• Handles LineString, MultiLineString, Polygon, and MultiPolygon inputs
• Returns a FeatureCollection of intersection Points
• Uses efficient sweepline algorithm for large geometries
• Optional ignoreSelfIntersections parameter for single-feature analysis

Dependencies: packages/turf-line-intersect/package.json71-76

• @turf/helpers - GeoJSON construction
• sweepline-intersections - Bentley-Ottmann algorithm implementation

The sweepline algorithm achieves O((n+k) log n) time complexity where n is the number of segments and k is the number of intersections, making it efficient for complex geometries.

Line Segment Operation

Overview

The @turf/line-segment module converts any line or polygon geometry into a FeatureCollection of two-vertex LineString segments. Each segment represents a single edge in the original geometry.

Functionality:

• Processes LineString, MultiLineString, Polygon, MultiPolygon, and mixed FeatureCollections
• Extracts all coordinate pairs as individual LineString features
• Preserves original feature properties on segment features
• Uses @turf/meta iteration utilities for geometry traversal

Use Cases:

• Preprocessing for spatial indexing (as in line-split)
• Analyzing individual edges of complex geometries
• Input for algorithms requiring segment-level processing

Dependencies: packages/turf-line-segment/package.json64-70

• @turf/helpers - LineString creation
• @turf/meta - Coordinate iteration with segmentEach
• @turf/invariant - Type validation

The module uses segmentEach from @turf/meta to efficiently iterate over all coordinate pairs in nested geometries.

Line Chunk Operation

Overview

The @turf/line-chunk module divides a LineString into equal-length segments based on a specified distance. Unlike line-segment which splits at every vertex, line-chunk creates segments of consistent measured length.

Algorithm:

1. Calculate total line length using @turf/length
2. Determine number of chunks based on segment length
3. Use @turf/line-slice-along to extract each chunk at measured distances
4. Return FeatureCollection of length-based segments

Parameters:

• Input: LineString or MultiLineString
• segmentLength: Desired length of each chunk
• units: Distance units (miles, kilometers, meters, etc.)
• reverse: Optional flag to chunk from end to start

Dependencies: packages/turf-line-chunk/package.json73-79

• @turf/length - Total distance calculation
• @turf/line-slice-along - Extract line portion between distances
• @turf/meta - Geometry iteration

Spatial Indexing with RBush

Line processing modules use rbush for efficient spatial queries. The R-tree data structure provides O(log n) search performance for finding geometries within a bounding box.

Integration Pattern

100%

@turf/geojson-rbush Wrapper:

• Provides GeoJSON-specific interface to rbush
• Automatically calculates bounding boxes from geometries
• Returns GeoJSON FeatureCollection from queries
• Supports load, insert, remove, and search operations

Usage in Line Split: packages/turf-line-split/index.js1

import { geojsonRbush as rbush } from "@turf/geojson-rbush";

The spatial index enables efficient filtering of candidate segments:

1. Load Phase: Insert all line segments into tree packages/turf-line-split/index.js84
2. Query Phase: Search for segments intersecting splitter's bbox packages/turf-line-split/index.js88
3. Dynamic Updates: Remove and re-insert modified segments packages/turf-line-split/index.js99-104

Edge Cases and Precision Handling

Line processing operations must handle several geometric edge cases:

Endpoint Matching

When a split point exactly matches a line endpoint, the line should not be split packages/turf-line-split/index.js126-130:

if (
  pointsEquals(startPoint, getCoord(splitter)) ||
  pointsEquals(endPoint, getCoord(splitter))
)
  return featureCollection([line]);

This prevents creating degenerate single-vertex LineStrings.

Coordinate Duplication Prevention

When splitting at a vertex that matches a split point, avoid duplicating coordinates in the output packages/turf-line-split/index.js159-161:

// Don't duplicate splitter coordinate (Issue #688)
if (pointsEquals(splitterCoords, currentCoords))
  return [splitterCoords];

Floating-Point Precision

The splitter geometry is truncated to 7 decimal places before spatial indexing to avoid precision-related issues in rbush packages/turf-line-split/index.js42-44:

// remove excessive decimals from splitter
// to avoid possible approximation issues in rbush
var truncatedSplitter = truncate(splitter, { precision: 7 });

This addresses issues reported in packages/turf-line-split/test.ts153-191 where minute coordinate differences caused incorrect spatial queries.

Empty Result Handling

When no segments are found within the search bbox, return the original line unchanged packages/turf-line-split/index.js141 This occurs when the split point is not actually on the line.

Test Coverage and Known Issues

Test Organization

Test fixtures are organized in input/output pairs:

• Input: packages/turf-line-split/test/in/ - GeoJSON with line and splitter features
• Output: packages/turf-line-split/test/out/ - Expected split results with colorized segments

Test cases cover:

• Basic scenarios: Point, MultiPoint, LineString, Polygon splitters
• Edge cases: Endpoints, vertices, precision issues
• Complex geometries: MultiLineString, MultiPolygon, polygons with holes
• Historical bugs: Issues #688, #852, #1075, #1232, #2288

Historical Issues

Issue #688 - Coordinate Duplication packages/turf-line-split/test.ts125-151

• Problem: Split points on vertices created 3-vertex lines instead of 2-vertex segments
• Solution: Skip duplicate coordinate when split point matches segment endpoint

Issue #852 - Floating-Point Precision packages/turf-line-split/test.ts153-191

• Problem: Coordinates with many decimal places caused rbush query failures
• Solution: Truncate splitter to 7 decimal precision before indexing

Issue #1075 - Multiple Points on Line packages/turf-line-split/test.ts206-218

• Problem: Sequential splitting with multiple points failed
• Solution: Dynamic spatial index updates with proper ID management

Issue #1232 - Complex Polygon Splitting packages/turf-line-split/test.ts220-305

• Problem: Lines not split correctly at polygon boundary intersections
• Solution: Improved intersection point calculation with ignoreSelfIntersections flag

Issue #2288 - Wavy Lines packages/turf-line-split/test.ts307-336

• Problem: Lines with many vertices not split at polygon intersections
• Solution: Enhanced handling of multi-segment intersection scenarios

Performance Characteristics

Operation	Time Complexity	Space Complexity	Notes
Line Split (single point)	O(n log n)	O(n)	n = number of segments; dominated by rbush operations
Line Split (k points)	O(k·n log n)	O(n)	Sequential processing of k points
Line Intersect	O((n+i) log n)	O(n)	n = segments, i = intersections; Bentley-Ottmann
Line Segment	O(n)	O(n)	n = number of coordinate pairs
Line Chunk	O(n·c)	O(c)	n = segments, c = number of chunks

Optimization Techniques:

• Spatial Indexing: RBush reduces candidate segment searches from O(n) to O(log n)
• Early Termination: Endpoint checks avoid unnecessary processing packages/turf-line-split/index.js126-130
• Single-Feature Optimization: Skip distance calculation when only one candidate exists packages/turf-line-split/index.js189
• Sweepline Algorithm: Line intersections use efficient Bentley-Ottmann instead of brute-force O(n²)

Related Modules

Line processing operations integrate with other Turf.js modules:

Measurement Dependencies:

• @turf/length - Total line length for chunking operations
• @turf/distance - Point-to-point distance calculations
• @turf/nearest-point-on-line - Find closest point on line to given coordinate

Transformation Operations:

• @turf/line-slice - Extract line portion between two points
• @turf/line-slice-along - Extract line portion between two distances
• @turf/truncate - Reduce coordinate precision

Analysis Operations:

• @turf/line-overlap - Find shared segments between two lines
• @turf/point-to-line-distance - Shortest distance from point to line
• @turf/nearest-point-to-line - Closest point feature to a line

For coordinate processing and transformations, see Coordinate Processing. For clustering and spatial analysis using line-based features, see Spatial Analysis.