与 Rust 勾心斗角 · 包围球

OFF 文件记录的是多面体信息,将其内容解析为 Mesh 结构后,便可基于后者为多面体网格构造包围球。

球体

用泛型的结构体定义球体:

struct Sphere {
    n: usize,       // 维度
    center: Vec, // 中心
    radius: T       // 半径
}

然后为该结构定义 new 方法:

impl Sphere {
    fn new(n: usize) -> Sphere {
        Sphere{n: n, center: vec![0.0; n], radius: 0.0}
    }
}

倘若调用该方法,rustc 会有以下指责:

  • vec![...] 的第一个参数的类型本该是 T,不是浮点型;
  • Sphereradius 成员赋的值,其类型应该是 T,不是浮点型;
  • vec![...] 的第一个参数需要实现 std::Clone Trait。

前两个指责,是希望我们为 T 定义 0,因为 rustc 不知道 T 类型的 0 值的形式。第三个指责是希望为 T 增加约束。要解决这些问题,我能想出的方案是

use std::clone;

struct Sphere {
    n: usize,
    center: Vec,
    radius: T
}

trait Zero {
    fn zero() -> Self;
}

impl Zero for f64 {
    fn zero() -> Self {
        0.0
    }
}

impl Sphere {
    fn new(n: usize) -> Sphere {
        Sphere{n: n, center: vec![T::zero(); n], radius: T::zero()}
    }
}

基于以上代码定义的球体,能够支持以下语句:

let sphere: Sphere = Sphere::new(3);

趁热打铁,再为球体实现 Display Trait 吧,现在已经驾轻就熟了,

use std::fmt;

impl fmt::Display for Sphere {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let mut info = String::new();
        info += "球体:";
        info += format!("维度 {};", self.n).as_str();
        info += format!("中心 (").as_str();
        for i in 0 .. self.n - 1 {
            info += format!("{}, ", self.center[i]).as_str();
        }
        info += format!("{});", self.center[self.n - 1]).as_str();
        info += format!("半径 {}.", self.radius).as_str();
        write!(f, "{}", info)
    }
}

网格的中心

Mesh 实例的中心即包围球的中心。现在为 Mesh 结构增加 center 方法,用于计算 Mesh 实例的中心,以下是该过程的基本泛型框架:

impl Mesh {
    fn center(&self) -> Vec {
        let mut x = vec![T::zero(); self.n];
        // 计算 self 的中心,将结果存于 x
        return x;
    }
}

我敢肯定,rustc 会根据具体的网格中心计算代码继续要求我为 T 增加类型约束,而且这个过程也会让我有些焦虑。倘若我毫不焦虑,而且对 rustc 有所感激,认为它饱含圣光,指出了我的代码的疏漏,那我敢肯定,我被 rustc PUA 了。

网格的中心,可以取为网格顶点集合的均值点:

// 计算 self 的中心,将结果存于 x
for x_i in &self.points {
    for j in 0 .. self.n {
        x[j] += x_i[j] / self.points.len() as T;
    }
}

对于上述代码,rustc 认为:

  • 它不知该如何进行类型 T 的除法运算;
  • self.nusize 类型,它无法使用 as 转换为 T 类型,因为 as 只能用于基本类型的转换。

对于第一个问题,为 T 增加 std::ops::Div 约束便可解决。对于第二个问题,一种可行的方案是,为 T 增加 std::convert::From 约束,然后将 self.points.len() as T 修改为 self.points.len().into(),以实现 self.points.len() 的类型从 usizeT 的转换。于是,Meshcenter 方法的代码变为

impl
     + std::convert::From> Mesh {
    fn center(&self) -> Vec {
        let mut x = vec![T::zero(); self.n];
        // 计算 self 的中心,将结果存于 x
        for x_i in &self.points {
            for j in 0 .. self.n {
                x[j] += x_i[j] / self.points.len().into();
            }
        }
        return x;
    }
}

