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/// A solid polygon face extracted from a `PolyTree64`.
414///
415/// `outer` is a filled contour. `holes` contains only the immediate hole
416/// children of that contour; islands nested inside those holes are returned as
417/// separate `PolyFace64` values.
418#[derive(Debug, Clone, PartialEq)]
419pub struct PolyFace64 {
420    pub node_index: usize,
421    pub depth: u32,
422    pub outer: Path64,
423    pub holes: Paths64,
424    pub hole_node_indices: Vec<usize>,
425}
426
427/// Helper: recursively collect paths from a PolyPath64 node.
428fn poly_path_to_paths64(tree: &PolyTree64, node_idx: usize, paths: &mut Paths64) {
429    let polygon = tree.nodes[node_idx].polygon().clone();
430    if !polygon.is_empty() {
431        paths.push(polygon);
432    }
433    for &child_idx in tree.nodes[node_idx].children() {
434        poly_path_to_paths64(tree, child_idx, paths);
435    }
436}
437
438/// Helper: recursively collect paths from a PolyPathD node.
439fn poly_path_to_paths_d(tree: &PolyTreeD, node_idx: usize, paths: &mut PathsD) {
440    let polygon = tree.nodes[node_idx].polygon().clone();
441    if !polygon.is_empty() {
442        paths.push(polygon);
443    }
444    for &child_idx in tree.nodes[node_idx].children() {
445        poly_path_to_paths_d(tree, child_idx, paths);
446    }
447}
448
449/// Convert a PolyTree64 to a flat list of Paths64.
450/// Direct port from clipper.h PolyTreeToPaths64.
451pub fn poly_tree_to_paths64(polytree: &PolyTree64) -> Paths64 {
452    let mut result = Paths64::new();
453    let root = &polytree.nodes[0];
454    for &child_idx in root.children() {
455        poly_path_to_paths64(polytree, child_idx, &mut result);
456    }
457    result
458}
459
460/// Helper: recursively collect solid faces from a PolyPath64 node.
461fn poly_path_to_faces64(tree: &PolyTree64, node_idx: usize, faces: &mut Vec<PolyFace64>) {
462    let node = &tree.nodes[node_idx];
463
464    if !node.polygon().is_empty() && !tree.is_hole(node_idx) {
465        let mut holes = Paths64::new();
466        let mut hole_node_indices = Vec::new();
467        for &child_idx in node.children() {
468            let child = &tree.nodes[child_idx];
469            if tree.is_hole(child_idx) && !child.polygon().is_empty() {
470                holes.push(child.polygon().clone());
471                hole_node_indices.push(child_idx);
472            }
473        }
474
475        faces.push(PolyFace64 {
476            node_index: node_idx,
477            depth: tree.level(node_idx),
478            outer: node.polygon().clone(),
479            holes,
480            hole_node_indices,
481        });
482    }
483
484    for &child_idx in node.children() {
485        poly_path_to_faces64(tree, child_idx, faces);
486    }
487}
488
489/// Convert a `PolyTree64` into solid faces with immediate hole ownership.
490///
491/// Each non-hole node becomes one `PolyFace64`. Immediate hole children are
492/// attached to that face. Nested islands below those holes are returned as
493/// independent faces.
494#[must_use]
495pub fn poly_tree_to_faces64(polytree: &PolyTree64) -> Vec<PolyFace64> {
496    let mut result = Vec::new();
497    let root = &polytree.nodes[0];
498    for &child_idx in root.children() {
499        poly_path_to_faces64(polytree, child_idx, &mut result);
500    }
501    result
502}
503
504/// Convert a PolyTreeD to a flat list of PathsD.
505/// Direct port from clipper.h PolyTreeToPathsD.
506pub fn poly_tree_to_paths_d(polytree: &PolyTreeD) -> PathsD {
507    let mut result = PathsD::new();
508    let root = &polytree.nodes[0];
509    for &child_idx in root.children() {
510        poly_path_to_paths_d(polytree, child_idx, &mut result);
511    }
512    result
513}
514
515/// Check that all children in a PolyTree64 are fully contained by their parents.
516/// Direct port from clipper.h CheckPolytreeFullyContainsChildren.
517pub fn check_polytree_fully_contains_children(polytree: &PolyTree64) -> bool {
518    let root = &polytree.nodes[0];
519    for &child_idx in root.children() {
520        if polytree.nodes[child_idx].count() > 0
521            && !poly_path64_contains_children(polytree, child_idx)
522        {
523            return false;
524        }
525    }
526    true
527}
528
529/// Helper: check if a PolyPath64 node's children are all contained within it.
530/// Direct port from clipper.h details::PolyPath64ContainsChildren.
531fn poly_path64_contains_children(tree: &PolyTree64, node_idx: usize) -> bool {
532    let parent_polygon = tree.nodes[node_idx].polygon();
533    for &child_idx in tree.nodes[node_idx].children() {
534        let child_polygon = tree.nodes[child_idx].polygon();
535        // Return false if this child isn't fully contained by its parent.
536        // Checking for a single vertex outside is a bit too crude since
537        // it doesn't account for rounding errors. It's better to check
538        // for consecutive vertices found outside the parent's polygon.
539        let mut outside_cnt: i32 = 0;
540        for pt in child_polygon {
541            let result = point_in_polygon(*pt, parent_polygon);
542            if result == PointInPolygonResult::IsInside {
543                outside_cnt -= 1;
544            } else if result == PointInPolygonResult::IsOutside {
545                outside_cnt += 1;
546            }
547            if outside_cnt > 1 {
548                return false;
549            } else if outside_cnt < -1 {
550                break;
551            }
552        }
553
554        // Now check any nested children too
555        if tree.nodes[child_idx].count() > 0 && !poly_path64_contains_children(tree, child_idx) {
556            return false;
557        }
558    }
559    true
560}
561
562// ============================================================================
563// MakePath
564// ============================================================================
565
566/// Create a Path64 from a flat slice of coordinate pairs [x0, y0, x1, y1, ...].
567/// Direct port from clipper.h MakePath.
568pub fn make_path64(coords: &[i64]) -> Path64 {
569    let size = coords.len() - coords.len() % 2;
570    let mut result = Path64::with_capacity(size / 2);
571    let mut i = 0;
572    while i < size {
573        result.push(Point64::new(coords[i], coords[i + 1]));
574        i += 2;
575    }
576    result
577}
578
579/// Create a PathD from a flat slice of coordinate pairs [x0, y0, x1, y1, ...].
580/// Direct port from clipper.h MakePathD.
581pub fn make_path_d(coords: &[f64]) -> PathD {
582    let size = coords.len() - coords.len() % 2;
583    let mut result = PathD::with_capacity(size / 2);
584    let mut i = 0;
585    while i < size {
586        result.push(Point::<f64>::new(coords[i], coords[i + 1]));
587        i += 2;
588    }
589    result
590}
591
592// ============================================================================
593// TrimCollinear
594// ============================================================================
595
596/// Remove collinear points from a Path64.
597/// Direct port from clipper.h TrimCollinear.
598pub fn trim_collinear_64(p: &Path64, is_open_path: bool) -> Path64 {
599    let len = p.len();
600    if len < 3 {
601        if !is_open_path || len < 2 || p[0] == p[1] {
602            return Path64::new();
603        } else {
604            return p.clone();
605        }
606    }
607
608    let mut dst = Path64::with_capacity(len);
609    let mut src_idx: usize = 0;
610    let mut stop = len - 1;
611
612    if !is_open_path {
613        while src_idx != stop && is_collinear(p[stop], p[src_idx], p[src_idx + 1]) {
614            src_idx += 1;
615        }
616        while src_idx != stop && is_collinear(p[stop - 1], p[stop], p[src_idx]) {
617            stop -= 1;
618        }
619        if src_idx == stop {
620            return Path64::new();
621        }
622    }
623
624    let mut prev_idx = src_idx;
625    dst.push(p[prev_idx]);
626    src_idx += 1;
627
628    while src_idx < stop {
629        if !is_collinear(p[prev_idx], p[src_idx], p[src_idx + 1]) {
630            prev_idx = src_idx;
631            dst.push(p[prev_idx]);
632        }
633        src_idx += 1;
634    }
635
636    if is_open_path || !is_collinear(p[prev_idx], p[stop], dst[0]) {
637        dst.push(p[stop]);
638    } else {
639        while dst.len() > 2 && is_collinear(dst[dst.len() - 1], dst[dst.len() - 2], dst[0]) {
640            dst.pop();
641        }
642        if dst.len() < 3 {
643            return Path64::new();
644        }
645    }
646    dst
647}
648
649/// Remove collinear points from a PathD (scales to integer for precision).
650/// Direct port from clipper.h TrimCollinear (PathD overload).
651pub fn trim_collinear_d(path: &PathD, precision: i32, is_open_path: bool) -> PathD {
652    let mut error_code = 0;
653    let mut prec = precision;
654    check_precision_range(&mut prec, &mut error_code);
655    if error_code != 0 {
656        return PathD::new();
657    }
658    let scale = 10f64.powi(precision);
659    let p: Path64 = scale_path(path, scale, scale, &mut error_code);
660    if error_code != 0 {
661        return PathD::new();
662    }
663    let p = trim_collinear_64(&p, is_open_path);
664    scale_path(&p, 1.0 / scale, 1.0 / scale, &mut error_code)
665}
666
667// ============================================================================
668// Distance / Length
669// ============================================================================
670
671/// Compute the distance between two points.
672/// Direct port from clipper.h Distance.
673pub fn distance<T>(pt1: Point<T>, pt2: Point<T>) -> f64
674where
675    T: Copy + ToF64,
676{
677    distance_sqr(pt1, pt2).sqrt()
678}
679
680/// Compute the total length of a path.
681/// Direct port from clipper.h Length.
682pub fn path_length<T>(path: &Path<T>, is_closed_path: bool) -> f64
683where
684    T: Copy + ToF64,
685{
686    let mut result = 0.0;
687    if path.len() < 2 {
688        return result;
689    }
690    for i in 0..path.len() - 1 {
691        result += distance(path[i], path[i + 1]);
692    }
693    if is_closed_path {
694        result += distance(path[path.len() - 1], path[0]);
695    }
696    result
697}
698
699// ============================================================================
700// NearCollinear
701// ============================================================================
702
703/// Check if three points are nearly collinear within a tolerance.
704/// Direct port from clipper.h NearCollinear.
705pub fn near_collinear<T>(
706    pt1: Point<T>,
707    pt2: Point<T>,
708    pt3: Point<T>,
709    sin_sqrd_min_angle_rads: f64,
710) -> bool
711where
712    T: Copy + ToF64,
713{
714    let cp = cross_product_three_points(pt1, pt2, pt3).abs();
715    (cp * cp) / (distance_sqr(pt1, pt2) * distance_sqr(pt2, pt3)) < sin_sqrd_min_angle_rads
716}
717
718// ============================================================================
719// SimplifyPath / SimplifyPaths
720// ============================================================================
721
722/// Helper: get next non-flagged index (wrapping).
723fn get_next(current: usize, high: usize, flags: &[bool]) -> usize {
724    let mut c = current + 1;
725    while c <= high && flags[c] {
726        c += 1;
727    }
728    if c <= high {
729        return c;
730    }
731    c = 0;
732    while flags[c] {
733        c += 1;
734    }
735    c
736}
737
738/// Helper: get prior non-flagged index (wrapping).
739fn get_prior(current: usize, high: usize, flags: &[bool]) -> usize {
740    let mut c = if current == 0 { high } else { current - 1 };
741    while c > 0 && flags[c] {
742        c -= 1;
743    }
744    if !flags[c] {
745        return c;
746    }
747    c = high;
748    while flags[c] {
749        c -= 1;
750    }
751    c
752}
753
754/// Simplify a path by removing vertices that are within epsilon distance
755/// of an imaginary line between their neighbors.
756/// Direct port from clipper.h SimplifyPath.
757pub fn simplify_path<T>(path: &Path<T>, epsilon: f64, is_closed_path: bool) -> Path<T>
758where
759    T: Copy + ToF64 + FromF64 + Num + PartialEq,
760{
761    let len = path.len();
762    if len < 4 {
763        return path.clone();
764    }
765    let high = len - 1;
766    let eps_sqr = sqr(epsilon);
767
768    let mut flags = vec![false; len];
769    let mut dist_sqr = vec![0.0f64; len];
770
771    if is_closed_path {
772        dist_sqr[0] = perpendic_dist_from_line_sqrd(path[0], path[high], path[1]);
773        dist_sqr[high] = perpendic_dist_from_line_sqrd(path[high], path[0], path[high - 1]);
774    } else {
775        dist_sqr[0] = constants::MAX_DBL;
776        dist_sqr[high] = constants::MAX_DBL;
777    }
778    for i in 1..high {
779        dist_sqr[i] = perpendic_dist_from_line_sqrd(path[i], path[i - 1], path[i + 1]);
780    }
781
782    let mut curr = 0usize;
783    loop {
784        if dist_sqr[curr] > eps_sqr {
785            let start = curr;
786            loop {
787                curr = get_next(curr, high, &flags);
788                if curr == start || dist_sqr[curr] <= eps_sqr {
789                    break;
790                }
791            }
792            if curr == start {
793                break;
794            }
795        }
796
797        let prior = get_prior(curr, high, &flags);
798        let mut next = get_next(curr, high, &flags);
799        if next == prior {
800            break;
801        }
802
803        let prior2;
804        let prior_for_update;
805        if dist_sqr[next] < dist_sqr[curr] {
806            prior_for_update = curr;
807            curr = next;
808            next = get_next(next, high, &flags);
809            prior2 = get_prior(prior_for_update, high, &flags);
810        } else {
811            prior_for_update = prior;
812            prior2 = get_prior(prior, high, &flags);
813        }
814
815        flags[curr] = true;
816        curr = next;
817        next = get_next(next, high, &flags);
818
819        if is_closed_path || (curr != high && curr != 0) {
820            dist_sqr[curr] =
821                perpendic_dist_from_line_sqrd(path[curr], path[prior_for_update], path[next]);
822        }
823        if is_closed_path || (prior_for_update != 0 && prior_for_update != high) {
824            dist_sqr[prior_for_update] =
825                perpendic_dist_from_line_sqrd(path[prior_for_update], path[prior2], path[curr]);
826        }
827    }
828
829    let mut result = Vec::with_capacity(len);
830    for i in 0..len {
831        if !flags[i] {
832            result.push(path[i]);
833        }
834    }
835    result
836}
837
838/// Simplify multiple paths.
839/// Direct port from clipper.h SimplifyPaths.
840pub fn simplify_paths<T>(paths: &Paths<T>, epsilon: f64, is_closed_path: bool) -> Paths<T>
841where
842    T: Copy + ToF64 + FromF64 + Num + PartialEq,
843{
844    let mut result = Vec::with_capacity(paths.len());
845    for path in paths {
846        result.push(simplify_path(path, epsilon, is_closed_path));
847    }
848    result
849}
850
851// Note: path2_contains_path1 is already implemented in engine_fns.rs
852// and re-exported from the crate root.
853
854// ============================================================================
855// Ramer-Douglas-Peucker
856// ============================================================================
857
858/// Recursive helper for Ramer-Douglas-Peucker algorithm.
859/// Direct port from clipper.h RDP.
860fn rdp<T>(path: &Path<T>, begin: usize, end: usize, eps_sqrd: f64, flags: &mut Vec<bool>)
861where
862    T: Copy + ToF64 + PartialEq,
863{
864    let mut idx = 0;
865    let mut max_d = 0.0;
866    let mut actual_end = end;
867
868    // Handle duplicate endpoints
869    while actual_end > begin && path[begin] == path[actual_end] {
870        flags[actual_end] = false;
871        actual_end -= 1;
872    }
873
874    for i in (begin + 1)..actual_end {
875        let d = perpendic_dist_from_line_sqrd(path[i], path[begin], path[actual_end]);
876        if d <= max_d {
877            continue;
878        }
879        max_d = d;
880        idx = i;
881    }
882
883    if max_d <= eps_sqrd {
884        return;
885    }
886
887    flags[idx] = true;
888    if idx > begin + 1 {
889        rdp(path, begin, idx, eps_sqrd, flags);
890    }
891    if idx < actual_end - 1 {
892        rdp(path, idx, actual_end, eps_sqrd, flags);
893    }
894}
895
896/// Simplify a path using the Ramer-Douglas-Peucker algorithm.
897/// Direct port from clipper.h RamerDouglasPeucker.
898pub fn ramer_douglas_peucker<T>(path: &Path<T>, epsilon: f64) -> Path<T>
899where
900    T: Copy + ToF64 + PartialEq,
901{
902    let len = path.len();
903    if len < 5 {
904        return path.clone();
905    }
906    let mut flags = vec![false; len];
907    flags[0] = true;
908    flags[len - 1] = true;
909    rdp(path, 0, len - 1, sqr(epsilon), &mut flags);
910    let mut result = Vec::with_capacity(len);
911    for i in 0..len {
912        if flags[i] {
913            result.push(path[i]);
914        }
915    }
916    result
917}
918
919/// Simplify multiple paths using the Ramer-Douglas-Peucker algorithm.
920/// Direct port from clipper.h RamerDouglasPeucker (Paths overload).
921pub fn ramer_douglas_peucker_paths<T>(paths: &Paths<T>, epsilon: f64) -> Paths<T>
922where
923    T: Copy + ToF64 + PartialEq,
924{
925    let mut result = Vec::with_capacity(paths.len());
926    for path in paths {
927        result.push(ramer_douglas_peucker(path, epsilon));
928    }
929    result
930}
931
932// ============================================================================
933// Tests
934// ============================================================================
935
936#[cfg(test)]
937#[path = "clipper_tests.rs"]
938mod tests;
clipper2_rust/clipper.rs

clipper2_rust/
clipper.rs
