// Ports the sweep of ClipperBase in Clipper2 2.0.1 src/clipper.engine.cpp
// (commit 642390d), Boost Software License 1.0, Copyright (c) Angus Johnson
// 2010-2026. See NOTICE.
///|
fn Clipper64::start_open_path(
self : Clipper64,
e : Active,
pt : Point64,
) -> OutPt {
let outrec = self.new_outrec()
outrec.is_open = true
if e.wind_dx > 0 {
outrec.front_edge = Some(e)
outrec.back_edge = None
} else {
outrec.front_edge = None
outrec.back_edge = Some(e)
}
e.outrec = Some(outrec)
let op = OutPt::new(pt, outrec)
outrec.pts = Some(op)
op
}
///|
fn Clipper64::update_edge_into_ael(self : Clipper64, e : Active) -> Unit {
e.bot = e.top
e.vertex_top = next_vertex(e)
e.top = e.vertex_top.pt
e.curr_x = e.bot.x
set_dx(e)
if is_joined(e) {
self.split(e, e.bot)
}
if is_horizontal(e) {
if !is_open(e) {
trim_horz(e, self.preserve_collinear)
}
return
}
self.insert_scanline(e.top.y)
self.check_join_left(e, e.bot)
self.check_join_right(e, e.bot, check_curr_x=true)
}
///|
fn find_edge_with_matching_loc_min(e : Active) -> Active? {
let mut result = e.next_in_ael
while result is Some(r) {
if physical_equal(r.local_min, e.local_min) {
return Some(r)
} else if !is_horizontal(r) && e.bot != r.bot {
result = None
} else {
result = r.next_in_ael
}
}
result = e.prev_in_ael
while result is Some(r) {
if physical_equal(r.local_min, e.local_min) {
return Some(r)
} else if !is_horizontal(r) && e.bot != r.bot {
return None
} else {
result = r.prev_in_ael
}
}
result
}
///|
fn Clipper64::intersect_edges(
self : Clipper64,
e1 : Active,
e2 : Active,
pt : Point64,
) -> Unit {
if self.has_open_paths && (is_open(e1) || is_open(e2)) {
if is_open(e1) && is_open(e2) {
return
}
let (edge_o, edge_c) = if is_open(e1) { (e1, e2) } else { (e2, e1) }
if is_joined(edge_c) {
self.split(edge_c, pt)
}
if edge_c.wind_cnt.abs() != 1 {
return
}
match self.cliptype {
Union => if !is_hot_edge(edge_c) { return }
_ => if edge_c.local_min.polytype == Subject { return }
}
match self.fillrule {
Positive => if edge_c.wind_cnt != 1 { return }
Negative => if edge_c.wind_cnt != -1 { return }
_ => if edge_c.wind_cnt.abs() != 1 { return }
}
if is_hot_edge(edge_o) {
self.add_out_pt(edge_o, pt) |> ignore
let o = edge_o.outrec.unwrap()
if is_front(edge_o) {
o.front_edge = None
} else {
o.back_edge = None
}
edge_o.outrec = None
} else if pt == edge_o.local_min.vertex.pt &&
!is_open_end_vertex(edge_o.local_min.vertex) {
match find_edge_with_matching_loc_min(edge_o) {
Some(e3) if is_hot_edge(e3) => {
let o = e3.outrec.unwrap()
edge_o.outrec = Some(o)
if edge_o.wind_dx > 0 {
set_sides(o, edge_o, e3)
} else {
set_sides(o, e3, edge_o)
}
return
}
_ => self.start_open_path(edge_o, pt) |> ignore
}
} else {
self.start_open_path(edge_o, pt) |> ignore
}
return
}
if is_joined(e1) {
self.split(e1, pt)
}
if is_joined(e2) {
self.split(e2, pt)
}
if e1.local_min.polytype == e2.local_min.polytype {
if self.fillrule == EvenOdd {
let old = e1.wind_cnt
e1.wind_cnt = e2.wind_cnt
e2.wind_cnt = old
} else {
if e1.wind_cnt + e2.wind_dx == 0 {
e1.wind_cnt = -e1.wind_cnt
} else {
e1.wind_cnt += e2.wind_dx
}
if e2.wind_cnt - e1.wind_dx == 0 {
e2.wind_cnt = -e2.wind_cnt
} else {
e2.wind_cnt -= e1.wind_dx
}
}
} else if self.fillrule != EvenOdd {
e1.wind_cnt2 += e2.wind_dx
e2.wind_cnt2 -= e1.wind_dx
} else {
e1.wind_cnt2 = if e1.wind_cnt2 == 0 { 1 } else { 0 }
e2.wind_cnt2 = if e2.wind_cnt2 == 0 { 1 } else { 0 }
}
let (old_e1_windcnt, old_e2_windcnt) = match self.fillrule {
EvenOdd | NonZero => (e1.wind_cnt.abs(), e2.wind_cnt.abs())
Positive => (e1.wind_cnt, e2.wind_cnt)
Negative => (-e1.wind_cnt, -e2.wind_cnt)
}
let e1_in_01 = old_e1_windcnt == 0 || old_e1_windcnt == 1
let e2_in_01 = old_e2_windcnt == 0 || old_e2_windcnt == 1
if (!is_hot_edge(e1) && !e1_in_01) || (!is_hot_edge(e2) && !e2_in_01) {
return
}
if is_hot_edge(e1) && is_hot_edge(e2) {
if (old_e1_windcnt != 0 && old_e1_windcnt != 1) ||
(old_e2_windcnt != 0 && old_e2_windcnt != 1) ||
(e1.local_min.polytype != e2.local_min.polytype && self.cliptype != Xor) {
self.add_local_max_poly(e1, e2, pt) |> ignore
} else if is_front(e1) || same_outrec(e1.outrec, e2.outrec) {
self.add_local_max_poly(e1, e2, pt) |> ignore
self.add_local_min_poly(e1, e2, pt) |> ignore
} else {
self.add_out_pt(e1, pt) |> ignore
self.add_out_pt(e2, pt) |> ignore
swap_outrecs(e1, e2)
}
} else if is_hot_edge(e1) {
self.add_out_pt(e1, pt) |> ignore
swap_outrecs(e1, e2)
} else if is_hot_edge(e2) {
self.add_out_pt(e2, pt) |> ignore
swap_outrecs(e1, e2)
} else {
let (e1_wc2, e2_wc2) = match self.fillrule {
EvenOdd | NonZero => (e1.wind_cnt2.abs(), e2.wind_cnt2.abs())
Positive => (e1.wind_cnt2, e2.wind_cnt2)
Negative => (-e1.wind_cnt2, -e2.wind_cnt2)
}
if !is_same_poly_type(e1, e2) {
self.add_local_min_poly(e1, e2, pt) |> ignore
} else if old_e1_windcnt == 1 && old_e2_windcnt == 1 {
match self.cliptype {
Union =>
if e1_wc2 <= 0 && e2_wc2 <= 0 {
self.add_local_min_poly(e1, e2, pt) |> ignore
}
Difference =>
if (get_poly_type(e1) == Clip && e1_wc2 > 0 && e2_wc2 > 0) ||
(get_poly_type(e1) == Subject && e1_wc2 <= 0 && e2_wc2 <= 0) {
self.add_local_min_poly(e1, e2, pt) |> ignore
}
Xor => self.add_local_min_poly(e1, e2, pt) |> ignore
_ =>
if e1_wc2 > 0 && e2_wc2 > 0 {
self.add_local_min_poly(e1, e2, pt) |> ignore
}
}
}
}
}
///|
fn Clipper64::delete_from_ael(self : Clipper64, e : Active) -> Unit {
let prev = e.prev_in_ael
let next = e.next_in_ael
if prev is None && next is None && !same_active(self.actives, e) {
return
}
match prev {
Some(p) => p.next_in_ael = next
None => self.actives = next
}
if next is Some(n) {
n.prev_in_ael = prev
}
e.prev_in_ael = None
e.next_in_ael = None
}
///|
fn Clipper64::adjust_curr_x_and_copy_to_sel(
self : Clipper64,
top_y : Int64,
) -> Unit {
let mut e = self.actives
self.sel = e
while e is Some(a) {
a.prev_in_sel = a.prev_in_ael
a.next_in_sel = a.next_in_ael
a.jump = a.next_in_sel
a.curr_x = top_x(a, top_y)
e = a.next_in_ael
}
}
///|
fn Clipper64::execute_internal(
self : Clipper64,
ct : ClipType,
fillrule : FillRule,
use_polytrees : Bool,
) -> Bool {
self.cliptype = ct
self.fillrule = fillrule
self.using_polytree = use_polytrees
self.reset()
guard ct != NoClip && self.pop_scanline() is Some(first) else { return true }
let mut y = first
while self.succeeded {
self.insert_local_minima_into_ael(y)
while self.pop_horz() is Some(e) {
self.do_horizontal(e)
}
if self.horz_seg_list.length() > 0 {
self.convert_horz_segs_to_joins()
self.horz_seg_list.clear()
}
self.bot_y = y
guard self.pop_scanline() is Some(next) else { break }
y = next
self.do_intersections(y)
self.do_top_of_scanbeam(y)
while self.pop_horz() is Some(e) {
self.do_horizontal(e)
}
}
if self.succeeded {
self.process_horz_joins()
}
self.succeeded
}
///|
fn fix_outrec_pts(outrec : OutRec) -> Unit {
update_outrec_owner(outrec)
}
///|
fn Clipper64::do_intersections(self : Clipper64, top_y : Int64) -> Unit {
if self.build_intersect_list(top_y) {
self.process_intersect_list()
self.intersect_nodes.clear()
}
}
///|
fn Clipper64::add_new_intersect_node(
self : Clipper64,
e1 : Active,
e2 : Active,
top_y : Int64,
) -> Unit {
let mut ip = match get_line_intersect_pt(e1.bot, e1.top, e2.bot, e2.top) {
Some(p) => p
None => { x: e1.curr_x, y: top_y, }
}
if ip.y > self.bot_y || ip.y < top_y {
let abs_dx1 = e1.dx.abs()
let abs_dx2 = e2.dx.abs()
if abs_dx1 > 100.0 && abs_dx2 > 100.0 {
if abs_dx1 > abs_dx2 {
ip = get_closest_point_on_segment(ip, e1.bot, e1.top)
} else {
ip = get_closest_point_on_segment(ip, e2.bot, e2.top)
}
} else if abs_dx1 > 100.0 {
ip = get_closest_point_on_segment(ip, e1.bot, e1.top)
} else if abs_dx2 > 100.0 {
ip = get_closest_point_on_segment(ip, e2.bot, e2.top)
} else {
let y = if ip.y < top_y { top_y } else { self.bot_y }
let x = if abs_dx1 < abs_dx2 { top_x(e1, y) } else { top_x(e2, y) }
ip = { x, y, }
}
}
self.intersect_nodes.push({ pt: ip, edge1: e1, edge2: e2, })
}
///|
/// Finds the intersections in the current scanbeam with a merge sort of the
/// SEL that only ever swaps adjacent edges.
fn Clipper64::build_intersect_list(self : Clipper64, top_y : Int64) -> Bool {
guard self.actives is Some(a) && a.next_in_ael is Some(_) else {
return false
}
self.adjust_curr_x_and_copy_to_sel(top_y)
let mut left = self.sel
while left is Some(l0) && l0.jump is Some(_) {
let mut prev_base : Active? = None
while left is Some(lft) && lft.jump is Some(_) {
let mut curr_base = lft
let mut l = lft
let mut right = lft.jump
let mut l_end = right
let r_end = right.unwrap().jump
l.jump = r_end
while !same_opt(Some(l), l_end) && !same_opt(right, r_end) {
let r = right.unwrap()
if r.curr_x < l.curr_x {
let mut tmp = r.prev_in_sel.unwrap()
while true {
self.add_new_intersect_node(tmp, r, top_y)
if physical_equal(tmp, l) {
break
}
tmp = tmp.prev_in_sel.unwrap()
}
tmp = r
right = extract_from_sel(tmp)
l_end = right
insert1_before2_in_sel(tmp, l)
if physical_equal(l, curr_base) {
curr_base = tmp
curr_base.jump = r_end
match prev_base {
None => self.sel = Some(curr_base)
Some(p) => p.jump = Some(curr_base)
}
}
} else {
l = l.next_in_sel.unwrap()
}
}
prev_base = Some(curr_base)
left = r_end
}
left = self.sel
}
self.intersect_nodes.length() > 0
}
///|
fn same_opt(a : Active?, b : Active?) -> Bool {
match (a, b) {
(None, None) => true
(Some(x), Some(y)) => physical_equal(x, y)
_ => false
}
}
///|
fn Clipper64::process_intersect_list(self : Clipper64) -> Unit {
let nodes = self.intersect_nodes
libcxx_sort(nodes, intersect_list_less)
for i in 0.. Unit {
let next = e2.next_in_ael
if next is Some(n) {
n.prev_in_ael = Some(e1)
}
let prev = e1.prev_in_ael
if prev is Some(p) {
p.next_in_ael = Some(e2)
}
e2.prev_in_ael = prev
e2.next_in_ael = Some(e1)
e1.prev_in_ael = Some(e2)
e1.next_in_ael = next
if e2.prev_in_ael is None {
self.actives = Some(e2)
}
}
///|
fn Clipper64::do_top_of_scanbeam(self : Clipper64, y : Int64) -> Unit {
self.sel = None
let mut e = self.actives
while e is Some(a) {
if a.top.y == y {
a.curr_x = a.top.x
if is_maxima(a) {
e = self.do_maxima(a)
continue
} else {
if is_hot_edge(a) {
self.add_out_pt(a, a.top) |> ignore
}
self.update_edge_into_ael(a)
if is_horizontal(a) {
self.push_horz(a)
}
}
} else {
a.curr_x = top_x(a, y)
}
e = a.next_in_ael
}
}
///|
fn Clipper64::do_maxima(self : Clipper64, e : Active) -> Active? {
let prev_e = e.prev_in_ael
let mut next_e = e.next_in_ael
if is_open_end(e) {
if is_hot_edge(e) {
self.add_out_pt(e, e.top) |> ignore
}
if !is_horizontal(e) {
if is_hot_edge(e) {
let o = e.outrec.unwrap()
if is_front(e) {
o.front_edge = None
} else {
o.back_edge = None
}
e.outrec = None
}
self.delete_from_ael(e)
}
return next_e
}
guard get_maxima_pair(e) is Some(max_pair) else { return next_e }
if is_joined(e) {
self.split(e, e.top)
}
if is_joined(max_pair) {
self.split(max_pair, max_pair.top)
}
while !same_opt(next_e, Some(max_pair)) {
let n = next_e.unwrap()
self.intersect_edges(e, n, e.top)
self.swap_positions_in_ael(e, n)
next_e = e.next_in_ael
}
if is_open(e) {
if is_hot_edge(e) {
self.add_local_max_poly(e, max_pair, e.top) |> ignore
}
self.delete_from_ael(max_pair)
self.delete_from_ael(e)
return match prev_e {
Some(p) => p.next_in_ael
None => self.actives
}
}
if is_hot_edge(e) {
self.add_local_max_poly(e, max_pair, e.top) |> ignore
}
self.delete_from_ael(e)
self.delete_from_ael(max_pair)
match prev_e {
Some(p) => p.next_in_ael
None => self.actives
}
}
///|
fn Clipper64::split(self : Clipper64, e : Active, pt : Point64) -> Unit {
if e.join_with == Right {
e.join_with = NoJoin
let n = e.next_in_ael.unwrap()
n.join_with = NoJoin
self.add_local_min_poly(e, n, pt, is_new=true) |> ignore
} else {
e.join_with = NoJoin
let p = e.prev_in_ael.unwrap()
p.join_with = NoJoin
self.add_local_min_poly(p, e, pt, is_new=true) |> ignore
}
}
///|
fn Clipper64::check_join_left(
self : Clipper64,
e : Active,
pt : Point64,
check_curr_x~ : Bool = false,
) -> Unit {
guard e.prev_in_ael is Some(prev) else { return }
if !is_hot_edge(e) ||
!is_hot_edge(prev) ||
is_horizontal(e) ||
is_horizontal(prev) ||
is_open(e) ||
is_open(prev) {
return
}
if (pt.y < e.top.y + 2L || pt.y < prev.top.y + 2L) &&
(e.bot.y > pt.y || prev.bot.y > pt.y) {
return
}
if check_curr_x {
if perpendic_dist_from_line_sqrd(pt, prev.bot, prev.top) > 0.25 {
return
}
} else if e.curr_x != prev.curr_x {
return
}
if !is_collinear(e.top, pt, prev.top) {
return
}
let ei = e.outrec.unwrap().idx
let pi = prev.outrec.unwrap().idx
if ei == pi {
self.add_local_max_poly(prev, e, pt) |> ignore
} else if ei < pi {
self.join_outrec_paths(e, prev)
} else {
self.join_outrec_paths(prev, e)
}
prev.join_with = Right
e.join_with = Left
}
///|
fn Clipper64::check_join_right(
self : Clipper64,
e : Active,
pt : Point64,
check_curr_x~ : Bool = false,
) -> Unit {
guard e.next_in_ael is Some(next) else { return }
if !is_hot_edge(e) ||
!is_hot_edge(next) ||
is_horizontal(e) ||
is_horizontal(next) ||
is_open(e) ||
is_open(next) {
return
}
if (pt.y < e.top.y + 2L || pt.y < next.top.y + 2L) &&
(e.bot.y > pt.y || next.bot.y > pt.y) {
return
}
if check_curr_x {
if perpendic_dist_from_line_sqrd(pt, next.bot, next.top) > 0.35 {
return
}
} else if e.curr_x != next.curr_x {
return
}
if !is_collinear(e.top, pt, next.top) {
return
}
let ei = e.outrec.unwrap().idx
let ni = next.outrec.unwrap().idx
if ei == ni {
self.add_local_max_poly(e, next, pt) |> ignore
} else if ei < ni {
self.join_outrec_paths(e, next)
} else {
self.join_outrec_paths(next, e)
}
e.join_with = Right
next.join_with = Left
}