然而,rustc 意犹未尽,继续认为它不知道该怎么用 += 处理 T 类型的值,于是我需要继续为 T 增加约束 std::ops::AddAssign,结果 Meshcenter 方法的代码变成

impl
     + std::convert::From
     + std::ops::AddAssign> Mesh {
    fn center(&self) -> Vec {
        let mut x = vec![T::zero(); self.n];
        // 计算 self 的中心,将结果存于 x
        for x_i in &self.points {
            for j in 0 .. self.n {
                x[j] += x_i[j] / self.points.len().into();
            }
        }
        return x;
    }
}

这样便万事大吉了吗?当然不是,rustc 会继续认为 x[j] += x_i[j] / ... 里的 x_i[j] 无法移动,原因是它对应的类型 T 未实现 copy Trait,因此不得不继续为 T 追加 std::marker::Copy 约束。现在,Meshcenter 方法的代码变为

impl
     + std::convert::From
     + std::ops::AddAssign
     + std::marker::Copy> Mesh {
    fn center(&self) -> Vec {
        let mut x = vec![T::zero(); self.n];
        // 计算 self 的中心,将结果存于 x
        for x_i in &self.points {
            for j in 0 .. self.n {
                x[j] += x_i[j] / self.points.len().into();
            }
        }
        return x;
    }
}

然后,rustc 不再说什么,这时我才有余力看出代码里存在一处性能问题需要解决,即

for x_i in &self.points {
    for j in 0 .. self.n {
        x[j] += x_i[j] / self.points.len().into();
    }
}

需要修改为

let n: T = self.points.len().into();
for x_i in &self.points {
    for j in 0 .. self.n {
        x[j] += x_i[j] / n;
    }
}

以下代码可用于测试 Meshcenter 方法是否真的能算出多面体的中心:

let dim = 3;
let mut mesh: Mesh = Mesh::new(dim);
mesh.load("foo.off");

let center: Vec = mesh.center();
let mut sphere: Sphere = Sphere::new(dim);
for i in 0 .. dim {
    sphere.center[i] = center[i];
}
println!("{}", sphere);

但是,rustc 编译上述代码时,会很傲骄地说 f64: From 没实现,也就是说 Rust 标准库里为 f64 类型实现了一大堆的的 From<...>,然而唯独没实现 From,亦即 Meshcenter 方法里的代码

let n: T = self.points.len().into();

无法通过编译。于是,之前的一堆努力,崩溃于这最后一片无辜的雪花。为了挽回败局,我只好在代码里用了武当派的梯云纵,左脚踩右脚,右脚踩左脚,扶摇直上……

impl
     + std::convert::From
     + std::ops::AddAssign
     + std::marker::Copy> Mesh {
    fn center(&self) -> Vec {
        let mut x = vec![T::zero(); self.n];
        // 计算 self 的中心,将结果存于 x
        let n: T = (self.points.len() as f64).into();
        for x_i in &self.points {
            for j in 0 .. self.n {
                x[j] += x_i[j] / n;
            }
        }
        return x;
    }
}

网格的半径

网格的半径是网格顶点到网格中心的最大距离,为便于实现该过程,先定义一个泛型函数,用于计算两点间的距离:

fn distance(a: &Vec, b: &Vec) -> T {
    let na = a.len();
    let nb = b.len();
    assert_eq!(na, nb);
    let mut d: T = T::zero();
    for i in 0 .. na {
        let t = a[i] - b[i];
        d += t * t;
    }
    return d.sqrt();
}

经过 rustc 的一番调教,distance 函数变为

fn distance
            + std::ops::Mul
            + std::ops::AddAssign
            + Copy>(a: &Vec, b: &Vec) -> T {
    let na = a.len();
    let nb = b.len();
    assert_eq!(na, nb);
    let mut d: T = T::zero();
    for i in 0 .. na {
        let t = a[i] - b[i];
        d += t * t;
    }
    return d.sqrt();
}

即便如此,该函数依然无法通过编译,因为 rustc 认为它无法确定 T 类型的实例有 sqrt 方法。既然天不佑我,那就别怪我代码写得丑:

