Skip to content

rust/sedona-geometry: WraparoundInterval::merge_value() and WraparoundInterval::merge_interval() need finite bounds to merge across the antimeridian #861

@paleolimbot

Description

@paleolimbot

While the current logic is correct, it does not make the smallest possible update to the intervals involved (e.g., successively merging a -179 and 179 will result in a non-wraparound interval because it does not know that the wraparound version is smaller than the non-wraparound.

fn merge_interval(&self, other: &Self) -> Self {
if self.is_empty() {
return *other;
}
if other.is_empty() {
return *self;
}
let (wraparound, not_wraparound) = match (self.is_wraparound(), other.is_wraparound()) {
// Handle wraparound/not wraparound below
(true, false) => (self, other),
(false, true) => (other, self),
// Both are wraparound: Merge the two left intervals, then merge the two right intervals
// and check if we need the full interval
(true, true) => {
let (left, right) = self.split();
let (other_left, other_right) = other.split();
let new_left = left.merge_interval(&other_left);
let new_right = right.merge_interval(&other_right);
// If the left and right intervals intersect each other, we need the full interval
if new_left.intersects_interval(&new_right) {
return WraparoundInterval::full();
} else {
return WraparoundInterval::new(new_right.lo(), new_left.hi());
}
}
// Neither are wraparound: just merge the inner intervals
(false, false) => {
return Self {
inner: self.inner.merge_interval(&other.inner),
};
}
};
let (left, right) = wraparound.split();
let distance_not_wraparound_left = (not_wraparound.mid() - left.hi()).abs();
let distance_not_wraparound_right = (not_wraparound.mid() - right.lo()).abs();
let (new_left, new_right) = if distance_not_wraparound_left < distance_not_wraparound_right
{
(left.merge_interval(&not_wraparound.inner), right)
} else {
(left, right.merge_interval(&not_wraparound.inner))
};
// If the left and right intervals intersect each other, we need the full interval
if new_left.intersects_interval(&new_right) {
WraparoundInterval::full()
} else {
WraparoundInterval::new(new_right.lo(), new_left.hi())
}
}
fn merge_value(&self, value: f64) -> Self {
if self.intersects_value(value) || value.is_nan() {
return *self;
}
if !self.is_wraparound() {
return Self {
inner: self.inner.merge_value(value),
};
}
// Move only one of the endpoints
let distance_left = value - self.inner.hi;
let distance_right = self.inner.lo - value;
debug_assert!(distance_left > 0.0);
debug_assert!(distance_right > 0.0);
if distance_left < distance_right {
Self {
inner: Interval {
lo: self.inner.lo,
hi: value,
},
}
} else {
Self {
inner: Interval {
lo: value,
hi: self.inner.hi,
},
}
}
}

This is used in the statistics/bounding box merging (mostly just in the statistics merging). To do the right thing we need to pass through finite coordinate system bounds when merging these.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type
    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions