///|
/// Represents a 2D line segment between two points.
pub(all) struct Segment2D {
p1 : Point2D
p2 : Point2D
} derive(Debug, Eq)
///|
/// Creates a new 2D line segment.
pub fn Segment2D::new(p1 : Point2D, p2 : Point2D) -> Segment2D {
{ p1, p2 }
}
///|
/// Computes the length of the segment.
pub fn Segment2D::length(self : Segment2D) -> Double {
self.p1.distance(self.p2)
}
///|
/// Computes the midpoint of the segment.
pub fn Segment2D::midpoint(self : Segment2D) -> Point2D {
{ x: (self.p1.x + self.p2.x) * 0.5, y: (self.p1.y + self.p2.y) * 0.5 }
}
///|
/// Computes the shortest distance from a point to this line segment.
pub fn Segment2D::distance_to_point(self : Segment2D, p : Point2D) -> Double {
let dx = self.p2.x - self.p1.x
let dy = self.p2.y - self.p1.y
let len_sq = dx * dx + dy * dy
if len_sq < 1.0e-12 {
return self.p1.distance(p)
}
let t = ((p.x - self.p1.x) * dx + (p.y - self.p1.y) * dy) / len_sq
if t <= 0.0 {
self.p1.distance(p)
} else if t >= 1.0 {
self.p2.distance(p)
} else {
let proj = Point2D::new(self.p1.x + t * dx, self.p1.y + t * dy)
proj.distance(p)
}
}
///|
/// Checks if two 2D segments intersect, and returns the intersection point if any.
pub fn Segment2D::intersection(self : Segment2D, other : Segment2D) -> Point2D? {
let p = self.p1
let r = self.p2.sub(self.p1)
let q = other.p1
let s = other.p2.sub(other.p1)
let r_cross_s = r.cross(s)
let q_minus_p = q.sub(p)
let q_minus_p_cross_r = q_minus_p.cross(r)
if r_cross_s.abs() < 1.0e-12 {
return None // Collinear or parallel
}
let t = q_minus_p.cross(s) / r_cross_s
let u = q_minus_p_cross_r / r_cross_s
if t >= 0.0 && t <= 1.0 && u >= 0.0 && u <= 1.0 {
Some(Point2D::new(p.x + t * r.x, p.y + t * r.y))
} else {
None
}
}
///|
/// Represents a general 2D polygon with ordered vertices.
pub(all) struct Polygon2D {
vertices : Array[Point2D]
} derive(Debug, Eq)
///|
/// Creates a new polygon from an array of vertices.
pub fn Polygon2D::new(vertices : Array[Point2D]) -> Polygon2D {
{ vertices, }
}
///|
/// Computes perimeter of polygon.
pub fn Polygon2D::perimeter(self : Polygon2D) -> Double {
let n = self.vertices.length()
if n < 2 {
return 0.0
}
let mut total = 0.0
for i in 0.. Double {
let n = self.vertices.length()
if n < 3 {
return 0.0
}
let mut sum = 0.0
for i in 0.. Double {
self.signed_area().abs()
}
///|
/// Computes geometric centroid of polygon.
pub fn Polygon2D::centroid(self : Polygon2D) -> Point2D {
let n = self.vertices.length()
if n == 0 {
return { x: 0.0, y: 0.0 }
}
if n < 3 {
let mut sx = 0.0
let mut sy = 0.0
for p in self.vertices {
sx += p.x
sy += p.y
}
return { x: sx / n.to_double(), y: sy / n.to_double() }
}
let mut cx = 0.0
let mut cy = 0.0
let mut signed_a = 0.0
for i in 0.. Bool {
let n = self.vertices.length()
if n < 3 {
return false
}
let mut inside = false
let mut j = n - 1
for i in 0.. p.y) != (pj.y > p.y) &&
p.x < (pj.x - pi.x) * (p.y - pi.y) / (pj.y - pi.y) + pi.x {
inside = !inside
}
j = i
}
inside
}
///|
/// Tests whether polygon is strictly convex.
pub fn Polygon2D::is_convex(self : Polygon2D) -> Bool {
let n = self.vertices.length()
if n < 3 {
return false
}
let mut sign = 0.0
for i in 0.. 1.0e-10 {
if sign == 0.0 {
sign = if cross_val > 0.0 { 1.0 } else { -1.0 }
} else {
let curr_sign = if cross_val > 0.0 { 1.0 } else { -1.0 }
if curr_sign != sign {
return false
}
}
}
}
true
}
///|
/// Computes convex hull of 2D points using Andrew's Monotone Chain algorithm.
pub fn compute_convex_hull(points : Array[Point2D]) -> Polygon2D {
let n = points.length()
if n <= 3 {
return Polygon2D::new(points.copy())
}
// Sort points primarily by x, then by y
let pts = points.copy()
for i in 0..<(n - 1) {
let mut min_idx = i
for j in (i + 1)..= 2 {
let p0 = lower[lower.length() - 2]
let p1 = lower[lower.length() - 1]
if (p1.x - p0.x) * (p.y - p0.y) - (p1.y - p0.y) * (p.x - p0.x) <= 0.0 {
let _ = lower.pop()
} else {
break
}
}
lower.push(p)
}
// Build upper hull
let upper : Array[Point2D] = []
let mut idx = n - 1
while idx >= 0 {
let p = pts[idx]
while upper.length() >= 2 {
let p0 = upper[upper.length() - 2]
let p1 = upper[upper.length() - 1]
if (p1.x - p0.x) * (p.y - p0.y) - (p1.y - p0.y) * (p.x - p0.x) <= 0.0 {
let _ = upper.pop()
} else {
break
}
}
upper.push(p)
idx -= 1
}
// Concatenate lower and upper hull
let hull : Array[Point2D] = []
for i in 0..<(lower.length() - 1) {
hull.push(lower[i])
}
for i in 0..<(upper.length() - 1) {
hull.push(upper[i])
}
Polygon2D::new(hull)
}
///|
/// Computes minimum area enclosing rectangle using Rotating Calipers on a convex polygon.
pub fn min_area_bounding_box(polygon : Polygon2D) -> Quad {
let hull = if polygon.is_convex() {
polygon
} else {
compute_convex_hull(polygon.vertices)
}
let pts = hull.vertices
let n = pts.length()
if n == 0 {
return Quad::new(
Point2D::new(0.0, 0.0),
Point2D::new(0.0, 0.0),
Point2D::new(0.0, 0.0),
Point2D::new(0.0, 0.0),
)
}
if n == 1 {
let p = pts[0]
return Quad::new(p, p, p, p)
}
if n == 2 {
let p0 = pts[0]
let p1 = pts[1]
return Quad::new(p0, p1, p1, p0)
}
let mut min_area = 1.0e30
let mut best_quad = Quad::new(pts[0], pts[0], pts[0], pts[0])
for i in 0.. 1.0e-10 {
let u = edge.scale(1.0 / len) // Unit vector along edge
let v = Point2D::new(-u.y, u.x) // Perpendicular unit vector
let mut min_u = 1.0e30
let mut max_u = -1.0e30
let mut min_v = 1.0e30
let mut max_v = -1.0e30
for pt in pts {
let proj_u = pt.dot(u)
let proj_v = pt.dot(v)
if proj_u < min_u {
min_u = proj_u
}
if proj_u > max_u {
max_u = proj_u
}
if proj_v < min_v {
min_v = proj_v
}
if proj_v > max_v {
max_v = proj_v
}
}
let area = (max_u - min_u) * (max_v - min_v)
if area < min_area {
min_area = area
// Compute 4 corner points
let c0 = u.scale(min_u).add(v.scale(min_v))
let c1 = u.scale(max_u).add(v.scale(min_v))
let c2 = u.scale(max_u).add(v.scale(max_v))
let c3 = u.scale(min_u).add(v.scale(max_v))
best_quad = Quad::new(c0, c1, c2, c3)
}
}
}
best_quad
}
///|
/// Sutherland-Hodgman polygon clipping algorithm against a rectangular clipping window.
pub fn clip_polygon_to_rect(poly : Polygon2D, rect : Rect2D) -> Polygon2D {
let x_min = rect.x
let x_max = rect.x + rect.width
let y_min = rect.y
let y_max = rect.y + rect.height
let mut current = poly.vertices.copy()
// 1. Clip against left: x >= x_min
let mut next_pts : Array[Point2D] = []
let mut n = current.length()
if n > 0 {
let mut s = current[n - 1]
for e in current {
if e.x >= x_min {
if s.x >= x_min {
next_pts.push(e)
} else {
let t = (x_min - s.x) / (e.x - s.x)
next_pts.push(Point2D::new(x_min, s.y + t * (e.y - s.y)))
next_pts.push(e)
}
} else if s.x >= x_min {
let t = (x_min - s.x) / (e.x - s.x)
next_pts.push(Point2D::new(x_min, s.y + t * (e.y - s.y)))
}
s = e
}
}
current = next_pts
// 2. Clip against right: x <= x_max
next_pts = []
n = current.length()
if n > 0 {
let mut s = current[n - 1]
for e in current {
if e.x <= x_max {
if s.x <= x_max {
next_pts.push(e)
} else {
let t = (x_max - s.x) / (e.x - s.x)
next_pts.push(Point2D::new(x_max, s.y + t * (e.y - s.y)))
next_pts.push(e)
}
} else if s.x <= x_max {
let t = (x_max - s.x) / (e.x - s.x)
next_pts.push(Point2D::new(x_max, s.y + t * (e.y - s.y)))
}
s = e
}
}
current = next_pts
// 3. Clip against top: y >= y_min
next_pts = []
n = current.length()
if n > 0 {
let mut s = current[n - 1]
for e in current {
if e.y >= y_min {
if s.y >= y_min {
next_pts.push(e)
} else {
let t = (y_min - s.y) / (e.y - s.y)
next_pts.push(Point2D::new(s.x + t * (e.x - s.x), y_min))
next_pts.push(e)
}
} else if s.y >= y_min {
let t = (y_min - s.y) / (e.y - s.y)
next_pts.push(Point2D::new(s.x + t * (e.x - s.x), y_min))
}
s = e
}
}
current = next_pts
// 4. Clip against bottom: y <= y_max
next_pts = []
n = current.length()
if n > 0 {
let mut s = current[n - 1]
for e in current {
if e.y <= y_max {
if s.y <= y_max {
next_pts.push(e)
} else {
let t = (y_max - s.y) / (e.y - s.y)
next_pts.push(Point2D::new(s.x + t * (e.x - s.x), y_max))
next_pts.push(e)
}
} else if s.y <= y_max {
let t = (y_max - s.y) / (e.y - s.y)
next_pts.push(Point2D::new(s.x + t * (e.x - s.x), y_max))
}
s = e
}
}
Polygon2D::new(next_pts)
}