trait Sqrt {
    fn sqrt(self) -> T;
}

fn distance
            + std::ops::Mul
            + std::ops::AddAssign
            + Copy
            + Sqrt>(a: &Vec, b: &Vec) -> T {
    let na = a.len();
    let nb = b.len();
    assert_eq!(na, nb);
    let mut d: T = T::zero();
    for i in 0 .. na {
        let t = a[i] - b[i];
        d += t * t;
    }
    return d.sqrt();
}

若点的坐标值是 f64 类型,只需为该类型实现 Sqrt Trait,

impl Sqrt for f64 {
    fn sqrt(self) -> f64 {
        self.sqrt()
    }
}

便可使用 distance 计算两点距离,例如

let a: Vec = vec![0.0, 0.0, 0.0];
let b: Vec = vec![1.0, 1.0, 1.0];
println!("{}", distance(&a, &b));

结果为 1.7320508075688772

有了 distance 函数,便可计算网格半径:

impl 
      + std::ops::Sub
      + std::ops::Mul
      + std::cmp::PartialOrd> Mesh {
    fn radius(&self, center: &Vec) -> T {
        let mut r = T::zero();
        for x in &self.points {
            let d = distance(x, center);
            if r < d {
                r = d;
            }
        }
        return r;
    }
}

要写出上述代码,自然少不了 rustc 对类型的 T 各种具体约束的循循善诱……

网格的包围球

现在,将 Meshcenterradius 方法合并为 bounding_sphere

impl
     + std::convert::From
     + std::ops::AddAssign
     + std::marker::Copy
     + Sqrt
     + std::ops::Sub
     + std::ops::Mul
     + std::cmp::PartialOrd> Mesh {
    fn bounding_sphere(&self) -> Sphere {
        let mut sphere: Sphere = Sphere::new(self.n);
        // 计算包围球中心
        let n: T = (self.points.len() as f64).into();
        for x_i in &self.points {
            for j in 0 .. self.n {
                sphere.center[j] += x_i[j] / n;
            }
        }
        // 计算包围球半径
        for x in &self.points {
            let d = distance(x, &sphere.center);
            if sphere.radius < d {
                sphere.radius = d;
            }
        }
        return sphere;
    }
}

以下为 Meshbounding_sphere 方法的调用示例:

let dim = 3;
let mut mesh: Mesh = Mesh::new(dim);
mesh.load("foo.off");
let sphere: Sphere = mesh.bounding_sphere();
println!("{}", sphere);

Rust 泛型之我见

最好别用泛型。

最好别用泛型。

最好别用泛型。

小结

use std::{fmt, clone, ops, convert, marker, cmp};
use std::path::Path;
use std::fs::File;
use std::io::{BufRead, BufReader};
use std::str::FromStr;
use std::num::ParseFloatError;
use std::ops::Index;

trait Zero {
    fn zero() -> Self;
}

impl Zero for f64 {
    fn zero() -> Self {
        0.0
    }
}

trait Length {
    fn len(&self) -> usize;
}

impl Length for Vec {
    fn len(&self) -> usize {
        return self.len();
    }
}

struct Mesh {
    n: usize, // 维度
    points: Vec>,  // 点表
    facets: Vec> // 面表
}

impl> Mesh {
    fn new(n: usize) -> Mesh {
        return Mesh {n: n, points: Vec::new(), facets: Vec::new()};
    }
    fn load(&mut self, path: &str) {
        let path = Path::new(path);
        let file = File::open(path).unwrap();
        let buf = BufReader::new(file);

        let mut lines_iter = buf.lines().map(|l| l.unwrap());
        assert_eq!(lines_iter.next(), Some(String::from("OFF")));
        let second_line = lines_iter.next().unwrap();
        let mut split = second_line.split_whitespace();
        let n_of_points: usize = split.next().unwrap().parse().unwrap();
        let n_of_facets: usize = split.next().unwrap().parse().unwrap();

        for _i in 0 .. n_of_points {
            let line = lines_iter.next().unwrap();
            let mut p: Vec = Vec::new();
            for x in line.split_whitespace() {
                p.push(x.parse().unwrap());
            }
            self.points.push(p);
        }
        for _i in 0 .. n_of_facets {
            let line = lines_iter.next().unwrap();
            let mut f: Vec = Vec::new();
            let mut split = line.split_whitespace();
            let n:usize = split.next().unwrap().parse().unwrap();
            assert_eq!(n, self.n);
            for x in split {
                f.push(x.parse().unwrap());
            }
            assert_eq!(n, f.len());
            self.facets.push(f);        
        }
    }
}

