假设我有一组 D 维的 N 轴对齐超长方体。
每个超长方体都有一个顶点在原点，一个顶点在正轴(即所有坐标严格为正)。后一个顶点定义了超立方体，因此超立方体的集合可以由一组顶点给出，每个超立方体一个。
您可能会认为我已经从超长方体列表中删除了任何严格包含在另一个超长方体中的超长方体。 (目前我正在通过一个朴素的 O(N^2*D) 算法来做到这一点。附带问题:我可以做得更好吗？)
我需要找到所有超长方体的并集的顶点，不包括具有一个或多个零坐标的任何顶点。
在二维中，有 N-1 个这样的顶点，可以通过在一个(任意)坐标上对顶点进行排序来有效地找到它们，即在 O(N log(N)) 中。
D 维中有多少个这样的顶点？ (有两个立方体，似乎只有一个新顶点，所以可能还是 N-1？)我怎样才能有效地找到那些顶点？
最佳答案
一些缩写:Hj 表示“Hipercuboid j”，并且在原点处有一个顶点，在 {xi, yi, zi, wi, etc} 处有一个顶点。
如果 Hi 包含在 Hj 中，则 xi<=xj 、 yi<=yj 、 zi<=zj 等等。
如果你有 D 排序列表坐标，每个维度一个，那么通过简单查询坐标索引就可以很容易地检查 Hi 是否在 Hj 内部:posXi<posXj 和 posYi<posYj 和 posZi<posZj 等. 注意条件是“和”，而不是“或”。
如果某些 Hi 不遵守所有 Hj 的“与”规则，则顶点 i 是一个新顶点。
如果某个坐标 T 是“out”: posTi > posTlast 那么顶点 i 是一个新的顶点。
关于在非负立方体中找到轴对齐超立方体并集的顶点的算法，所有顶点都在原点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/56045395/