line_clipping/
lib.rs

1#![no_std]
2//! A Rust crate implementing line and polygon clipping algorithms. See the
3//! [documentation](https://docs.rs/line_clipping) for more information. The choice of algorithms is
4//! based on the following article which contains a good summary of the options:
5//!
6//! Matthes D, Drakopoulos V. [Line Clipping in 2D: Overview, Techniques and
7//! Algorithms](https://pmc.ncbi.nlm.nih.gov/articles/PMC9605407/). J Imaging. 2022 Oct
8//! 17;8(10):286. doi: 10.3390/jimaging8100286. PMID: 36286380; PMCID: PMC9605407.
9//!
10//! Supports:
11//!
12//! - [x] [Cohen-Sutherland](crate::cohen_sutherland)
13//! - [x] [Sutherland-Hodgman](https://docs.rs/line-clipping/latest/line_clipping/sutherland_hodgman/)
14//!   polygon clipping algorithm
15//!
16//! TODO
17//!
18//! - [ ] Cyrus-Beck
19//! - [ ] Liang-Barsky
20//! - [ ] Nicholl-Lee-Nicholl
21//! - [ ] More comprehensive testing
22//!
23//! # Installation
24//!
25//! ```shell
26//! cargo add line-clipping
27//! ```
28//!
29//! # Minimum supported Rust version
30//!
31//! The crate is built with Rust 1.85 to match the 2024 edition. The MSRV may increase in a
32//! future minor release, but will be noted in the changelog.
33//!
34//! # Usage
35//!
36//! ```rust
37//! use line_clipping::cohen_sutherland::clip_line;
38//! use line_clipping::{LineSegment, Point, Window};
39//!
40//! let line = LineSegment::new(Point::new(-10.0, -10.0), Point::new(20.0, 20.0));
41//! let window = Window::new(0.0, 10.0, 0.0, 10.0);
42//! let clipped_line = clip_line(line, window);
43//! ```
44//!
45//! # License
46//!
47//! Copyright (c) Josh McKinney
48//!
49//! This project is licensed under either of
50//!
51//! - MIT license ([LICENSE-MIT](LICENSE-MIT) or <http://opensource.org/licenses/MIT>)
52//! - Apache License, Version 2.0 ([LICENSE-APACHE](LICENSE-APACHE) or <http://www.apache.org/licenses/LICENSE-2.0>)
53//!
54//! at your option.
55//!
56//! # Contribution
57//!
58//! Contributions are welcome! Please open an issue or submit a pull request.
59//!
60//! Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in
61//! the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without
62//! any additional terms or conditions.
63pub mod cohen_sutherland;
64pub mod sutherland_hodgman;
65
66extern crate alloc;
67use alloc::vec::Vec;
68
69/// A point in 2D space.
70#[derive(Debug, Clone, Copy, PartialEq)]
71pub struct Point {
72    /// The x coordinate of the point.
73    pub x: f64,
74
75    /// The y coordinate of the point.
76    pub y: f64,
77}
78
79impl Point {
80    /// A point at the origin (0.0, 0.0).
81    pub const ORIGIN: Self = Self { x: 0.0, y: 0.0 };
82
83    /// Creates a new point.
84    #[must_use]
85    pub const fn new(x: f64, y: f64) -> Self {
86        Self { x, y }
87    }
88}
89
90/// A line segment in 2D space.
91#[derive(Debug, Clone, Copy, PartialEq)]
92pub struct LineSegment {
93    /// The first point of the line segment.
94    pub p1: Point,
95
96    /// The second point of the line segment.
97    pub p2: Point,
98}
99
100impl LineSegment {
101    /// Creates a new line segment.
102    #[must_use]
103    pub const fn new(p1: Point, p2: Point) -> Self {
104        Self { p1, p2 }
105    }
106}
107
108/// A polygon represented by an ordered sequence of boundary vertices.
109///
110/// Vertices must occur consecutively around the polygon boundary, either clockwise or
111/// counter-clockwise. The final edge back to the first vertex is implicit, so the first vertex
112/// should not be repeated at the end.
113///
114/// A polygon can be concave or self-intersecting, but some algorithms may return degenerate
115/// boundaries for those inputs. This type represents one boundary only; it cannot represent holes
116/// or multiple disconnected polygons.
117#[derive(Debug, Clone, PartialEq)]
118pub struct Polygon {
119    /// Vertices of the polygon.
120    pub vertices: Vec<Point>,
121}
122
123impl Polygon {
124    /// Creates a polygon by copying an ordered slice of boundary vertices.
125    #[must_use]
126    pub fn new(vertices: &[Point]) -> Self {
127        Self {
128            vertices: vertices.to_vec(),
129        }
130    }
131}
132
133impl From<Vec<Point>> for Polygon {
134    fn from(vertices: Vec<Point>) -> Self {
135        Self { vertices }
136    }
137}
138
139/// A rectangular region to clip geometry against.
140#[derive(Debug, Clone, Copy)]
141pub struct Window {
142    /// The minimum x coordinate of the window.
143    pub x_min: f64,
144
145    /// The maximum x coordinate of the window.
146    pub x_max: f64,
147
148    /// The minimum y coordinate of the window.
149    pub y_min: f64,
150
151    /// The maximum y coordinate of the window.
152    pub y_max: f64,
153}
154
155impl Window {
156    /// Creates a new window.
157    #[must_use]
158    pub const fn new(x_min: f64, x_max: f64, y_min: f64, y_max: f64) -> Self {
159        Self {
160            x_min,
161            x_max,
162            y_min,
163            y_max,
164        }
165    }
166}
line_clipping/lib.rs

line_clipping/
lib.rs
