#geometry #centerline #median-axis

centerline

Simple library for finding centerlines of 2D closed geometry

15 releases (7 breaking)

Uses new Rust 2021

new 0.7.0 Nov 24, 2021
0.6.1 Sep 6, 2021
0.5.1 Jul 11, 2021
0.0.3 Mar 25, 2021

#62 in Math

Download history 28/week @ 2021-08-10 4/week @ 2021-08-17 2/week @ 2021-08-24 19/week @ 2021-08-31 23/week @ 2021-09-07 9/week @ 2021-09-14 4/week @ 2021-09-21 31/week @ 2021-09-28 14/week @ 2021-10-05 39/week @ 2021-10-12 32/week @ 2021-10-19 23/week @ 2021-10-26 17/week @ 2021-11-02 28/week @ 2021-11-09 11/week @ 2021-11-16 26/week @ 2021-11-23

86 downloads per month
Used in toxicblend

AGPL-3.0

505KB
2.5K SLoC

crates.io Documentation Workflow dependency status license

This simple library tries to find centerlines, aka the median-axis, of closed 2D geometries.

It is focused on letter like shapes, i.e. vertex loops with potential enclosed islands of loops. Loops directly connected to other loops does not work at the moment.

It uses a segmented voronoi diagram as a base, then it filters out the 'spiky' bits (green) by comparing the angle between the edge (green), and the input geometry (red) that created it. If the angle is close to 90°, it will be ignored. Note that the result (blue) technically is not a true centerline after the spikes has been filtered out, but it makes for much cleaner tool-paths etc. It also performs a line simplification on the resulting center-line.

unfiltered filtered

let segments = ...same as boost voronoi segments...
let mut centerline = Centerline::<i32, f32, i64, f64>::with_segments(segments);
centerline.build_voronoi()?;
// the cosine value of the angle limit. 
let cos_angle:f32 = 0.38;
// the RDP simplification distance
let centerline_simplification:f32 = 0.1;

let _= centerline.calculate_centerline(cos_angle, centerline_simplification, None)?;
println!(
   "Result: lines:{}, line_strings:{}",
   centerline.lines.as_ref().map_or(0,|x|x.len()),
   centerline.line_strings.as_ref().map_or(0,|x|x.len())
);

Gui example

cargo run --example fltk_gui --features=obj-rs --release

The example only displays 2D, but the generated center-line is actually 3D line segments.
The Z coordinate is the distance between the 2D center-line, and the geometry that created it.

The example GUI takes .obj files as input. The .obj file needs to be 2D in some axis aligned plane (one of the coordinates needs to be zero). Also make sure there are no intersecting outer edges.

Rust requirement

The crate is only tested on 1.56 and above (2021 edition).

Will automatically use #![feature(hash_drain_filter)] and #![feature(map_first_last)] if run on rust +nightly.

Todo

  • Sometimes a shape registers as 'outside' it's convex hull
  • Add opengl to fltk_gui so that the 3D aspect of the center-line can be visualized.

Dependencies

~5.5MB
~104K SLoC

pŞa