clipper2_rust/
clipper.rs

1/*******************************************************************************
2* Author    :  Angus Johnson (original C++), Rust port                        *
3* Date      :  2025                                                           *
4* Website   :  https://www.angusj.com                                         *
5* Copyright :  Angus Johnson 2010-2025                                        *
6* Purpose   :  Simple public API for the Clipper Library                      *
7* License   :  https://www.boost.org/LICENSE_1_0.txt                          *
8*******************************************************************************/
9
10//! Public API convenience functions for the Clipper2 library.
11//!
12//! Direct port from clipper.h. These functions provide a simple interface
13//! for common polygon operations: boolean operations, path offsetting,
14//! rect clipping, path simplification, and various geometric utilities.
15
16use crate::core::{
17    check_precision_range, constants, cross_product_three_points, distance_sqr, is_collinear,
18    perpendic_dist_from_line_sqrd, point_in_polygon, scale_path, scale_paths, scale_rect, sqr,
19    FromF64, Path, Path64, PathD, Paths, Paths64, PathsD, Point, Point64, PointInPolygonResult,
20    Rect64, RectD, ToF64,
21};
22use crate::engine::ClipType;
23use crate::engine_public::{Clipper64, ClipperD, PolyTree64, PolyTreeD};
24use crate::offset::{ClipperOffset, EndType, JoinType};
25use crate::rectclip::{RectClip64, RectClipLines64};
26use crate::FillRule;
27use num_traits::Num;
28
29// ============================================================================
30// Boolean Operations (Paths64)
31// ============================================================================
32
33/// Perform a boolean operation on Paths64.
34/// Direct port from clipper.h BooleanOp (Paths64 overload).
35pub fn boolean_op_64(
36    clip_type: ClipType,
37    fill_rule: FillRule,
38    subjects: &Paths64,
39    clips: &Paths64,
40) -> Paths64 {
41    let mut result = Paths64::new();
42    let mut clipper = Clipper64::new();
43    clipper.add_subject(subjects);
44    clipper.add_clip(clips);
45    clipper.execute(clip_type, fill_rule, &mut result, None);
46    result
47}
48
49/// Perform a boolean operation on Paths64 with PolyTree64 output.
50/// Direct port from clipper.h BooleanOp (PolyTree64 overload).
51pub fn boolean_op_tree_64(
52    clip_type: ClipType,
53    fill_rule: FillRule,
54    subjects: &Paths64,
55    clips: &Paths64,
56    solution: &mut PolyTree64,
57) {
58    let mut sol_open = Paths64::new();
59    let mut clipper = Clipper64::new();
60    clipper.add_subject(subjects);
61    clipper.add_clip(clips);
62    clipper.execute_tree(clip_type, fill_rule, solution, &mut sol_open);
63}
64
65/// Perform a boolean operation on PathsD.
66/// Direct port from clipper.h BooleanOp (PathsD overload).
67pub fn boolean_op_d(
68    clip_type: ClipType,
69    fill_rule: FillRule,
70    subjects: &PathsD,
71    clips: &PathsD,
72    precision: i32,
73) -> PathsD {
74    let mut error_code = 0;
75    let mut prec = precision;
76    check_precision_range(&mut prec, &mut error_code);
77    let mut result = PathsD::new();
78    if error_code != 0 {
79        return result;
80    }
81    let mut clipper = ClipperD::new(precision);
82    clipper.add_subject(subjects);
83    clipper.add_clip(clips);
84    clipper.execute(clip_type, fill_rule, &mut result, None);
85    result
86}
87
88/// Perform a boolean operation on PathsD with PolyTreeD output.
89/// Direct port from clipper.h BooleanOp (PolyTreeD overload).
90pub fn boolean_op_tree_d(
91    clip_type: ClipType,
92    fill_rule: FillRule,
93    subjects: &PathsD,
94    clips: &PathsD,
95    polytree: &mut PolyTreeD,
96    precision: i32,
97) {
98    polytree.clear();
99    let mut error_code = 0;
100    let mut prec = precision;
101    check_precision_range(&mut prec, &mut error_code);
102    if error_code != 0 {
103        return;
104    }
105    let mut clipper = ClipperD::new(precision);
106    clipper.add_subject(subjects);
107    clipper.add_clip(clips);
108    let mut open_paths = PathsD::new();
109    clipper.execute_tree(clip_type, fill_rule, polytree, &mut open_paths);
110}
111
112// ============================================================================
113// Intersect
114// ============================================================================
115
116/// Compute the intersection of subjects and clips (Paths64).
117/// Direct port from clipper.h Intersect.
118pub fn intersect_64(subjects: &Paths64, clips: &Paths64, fill_rule: FillRule) -> Paths64 {
119    boolean_op_64(ClipType::Intersection, fill_rule, subjects, clips)
120}
121
122/// Compute the intersection of subjects and clips (PathsD).
123/// Direct port from clipper.h Intersect (PathsD overload).
124pub fn intersect_d(
125    subjects: &PathsD,
126    clips: &PathsD,
127    fill_rule: FillRule,
128    precision: i32,
129) -> PathsD {
130    boolean_op_d(
131        ClipType::Intersection,
132        fill_rule,
133        subjects,
134        clips,
135        precision,
136    )
137}
138
139// ============================================================================
140// Union
141// ============================================================================
142
143/// Compute the union of subjects and clips (Paths64).
144/// Direct port from clipper.h Union.
145pub fn union_64(subjects: &Paths64, clips: &Paths64, fill_rule: FillRule) -> Paths64 {
146    boolean_op_64(ClipType::Union, fill_rule, subjects, clips)
147}
148
149/// Compute the union of subjects and clips (PathsD).
150/// Direct port from clipper.h Union (PathsD overload).
151pub fn union_d(subjects: &PathsD, clips: &PathsD, fill_rule: FillRule, precision: i32) -> PathsD {
152    boolean_op_d(ClipType::Union, fill_rule, subjects, clips, precision)
153}
154
155/// Compute the union of subjects only (no clips) (Paths64).
156/// Direct port from clipper.h Union (subjects-only overload).
157pub fn union_subjects_64(subjects: &Paths64, fill_rule: FillRule) -> Paths64 {
158    let mut result = Paths64::new();
159    let mut clipper = Clipper64::new();
160    clipper.add_subject(subjects);
161    clipper.execute(ClipType::Union, fill_rule, &mut result, None);
162    result
163}
164
165/// Compute the union of subjects only (no clips) (PathsD).
166/// Direct port from clipper.h Union (subjects-only PathsD overload).
167pub fn union_subjects_d(subjects: &PathsD, fill_rule: FillRule, precision: i32) -> PathsD {
168    let mut result = PathsD::new();
169    let mut error_code = 0;
170    let mut prec = precision;
171    check_precision_range(&mut prec, &mut error_code);
172    if error_code != 0 {
173        return result;
174    }
175    let mut clipper = ClipperD::new(precision);
176    clipper.add_subject(subjects);
177    clipper.execute(ClipType::Union, fill_rule, &mut result, None);
178    result
179}
180
181// ============================================================================
182// Difference
183// ============================================================================
184
185/// Compute the difference of subjects minus clips (Paths64).
186/// Direct port from clipper.h Difference.
187pub fn difference_64(subjects: &Paths64, clips: &Paths64, fill_rule: FillRule) -> Paths64 {
188    boolean_op_64(ClipType::Difference, fill_rule, subjects, clips)
189}
190
191/// Compute the difference of subjects minus clips (PathsD).
192/// Direct port from clipper.h Difference (PathsD overload).
193pub fn difference_d(
194    subjects: &PathsD,
195    clips: &PathsD,
196    fill_rule: FillRule,
197    precision: i32,
198) -> PathsD {
199    boolean_op_d(ClipType::Difference, fill_rule, subjects, clips, precision)
200}
201
202// ============================================================================
203// Xor
204// ============================================================================
205
206/// Compute the symmetric difference (Xor) of subjects and clips (Paths64).
207/// Direct port from clipper.h Xor.
208pub fn xor_64(subjects: &Paths64, clips: &Paths64, fill_rule: FillRule) -> Paths64 {
209    boolean_op_64(ClipType::Xor, fill_rule, subjects, clips)
210}
211
212/// Compute the symmetric difference (Xor) of subjects and clips (PathsD).
213/// Direct port from clipper.h Xor (PathsD overload).
214pub fn xor_d(subjects: &PathsD, clips: &PathsD, fill_rule: FillRule, precision: i32) -> PathsD {
215    boolean_op_d(ClipType::Xor, fill_rule, subjects, clips, precision)
216}
217
218// ============================================================================
219// InflatePaths
220// ============================================================================
221
222/// Inflate (or deflate) paths by a delta amount (Paths64).
223/// Direct port from clipper.h InflatePaths.
224pub fn inflate_paths_64(
225    paths: &Paths64,
226    delta: f64,
227    jt: JoinType,
228    et: EndType,
229    miter_limit: f64,
230    arc_tolerance: f64,
231) -> Paths64 {
232    if delta == 0.0 {
233        return paths.clone();
234    }
235    let mut clip_offset = ClipperOffset::new(miter_limit, arc_tolerance, false, false);
236    clip_offset.add_paths(paths, jt, et);
237    let mut solution = Paths64::new();
238    clip_offset.execute(delta, &mut solution);
239    solution
240}
241
242/// Inflate (or deflate) paths by a delta amount (PathsD).
243/// Direct port from clipper.h InflatePaths (PathsD overload).
244pub fn inflate_paths_d(
245    paths: &PathsD,
246    delta: f64,
247    jt: JoinType,
248    et: EndType,
249    miter_limit: f64,
250    precision: i32,
251    arc_tolerance: f64,
252) -> PathsD {
253    let mut error_code = 0;
254    let mut prec = precision;
255    check_precision_range(&mut prec, &mut error_code);
256    if delta == 0.0 {
257        return paths.clone();
258    }
259    if error_code != 0 {
260        return PathsD::new();
261    }
262    let scale = 10f64.powi(precision);
263    let mut clip_offset = ClipperOffset::new(miter_limit, arc_tolerance * scale, false, false);
264    let scaled_paths: Paths64 = scale_paths(paths, scale, scale, &mut error_code);
265    if error_code != 0 {
266        return PathsD::new();
267    }
268    clip_offset.add_paths(&scaled_paths, jt, et);
269    let mut solution = Paths64::new();
270    clip_offset.execute(delta * scale, &mut solution);
271    scale_paths(&solution, 1.0 / scale, 1.0 / scale, &mut error_code)
272}
273
274// ============================================================================
275// TranslatePath / TranslatePaths
276// ============================================================================
277
278/// Translate all points in a path by (dx, dy).
279/// Direct port from clipper.h TranslatePath.
280pub fn translate_path<T>(path: &Path<T>, dx: T, dy: T) -> Path<T>
281where
282    T: Copy + std::ops::Add<Output = T>,
283{
284    let mut result = Vec::with_capacity(path.len());
285    for pt in path {
286        result.push(Point {
287            x: pt.x + dx,
288            y: pt.y + dy,
289        });
290    }
291    result
292}
293
294/// Translate all paths by (dx, dy).
295/// Direct port from clipper.h TranslatePaths.
296pub fn translate_paths<T>(paths: &Paths<T>, dx: T, dy: T) -> Paths<T>
297where
298    T: Copy + std::ops::Add<Output = T>,
299{
300    let mut result = Vec::with_capacity(paths.len());
301    for path in paths {
302        result.push(translate_path(path, dx, dy));
303    }
304    result
305}
306
307// ============================================================================
308// RectClip
309// ============================================================================
310
311/// Clip paths to a rectangle (Paths64).
312/// Direct port from clipper.h RectClip.
313pub fn rect_clip_64(rect: &Rect64, paths: &Paths64) -> Paths64 {
314    if rect.is_empty() || paths.is_empty() {
315        return Paths64::new();
316    }
317    let mut rc = RectClip64::new(*rect);
318    rc.execute(paths)
319}
320
321/// Clip a single path to a rectangle (Paths64 output).
322/// Direct port from clipper.h RectClip (single path overload).
323pub fn rect_clip_path_64(rect: &Rect64, path: &Path64) -> Paths64 {
324    if rect.is_empty() || path.is_empty() {
325        return Paths64::new();
326    }
327    let mut rc = RectClip64::new(*rect);
328    rc.execute(&vec![path.clone()])
329}
330
331/// Clip paths to a rectangle (PathsD).
332/// Direct port from clipper.h RectClip (PathsD overload).
333pub fn rect_clip_d(rect: &RectD, paths: &PathsD, precision: i32) -> PathsD {
334    if rect.is_empty() || paths.is_empty() {
335        return PathsD::new();
336    }
337    let mut error_code = 0;
338    let mut prec = precision;
339    check_precision_range(&mut prec, &mut error_code);
340    if error_code != 0 {
341        return PathsD::new();
342    }
343    let scale = 10f64.powi(precision);
344    let r: Rect64 = scale_rect(rect, scale);
345    let mut rc = RectClip64::new(r);
346    let pp: Paths64 = scale_paths(paths, scale, scale, &mut error_code);
347    if error_code != 0 {
348        return PathsD::new();
349    }
350    let result = rc.execute(&pp);
351    scale_paths(&result, 1.0 / scale, 1.0 / scale, &mut error_code)
352}
353
354/// Clip a single path to a rectangle (PathsD).
355/// Direct port from clipper.h RectClip (single PathD overload).
356pub fn rect_clip_path_d(rect: &RectD, path: &PathD, precision: i32) -> PathsD {
357    rect_clip_d(rect, &vec![path.clone()], precision)
358}
359
360// ============================================================================
361// RectClipLines
362// ============================================================================
363
364/// Clip open lines to a rectangle (Paths64).
365/// Direct port from clipper.h RectClipLines.
366pub fn rect_clip_lines_64(rect: &Rect64, lines: &Paths64) -> Paths64 {
367    if rect.is_empty() || lines.is_empty() {
368        return Paths64::new();
369    }
370    let mut rcl = RectClipLines64::new(*rect);
371    rcl.execute(lines)
372}
373
374/// Clip a single open line to a rectangle (Paths64 output).
375/// Direct port from clipper.h RectClipLines (single path overload).
376pub fn rect_clip_line_64(rect: &Rect64, line: &Path64) -> Paths64 {
377    rect_clip_lines_64(rect, &vec![line.clone()])
378}
379
380/// Clip open lines to a rectangle (PathsD).
381/// Direct port from clipper.h RectClipLines (PathsD overload).
382pub fn rect_clip_lines_d(rect: &RectD, lines: &PathsD, precision: i32) -> PathsD {
383    if rect.is_empty() || lines.is_empty() {
384        return PathsD::new();
385    }
386    let mut error_code = 0;
387    let mut prec = precision;
388    check_precision_range(&mut prec, &mut error_code);
389    if error_code != 0 {
390        return PathsD::new();
391    }
392    let scale = 10f64.powi(precision);
393    let r: Rect64 = scale_rect(rect, scale);
394    let mut rcl = RectClipLines64::new(r);
395    let p: Paths64 = scale_paths(lines, scale, scale, &mut error_code);
396    if error_code != 0 {
397        return PathsD::new();
398    }
399    let result = rcl.execute(&p);
400    scale_paths(&result, 1.0 / scale, 1.0 / scale, &mut error_code)
401}
402
403/// Clip a single open line to a rectangle (PathsD).
404/// Direct port from clipper.h RectClipLines (single PathD overload).
405pub fn rect_clip_line_d(rect: &RectD, line: &PathD, precision: i32) -> PathsD {
406    rect_clip_lines_d(rect, &vec![line.clone()], precision)
407}
408
409// ============================================================================
410// PolyTree conversion
411// ============================================================================
412
413/// Helper: recursively collect paths from a PolyPath64 node.
414fn poly_path_to_paths64(tree: &PolyTree64, node_idx: usize, paths: &mut Paths64) {
415    let polygon = tree.nodes[node_idx].polygon().clone();
416    if !polygon.is_empty() {
417        paths.push(polygon);
418    }
419    for &child_idx in tree.nodes[node_idx].children() {
420        poly_path_to_paths64(tree, child_idx, paths);
421    }
422}
423
424/// Helper: recursively collect paths from a PolyPathD node.
425fn poly_path_to_paths_d(tree: &PolyTreeD, node_idx: usize, paths: &mut PathsD) {
426    let polygon = tree.nodes[node_idx].polygon().clone();
427    if !polygon.is_empty() {
428        paths.push(polygon);
429    }
430    for &child_idx in tree.nodes[node_idx].children() {
431        poly_path_to_paths_d(tree, child_idx, paths);
432    }
433}
434
435/// Convert a PolyTree64 to a flat list of Paths64.
436/// Direct port from clipper.h PolyTreeToPaths64.
437pub fn poly_tree_to_paths64(polytree: &PolyTree64) -> Paths64 {
438    let mut result = Paths64::new();
439    let root = &polytree.nodes[0];
440    for &child_idx in root.children() {
441        poly_path_to_paths64(polytree, child_idx, &mut result);
442    }
443    result
444}
445
446/// Convert a PolyTreeD to a flat list of PathsD.
447/// Direct port from clipper.h PolyTreeToPathsD.
448pub fn poly_tree_to_paths_d(polytree: &PolyTreeD) -> PathsD {
449    let mut result = PathsD::new();
450    let root = &polytree.nodes[0];
451    for &child_idx in root.children() {
452        poly_path_to_paths_d(polytree, child_idx, &mut result);
453    }
454    result
455}
456
457/// Check that all children in a PolyTree64 are fully contained by their parents.
458/// Direct port from clipper.h CheckPolytreeFullyContainsChildren.
459pub fn check_polytree_fully_contains_children(polytree: &PolyTree64) -> bool {
460    let root = &polytree.nodes[0];
461    for &child_idx in root.children() {
462        if polytree.nodes[child_idx].count() > 0
463            && !poly_path64_contains_children(polytree, child_idx)
464        {
465            return false;
466        }
467    }
468    true
469}
470
471/// Helper: check if a PolyPath64 node's children are all contained within it.
472/// Direct port from clipper.h details::PolyPath64ContainsChildren.
473fn poly_path64_contains_children(tree: &PolyTree64, node_idx: usize) -> bool {
474    let parent_polygon = tree.nodes[node_idx].polygon();
475    for &child_idx in tree.nodes[node_idx].children() {
476        let child_polygon = tree.nodes[child_idx].polygon();
477        // Return false if this child isn't fully contained by its parent.
478        // Checking for a single vertex outside is a bit too crude since
479        // it doesn't account for rounding errors. It's better to check
480        // for consecutive vertices found outside the parent's polygon.
481        let mut outside_cnt: i32 = 0;
482        for pt in child_polygon {
483            let result = point_in_polygon(*pt, parent_polygon);
484            if result == PointInPolygonResult::IsInside {
485                outside_cnt -= 1;
486            } else if result == PointInPolygonResult::IsOutside {
487                outside_cnt += 1;
488            }
489            if outside_cnt > 1 {
490                return false;
491            } else if outside_cnt < -1 {
492                break;
493            }
494        }
495
496        // Now check any nested children too
497        if tree.nodes[child_idx].count() > 0 && !poly_path64_contains_children(tree, child_idx) {
498            return false;
499        }
500    }
501    true
502}
503
504// ============================================================================
505// MakePath
506// ============================================================================
507
508/// Create a Path64 from a flat slice of coordinate pairs [x0, y0, x1, y1, ...].
509/// Direct port from clipper.h MakePath.
510pub fn make_path64(coords: &[i64]) -> Path64 {
511    let size = coords.len() - coords.len() % 2;
512    let mut result = Path64::with_capacity(size / 2);
513    let mut i = 0;
514    while i < size {
515        result.push(Point64::new(coords[i], coords[i + 1]));
516        i += 2;
517    }
518    result
519}
520
521/// Create a PathD from a flat slice of coordinate pairs [x0, y0, x1, y1, ...].
522/// Direct port from clipper.h MakePathD.
523pub fn make_path_d(coords: &[f64]) -> PathD {
524    let size = coords.len() - coords.len() % 2;
525    let mut result = PathD::with_capacity(size / 2);
526    let mut i = 0;
527    while i < size {
528        result.push(Point::<f64>::new(coords[i], coords[i + 1]));
529        i += 2;
530    }
531    result
532}
533
534// ============================================================================
535// TrimCollinear
536// ============================================================================
537
538/// Remove collinear points from a Path64.
539/// Direct port from clipper.h TrimCollinear.
540pub fn trim_collinear_64(p: &Path64, is_open_path: bool) -> Path64 {
541    let len = p.len();
542    if len < 3 {
543        if !is_open_path || len < 2 || p[0] == p[1] {
544            return Path64::new();
545        } else {
546            return p.clone();
547        }
548    }
549
550    let mut dst = Path64::with_capacity(len);
551    let mut src_idx: usize = 0;
552    let mut stop = len - 1;
553
554    if !is_open_path {
555        while src_idx != stop && is_collinear(p[stop], p[src_idx], p[src_idx + 1]) {
556            src_idx += 1;
557        }
558        while src_idx != stop && is_collinear(p[stop - 1], p[stop], p[src_idx]) {
559            stop -= 1;
560        }
561        if src_idx == stop {
562            return Path64::new();
563        }
564    }
565
566    let mut prev_idx = src_idx;
567    dst.push(p[prev_idx]);
568    src_idx += 1;
569
570    while src_idx < stop {
571        if !is_collinear(p[prev_idx], p[src_idx], p[src_idx + 1]) {
572            prev_idx = src_idx;
573            dst.push(p[prev_idx]);
574        }
575        src_idx += 1;
576    }
577
578    if is_open_path || !is_collinear(p[prev_idx], p[stop], dst[0]) {
579        dst.push(p[stop]);
580    } else {
581        while dst.len() > 2 && is_collinear(dst[dst.len() - 1], dst[dst.len() - 2], dst[0]) {
582            dst.pop();
583        }
584        if dst.len() < 3 {
585            return Path64::new();
586        }
587    }
588    dst
589}
590
591/// Remove collinear points from a PathD (scales to integer for precision).
592/// Direct port from clipper.h TrimCollinear (PathD overload).
593pub fn trim_collinear_d(path: &PathD, precision: i32, is_open_path: bool) -> PathD {
594    let mut error_code = 0;
595    let mut prec = precision;
596    check_precision_range(&mut prec, &mut error_code);
597    if error_code != 0 {
598        return PathD::new();
599    }
600    let scale = 10f64.powi(precision);
601    let p: Path64 = scale_path(path, scale, scale, &mut error_code);
602    if error_code != 0 {
603        return PathD::new();
604    }
605    let p = trim_collinear_64(&p, is_open_path);
606    scale_path(&p, 1.0 / scale, 1.0 / scale, &mut error_code)
607}
608
609// ============================================================================
610// Distance / Length
611// ============================================================================
612
613/// Compute the distance between two points.
614/// Direct port from clipper.h Distance.
615pub fn distance<T>(pt1: Point<T>, pt2: Point<T>) -> f64
616where
617    T: Copy + ToF64,
618{
619    distance_sqr(pt1, pt2).sqrt()
620}
621
622/// Compute the total length of a path.
623/// Direct port from clipper.h Length.
624pub fn path_length<T>(path: &Path<T>, is_closed_path: bool) -> f64
625where
626    T: Copy + ToF64,
627{
628    let mut result = 0.0;
629    if path.len() < 2 {
630        return result;
631    }
632    for i in 0..path.len() - 1 {
633        result += distance(path[i], path[i + 1]);
634    }
635    if is_closed_path {
636        result += distance(path[path.len() - 1], path[0]);
637    }
638    result
639}
640
641// ============================================================================
642// NearCollinear
643// ============================================================================
644
645/// Check if three points are nearly collinear within a tolerance.
646/// Direct port from clipper.h NearCollinear.
647pub fn near_collinear<T>(
648    pt1: Point<T>,
649    pt2: Point<T>,
650    pt3: Point<T>,
651    sin_sqrd_min_angle_rads: f64,
652) -> bool
653where
654    T: Copy + ToF64,
655{
656    let cp = cross_product_three_points(pt1, pt2, pt3).abs();
657    (cp * cp) / (distance_sqr(pt1, pt2) * distance_sqr(pt2, pt3)) < sin_sqrd_min_angle_rads
658}
659
660// ============================================================================
661// SimplifyPath / SimplifyPaths
662// ============================================================================
663
664/// Helper: get next non-flagged index (wrapping).
665fn get_next(current: usize, high: usize, flags: &[bool]) -> usize {
666    let mut c = current + 1;
667    while c <= high && flags[c] {
668        c += 1;
669    }
670    if c <= high {
671        return c;
672    }
673    c = 0;
674    while flags[c] {
675        c += 1;
676    }
677    c
678}
679
680/// Helper: get prior non-flagged index (wrapping).
681fn get_prior(current: usize, high: usize, flags: &[bool]) -> usize {
682    let mut c = if current == 0 { high } else { current - 1 };
683    while c > 0 && flags[c] {
684        c -= 1;
685    }
686    if !flags[c] {
687        return c;
688    }
689    c = high;
690    while flags[c] {
691        c -= 1;
692    }
693    c
694}
695
696/// Simplify a path by removing vertices that are within epsilon distance
697/// of an imaginary line between their neighbors.
698/// Direct port from clipper.h SimplifyPath.
699pub fn simplify_path<T>(path: &Path<T>, epsilon: f64, is_closed_path: bool) -> Path<T>
700where
701    T: Copy + ToF64 + FromF64 + Num + PartialEq,
702{
703    let len = path.len();
704    if len < 4 {
705        return path.clone();
706    }
707    let high = len - 1;
708    let eps_sqr = sqr(epsilon);
709
710    let mut flags = vec![false; len];
711    let mut dist_sqr = vec![0.0f64; len];
712
713    if is_closed_path {
714        dist_sqr[0] = perpendic_dist_from_line_sqrd(path[0], path[high], path[1]);
715        dist_sqr[high] = perpendic_dist_from_line_sqrd(path[high], path[0], path[high - 1]);
716    } else {
717        dist_sqr[0] = constants::MAX_DBL;
718        dist_sqr[high] = constants::MAX_DBL;
719    }
720    for i in 1..high {
721        dist_sqr[i] = perpendic_dist_from_line_sqrd(path[i], path[i - 1], path[i + 1]);
722    }
723
724    let mut curr = 0usize;
725    loop {
726        if dist_sqr[curr] > eps_sqr {
727            let start = curr;
728            loop {
729                curr = get_next(curr, high, &flags);
730                if curr == start || dist_sqr[curr] <= eps_sqr {
731                    break;
732                }
733            }
734            if curr == start {
735                break;
736            }
737        }
738
739        let prior = get_prior(curr, high, &flags);
740        let mut next = get_next(curr, high, &flags);
741        if next == prior {
742            break;
743        }
744
745        let prior2;
746        let prior_for_update;
747        if dist_sqr[next] < dist_sqr[curr] {
748            prior_for_update = curr;
749            curr = next;
750            next = get_next(next, high, &flags);
751            prior2 = get_prior(prior_for_update, high, &flags);
752        } else {
753            prior_for_update = prior;
754            prior2 = get_prior(prior, high, &flags);
755        }
756
757        flags[curr] = true;
758        curr = next;
759        next = get_next(next, high, &flags);
760
761        if is_closed_path || (curr != high && curr != 0) {
762            dist_sqr[curr] =
763                perpendic_dist_from_line_sqrd(path[curr], path[prior_for_update], path[next]);
764        }
765        if is_closed_path || (prior_for_update != 0 && prior_for_update != high) {
766            dist_sqr[prior_for_update] =
767                perpendic_dist_from_line_sqrd(path[prior_for_update], path[prior2], path[curr]);
768        }
769    }
770
771    let mut result = Vec::with_capacity(len);
772    for i in 0..len {
773        if !flags[i] {
774            result.push(path[i]);
775        }
776    }
777    result
778}
779
780/// Simplify multiple paths.
781/// Direct port from clipper.h SimplifyPaths.
782pub fn simplify_paths<T>(paths: &Paths<T>, epsilon: f64, is_closed_path: bool) -> Paths<T>
783where
784    T: Copy + ToF64 + FromF64 + Num + PartialEq,
785{
786    let mut result = Vec::with_capacity(paths.len());
787    for path in paths {
788        result.push(simplify_path(path, epsilon, is_closed_path));
789    }
790    result
791}
792
793// Note: path2_contains_path1 is already implemented in engine_fns.rs
794// and re-exported from the crate root.
795
796// ============================================================================
797// Ramer-Douglas-Peucker
798// ============================================================================
799
800/// Recursive helper for Ramer-Douglas-Peucker algorithm.
801/// Direct port from clipper.h RDP.
802fn rdp<T>(path: &Path<T>, begin: usize, end: usize, eps_sqrd: f64, flags: &mut Vec<bool>)
803where
804    T: Copy + ToF64 + PartialEq,
805{
806    let mut idx = 0;
807    let mut max_d = 0.0;
808    let mut actual_end = end;
809
810    // Handle duplicate endpoints
811    while actual_end > begin && path[begin] == path[actual_end] {
812        flags[actual_end] = false;
813        actual_end -= 1;
814    }
815
816    for i in (begin + 1)..actual_end {
817        let d = perpendic_dist_from_line_sqrd(path[i], path[begin], path[actual_end]);
818        if d <= max_d {
819            continue;
820        }
821        max_d = d;
822        idx = i;
823    }
824
825    if max_d <= eps_sqrd {
826        return;
827    }
828
829    flags[idx] = true;
830    if idx > begin + 1 {
831        rdp(path, begin, idx, eps_sqrd, flags);
832    }
833    if idx < actual_end - 1 {
834        rdp(path, idx, actual_end, eps_sqrd, flags);
835    }
836}
837
838/// Simplify a path using the Ramer-Douglas-Peucker algorithm.
839/// Direct port from clipper.h RamerDouglasPeucker.
840pub fn ramer_douglas_peucker<T>(path: &Path<T>, epsilon: f64) -> Path<T>
841where
842    T: Copy + ToF64 + PartialEq,
843{
844    let len = path.len();
845    if len < 5 {
846        return path.clone();
847    }
848    let mut flags = vec![false; len];
849    flags[0] = true;
850    flags[len - 1] = true;
851    rdp(path, 0, len - 1, sqr(epsilon), &mut flags);
852    let mut result = Vec::with_capacity(len);
853    for i in 0..len {
854        if flags[i] {
855            result.push(path[i]);
856        }
857    }
858    result
859}
860
861/// Simplify multiple paths using the Ramer-Douglas-Peucker algorithm.
862/// Direct port from clipper.h RamerDouglasPeucker (Paths overload).
863pub fn ramer_douglas_peucker_paths<T>(paths: &Paths<T>, epsilon: f64) -> Paths<T>
864where
865    T: Copy + ToF64 + PartialEq,
866{
867    let mut result = Vec::with_capacity(paths.len());
868    for path in paths {
869        result.push(ramer_douglas_peucker(path, epsilon));
870    }
871    result
872}
873
874// ============================================================================
875// Tests
876// ============================================================================
877
878#[cfg(test)]
879#[path = "clipper_tests.rs"]
880mod tests;
clipper2_rust/clipper.rs

clipper2_rust/
clipper.rs
