#[cfg(test)]
pub(crate) mod tests;
#[derive(Clone, Copy)]
pub(crate) enum RegionBooleanOp {
Intersection,
Union,
Difference,
Xor,
}
pub(crate) fn clamp_coord(value: i32) -> i16 {
value.clamp(i32::from(i16::MIN), i32::from(i16::MAX)) as i16
}
pub(crate) fn endpoints_to_intervals(endpoints: &[i16]) -> Vec<(i16, i16)> {
endpoints
.chunks_exact(2)
.filter_map(|pair| (pair[0] < pair[1]).then_some((pair[0], pair[1])))
.collect()
}
pub(crate) fn intervals_to_endpoints(mut intervals: Vec<(i16, i16)>) -> Vec<i16> {
if intervals.is_empty() {
return Vec::new();
}
intervals.sort_unstable();
let mut merged: Vec<(i16, i16)> = Vec::with_capacity(intervals.len());
for (start, end) in intervals {
if start >= end {
continue;
}
if let Some((_, last_end)) = merged.last_mut() {
if start <= *last_end {
*last_end = (*last_end).max(end);
continue;
}
}
merged.push((start, end));
}
let mut endpoints = Vec::with_capacity(merged.len() * 2);
for (start, end) in merged {
endpoints.push(start);
endpoints.push(end);
}
endpoints
}
pub(crate) fn intersect_rows(lhs: &[i16], rhs: &[i16]) -> Vec<i16> {
let lhs = endpoints_to_intervals(lhs);
let rhs = endpoints_to_intervals(rhs);
let mut out = Vec::new();
let mut lhs_index = 0usize;
let mut rhs_index = 0usize;
while let (Some(&(lhs_start, lhs_end)), Some(&(rhs_start, rhs_end))) =
(lhs.get(lhs_index), rhs.get(rhs_index))
{
let start = lhs_start.max(rhs_start);
let end = lhs_end.min(rhs_end);
if start < end {
out.push((start, end));
}
if lhs_end < rhs_end {
lhs_index += 1;
} else {
rhs_index += 1;
}
}
intervals_to_endpoints(out)
}
pub(crate) fn union_rows(lhs: &[i16], rhs: &[i16]) -> Vec<i16> {
let mut intervals = endpoints_to_intervals(lhs);
intervals.extend(endpoints_to_intervals(rhs));
intervals_to_endpoints(intervals)
}
pub(crate) fn difference_rows(lhs: &[i16], rhs: &[i16]) -> Vec<i16> {
let lhs = endpoints_to_intervals(lhs);
let rhs = endpoints_to_intervals(rhs);
let mut out = Vec::new();
for (lhs_start, lhs_end) in lhs {
let mut start = lhs_start;
for &(rhs_start, rhs_end) in rhs.iter() {
if rhs_end <= start {
continue;
}
if rhs_start >= lhs_end {
break;
}
if rhs_start > start {
out.push((start, rhs_start.min(lhs_end)));
}
start = start.max(rhs_end);
if start >= lhs_end {
break;
}
}
if start < lhs_end {
out.push((start, lhs_end));
}
}
intervals_to_endpoints(out)
}
pub(crate) fn xor_rows(lhs: &[i16], rhs: &[i16]) -> Vec<i16> {
let mut intervals = endpoints_to_intervals(&difference_rows(lhs, rhs));
intervals.extend(endpoints_to_intervals(&difference_rows(rhs, lhs)));
intervals_to_endpoints(intervals)
}
pub(crate) fn combine_rows(lhs: &[i16], rhs: &[i16], op: RegionBooleanOp) -> Vec<i16> {
match op {
RegionBooleanOp::Intersection => intersect_rows(lhs, rhs),
RegionBooleanOp::Union => union_rows(lhs, rhs),
RegionBooleanOp::Difference => difference_rows(lhs, rhs),
RegionBooleanOp::Xor => xor_rows(lhs, rhs),
}
}
pub(crate) fn inset_row(row: &[i16], dh: i16) -> Vec<i16> {
if row.is_empty() {
return Vec::new();
}
let dh = i32::from(dh);
let intervals = endpoints_to_intervals(row)
.into_iter()
.filter_map(|(left, right)| {
let new_left = i32::from(left) + dh;
let new_right = i32::from(right) - dh;
(new_left < new_right).then_some((clamp_coord(new_left), clamp_coord(new_right)))
})
.collect::<Vec<_>>();
intervals_to_endpoints(intervals)
}
pub(crate) fn merge_endpoints(lhs: &[i16], rhs: &[i16]) -> Vec<i16> {
let mut merged = Vec::with_capacity(lhs.len() + rhs.len());
let mut lhs_index = 0usize;
let mut rhs_index = 0usize;
while lhs_index < lhs.len() || rhs_index < rhs.len() {
match (lhs.get(lhs_index), rhs.get(rhs_index)) {
(Some(&lhs_value), Some(&rhs_value)) if lhs_value < rhs_value => {
merged.push(lhs_value);
lhs_index += 1;
}
(Some(&lhs_value), Some(&rhs_value)) if rhs_value < lhs_value => {
merged.push(rhs_value);
rhs_index += 1;
}
(Some(_), Some(_)) => {
lhs_index += 1;
rhs_index += 1;
}
(Some(&lhs_value), None) => {
merged.push(lhs_value);
lhs_index += 1;
}
(None, Some(&rhs_value)) => {
merged.push(rhs_value);
rhs_index += 1;
}
(None, None) => break,
}
}
merged
}
pub(crate) fn endpoints_contain_point(endpoints: &[i16], x: i16) -> bool {
let mut in_region = false;
for &edge in endpoints {
if edge > x {
break;
}
in_region = !in_region;
}
in_region
}