乐趣区

关于rust:与-Rust-勾心斗角-包围球

jiezi

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

球体

用泛型的构造体定义球体：

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

而后为该构造定义 new` 办法：

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

假使调用该办法，rustc 会有以下指摘：

  • vec![...] 的第一个参数的类型本该是 T，不是浮点型；
  • 为 Sphere 的 radius 成员赋的值，其类型应该是 T，不是浮点型；
  • vec![...] 的第一个参数须要实现 std::Clone Trait。

前两个指摘，是心愿咱们为 T 定义 0，因为 rustc 不晓得 T 类型的 0 值的模式。第三个指摘是心愿为 T 减少束缚。要解决这些问题，我能想出的计划是 

use std::clone;

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

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

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

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

基于以上代码定义的球体，可能反对以下语句：

let sphere: Sphere<f64> = Sphere::new(3);

趁热打铁，再为球体实现 Display Trait 吧，当初曾经轻车熟路了，

use std::fmt;

impl<T: fmt::Display> fmt::Display for Sphere<T> {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<T: Zero + clone::Clone> Mesh<T> {fn center(&self) -> Vec<T> {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.n 为 usize 类型，它无奈应用 as 转换为 T 类型，因为 as 只能用于根本类型的转换。

对于第一个问题，为 T 减少 std::ops::Div<Output = T> 束缚便可解决。对于第二个问题，一种可行的计划是，为 T 减少 std::convert::From<usize> 束缚，而后将 self.points.len() as T 批改为 self.points.len().into()，以实现 self.points.len() 的类型从 usize 到 T 的转换。于是，Mesh 的 center 办法的代码变为 

impl<T: Zero
     + clone::Clone
     + std::ops::Div<Output = T>
     + std::convert::From<usize>> Mesh<T> {fn center(&self) -> Vec<T> {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，后果 Mesh 的 center 办法的代码变成 

impl<T: Zero
     + clone::Clone
     + std::ops::Div<Output = T>
     + std::convert::From<usize>
     + std::ops::AddAssign> Mesh<T> {fn center(&self) -> Vec<T> {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 束缚。当初，Mesh 的 center 办法的代码变为 

impl<T: Zero
     + clone::Clone
     + std::ops::Div<Output = T>
     + std::convert::From<usize>
     + std::ops::AddAssign
     + std::marker::Copy> Mesh<T> {fn center(&self) -> Vec<T> {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;
    }
}

以下代码可用于测试 Mesh 的 center 办法是否真的能算出多面体的核心：

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

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

然而，rustc 编译上述代码时，会很傲骄地说 f64: From<usize> 没实现，也就是说 Rust 规范库里为 f64 类型实现了一大堆的的 From<...>，然而唯独没实现 From<usize，亦即 Mesh 的 center 办法里的代码 

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

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

impl<T: Zero
     + clone::Clone
     + std::ops::Div<Output = T>
     + std::convert::From<f64>
     + std::ops::AddAssign
     + std::marker::Copy> Mesh<T> {fn center(&self) -> Vec<T> {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<T>(a: &Vec<T>, b: &Vec<T>) -> 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<T: Zero
            + std::ops::Sub<Output = T>
            + std::ops::Mul<Output = T>
            + std::ops::AddAssign
            + Copy>(a: &Vec<T>, b: &Vec<T>) -> 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<T> {fn sqrt(self) -> T;
}

fn distance<T: Zero
            + std::ops::Sub<Output = T>
            + std::ops::Mul<Output = T>
            + std::ops::AddAssign
            + Copy
            + Sqrt<T>>(a: &Vec<T>, b: &Vec<T>) -> 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<f64> for f64 {fn sqrt(self) -> f64 {self.sqrt()
    }
}

便可应用 distance 计算两点间隔，例如 

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

后果为 1.7320508075688772。

有了 distance 函数，便可计算网格半径：

impl <T: Zero
      + std::ops::AddAssign
      + std::marker::Copy
      + Sqrt<T>
      + std::ops::Sub<Output = T>
      + std::ops::Mul<Output = T>
      + std::cmp::PartialOrd> Mesh<T> {fn radius(&self, center: &Vec<T>) -> 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 各种具体束缚的谆谆告诫……

网格的突围球

当初，将 Mesh 的 center 和 radius 办法合并为 bounding_sphere：

impl<T: Zero
     + clone::Clone
     + std::ops::Div<Output = T>
     + std::convert::From<f64>
     + std::ops::AddAssign
     + std::marker::Copy
     + Sqrt<T>
     + std::ops::Sub<Output = T>
     + std::ops::Mul<Output = T>
     + std::cmp::PartialOrd> Mesh<T> {fn bounding_sphere(&self) -> Sphere<T> {let mut sphere: Sphere<T> = 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;
    }
}

以下为 Mesh 的 bounding_sphere 办法的调用示例：

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

Rust 泛型之我见

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<T> Length for Vec<T> {fn len(&self) -> usize {return self.len();
    }
}

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

impl<T: FromStr<Err = ParseFloatError>> Mesh<T> {fn new(n: usize) -> Mesh<T> {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<T> = 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<usize> = 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<T> {
    status: bool,
    body: fn(&T) -> String
}

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

fn matrix_fmt<T: Length + Index<usize>>(v: &Vec<T>,
                                        prefix: Prefix<T>) -> String
where <T as Index<usize>>::Output: fmt::Display,
      <T as Index<usize>>::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<T: fmt::Display> fmt::Display for Mesh<T> {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<T> {fn sqrt(self) -> T;
}

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

fn distance<T: Zero
            + ops::Sub<Output = T>
            + ops::Mul<Output = T>
            + ops::AddAssign
            + Copy
            + Sqrt<T>>(a: &Vec<T>, b: &Vec<T>) -> 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<T> {
    n: usize,
    center: Vec<T>,
    radius: T
}

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

impl<T: fmt::Display> fmt::Display for Sphere<T> {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<T: Zero
     + clone::Clone
     + ops::Div<Output = T>
     + convert::From<f64>
     + ops::AddAssign
     + marker::Copy
     + Sqrt<T>
     + ops::Sub<Output = T>
     + ops::Mul<Output = T>
     + cmp::PartialOrd> Mesh<T> {fn bounding_sphere(&self) -> Sphere<T> {let mut sphere: Sphere<T> = 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<f64> = Mesh::new(dim);
    mesh.load("foo.off");
    let sphere: Sphere<f64> = mesh.bounding_sphere();
    println!("{}", sphere);
}
退出移动版