1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
// plotters-conrod
//
// Conrod backend for Plotters
// Copyright: 2020, Valerian Saliou <valerian@valeriansaliou.name>
// License: MIT
use conrod_core::position::Scalar as ConrodScalar;
use num_traits::identities::{One, Zero};
type ShapeSplitterValue = ConrodScalar;
type ShapeSplitterPoint = [ShapeSplitterValue; 2];
pub(crate) struct ShapeSplitter {
last_point: ShapeSplitterPoint,
path_segments: Vec<[ShapeSplitterPoint; 2]>,
}
impl ShapeSplitter {
pub(crate) fn try_from(path: &[ShapeSplitterPoint]) -> Result<Self, ()> {
// Only proceed if we have enough points to form at least a triangle
if path.len() >= 3 {
// Map all unique segments for the simplified path
let mut path_segments = Vec::new();
for index in 0..(path.len() - 1) {
let (current_point, next_point) = (path[index], path[index + 1]);
path_segments.push([current_point, next_point]);
}
Ok(Self {
last_point: path[path.len() - 1],
path_segments,
})
} else {
Err(())
}
}
#[allow(clippy::float_cmp)]
pub(crate) fn collect(&mut self) -> Vec<Vec<ShapeSplitterPoint>> {
let (mut closed_shapes, mut current_shape_index) = (vec![Vec::new()], 0);
// Intersect each segment with all of its following segments, iteratively, and \
// create paths for closed shapes.
for index in 0..self.path_segments.len() {
let path_segment = &self.path_segments[index];
// Push opening (or current) point?
// Notice: check that previously pushed point does not match opening point, as in some \
// cases the last pushed intersection point would be equal to the opening point to \
// push there.
Self::append_point(&mut closed_shapes[current_shape_index], path_segment[0]);
for sibling_index in (index + 1)..self.path_segments.len() {
let sibling_path_segment = &self.path_segments[sibling_index];
// The lines are not directly connected? Proceed with intersection check.
if path_segment[1] != sibling_path_segment[0]
&& path_segment[0] != sibling_path_segment[1]
{
let intersection = Self::intersects(path_segment, sibling_path_segment);
// An intersection has been found, the current shape can be closed and yielded
if let Some(point_intersect) = intersection {
// Close current closed shape at this point (ensure we are not pushing an \
// intersection equal to the starting point right after it)
Self::append_point(
&mut closed_shapes[current_shape_index],
point_intersect,
);
// Start a new shape at this point (will be closed upon a future iteration)
closed_shapes.push(vec![point_intersect]);
current_shape_index += 1;
}
}
}
}
// Close the first shape with the last point from the original shape?
// Notice: points shall not be repeated, hence why there is a check that we are not \
// closing the shape with either its starting point, or already-there ending point.
if !closed_shapes.is_empty() {
Self::append_point(&mut closed_shapes[0], self.last_point);
}
closed_shapes
}
#[allow(clippy::many_single_char_names, clippy::float_cmp)]
fn intersects(
line: &[ShapeSplitterPoint; 2],
other: &[ShapeSplitterPoint; 2],
) -> Option<ShapeSplitterPoint> {
// Adapted from: https://github.com/ucarion/line_intersection/blob/master/src/lib.rs#L108
let p = line[0];
let q = other[0];
let r = [line[1][0] - line[0][0], line[1][1] - line[0][1]];
let s = [other[1][0] - other[0][0], other[1][1] - other[0][1]];
let r_cross_s = Self::point_cross(&r, &s);
let q_minus_p = [q[0] - p[0], q[1] - p[1]];
// Lines parallel? Ignore.
if r_cross_s == ShapeSplitterValue::zero() {
None
} else {
// Lines are not parallel, continue.
let t = Self::point_cross(&q_minus_p, &Self::point_divide(&s, r_cross_s));
let u = Self::point_cross(&q_minus_p, &Self::point_divide(&r, r_cross_s));
// Do the lines intersect in one point?
let t_in_range = ShapeSplitterValue::zero() <= t && t <= ShapeSplitterValue::one();
let u_in_range = ShapeSplitterValue::zero() <= u && u <= ShapeSplitterValue::one();
if t_in_range && u_in_range {
// Return intersection point coordinates (rounded as to avoid floating point errors)
Some([(p[0] + t * r[0]).round(), (p[1] + t * r[1]).round()])
} else {
None
}
}
}
#[inline(always)]
fn point_cross(point: &ShapeSplitterPoint, other: &ShapeSplitterPoint) -> ShapeSplitterValue {
point[0] * other[1] - point[1] * other[0]
}
#[inline(always)]
fn point_divide(point: &ShapeSplitterPoint, other: ShapeSplitterValue) -> ShapeSplitterPoint {
[point[0] / other, point[1] / other]
}
#[inline(always)]
#[allow(clippy::float_cmp)]
fn append_point(container: &mut Vec<ShapeSplitterPoint>, point: ShapeSplitterPoint) {
let container_size = container.len();
if container_size == 0 || (container[container_size - 1] != point && container[0] != point)
{
container.push(point);
}
}
}