12 releases (7 breaking)

Uses new Rust 2021

0.8.0 Nov 24, 2021
0.7.0 Sep 5, 2021
0.6.3 Jul 31, 2021
0.0.13 Mar 25, 2021

#2 in #intersection

28 downloads per month
Used in 2 crates


3.5K SLoC

crates.io Documentation Workflow dependency status license

Lackadaisical 2d and 3d polylines for cgmath

Data structures and methods for polylines/segments in 2D and 3D space.

There are 3D and 2D implementations of:

  • LineString, a sequence of points, aka Polyline.
  • Line, a finite two-point struct (no rays).
  • Ramer–Douglas-Peucker and
  • Visvalingam-Whyatt line simplification algorithms.
  • Sampling of boostvoronoi parabolic arc curves.
  • Rudimentary functionality to save to .obj file

There are 2D implementations of:

  • LineString2 convex hull calculation (gift wrapping & Graham scan)
  • Aabb axis aligned bounding box.
  • Self intersection tests for line strings, or groups of lines O( n log n + i log n).
  • Convex hull containment test
  • Simple affine transformation (pan, zoom)

If you want to use this library in your cgmath project you add this to your Cargo.toml:

linestring = {version="0.8"}

Rust toolchains

This crate uses #![feature(map_first_last)] if compiled by +nightly. This is functionality is only emulated when run on +stable.

Demo GUI

Run the line simplification example with :

cargo run --example fltk_gui


  • Improve on error handling
  • Benchmark and optimize (add smallvec to simplify rdp?)
  • optimize Ramer–Douglas-Peucker
  • optimize Visvalingam-Whyatt
  • Stable overlapping co-linear line detection
  • Add subdivide
  • Use Point-by-value instead of &Point


~64K SLoC