问题标签 [range-tree]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
21 问题
0
投票
0
回答
33
浏览
algorithm - 在可以包含给定项目的盒子列表中找到最小的盒子
问题如下：给定一个 3d 项目和一个 3d 盒子列表，所有矩形长方体，找到可以包含给定项目的最小体积的盒子。只允许旋转 90 度的倍数。
一种解决方案是使用 3d 范围树。假设一个 3d 对象定义为具有 3 个维度(x, y, z)，其中维度已排序：x <= y <= z. 那么一个盒子(x1,y1,z1)可以包含一个项目(x2,y2,z2)if x1 >= x2, y1 >= y2, and z1 >= z2。因此，我们可以使用 3d 范围树来查找范围内的所有框{[x2, infinity], [y2, infinity], [z2, infinity]}并返回体积最小的框。有没有更好或更有效的解决方案？
注意 2：看起来这个问题可以归类为约束最近邻搜索，请参阅本文。