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

use super::ray_cast::*;
use super::super::path::*;
use super::super::graph_path::*;
use super::super::super::super::geo::*;

//
// This uses a simple ray casting algorithm to perform the addition
// 
// Basic idea is to cast a ray at an edge which is currently uncategorised, and mark the edges it crosses as interior or
// exterior depending on whether or not we consider it as crossing into or out of the final shape.
//

impl<Point: Coordinate+Coordinate2D> GraphPath<Point, PathLabel> {
    ///
    /// Given a labelled graph path, marks exterior edges by adding `PathSource::Path1` and `PathSource::Path2`
    ///
    /// This is used to implement the `path_add()` arithmetic function, and is generally called after using `collide()`
    /// to combine the two input paths.
    ///
    pub fn set_exterior_by_adding(&mut self) {
        // Use an even-odd winding rule (all edges are considered 'external')
        self.set_edge_kinds_by_ray_casting(|path_crossings| (path_crossings[0]&1) != 0 || (path_crossings[1]&1) != 0);
    }

    ///
    /// Given a path that intersects itself (ie, only contains SourcePath::Path1), discovers the 'true' exterior edge.
    ///
    pub fn set_exterior_by_removing_interior_points(&mut self) {
        // All points inside the path are considered 'interior' (non-zero winding rule)
        self.set_edge_kinds_by_ray_casting(|path_crossings| path_crossings[0] != 0 || path_crossings[1] != 0);
    }
}

///
/// Generates the path formed by adding two sets of paths
///
/// Each of the two paths passed into this function is assumed not to overlap themselves. IE, this does not perform self-intersection 
/// on either `path1` or `path2`. This provides both a performance optimisation and finer control over how self-intersecting paths are
/// handled. See `path_remove_interior_points()` and `path_remove_overlapped_points()` for a way to eliminate overlaps.
/// 
/// The input vectors represent the external edges of the path to add (a single BezierPath cannot have any holes in it, so a set of them
/// effectively represents a path intended to be rendered with an even-odd winding rule)
///
pub fn path_add<POut>(path1: &Vec<impl BezierPath<Point=POut::Point>>, path2: &Vec<impl BezierPath<Point=POut::Point>>, accuracy: f64) -> Vec<POut>
where
    POut:           BezierPathFactory,
    POut::Point:    Coordinate+Coordinate2D,
{
    // If either path is empty, short-circuit by returning the other
    if path1.is_empty() {
        return path2.iter()
            .map(|path| POut::from_path(path))
            .collect();
    } else if path2.is_empty() {
        return path1.iter()
            .map(|path| POut::from_path(path))
            .collect();
    }

    // Create the graph path from the source side
    let mut merged_path = GraphPath::new();
    merged_path         = merged_path.merge(GraphPath::from_merged_paths(path1.iter().map(|path| (path, PathLabel(0)))));

    // Collide with the target side to generate a full path
    merged_path         = merged_path.collide(GraphPath::from_merged_paths(path2.iter().map(|path| (path, PathLabel(1)))), accuracy);
    merged_path.round(accuracy);

    // Set the exterior edges using the 'add' algorithm
    merged_path.set_exterior_by_adding();
    merged_path.heal_exterior_gaps();

    // Produce the final result
    merged_path.exterior_paths()
}

///
/// Generates the path formed by removing any interior points from an existing path. This considers only the outermost edges of the 
/// path to be the true edges, so if there are sub-paths inside an outer path, they will be removed.
///
/// This is a strict version of the 'non-zero' winding rule. It's useful for things like a path that was generated from a brush stroke
/// and might self-overlap: this can be passed a drawing of a loop made by overlapping the ends and it will output two non-overlapping 
/// subpaths.
///
/// See `path_remove_overlapped_points()` for a version that considers all edges within the path to be exterior edges.
///
pub fn path_remove_interior_points<P1: BezierPath, POut: BezierPathFactory>(path: &Vec<P1>, accuracy: f64) -> Vec<POut>
where
    P1::Point:  Coordinate+Coordinate2D,
    POut:       BezierPathFactory<Point=P1::Point>,
{
    // Create the graph path from the source side
    let mut merged_path = GraphPath::new();
    merged_path         = merged_path.merge(GraphPath::from_merged_paths(path.iter().map(|path| (path, PathLabel(0)))));

    // Collide the path with itself to find the intersections
    merged_path.self_collide(accuracy);
    merged_path.round(accuracy);

    // Set the exterior edges by considering all points inside an edge as 'interior'
    merged_path.set_exterior_by_removing_interior_points();
    merged_path.heal_exterior_gaps();

    // Produce the final result
    let result = merged_path.exterior_paths();
    test_assert!(result.len() != 0 || path.is_empty());

    result
}

///
/// Generates the path formed by removing any interior points from an existing path. This considers all edges to be exterior edges
/// and will remove those that are obscured by another part of the path.
///
/// This works like the 'even-odd' winding rule.
///
/// If a path self-intersects, this will leave a hole behind. See `path_remove_interior_points()` for a way to remove the interior
/// parts of a path so that all points inside the boundary are filled. This function is useful for cleaning up paths from other
/// sources, then the other arithmetic operations can be used to reshape the resulting path.
///
/// Note that calling 'subtract' is a more reliable way to cut a hole in an existing path than relying on a winding rule, as
/// winding rules presuppose you can tell if a subpath is inside or outside of an existing path.
///
pub fn path_remove_overlapped_points<P1: BezierPath, POut: BezierPathFactory>(path: &Vec<P1>, accuracy: f64) -> Vec<POut>
where
    P1::Point:  Coordinate+Coordinate2D,
    POut:       BezierPathFactory<Point=P1::Point>,
{
    // Create the graph path from the source side
    let mut merged_path = GraphPath::new();
    merged_path         = merged_path.merge(GraphPath::from_merged_paths(path.iter().map(|path| (path, PathLabel(0)))));

    // Collide the path with itself to find the intersections
    merged_path.self_collide(accuracy);
    merged_path.round(accuracy);

    // Set the exterior edges using the 'add' algorithm
    merged_path.set_exterior_by_adding();
    merged_path.heal_exterior_gaps();

    // Produce the final result
    let result = merged_path.exterior_paths();
    test_assert!(result.len() != 0 || path.is_empty());

    result
}