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
12pub 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 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 pub fn fill_style<S: Into<ShapeStyle>>(mut self, style: S) -> Self {
39 self.fill = Some(style.into());
40 self
41 }
42
43 pub fn border_style<S: Into<ShapeStyle>>(mut self, style: S) -> Self {
45 self.border = Some(style.into());
46 self
47 }
48
49 pub const fn normalization(mut self, normalization: Normalization) -> Self {
51 self.normalization = normalization;
52 self
53 }
54
55 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#[derive(Clone, Debug, PartialEq)]
82pub struct PreparedPolygon {
83 vertices: Vec<TernaryCartesian>,
84}
85
86impl PreparedPolygon {
87 pub fn vertices(&self) -> &[TernaryCartesian] {
89 &self.vertices
90 }
91
92 pub const fn is_empty(&self) -> bool {
94 self.vertices.is_empty()
95 }
96}
97
98#[derive(Clone, Debug, PartialEq)]
100#[non_exhaustive]
101pub enum PolygonError {
102 TooFewVertices { distinct: usize },
104 InvalidPoint {
106 index: usize,
107 source: crate::coord::Error,
108 },
109 Degenerate,
111 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
147pub 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
365pub(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}