我很不擅长数学，但我需要找到所有靠近通过该空间的矢量射影的3D空间中的点。可以按任何算法所需的方式存储这些点，但我想不出任何特别有利的排序方法。是否有现成的C ++算法来完成此任务？如果有（或没有），它涉及哪种数学概念，因为我想试图理解它并将自己变成一个椒盐卷心酥。该算法将在可能包含100,000个点的空间中操作，需要测试约1,000,000个向量，并在1/30秒内完成这些向量。当然，我怀疑是否有任何算法能够完成功绩，但看看是否真的如此会很有趣。
在三维空间中寻找靠近向量的点
3
- Anne Quinn
4
只是出于好奇，你到底在做什么？ - Mike Bailey
@clairvoire - 抱歉，在 http://stackoverflow.com/questions/7136024/legality-of-emulating-a-technique-seen-in-a-tech-demo 的评论中我并不是有意要吓跑你，更不是要让你删帖。我应该更加圆滑一些。 （那个帖子已经被删除了，所以我只好在这里评论，因为我不能在那里回复）。 - msw
@msw - 嗯，那个问题超出了SO的范围，阅读与之相关的更多或少相同的问题所涉及的相关问题向我展示了这一点。你已经足够机智了，不用担心！ - Anne Quinn
@Mike - 我想尝试编写一个渲染器，它可以在空间中使用浮点数工作，类似于体素渲染器，但是点的位置不与3D网格对齐。被测试的向量对应于屏幕上的像素（因此估计为100万）。 - Anne Quinn
2个回答
4
您可能希望将点存储在某些空间数据结构中。我想到的有：
它们具有略微不同的属性。八叉树将整个世界划分为8个大小相等的立方体，组织成一个更大的立方体。然后将每个立方体分成 8 个大小均匀的立方体。您继续分割立方体，直到在一个立方体中的点数少于某个特定数量。使用这个树结构，您可以很容易地遍历树，并提取可能与给定立方体相交的所有点。一旦您获得了该点列表，就可以逐个测试这些点。由于测试几何结构是一个球体（距离一个点），因此您会在球体周围画一个正方体，并获取可能与其相交的点。作为优化，您还可以在圆圈内部绘制一个正方体，任何肯定与之相交的物体都可以立即包含在您的命中集合中。BSP树是一种二进制空间分割树，由三维平面组成的二叉树。使用这种方法的主要问题是在遍历时可能需要进行许多平方根运算才能找到平面的距离。原则上相同，当节点包含少于某个点数时，将创建一个带有这些点的叶子节点。BSP树中的所有叶子节点都是凸多边形（除了沿周长的叶子节点，它们将是无限大的多边形）。建立BSP时，您希望将每个步骤中的点分成两半，以获得真正的O（log n）搜索。
kd树是BSP的一种特殊情况，其中所有平面都与坐标轴对齐。这通常会显着加速对它们的测试，但不允许您根据点集优化平面。
我不知道任何C ++库实现这些功能，但我确定这里有很多。这些都是游戏中常用的技术，因此您可能需要查看游戏引擎。
- Arvid
1
谢谢！我会看看这三个，但我必须说我对八叉树相当着迷。为了优化起见，在检查接近性时，我也可以仅检查点是否在轴向正方形的范围内，而不是圆形。具有讽刺意味的是，这实际上会产生更准确的结果。 - Anne Quinn
1
当你把八叉树看作一条曲线时，可能会有助于你理解它是如何填充空间的，只经过每个坐标一次且不交叉。这条曲线将三维复杂性映射到一维复杂性。其中有一些怪物曲线，例如z曲线、希尔伯特曲线和摩尔曲线。后者是4个希尔伯特曲线的副本，并具有非常好的空间填充质量。但是，最近点的搜索不是使用迪杰斯特拉算法解决的吗？
- Micromega
1
查找那个特定的算法，我认为不需要。只有在需要有效地给向量赋予宽度时，才需要找到靠近向量的点，因为没有宽度的向量否则永远不会与完美微小的点相交。我认为八叉树作为广义相位是非常有用的，当测试要具体测试哪些点时。 - Anne Quinn
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接