Rust-Crater

这是一个数据结构库，以我的C数据结构库命名。

Rust比C提供了更多的内置数据结构，所以很多内容都是不必要的。向量、哈希表、二叉堆和参数解析已经提供。

甚至还有一些非常罕见的向量函数，如select_nth_unstable，几乎与我的vec_ith + vec_partition_with_median相同：这两个都提供了在未排序的向量中根据某些比较函数在线性时间内找到第n个元素的方法，然后对向量进行分区，使第n个元素位于第n个索引处，每个在其之前的元素是<=，每个在其之后的元素是=。不同之处在于我的vec_partition_with_median是一个三路分区函数，这意味着它将向量分为<、=和>区域，但实际上对于KD树来说，这是多余的，KD树是这里的主要关注点。

目前，这个库实现了非常通用的KD树、斐波那契堆和minmax堆。

已经有一些很好的KD树库可用，但它们没有一个足够通用以满足我的需求。对于简单的二维/三维KD树，其他库目前提供更多功能。对于不在笛卡尔空间中或具有奇异标量类型的KD树，这个库可能是一个好的选择。

Kiddo 是一个非常流行的 Rust 语言 KD 树库，它非常快速，但也存在一些非常极端的缺点（仅支持浮点坐标，整坐标功能削弱，不支持不可变树，不支持 n_nearest_within，并且需要使用 Fixed 类型进行冗余包装；查询边界是排他的，这一点未在文档中说明，并且查询功能不如我们的 k_closest 功能丰富（通常只支持 k 个最近或所有在范围内，内部边界永远不支持，区域边界和查询也不支持），无法从树中检索点，导致数据重复，树不能用作映射，除非手动创建单独的向量，还有几个冗余的泛型参数）。

kd-tree 是另一个非常流行的 KD 树库。与 Kiddo 不同，它并不声称是最快的，而且与 Kiddo 不同，它似乎有一个非常可用且灵活的 API。它支持泛型点类型，虽然不支持泛型拓扑，但它也内置了对流行的性能库 Rayon 和 nalgebra 的支持。

这个包 是一个很好的优先队列选择，如果您不需要这个包的先进灵活性，或者需要一个更广泛采用和支持的库。我们的 Fibonacci 堆相当底层，最适合在顶部实现其他库，因为它们是针对在 KD 树上执行 A* 操作而创建的。

特性

KD 树可以使用任意拓扑结构（2D、3D+、笛卡尔、嵌入在球体/环面等的表面上）。

这是通过与 KdTree 结构相关联的几个特质来实现的。

• KdPoint：表示树中的点。实现此特质类型只需要具有两个方法

  • KdPoint::cmp：给定树的一个层，比较该层中的两个点。对于笛卡尔点，这就像获取 layer%dim 坐标一样简单，但如果点嵌入在例如球体的表面上，如果 layer 是奇数，则可以根据角度比较，如果 layer 是偶数，则可以根据经度比较。
  • KdPoint::sqdist：给定两个点，计算它们之间的平方距离。KdPoint 对其表示的点坐标的类型没有限制；它甚至不假设点是用坐标表示的。相反，唯一关联的类型是 KdPoint::Distance，它由 KdPoint::sqdist 返回，并且只需要是 Ord。

• KdRegion：表示整个树或某些子树的边界。实现此特质类型只需要有四个方法。它们应该能够表示单个点，但不一定需要能够表示空区域（它被包装在 Option 中），并且如果区域高估其大小（例如，它可以为 min_sqdist 返回一个比真实值小的数字，但不能返回一个比真实值大的数字），则没有关系。

  • KdRegion::split：给定一个区域、区域内的一个点以及树中的一个层，将区域根据该层中的点分割成两个子区域。例如，如果KD树是二维笛卡尔坐标系，偶数层可能水平分割，奇数层垂直分割。一般而言，这可能涉及到用线/平面/超平面切割区域，或者将凸集分割成两个凸部分。树的外部边界被显式存储，但每个子树的边界在遍历时松散计算（即它们通常是高估的）。
  • KdRegion::single_point：从一个单点创建一个区域
  • KdRegion::extend：扩展一个区域，使其包含一个额外的点。通常，区域将是轴对齐包围盒（AABB），因此实现起来非常简单，但在一般情况下可能更复杂。
  • KdRegion::min_sqdist：返回一个小于等于给定点与此区域之间最小距离的数字。特别是，对于区域内部的点，如由 single_point 和 extend 添加的点，必须返回 0（或小于等于其他任何返回值）。通常，区域是凸的，所以如果适用，内部点的线性组合也在区域内。不在区域内的点应理想地返回大于0，以便尽可能剪枝，但不能大于它们的实际距离，否则搜索可能会出错。

这些默认实现也适用于任意维度和（几乎）任何坐标类型的笛卡尔KD树：CuPoint 和 CuRegion。

外部Crates

num-traits：这个crate绝对不是数值预演（Haskell），但它是在不添加200+个类型边界的情况下创建数学泛型特质的救星，这些类型边界与重载不同引用类型的不同排列的数值运算符有关。没有它基本上不可能重载这些运算符。 rand：C++有一个内置的rand库，但Rust没有，这非常奇怪。Rust通常在决定什么应该或不应该进入语言方面做出了更好的决定。话虽如此，这个随机数crate非常强大和优秀，甚至比Quickcheck（Haskell）还要好。重载 Uniform 随机分布来泛型生成 CuPoint<T, N> 仅需30秒。