快速空间划分启发式算法？

Question

我有一个由N条线段组成的（子）空间，这些线段总是属于一个凸多边形。它可能看起来像这样：

我想做的是开发一种启发式算法来选择分割空间的线段。选定的线段支撑线将会分割空间。有两个启发式因素相互作用:

1. 线段应该均匀地分割空间; 当完成时，子空间A中应该有与子空间B中一样多的线段 (平衡)
2. 线段的支撑线应该尽可能少地与其他线段相交 (分割) (自由)

一个例子:

蓝线: 完美自由，非常糟糕的平衡。

红线: 非常糟糕的自由，平庸的平衡。

绿线: 糟糕的自由，优秀的平衡。

紫线: 良好的自由，相当平衡。

在上面的例子中，综合启发式可能会选择紫线。

现在，我可以遍历每个线段并将其与每个其他线段进行比较（查看它们相交的方式以及它们在每侧的平衡情况）。但这需要O(N^2)操作。我更喜欢能在O(N log N)中运行的算法。

有没有关于循环遍历线段并给它们打分的O(N log N)算法的想法？我想到的一个想法是三次对线段进行排序并形成一些象限：

象限中心提供了大多数线段所在位置的想法。因此，可以使用它们来查找靠近此中心的线段，并检查其方向是否与象限相符。以某种方式。这将给出一个不错的平衡分数。

对于交叉点，我考虑为线段创建边界框并将其排序到树中，从而可能加快交叉估计速度？

一些额外的提示（我的输入数据大部分时间看起来像什么）

1. 大多数线段是轴向的（纯X或Y方向）
2. 大多数线段与其传播相比较小。

感谢任何新的想法或见解-最小的数据结构或策略提示都会有很大帮助！

- bombax

---

看起来像是二叉空间分割树问题。不太记得有什么启发式算法适用于此。对于kd树，有一种常见的叫做SAH（表面积启发式）的算法。它可以让你了解成本函数在细分过程中如何寻找最优解的相关思路。 - Nicko Po

是的，它是用于BSP构建的。不过那里提供了有用的数据结构指示，谢谢！ - bombax

在你的算法中，你是否关心线的方向？如果是用于BSP构建，则感觉后续线的方向不应该独立选择。你可能希望每条下一条线与前一次选择更或多或少垂直。这正确吗？ - Tomasz Lenarcik

Answer 1

解决方案

我发现了一个对于我的BSP树目的非常有效的启发式算法，同时也非常有趣。在下面的代码中，我首先尝试使用AABB树来询问“这条线段与哪些线段相交”。但即使如此，速度仍然太慢，因此最终我选择了一种昂贵的初始O(N^2)比较算法，随着BSP树的构建，它会快速加速，利用了一些巧妙的观察！

• 让每个BSP节点跟踪其子空间中仍留在其中的线段（以及必须从中选择下一个分割器的线段）。
• 让每个线段有四个与之关联的值：posCount、negCount、introduced和saved。如果该线段被分割，则还应具有对另一个线段的partner引用（否则为null）。
• 使用以下O(N^2)算法初始化根节点（即所有节点）的分割器：

算法calcRelationCounts(splitters S)：O(N^2)

for all splitters s in S
    s.posCount = s.negCount = s.introduced = s.saved = 0
    for all splitters vs in S
        if (s == vs) continue
        if vs is fully on the positive side of the plane of s
            s.posCount++
        else if vs is fully on the negative side of the plane of s
            s.negCount++
        else if vs intersects the plane of s
            s.negCount++, s.posCount++, s.introduced++
        else if vs is coplanar with s
            s.saved++

• 对于仍有分裂器的每个节点，选择最大化以下内容的节点：

算法evaluate(...)，其中treeDepth = floor(log2(splitterCountAtThisNode))：O(1)

evaluate(posCount, negCount, saved, introduced, treeDepth) {
    float f;
    if (treeDepth >= EVALUATE_X2) {
        f = EVALUATE_V2;
    } else if (treeDepth >= EVALUATE_X1) {
        float r = treeDepth - EVALUATE_X1;
        float w = EVALUATE_X2 - EVALUATE_X1;
        f = ((w-r) * EVALUATE_V1 + r * EVALUATE_V2) / w;
    } else {
        f = EVALUATE_V1;
    }

    float balanceScore = -f * BALANCE_WEIGHT * abs(posCount - negCount);
    float freedomScore = (1.0f-f) * (SAVED_WEIGHT * saved - INTRO_WEIGHT * introduced);
    return freedomScore + balanceScore;
}

以下是我的优化算法使用的魔数：

#define BALANCE_WEIGHT 437
#define INTRO_WEIGHT 750
#define SAVED_WEIGHT 562
#define EVALUATE_X1 3
#define EVALUATE_X2 31
#define EVALUATE_V1 0.0351639f
#define EVALUATE_V2 0.187508f

• 使用此分裂器作为此节点的分裂器，将其称为SEL。然后，将此节点中的所有分裂器分成三组：positives、negatives 和 remnants。

算法 distributeSplitters()：

for all splitters s at this node
    s.partner = null
    if s == SEL then add s to "remnants"
    else
        if s is fully on the positive side of SEL
            add s to "positives"
        else if s is fully on the negative side of SEL
            add s to "negatives
        else if s intersects SEL
            split s into two appropriate segments sp and sn
            sp.partner = sn, sn.partner = sp
            add sn to "negatives", sp to "positives" and s to "remnants"
        else if s coplanar with SEL
            add s to "remnants"

// the clever bit
if (positives.size() > negatives.size())
    calcRelationCounts(negatives)
    updateRelationCounts(positives, negatives, remnants)
else
    calcRelationCounts(positives)
    updateRelationCounts(negatives, positives, remnants)

add positives and negatives to appropriate child nodes for further processing

我意识到的巧妙之处是，通常，尤其是以上启发式算法的前几个拆分，会产生非常不平衡的拆分（但非常自由）。问题在于，当n很小的时候，您得到的是"O(N^2) + O((N-n)^2)" + ...，这是可怕的！相反，我意识到我们可以重新计算需要O(n^2)的最小拆分长度，然后只需迭代每个位拆分分隔器，并从较小的拆分部分中减去计数，这只需要O(Nn)，比O(N^2)好得多！以下是updateRelationCounts()的代码：

算法updateRelationCounts()：

updateRelationCounts(toUpdate, removed, remnants) {
    for all splitters s in toUpdate
            for all splitters vs in removed, then remnants
                if vs has a partner
                    if the partner intersects s
                        s.posCount++, s.negCount++, s.introduced++
                    else if the partner is fully on the positive side of s
                        s.posCount++
                    else if the partner is fully on the negative side of s
                        s.negCount++
                    else if the partner is coplanar with s
                        s.saved++
                else
                    if vs intersects s
                        s.posCount--, s.negCount--, s.introduced--
                    else if vs is fully on the positive side of s
                        s.posCount--
                    else if vs is fully on the negative side of s
                        s.negCount--
                    else if vs is coplanar with s
                        s.saved--

我现在已经仔细测试过了，似乎逻辑是正确的，更新操作正确地修改了posCount等变量，使它们与重新硬计算后的结果相同！

- bombax