Skip to main content

plotters_ternary/series/
polygon.rs

1use std::fmt;
2
3use plotters::backend::DrawingBackend;
4use plotters::element::{Drawable, PointCollection};
5use plotters::style::ShapeStyle;
6use plotters_backend::{BackendCoord, DrawingErrorKind};
7
8use crate::coord::{
9    Normalization, TernaryCartesian, TernaryGeometry, TernaryPoint, TernaryViewport, Tolerance,
10};
11
12/// A polygon in semantic ternary-composition coordinates.
13///
14/// Open and explicitly closed input sequences are both accepted.  Valid simple
15/// concave polygons are supported; self-intersecting polygons are rejected so
16/// rendering never depends on a backend-specific fill rule.
17pub struct TernaryPolygon<I> {
18    points: I,
19    fill: Option<ShapeStyle>,
20    border: Option<ShapeStyle>,
21    normalization: Normalization,
22    tolerance: Tolerance,
23}
24
25impl<I> TernaryPolygon<I> {
26    /// Construct a strict unit-sum polygon with no fill or border.
27    pub fn new(points: I) -> Self {
28        Self {
29            points,
30            fill: None,
31            border: None,
32            normalization: Normalization::RequireUnitSum,
33            tolerance: Tolerance::default(),
34        }
35    }
36
37    /// Fill the final clipped polygon with an independent Plotters style.
38    pub fn fill_style<S: Into<ShapeStyle>>(mut self, style: S) -> Self {
39        self.fill = Some(style.into());
40        self
41    }
42
43    /// Draw one independent border around the final clipped polygon.
44    pub fn border_style<S: Into<ShapeStyle>>(mut self, style: S) -> Self {
45        self.border = Some(style.into());
46        self
47    }
48
49    /// Select explicit composition validation or normalisation.
50    pub const fn normalization(mut self, normalization: Normalization) -> Self {
51        self.normalization = normalization;
52        self
53    }
54
55    /// Select the numerical tolerance used for preparation and clipping.
56    pub const fn tolerance(mut self, tolerance: Tolerance) -> Self {
57        self.tolerance = tolerance;
58        self
59    }
60
61    pub(crate) fn into_parts(
62        self,
63    ) -> (
64        I,
65        Option<ShapeStyle>,
66        Option<ShapeStyle>,
67        Normalization,
68        Tolerance,
69    ) {
70        (
71            self.points,
72            self.fill,
73            self.border,
74            self.normalization,
75            self.tolerance,
76        )
77    }
78}
79
80/// A backend-neutral polygon after validation, projection, and viewport clipping.
81#[derive(Clone, Debug, PartialEq)]
82pub struct PreparedPolygon {
83    vertices: Vec<TernaryCartesian>,
84}
85
86impl PreparedPolygon {
87    /// Return the final open vertex loop. The closing edge is implicit.
88    pub fn vertices(&self) -> &[TernaryCartesian] {
89        &self.vertices
90    }
91
92    /// Return whether clipping removed all positive-area geometry.
93    pub const fn is_empty(&self) -> bool {
94        self.vertices.is_empty()
95    }
96}
97
98/// Failures specific to polygon validation and preparation.
99#[derive(Clone, Debug, PartialEq)]
100#[non_exhaustive]
101pub enum PolygonError {
102    /// Fewer than three distinct vertices remain after tolerance cleanup.
103    TooFewVertices { distinct: usize },
104    /// A source composition could not be validated or projected.
105    InvalidPoint {
106        index: usize,
107        source: crate::coord::Error,
108    },
109    /// The source loop has effectively zero signed area.
110    Degenerate,
111    /// Two non-adjacent source edges intersect or touch.
112    SelfIntersection {
113        first_edge: usize,
114        second_edge: usize,
115    },
116}
117
118impl fmt::Display for PolygonError {
119    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
120        match self {
121            Self::TooFewVertices { distinct } => write!(
122                f,
123                "polygon needs at least three distinct vertices; found {distinct}"
124            ),
125            Self::InvalidPoint { index, source } => write!(
126                f,
127                "invalid ternary polygon point at index {index}: {source}"
128            ),
129            Self::Degenerate => write!(f, "polygon has effectively zero area"),
130            Self::SelfIntersection {
131                first_edge,
132                second_edge,
133            } => write!(f, "polygon edges {first_edge} and {second_edge} intersect"),
134        }
135    }
136}
137
138impl std::error::Error for PolygonError {
139    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
140        match self {
141            Self::InvalidPoint { source, .. } => Some(source),
142            Self::TooFewVertices { .. } | Self::Degenerate | Self::SelfIntersection { .. } => None,
143        }
144    }
145}
146
147/// Validate, project, and mathematically clip a simple ternary polygon.
148pub fn prepare_polygon<I, P>(
149    points: I,
150    geometry: TernaryGeometry,
151    viewport: TernaryViewport,
152    normalization: Normalization,
153    tolerance: Tolerance,
154) -> Result<PreparedPolygon, PolygonError>
155where
156    I: IntoIterator<Item = P>,
157    P: Into<TernaryPoint>,
158{
159    let mut projected = Vec::new();
160    for (index, point) in points.into_iter().enumerate() {
161        let point = geometry
162            .project(point.into(), normalization, tolerance)
163            .map_err(|source| PolygonError::InvalidPoint { index, source })?;
164        push_distinct(&mut projected, point, tolerance);
165    }
166    if projected.len() > 1 && same_point(projected[0], *projected.last().unwrap(), tolerance) {
167        projected.pop();
168    }
169    validate_source_polygon(&projected, tolerance)?;
170
171    let clipped = clip_polygon_to_viewport(projected, viewport, tolerance);
172    if clipped.len() < 3 || signed_area(&clipped).abs() <= tolerance.absolute {
173        return Ok(PreparedPolygon {
174            vertices: Vec::new(),
175        });
176    }
177    Ok(PreparedPolygon { vertices: clipped })
178}
179
180fn validate_source_polygon(
181    vertices: &[TernaryCartesian],
182    tolerance: Tolerance,
183) -> Result<(), PolygonError> {
184    if vertices.len() < 3 {
185        return Err(PolygonError::TooFewVertices {
186            distinct: vertices.len(),
187        });
188    }
189    for first in 0..vertices.len() {
190        let first_end = (first + 1) % vertices.len();
191        for second in (first + 1)..vertices.len() {
192            let second_end = (second + 1) % vertices.len();
193            if first == second || first_end == second || second_end == first {
194                continue;
195            }
196            if segments_intersect(
197                vertices[first],
198                vertices[first_end],
199                vertices[second],
200                vertices[second_end],
201                tolerance,
202            ) {
203                return Err(PolygonError::SelfIntersection {
204                    first_edge: first,
205                    second_edge: second,
206                });
207            }
208        }
209    }
210    if signed_area(vertices).abs() <= tolerance.absolute {
211        return Err(PolygonError::Degenerate);
212    }
213    Ok(())
214}
215
216fn clip_polygon_to_viewport(
217    mut vertices: Vec<TernaryCartesian>,
218    viewport: TernaryViewport,
219    tolerance: Tolerance,
220) -> Vec<TernaryCartesian> {
221    for boundary in [
222        Boundary::Left(viewport.x_min()),
223        Boundary::Right(viewport.x_max()),
224        Boundary::Bottom(viewport.y_min()),
225        Boundary::Top(viewport.y_max()),
226    ] {
227        vertices = clip_against_boundary(&vertices, boundary, tolerance);
228        if vertices.is_empty() {
229            break;
230        }
231    }
232    vertices
233}
234
235#[derive(Clone, Copy)]
236enum Boundary {
237    Left(f64),
238    Right(f64),
239    Bottom(f64),
240    Top(f64),
241}
242
243impl Boundary {
244    fn is_inside(self, point: TernaryCartesian, tolerance: Tolerance) -> bool {
245        match self {
246            Self::Left(value) => point.x >= value - tolerance.absolute,
247            Self::Right(value) => point.x <= value + tolerance.absolute,
248            Self::Bottom(value) => point.y >= value - tolerance.absolute,
249            Self::Top(value) => point.y <= value + tolerance.absolute,
250        }
251    }
252    fn intersection(self, from: TernaryCartesian, to: TernaryCartesian) -> TernaryCartesian {
253        match self {
254            Self::Left(x) | Self::Right(x) => {
255                let t = (x - from.x) / (to.x - from.x);
256                TernaryCartesian::new(x, from.y + t * (to.y - from.y))
257            }
258            Self::Bottom(y) | Self::Top(y) => {
259                let t = (y - from.y) / (to.y - from.y);
260                TernaryCartesian::new(from.x + t * (to.x - from.x), y)
261            }
262        }
263    }
264}
265
266fn clip_against_boundary(
267    vertices: &[TernaryCartesian],
268    boundary: Boundary,
269    tolerance: Tolerance,
270) -> Vec<TernaryCartesian> {
271    let mut output = Vec::new();
272    let Some(mut previous) = vertices.last().copied() else {
273        return output;
274    };
275    let mut previous_inside = boundary.is_inside(previous, tolerance);
276    for current in vertices.iter().copied() {
277        let current_inside = boundary.is_inside(current, tolerance);
278        if current_inside != previous_inside {
279            push_distinct(
280                &mut output,
281                boundary.intersection(previous, current),
282                tolerance,
283            );
284        }
285        if current_inside {
286            push_distinct(&mut output, current, tolerance);
287        }
288        previous = current;
289        previous_inside = current_inside;
290    }
291    if output.len() > 1 && same_point(output[0], *output.last().unwrap(), tolerance) {
292        output.pop();
293    }
294    output
295}
296
297fn signed_area(vertices: &[TernaryCartesian]) -> f64 {
298    vertices
299        .iter()
300        .zip(vertices.iter().cycle().skip(1))
301        .take(vertices.len())
302        .map(|(a, b)| a.x * b.y - a.y * b.x)
303        .sum::<f64>()
304        * 0.5
305}
306
307fn push_distinct(
308    points: &mut Vec<TernaryCartesian>,
309    point: TernaryCartesian,
310    tolerance: Tolerance,
311) {
312    if points
313        .last()
314        .is_none_or(|previous| !same_point(*previous, point, tolerance))
315    {
316        points.push(point);
317    }
318}
319
320fn same_point(left: TernaryCartesian, right: TernaryCartesian, tolerance: Tolerance) -> bool {
321    tolerance.is_close(left.x, right.x) && tolerance.is_close(left.y, right.y)
322}
323
324fn cross(a: TernaryCartesian, b: TernaryCartesian, c: TernaryCartesian) -> f64 {
325    (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)
326}
327
328fn on_segment(
329    a: TernaryCartesian,
330    b: TernaryCartesian,
331    point: TernaryCartesian,
332    tolerance: Tolerance,
333) -> bool {
334    cross(a, b, point).abs() <= tolerance.absolute
335        && point.x >= a.x.min(b.x) - tolerance.absolute
336        && point.x <= a.x.max(b.x) + tolerance.absolute
337        && point.y >= a.y.min(b.y) - tolerance.absolute
338        && point.y <= a.y.max(b.y) + tolerance.absolute
339}
340
341fn segments_intersect(
342    a: TernaryCartesian,
343    b: TernaryCartesian,
344    c: TernaryCartesian,
345    d: TernaryCartesian,
346    tolerance: Tolerance,
347) -> bool {
348    let ab_c = cross(a, b, c);
349    let ab_d = cross(a, b, d);
350    let cd_a = cross(c, d, a);
351    let cd_b = cross(c, d, b);
352    if (ab_c > tolerance.absolute && ab_d < -tolerance.absolute
353        || ab_c < -tolerance.absolute && ab_d > tolerance.absolute)
354        && (cd_a > tolerance.absolute && cd_b < -tolerance.absolute
355            || cd_a < -tolerance.absolute && cd_b > tolerance.absolute)
356    {
357        return true;
358    }
359    on_segment(a, b, c, tolerance)
360        || on_segment(a, b, d, tolerance)
361        || on_segment(c, d, a, tolerance)
362        || on_segment(c, d, b, tolerance)
363}
364
365/// An owned Plotters element that fills first and draws one final polygon border.
366pub(crate) struct PolygonElement<Coord> {
367    vertices: Vec<Coord>,
368    fill: Option<ShapeStyle>,
369    border: Option<ShapeStyle>,
370}
371
372impl<Coord> PolygonElement<Coord> {
373    pub(crate) fn new(
374        vertices: Vec<Coord>,
375        fill: Option<ShapeStyle>,
376        border: Option<ShapeStyle>,
377    ) -> Self {
378        Self {
379            vertices,
380            fill,
381            border,
382        }
383    }
384}
385
386impl<'a, Coord> PointCollection<'a, Coord> for &'a PolygonElement<Coord> {
387    type Point = &'a Coord;
388    type IntoIter = std::slice::Iter<'a, Coord>;
389    fn point_iter(self) -> Self::IntoIter {
390        self.vertices.iter()
391    }
392}
393
394impl<Coord, DB: DrawingBackend> Drawable<DB> for PolygonElement<Coord> {
395    fn draw<I: Iterator<Item = BackendCoord>>(
396        &self,
397        points: I,
398        backend: &mut DB,
399        _: (u32, u32),
400    ) -> Result<(), DrawingErrorKind<DB::ErrorType>> {
401        let coordinates: Vec<_> = points.collect();
402        if coordinates.len() < 3 {
403            return Ok(());
404        }
405        if let Some(style) = self.fill {
406            backend.fill_polygon(coordinates.iter().copied(), &style)?;
407        }
408        if let Some(style) = self.border {
409            let mut path = coordinates;
410            path.push(path[0]);
411            backend.draw_path(path, &style)?;
412        }
413        Ok(())
414    }
415}
416
417#[cfg(test)]
418mod tests {
419    use super::*;
420    use crate::coord::{Component, TriangleOrientation, VertexOrder};
421
422    fn point(a: f64, b: f64, c: f64) -> TernaryPoint {
423        TernaryPoint::new(a, b, c)
424    }
425    fn prepared(
426        points: impl IntoIterator<Item = TernaryPoint>,
427        viewport: TernaryViewport,
428    ) -> Result<PreparedPolygon, PolygonError> {
429        prepare_polygon(
430            points,
431            TernaryGeometry::default(),
432            viewport,
433            Normalization::RequireUnitSum,
434            Tolerance::default(),
435        )
436    }
437
438    #[test]
439    fn accepts_open_closed_and_simple_concave_source_loops() {
440        let viewport = TernaryViewport::full(TernaryGeometry::default());
441        let open = prepared(
442            [
443                point(0.2, 0.7, 0.1),
444                point(0.2, 0.1, 0.7),
445                point(0.7, 0.1, 0.2),
446            ],
447            viewport,
448        )
449        .unwrap();
450        let closed = prepared(
451            [
452                point(0.2, 0.7, 0.1),
453                point(0.2, 0.1, 0.7),
454                point(0.7, 0.1, 0.2),
455                point(0.2, 0.7, 0.1),
456            ],
457            viewport,
458        )
459        .unwrap();
460        assert_eq!(open, closed);
461        let concave = prepared(
462            [
463                point(0.1, 0.8, 0.1),
464                point(0.1, 0.1, 0.8),
465                point(0.35, 0.325, 0.325),
466                point(0.6, 0.1, 0.3),
467                point(0.6, 0.3, 0.1),
468            ],
469            viewport,
470        )
471        .unwrap();
472        assert_eq!(concave.vertices().len(), 5);
473    }
474
475    #[test]
476    fn rejects_degenerate_and_self_intersecting_loops() {
477        let viewport = TernaryViewport::full(TernaryGeometry::default());
478        assert!(matches!(
479            prepared(
480                [
481                    point(0.5, 0.5, 0.0),
482                    point(0.4, 0.6, 0.0),
483                    point(0.3, 0.7, 0.0)
484                ],
485                viewport
486            ),
487            Err(PolygonError::Degenerate)
488        ));
489        assert!(matches!(
490            prepared(
491                [
492                    point(0.2, 0.7, 0.1),
493                    point(0.6, 0.1, 0.3),
494                    point(0.2, 0.1, 0.7),
495                    point(0.6, 0.3, 0.1),
496                ],
497                viewport
498            ),
499            Err(PolygonError::SelfIntersection { .. })
500        ));
501    }
502
503    #[test]
504    fn clips_enclosing_and_external_polygons_without_backend_clamping() {
505        let viewport = TernaryViewport::new(0.35, 0.65, 0.15, 0.45).unwrap();
506        let enclosed = prepared(
507            [
508                point(1.0, 0.0, 0.0),
509                point(0.0, 1.0, 0.0),
510                point(0.0, 0.0, 1.0),
511            ],
512            viewport,
513        )
514        .unwrap();
515        assert_eq!(enclosed.vertices().len(), 4);
516        assert!(
517            enclosed
518                .vertices()
519                .iter()
520                .all(|point| viewport.contains(*point, Tolerance::default()).unwrap())
521        );
522        let outside = prepared(
523            [
524                point(0.0, 1.0, 0.0),
525                point(0.0, 0.9, 0.1),
526                point(0.1, 0.9, 0.0),
527            ],
528            viewport,
529        )
530        .unwrap();
531        assert!(outside.is_empty());
532    }
533
534    #[test]
535    fn clipping_handles_each_side_adjacent_opposite_and_boundary_cases() {
536        let viewport = TernaryViewport::new(0.0, 1.0, 0.0, 1.0).unwrap();
537        let tolerance = Tolerance::default();
538        let cases = [
539            vec![
540                cart(-0.2, 0.2),
541                cart(0.4, 0.2),
542                cart(0.4, 0.6),
543                cart(-0.2, 0.6),
544            ],
545            vec![
546                cart(0.6, 0.2),
547                cart(1.2, 0.2),
548                cart(1.2, 0.6),
549                cart(0.6, 0.6),
550            ],
551            vec![
552                cart(0.2, -0.2),
553                cart(0.8, -0.2),
554                cart(0.8, 0.3),
555                cart(0.2, 0.3),
556            ],
557            vec![
558                cart(0.2, 0.7),
559                cart(0.8, 0.7),
560                cart(0.8, 1.2),
561                cart(0.2, 1.2),
562            ],
563            vec![
564                cart(-0.2, 0.7),
565                cart(0.4, 0.7),
566                cart(0.4, 1.2),
567                cart(-0.2, 1.2),
568            ],
569            vec![
570                cart(-0.2, 0.35),
571                cart(1.2, 0.35),
572                cart(1.2, 0.55),
573                cart(-0.2, 0.55),
574            ],
575            vec![
576                cart(0.0, 0.2),
577                cart(0.5, 0.2),
578                cart(0.5, 0.7),
579                cart(0.0, 0.7),
580            ],
581        ];
582        for subject in cases {
583            let clipped = clip_polygon_to_viewport(subject, viewport, tolerance);
584            assert!(clipped.len() >= 3);
585            assert!(
586                clipped
587                    .iter()
588                    .all(|point| viewport.contains(*point, tolerance).unwrap())
589            );
590            assert!(
591                clipped
592                    .windows(2)
593                    .all(|pair| !same_point(pair[0], pair[1], tolerance))
594            );
595        }
596
597        let corner_tangent = clip_polygon_to_viewport(
598            vec![cart(1.0, 1.0), cart(1.3, 1.1), cart(1.1, 1.3)],
599            viewport,
600            tolerance,
601        );
602        assert!(
603            corner_tangent.len() < 3 || signed_area(&corner_tangent).abs() <= tolerance.absolute
604        );
605    }
606
607    #[test]
608    fn semantic_input_remains_valid_under_custom_order_and_downward_orientation() {
609        let points = [
610            point(0.65, 0.20, 0.15),
611            point(0.30, 0.50, 0.20),
612            point(0.20, 0.20, 0.60),
613        ];
614        let order = VertexOrder::new(Component::C, Component::A, Component::B).unwrap();
615        for orientation in [TriangleOrientation::Up, TriangleOrientation::Down] {
616            let geometry = TernaryGeometry::new(orientation, order);
617            let prepared = prepare_polygon(
618                points,
619                geometry,
620                TernaryViewport::full(geometry),
621                Normalization::RequireUnitSum,
622                Tolerance::default(),
623            )
624            .unwrap();
625            assert_eq!(prepared.vertices().len(), 3);
626            for vertex in prepared.vertices() {
627                let recovered = geometry.unproject(*vertex, Tolerance::default()).unwrap();
628                assert!(points.iter().any(|source| {
629                    source
630                        .as_array()
631                        .into_iter()
632                        .zip(recovered.as_array())
633                        .all(|(expected, actual)| Tolerance::default().is_close(expected, actual))
634                }));
635            }
636        }
637    }
638
639    const fn cart(x: f64, y: f64) -> TernaryCartesian {
640        TernaryCartesian::new(x, y)
641    }
642}