草庐IT

c++ - 预测 kD 树中所需的预分配节点数

coder 2024-02-25 原文

我正在以广度优先的方式在数组表示中实现动态kD-Tree(将节点存储在 std::vector 中)。每个i -th 非叶节点在 (i<<1)+1 处有一个左子节点和一个合适的 child 在(i<<1)+2 .它将支持点的增量插入和点的集合。 但是，我在确定增量预分配空间所需的可能节点数时遇到了问题。

我找到了 formula on the web ，这似乎是错误的:

N = min(m − 1, 2n − ½m − 1),

where m is the smallest power of 2 greater than or equal to n, the number of points.

我对公式的实现如下:

size_t required(size_t n)
{
    size_t m = nextPowerOf2(n);
    return min(m - 1, (n<<1) - (m>>1) - 1);
}

函数 nextPowerOf2 返回最大或等于 n 的 2 的幂

如有任何帮助，我们将不胜感激。

最佳答案

kd-tree的每个节点将空间分成两个空间。因此，kd 树中的节点数取决于您如何执行此划分:

1)如果你在空间的中点划分它们(也就是说，如果空间是从x1到x2，你用x3=(x1+x2)/2线划分空间)，那么: i) 每个点将被分配到它自己的节点，并且 ii) 每个中间节点都是空的。

在这种情况下，节点的数量将取决于点的坐标有多大。如果坐标以 |X| 为界，则 kd-tree 中的节点总数应略小于 log |X| * n(更准确地说，大约 log |X| * n - n log n + 2n)在最坏的情况下。要看到这一点，请考虑以下添加点的方式:添加多个集合，每个集合有两个随机分布的非常接近的点。对于每一对点，树将需要连续划分空间日志 |X|次，如果记录 |X|明显大于 log n，创建 log |X|过程中的中间节点。

2) 如果用一个点作为分界线来划分它们，那么每个节点(包括中间节点)都会包含一个点。因此，节点总数就是 n。但是，请注意，如果点不是以随机顺序给出(例如，如果点按 X 的升序给出，则树的深度将为O(n)。为了比较，(1)中树的深度至多为O(log |X|))。

关于c++ - 预测 kD 树中所需的预分配节点数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31123012/

点数ampsectioncode的c++geometrycomputer-sciencecomputational-geometrykdtree

有关c++ - 预测 kD 树中所需的预分配节点数的更多相关文章

  1. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  2. Ruby Koans about_array_assignment - 非平行与平行分配歧视 - 2

    通过ruby​​koans.com，我在about_array_assignment.rb中遇到了这两段代码你怎么知道第一个是非并行赋值，第二个是一个变量的并行赋值？在我看来，除了命名差异之外，代码几乎完全相同。4deftest_non_parallel_assignment5names=["John","Smith"]6assert_equal["John","Smith"],names7end45deftest_parallel_assignment_with_one_variable46first_name,=["John","Smith"]47assert_equal'John

  3. ruby - 在 Ruby 中重新分配常量时抛出异常？ - 2

    我早就知道Ruby中的“常量”(即大写的变量名)不是真正常量。与其他编程语言一样，对对象的引用是唯一存储在变量/常量中的东西。(侧边栏:Ruby确实具有“卡住”引用对象不被修改的功能，据我所知，许多其他语言都没有提供这种功能。)所以这是我的问题:当您将一个值重新分配给常量时，您会收到如下警告:>>FOO='bar'=>"bar">>FOO='baz'(irb):2:warning:alreadyinitializedconstantFOO=>"baz"有没有办法强制Ruby抛出异常而不是打印警告？很难弄清楚为什么有时会发生重新分配。 最佳答案

  4. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  5. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  6. ruby - 使对象的行为类似于 ruby​​ 中并行分配的数组 - 2

    假设您在Ruby中执行此操作:ar=[1,2]x,y=ar然后，x==1和y==2。是否有一种方法可以在我自己的类中定义，从而产生相同的效果？例如rb=AllYourCode.newx,y=rb到目前为止，对于这样的赋值，我所能做的就是使x==rb和y=nil。Python有这样一个特性:>>>classFoo:...def__iter__(self):...returniter([1,2])...>>>x,y=Foo()>>>x1>>>y2 最佳答案 是的。定义#to_ary。这将使您的对象被视为要分配的数组。irb>o=Obje

  7. 即使安装了 gem，Ruby 也找不到所需的库 - 2

    我花了几天时间尝试安装ruby​​1.9.2并让它与gems一起工作:-/我最终放弃了我的MacOSX10.6机器，下面是我的Ubuntu机器上的当前状态。任何建议将不胜感激!#rubytest.rb:29:in`require':nosuchfiletoload--mongo(LoadError)from:29:in`require'fromtest.rb:1:in`'#cattest.rbrequire'mongo'db=Mongo::Connection.new.db("mydb")#gemwhichmongo/usr/local/rvm/gems/ruby-1.9.2-p0/g

  8. ruby - Rails -- :id attribute? 所需的数据库索引 - 2

    因此，当我遵循MichaelHartl的RubyonRails教程时，我注意到在用户表中，我们为:email属性添加了一个唯一索引，以提高find的效率方法，因此它不会逐行搜索。到目前为止，我们一直在根据情况使用find_by_email和find_by_id进行搜索。然而，我们从未为:id属性设置索引。:id是否自动索引，因为它在默认情况下是唯一的并且本质上是顺序的？或者情况并非如此，我应该为:id搜索添加索引吗？ 最佳答案 大多数数据库(包括sqlite，这是RoR中的默认数据库)会自动索引主键，对于RailsMigration

  9. ruby-on-rails - 使用 Dragonfly 从 URL 分配图像 - 2

    我正在使用Dragonfly在Rails3.1应用程序上处理图像。我正在努力通过url将图像分配给模型。我有一个很好的表格:{:multipart=>true}do|f|%>RemovePicture?Dragonfly的文档指出:Dragonfly提供了一个直接从url分配的访问器:@album.cover_image_url='http://some.url/file.jpg'但是当我在控制台中尝试时:=>#ruby-1.9.2-p290>picture.image_url="http://i.imgur.com/QQiMz.jpg"=>"http://i.imgur.com/QQ

  10. arrays - Ruby 数组 += vs 推送 - 2

    我有一个数组数组，想将元素附加到子数组。+=做我想做的，但我想了解为什么push不做。我期望的行为(并与+=一起工作):b=Array.new(3,[])b[0]+=["apple"]b[1]+=["orange"]b[2]+=["frog"]b=>[["苹果"],["橙子"],["Frog"]]通过推送，我将推送的元素附加到每个子数组(为什么？):a=Array.new(3,[])a[0].push("apple")a[1].push("orange")a[2].push("frog")a=>[[“苹果”、“橙子”、“Frog”]、[“苹果”、“橙子”、“Frog”]、[“苹果”、“

随机推荐