struct Prefix {
    status: bool,
    body: fn(&T) -> String
}

impl Prefix {
    fn new() -> Prefix {
        Prefix{status: false, body: |_| "".to_string()}
    }
}

fn matrix_fmt>(v: &Vec,
                                        prefix: Prefix) -> String
where >::Output: fmt::Display,
      >::Output: Sized {
    let mut s = String::new();
    for x in v {
        let n = x.len();
        if prefix.status {
            s += (prefix.body)(x).as_str();
        }
        for i in 0 .. n {
            if i == n - 1 {
                s += format!("{}\n", x[i]).as_str();
            } else {
                s += format!("{} ", x[i]).as_str();
            }
        }
    }
    return s;
}

impl fmt::Display for Mesh {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let mut info = String::new();
        info += format!("OFF\n").as_str();
        info += format!("{0} {1} 0\n", self.points.len(), self.facets.len()).as_str();
        info += matrix_fmt(&self.points,  Prefix::new()).as_str();
        info += matrix_fmt(&self.facets, Prefix{status: true,
                                                body: |x| format!("{} ", x.len())}).as_str();
        write!(f, "{}", info)
    }
}

trait Sqrt {
    fn sqrt(self) -> T;
}

impl Sqrt for f64 {
    fn sqrt(self) -> f64 {
        self.sqrt()
    }
}

fn distance
            + ops::Mul
            + ops::AddAssign
            + Copy
            + Sqrt>(a: &Vec, b: &Vec) -> T {
    let na = a.len();
    let nb = b.len();
    assert_eq!(na, nb);
    let mut d: T = T::zero();
    for i in 0 .. na {
        let t = a[i] - b[i];
        d += t * t;
    }
    return d.sqrt();
}

struct Sphere {
    n: usize,
    center: Vec,
    radius: T
}

impl Sphere {
    fn new(n: usize) -> Sphere {
        Sphere{n: n, center: vec![T::zero(); n], radius: T::zero()}
    }
}

impl fmt::Display for Sphere {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let mut info = String::new();
        info += "球体:";
        info += format!("维度 {};", self.n).as_str();
        info += format!("中心 (").as_str();
        for i in 0 .. self.n - 1 {
            info += format!("{}, ", self.center[i]).as_str();
        }
        info += format!("{});", self.center[self.n - 1]).as_str();
        info += format!("半径 {}.", self.radius).as_str();
        write!(f, "{}", info)
    }
}

impl
     + convert::From
     + ops::AddAssign
     + marker::Copy
     + Sqrt
     + ops::Sub
     + ops::Mul
     + cmp::PartialOrd> Mesh {
    fn bounding_sphere(&self) -> Sphere {
        let mut sphere: Sphere = Sphere::new(self.n);
        // 计算包围球中心
        let n: T = (self.points.len() as f64).into();
        for x_i in &self.points {
            for j in 0 .. self.n {
                sphere.center[j] += x_i[j] / n;
            }
        }
        // 计算包围球半径
        for x in &self.points {
            let d = distance(x, &sphere.center);
            if sphere.radius < d {
                sphere.radius = d;
            }
        }
        return sphere;
    }
}

fn main() {
    let dim = 3;
    let mut mesh: Mesh = Mesh::new(dim);
    mesh.load("foo.off");
    let sphere: Sphere = mesh.bounding_sphere();
    println!("{}", sphere);
}

你可能感兴趣的