在 3D 空间中搜索靠近向量的点
我的数学很糟糕，但我遇到了一种情况，我需要找到 3D 空间中任意接近通过同一空间投影的向量的所有点。这些点可以以算法要求的任何方式存储，但我无法想到对它们有任何特别有利的排序。
是否有任何现有的 C++ 算法可以实现此功能？如果是这样（或不是），它会涉及什么样的数学概念，因为我很想尝试理解它并将我的大脑绑在椒盐卷饼上。
（这个算法将在一个可能有 100,000 个点的空间上运行，它需要测试大约 1,000,000 个向量，并且需要在 1/30 秒内完成这些向量。我当然怀疑是否有任何算法可以完成这项壮举无论如何，但看看这是否属实会很有趣）。
I'm terrible with math, but I have a situation where I need to find all points in a 3D space that are arbitrarily close to a vector being projected through that same space. The points can be stored in any fashion the algorithm calls for, not that I can think of any particularly beneficial ordering for them.
Are there any existing C++ algorithms for this feat? And if so (or not), what kind of mathematical concept does or would it entail, since I'd love to attempt to understand it and tie my brain into a pretzel.
( This algorithm would be operating on a space with perhaps 100,000 points in it, it would need to test around 1,000,000 vectors, and need to complete those vectors within 1/30th of a second. I of course doubt if any algorithm can perform this feat at all, but it'll be fun to see if that's true or not. )
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您可能希望将点存储在某种空间数据结构中。我想到的是：
它们的属性略有不同。八叉树将整个世界分成 8 个大小相等的立方体，这些立方体各自组织成一个更大的立方体。然后将每个立方体依次分成 8 个大小均匀的立方体。你不断地分裂立方体，直到立方体中的点数少于一定数量。通过这种树结构，您可以非常轻松地遍历树，提取可能与给定立方体相交的所有点。一旦你有了要点列表，你就可以一次测试一个。由于您的测试几何体是一个球体（距点的距离），您将在球体周围外接一个立方体并获取可能与其相交的点。作为一种优化，您还可以在您的圆圈中刻入一个立方体，以及任何肯定与它相交的东西，您可以立即将其包含在您的命中集中。
BSP 树是一个二元空间分区树。它是 3 空间中的平面树，形成二叉树。使用它来解决您的问题的主要问题是，您可能需要在遍历它时进行大量平方根，才能找到到平面的距离。不过原理是一样的，一旦你的点少于一定数量，你就会形成一片叶子，其中包含这些点。 BSP 树中的所有叶子都是凸多边形（沿着周边的叶子除外，它们将是无限大的多边形）。构建 BSP 时，您希望将每个步骤的点分成两半，以真正获得 O(log n) 搜索。
kd 树是 BSP 的特例，其中所有平面都是轴对齐的。这通常会显着加快针对它们的测试速度，但也不允许您根据一组点来优化飞机。
我不知道有任何 C++ 库可以实现这些，但我确信有很多。这些是视频游戏中相当常见的技术，因此您可能需要查看游戏引擎。
You would probably want to store your points in some spatial data structure. The ones that come to mind are:
They have slightly different properties. An oct-tree divides the entire world up into 8 equally sized cubes, organized to themselves form a larger cube. Each of these cubes are then in turn split into 8, evenly sized, cubes. You keep splitting the cubes until you have less than some number of points in a cube. With this tree structure, you can quite easily traverse the tree, extracting all points that may intersect a given cube. Once you have that list of points, you can test them one at a time. Since your test geometry is a sphere (distance from a point) you would circumscribe a cube around the sphere and get the points that may intersect it. As an optimization, you may also inscribe a cube in your circle, and anything that for sure intersects that, you can simply include in your hit-set right away.
The BSP tree is a Binary space partitioning tree. It's a tree of planes in 3-space, forming a binary tree. The main problem of using this for your problem is that you might have to do a lot of square roots while traversing it, to find the distance to the planes. The principle is the same though, once you have fewer than some number of points you form a leaf with those points in it. All leaves in a BSP tree are convex polygons (except for the leaves that are along the perimeter, which will be infinitely large polygons). When building the BSP, you want to split the points in half for each step, to truly get O(log n) searches.
The kd-tree is a special case of BSP, where all planes are axis aligned. This typically speeds up tests against them quite significantly, but doesn't allow you to optimize the planes based on your set of points quite as well.
I don't know of any c++ libraries that implement these, but I'm sure there are plenty of them. These are fairly common techniques used in video games, so you might want to look at game engines.
当您可以将八叉树视为一条曲线，该曲线填充仅遍历每个坐标一次且不交叉自身的空间时，它可能会帮助您理解八叉树。该曲线将 3d 复杂性映射到 1d 复杂性。有一些这种怪物曲线，如 z 曲线、希尔伯特曲线和摩尔曲线。后者是 4 条希尔伯特曲线的副本，具有非常好的空间填充质量。但是寻找最近点不是用dijkstra算法解决的吗？
It might help your understanding of octrees when you can think of it as a curve that fills the space traversing every coordinate only once and w/o crossing itself. The curve maps the 3d complexity to a 1d complexity. There are some of this monster curve, like the z curve, the hilbert curve, and the moore curve. The latter is a copy of 4 hilbert curves and has very good space fills quality. But isn't a search for the closest points not solved with dijkstra algorithm?