Why must point scalars be signed? #129
Comments
|
I think that using unsigned numbers would mean that we would have to audit all algorithms to not produce underflow at zero and thereby produce nonsensical results (or panic in debug builds). And even this check would most likely imply the introduction of new failure modes into the API or at least document new possibilities of panics. Personally, I would recommend to use a signed type in the tree and convert your coordinates when interface with the rest of your code. If you are confident, you can also effectively circumvent the requirement without changes to the impl Signed for MyFancyNumberType {
fn abs(&self) -> Self { unreachable!() }
fn abs_sub(&self, other: &Self) -> Self { unreachable!() }
fn signum(&self) -> Self { unreachable!() }
fn is_positive(&self) -> bool { unreachable!() }
fn is_negative(&self) -> bool { unreachable!() }
} |
I went down this rabbit hole yesterday. So far, I've found that the pub trait PointExt: Point {
fn abs_diff(&self, other: &Self) -> Self {
self.component_wise(other, |l, r| {
if l < r {
r - l
} else {
l - r
}
})
}
fn distance_2(&self, other: &Self) -> Self::Scalar {
self.abs_diff(other).length_2()
}
}In an optimized build, However, fn length_2(&self) -> Self::Scalar {
self.fold(Zero::zero(), |acc, cur| cur * cur + acc)
}I think it would be correct-ish to implement this in terms of It might be good to use more saturating/wrapping operations in these calculations, as it would extend the range of signed numbers that can be used with this library.
I think this is what I'll end up doing (or implement my own specialized version of R-tree). For my project, I will likely have a rather huge spatial index that would benefit from being memory mapped, something that this library cannot provide yet, so I might go down the latter path. |
|
I tried converting my fn u64_to_i64(x: u64) -> i64 {
// Simply flip the sign bit. This is equivalent to subtracting 2^63.
(x ^ (i64::MIN as u64)) as i64
}But I still run into overflow problems. My rectangles can be very large, or even take up the entire First, I ran into an overflow in |x, y| (x + y) / twoOverflows can be avoided by calculating it like this instead: |x, y| x / two + y / two(It's just one additional Next, I am still running into the |
|
Thanks @jasonwhite for the in-depth changeset required for this; reg. the I am for merging a PR to support unsigned types as long it's a not a huge regression. |
|
I'll likely end up going with a quadtree instead. My use-case doesn't require the need to find the nearest neighbors. I only care about querying for which rectangles overlap with a given input. Feel free to close this issue, but I suspect others may be interested in having support for unsigned numbers (provided that they are small enough to avoid overflow). FYI, I'm not able to run the benchmarks because of a problem compiling the |
I've just now opened #131 which should address that error. |
If fear the change is unpalatable in the general case. I think that generally, this operation significantly profits from using signed types. As an alternative, we could have a helper trait like |
|
I'm a bit confused why overflow should occur at all. I took a long time to painfully implement unsigned ints. Now the unsigned ints are overflowing. Why does RStar subtract from unsigned ints at all? Error: Code: |
|
Usually for computing distances. Which basically applies here as well, i.e. your bracktrace comes from node.children.sort_by(|l, r| {
let l_center = l.envelope().center();
let r_center = r.envelope().center();
l_center
.sub(¢er)
.length_2()
.partial_cmp(&(r_center.sub(¢er)).length_2())
.unwrap()
});which implements the R* insertion strategy by splitting a node along its center by sorting its children based on lexicographical distance to it. |
While evaluating this crate to see if I can use it for a project, I bumped into the issue that
RTreeNumrequiresSigned. I was hoping to use this data structure with unsigned integers (not floats). I'm not aware of any fundamental reason why an R-tree can't be used with unsigned numbers. I was able to remove the requirement locally and all the tests still pass. Is there something I'm missing or is it just a historical artifact? Thanks!The text was updated successfully, but these errors were encountered: