// Ports Clipper2 2.0.1 src/clipper.offset.cpp and InflatePaths and Ellipse of
// include/clipper2/clipper.h (commit 642390d), Boost Software License 1.0,
// Copyright (c) Angus Johnson 2010-2026. See NOTICE.
///|
/// How offset paths turn corners (`JoinType`): `Square` cuts them at exactly
/// the offset distance, `Bevel` cuts them closer in, `Round` follows an arc,
/// `Miter` extends edges up to the miter limit.
#derive(Eq)
pub(all) enum JoinType {
Square
Bevel
Round
Miter
}
///|
/// How offset paths end (`EndType`): `Polygon` one side of a closed path,
/// `Joined` both sides with the ends joined, `Butt`, `Square` and `Round` both
/// sides of an open path with those caps.
#derive(Eq)
pub(all) enum EndType {
Polygon
Joined
Butt
Square
Round
}
///|
const FLOATING_POINT_TOLERANCE : Double = 1.0e-12
///|
/// Default arc tolerance as a share of the offset (1/500).
const ARC_CONST : Double = 0.002
///|
const PI : Double = 3.141592653589793
///|
priv struct PointD {
x : Double
y : Double
}
///|
/// `x` rounded half away from zero (`std::round`).
fn round_away(x : Double) -> Int64 {
let t = if x < 0.0 { x.ceil() } else { x.floor() }
if (x - t).abs() >= 0.5 {
if x < 0.0 {
(t - 1.0).to_int64()
} else {
(t + 1.0).to_int64()
}
} else {
t.to_int64()
}
}
///|
/// A Point64 from doubles, rounded as Clipper2's `Point64(double, double)`.
fn point64(x : Double, y : Double) -> Point64 {
{ x: round_away(x), y: round_away(y), }
}
///|
fn hypot(x : Double, y : Double) -> Double {
(x * x + y * y).sqrt()
}
///|
fn get_unit_normal(pt1 : Point64, pt2 : Point64) -> PointD {
if pt1 == pt2 {
return { x: 0.0, y: 0.0, }
}
let dx = (pt2.x - pt1.x).to_double()
let dy = (pt2.y - pt1.y).to_double()
let inverse_hypot = 1.0 / hypot(dx, dy)
{ x: dy * inverse_hypot, y: -(dx * inverse_hypot), }
}
///|
fn normalize_vector(v : PointD) -> PointD {
let h = hypot(v.x, v.y)
if h.abs() < 0.001 {
return { x: 0.0, y: 0.0, }
}
let inverse_hypot = 1.0 / h
{ x: v.x * inverse_hypot, y: v.y * inverse_hypot, }
}
///|
fn get_perpendic(pt : Point64, norm : PointD, delta : Double) -> Point64 {
point64(pt.x.to_double() + norm.x * delta, pt.y.to_double() + norm.y * delta)
}
///|
fn get_perpendic_d(pt : Point64, norm : PointD, delta : Double) -> PointD {
{
x: pt.x.to_double() + norm.x * delta,
y: pt.y.to_double() + norm.y * delta,
}
}
///|
/// `GetLineIntersectPt` for doubles: None when parallel.
fn get_line_intersect_pt_d(
ln1a : PointD,
ln1b : PointD,
ln2a : PointD,
ln2b : PointD,
) -> PointD? {
let dx1 = ln1b.x - ln1a.x
let dy1 = ln1b.y - ln1a.y
let dx2 = ln2b.x - ln2a.x
let dy2 = ln2b.y - ln2a.y
let det = dy1 * dx2 - dy2 * dx1
if det == 0.0 {
return None
}
let t = ((ln1a.x - ln2a.x) * dy2 - (ln1a.y - ln2a.y) * dx2) / det
if t <= 0.0 {
Some(ln1a)
} else if t >= 1.0 {
Some(ln1b)
} else {
Some({ x: ln1a.x + t * dx1, y: ln1a.y + t * dy1, })
}
}
///|
/// Strips consecutive duplicates, and for closed paths a last point equal to
/// the first (`StripDuplicates`).
fn strip_duplicates(path : Array[Point64], is_closed : Bool) -> Array[Point64] {
let out = []
for p in path {
if out.is_empty() || out[out.length() - 1] != p {
out.push(p)
}
}
if is_closed {
while out.length() > 1 && out[out.length() - 1] == out[0] {
out.pop() |> ignore
}
}
out
}
///|
priv struct OffsetGroup {
paths_in : Array[Array[Point64]]
lowest_path_idx : Int32?
is_reversed : Bool
join_type : JoinType
end_type : EndType
}
///|
/// The path holding the lowest point (largest y, then smallest x) and
/// whether its area is negative (`GetLowestClosedPathInfo`).
fn get_lowest_closed_path_info(paths : Array[Array[Point64]]) -> (Int32?, Bool) {
let mut idx = None
let mut is_neg_area = false
let mut bot_x = @int64.MAX_VALUE
let mut bot_y = @int64.MIN_VALUE
for i, path in paths {
let mut a = @double.max_value
for pt in path {
if pt.y < bot_y || (pt.y == bot_y && pt.x >= bot_x) {
continue
}
if a == @double.max_value {
a = area(path[:])
if a == 0.0 {
break
}
is_neg_area = a < 0.0
}
idx = Some(i)
bot_x = pt.x
bot_y = pt.y
}
}
(idx, is_neg_area)
}
///|
fn OffsetGroup::new(
paths : Array[Array[Point64]],
join_type : JoinType,
end_type : EndType,
) -> OffsetGroup {
let is_joined = end_type == Polygon || end_type == Joined
let paths_in = paths.map(p => strip_duplicates(p, is_joined))
if end_type == Polygon {
let (idx, neg) = get_lowest_closed_path_info(paths_in)
{
paths_in,
lowest_path_idx: idx,
is_reversed: idx is Some(_) && neg,
join_type,
end_type,
}
} else {
{
paths_in,
lowest_path_idx: None,
is_reversed: false,
join_type,
end_type,
}
}
}
///|
/// Inflates or shrinks paths (Clipper2's `ClipperOffset`): add groups of
/// paths with their join and end types, then `execute` with a distance.
pub struct ClipperOffset {
priv mut delta : Double
priv mut group_delta : Double
priv mut temp_lim : Double
priv mut steps_per_rad : Double
priv mut step_sin : Double
priv mut step_cos : Double
priv norms : Array[PointD]
priv path_out : Array[Point64]
priv solution : Array[Array[Point64]]
priv groups : Array[OffsetGroup]
priv mut join_type : JoinType
priv mut end_type : EndType
priv miter_limit : Double
priv arc_tolerance : Double
priv preserve_collinear : Bool
priv reverse_solution : Bool
}
///|
/// An offsetter; `arc_tolerance` 0 means the offset distance / 500.
pub fn ClipperOffset::new(
miter_limit~ : Double = 2.0,
arc_tolerance~ : Double = 0.0,
preserve_collinear~ : Bool = false,
reverse_solution~ : Bool = false,
) -> ClipperOffset {
{
delta: 0.0,
group_delta: 0.0,
temp_lim: 0.0,
steps_per_rad: 0.0,
step_sin: 0.0,
step_cos: 0.0,
norms: [],
path_out: [],
solution: [],
groups: [],
join_type: Bevel,
end_type: Polygon,
miter_limit,
arc_tolerance,
preserve_collinear,
reverse_solution,
}
}
///|
/// Adds paths to offset together with `join_type` and `end_type`.
pub fn ClipperOffset::add_paths(
self : ClipperOffset,
paths : Array[Array[Point64]],
join_type : JoinType,
end_type : EndType,
) -> Unit {
if paths.is_empty() {
return
}
self.groups.push(OffsetGroup::new(paths, join_type, end_type))
}
///|
fn ClipperOffset::build_normals(
self : ClipperOffset,
path : Array[Point64],
) -> Unit {
self.norms.clear()
if path.is_empty() {
return
}
for i in 0..<(path.length() - 1) {
self.norms.push(get_unit_normal(path[i], path[i + 1]))
}
self.norms.push(get_unit_normal(path[path.length() - 1], path[0]))
}
///|
fn ClipperOffset::do_bevel(
self : ClipperOffset,
path : Array[Point64],
j : Int32,
k : Int32,
) -> Unit {
let n = self.norms
let px = path[j].x.to_double()
let py = path[j].y.to_double()
if j == k {
let abs_delta = self.group_delta.abs()
self.path_out.push(
point64(px - abs_delta * n[j].x, py - abs_delta * n[j].y),
)
self.path_out.push(
point64(px + abs_delta * n[j].x, py + abs_delta * n[j].y),
)
} else {
let d = self.group_delta
self.path_out.push(point64(px + d * n[k].x, py + d * n[k].y))
self.path_out.push(point64(px + d * n[j].x, py + d * n[j].y))
}
}
///|
fn ClipperOffset::do_square(
self : ClipperOffset,
path : Array[Point64],
j : Int32,
k : Int32,
) -> Unit {
let n = self.norms
let vec : PointD = if j == k {
{ x: n[j].y, y: -n[j].x, }
} else {
normalize_vector({ x: -n[k].y + n[j].y, y: n[k].x + -n[j].x, })
}
let d = self.group_delta
let abs_delta = d.abs()
let pt_q : PointD = {
x: path[j].x.to_double() + abs_delta * vec.x,
y: path[j].y.to_double() + abs_delta * vec.y,
}
let pt1 : PointD = { x: pt_q.x + d * vec.y, y: pt_q.y + d * -vec.x, }
let pt2 : PointD = { x: pt_q.x + d * -vec.y, y: pt_q.y + d * vec.x, }
let pt3 = get_perpendic_d(path[k], n[k], d)
let reflect = (p : PointD) => {
point64(pt_q.x + (pt_q.x - p.x), pt_q.y + (pt_q.y - p.y))
}
if j == k {
let pt4 : PointD = { x: pt3.x + vec.x * d, y: pt3.y + vec.y * d, }
let pt = get_line_intersect_pt_d(pt1, pt2, pt3, pt4).unwrap_or(pt_q)
self.path_out.push(reflect(pt))
self.path_out.push(point64(pt.x, pt.y))
} else {
let pt4 = get_perpendic_d(path[j], n[k], d)
let pt = get_line_intersect_pt_d(pt1, pt2, pt3, pt4).unwrap_or(pt_q)
self.path_out.push(point64(pt.x, pt.y))
self.path_out.push(reflect(pt))
}
}
///|
fn ClipperOffset::do_miter(
self : ClipperOffset,
path : Array[Point64],
j : Int32,
k : Int32,
cos_a : Double,
) -> Unit {
let q = self.group_delta / (cos_a + 1.0)
let n = self.norms
self.path_out.push(
point64(
path[j].x.to_double() + (n[k].x + n[j].x) * q,
path[j].y.to_double() + (n[k].y + n[j].y) * q,
),
)
}
///|
fn ClipperOffset::do_round(
self : ClipperOffset,
path : Array[Point64],
j : Int32,
k : Int32,
angle : Double,
) -> Unit {
let pt = path[j]
let n = self.norms
let mut ox = n[k].x * self.group_delta
let mut oy = n[k].y * self.group_delta
if j == k {
ox = -ox
oy = -oy
}
let px = pt.x.to_double()
let py = pt.y.to_double()
self.path_out.push(point64(px + ox, py + oy))
let steps = (self.steps_per_rad * angle.abs()).ceil().to_int()
for _ in 1.. Unit {
if path[j] == path[k] {
return
}
let n = self.norms
// CrossProduct and DotProduct of the two normals.
let mut sin_a = n[j].y * n[k].x - n[k].y * n[j].x
let cos_a = n[j].x * n[k].x + n[j].y * n[k].y
if sin_a > 1.0 {
sin_a = 1.0
} else if sin_a < -1.0 {
sin_a = -1.0
}
if self.group_delta.abs() <= FLOATING_POINT_TOLERANCE {
self.path_out.push(path[j])
return
}
if cos_a > -0.999 && sin_a * self.group_delta < 0.0 {
// Concave: three points making a negative region the final union removes.
self.path_out.push(get_perpendic(path[j], n[k], self.group_delta))
self.path_out.push(path[j])
self.path_out.push(get_perpendic(path[j], n[j], self.group_delta))
} else if cos_a > 0.999 && self.join_type != Round {
self.do_miter(path, j, k, cos_a)
} else if self.join_type == Miter {
if cos_a > self.temp_lim - 1.0 {
self.do_miter(path, j, k, cos_a)
} else {
self.do_square(path, j, k)
}
} else if self.join_type == Round {
self.do_round(path, j, k, @math.atan2(sin_a, cos_a))
} else if self.join_type == Bevel {
self.do_bevel(path, j, k)
} else {
self.do_square(path, j, k)
}
}
///|
fn ClipperOffset::offset_polygon(
self : ClipperOffset,
path : Array[Point64],
) -> Unit {
self.path_out.clear()
let mut k = path.length() - 1
for j in 0.. Unit {
self.offset_polygon(path)
let reverse_path = path.copy()
reverse_path.rev_in_place()
self.norms.rev_in_place()
self.norms.push(self.norms[0])
self.norms.remove(0) |> ignore
for i in 0.. Unit {
if self.group_delta.abs() <= FLOATING_POINT_TOLERANCE {
self.path_out.push(path[i])
return
}
match self.end_type {
Butt => self.do_bevel(path, i, i)
Round => self.do_round(path, i, i, PI)
_ => self.do_square(path, i, i)
}
}
///|
fn ClipperOffset::offset_open_path(
self : ClipperOffset,
path : Array[Point64],
) -> Unit {
self.do_cap(path, 0)
let high_i = path.length() - 1
let mut k = 0
for j in 1.. 0; i = i - 1 {
n[i] = { x: -n[i - 1].x, y: -n[i - 1].y, }
}
n[0] = n[high_i]
self.do_cap(path, high_i)
let mut k = high_i
for j = high_i - 1; j > 0; j = j - 1 {
self.offset_point(path, j, k)
k = j
}
self.solution.push(self.path_out.copy())
}
///|
/// A circle of `steps` points around `center` (Clipper2's `Ellipse` with equal
/// radii; at least π√r steps).
fn ellipse(center : Point64, radius : Double, steps : Int32) -> Array[Point64] {
if radius <= 0.0 {
return []
}
let steps = if steps <= 2 { (PI * radius.sqrt()).to_int() } else { steps }
let si = @math.sin(2.0 * PI / steps.to_double())
let co = @math.cos(2.0 * PI / steps.to_double())
let mut dx = co
let mut dy = si
let cx = center.x.to_double()
let cy = center.y.to_double()
let result = [point64(cx + radius, cy)]
for _ in 1.. Unit {
if group.end_type == Polygon {
if group.lowest_path_idx is None {
self.delta = self.delta.abs()
}
self.group_delta = if group.is_reversed { -self.delta } else { self.delta }
} else {
self.group_delta = self.delta.abs()
}
let abs_delta = self.group_delta.abs()
self.join_type = group.join_type
self.end_type = group.end_type
if group.join_type == Round || group.end_type == Round {
let arc_tol = if self.arc_tolerance > FLOATING_POINT_TOLERANCE {
@cmp.minimum(abs_delta, self.arc_tolerance)
} else {
abs_delta * ARC_CONST
}
let steps_per_360 = @cmp.minimum(
PI / @math.acos(1.0 - arc_tol / abs_delta),
abs_delta * PI,
)
self.step_sin = @math.sin(2.0 * PI / steps_per_360)
self.step_cos = @math.cos(2.0 * PI / steps_per_360)
if self.group_delta < 0.0 {
self.step_sin = -self.step_sin
}
self.steps_per_rad = steps_per_360 / (2.0 * PI)
}
for path in group.paths_in {
self.path_out.clear()
let len = path.length()
if len == 1 {
if self.group_delta < 1.0 {
continue
}
let pt = path[0]
if group.join_type == Round {
let steps = if self.steps_per_rad > 0.0 {
(self.steps_per_rad * 2.0 * PI).ceil().to_int()
} else {
0
}
self.solution.push(ellipse(pt, abs_delta, steps))
} else {
let d = abs_delta.ceil().to_int64()
self.solution.push([
{ x: pt.x - d, y: pt.y - d, },
{ x: pt.x + d, y: pt.y - d, },
{ x: pt.x + d, y: pt.y + d, },
{ x: pt.x - d, y: pt.y + d, },
])
}
continue
}
if len == 2 && group.end_type == Joined {
self.end_type = if group.join_type == Round { Round } else { Square }
}
self.build_normals(path)
match self.end_type {
Polygon => self.offset_polygon(path)
Joined => self.offset_open_joined(path)
_ => self.offset_open_path(path)
}
}
}
///|
/// The added paths offset by `delta` (outwards for positive values on
/// polygons), with overlaps merged.
pub fn ClipperOffset::execute(
self : ClipperOffset,
delta : Double,
) -> Array[Array[Point64]] {
self.solution.clear()
if self.groups.is_empty() {
return []
}
if delta.abs() < 0.5 {
for g in self.groups {
for p in g.paths_in {
self.solution.push(p)
}
}
} else {
self.temp_lim = if self.miter_limit <= 1.0 {
2.0
} else {
2.0 / (self.miter_limit * self.miter_limit)
}
self.delta = delta
for g in self.groups {
self.do_group_offset(g)
}
}
if self.solution.is_empty() {
return []
}
let mut paths_reversed = false
for g in self.groups {
if g.end_type == Polygon {
paths_reversed = g.is_reversed
break
}
}
let c = Clipper64::new()
c.set_preserve_collinear(self.preserve_collinear)
c.set_reverse_solution(self.reverse_solution != paths_reversed)
c.add_subject(self.solution)
let fill : FillRule = if paths_reversed { Negative } else { Positive }
match c.execute(Union, fill) {
Some((closed, _)) => closed
None => []
}
}
///|
/// `paths` offset by `delta` with one join and end type (Clipper2's
/// `InflatePaths`; a positive `delta` grows polygons).
pub fn inflate_paths(
paths : Array[Array[Point64]],
delta : Double,
join_type : JoinType,
end_type : EndType,
miter_limit~ : Double = 2.0,
arc_tolerance~ : Double = 0.0,
) -> Array[Array[Point64]] {
if delta == 0.0 {
return paths
}
let o = ClipperOffset::new(miter_limit~, arc_tolerance~)
o.add_paths(paths, join_type, end_type)
o.execute(delta)
}