algorithm - 快速空间分区启发式？

Question

我有一个(子)空间，其中填充了 N 线段。这些线段始终是凸多边形的一部分。它可能看起来像这样:

我想做的是开发一种启发式方法来选择用于分割空间的线段。所选线段的支撑线将分割空间。有两个相互矛盾的启发式因素:

1. 线段要平分空间；完成后，子空间 A 中的线段数量应与子空间 B 中的线段数量相同(balance)
2. 线段的支撑线应与(拆分)尽可能少的其他线段相交(自由)

一个例子:

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

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

绿线:自由度差，平衡性好。

紫线:良好的自由度，体面的平衡。

在上面的示例中，组合启发式可能会选择紫色线。

现在我可以遍历每个线段并将其与其他所有线段进行比较(查看它与哪些线段相交以及它们在每一侧的平衡程度)。但这需要 O(N^2) 操作。我更喜欢在 O(N log N) 中运行的东西。

关于遍历线段并给它们打分的 O(N log N) 算法有什么想法吗？我的一个想法是对这些段进行三次排序并形成一些象限:

象限中心给出了大多数线段所在的位置。因此，也许可以使用它们在该中心附近找到一条线段，并检查其相对于象限的方向是否正确。不知何故。这会给出一个不错的平衡分数。

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

一些额外的提示(很多时候我的输入数据看起来像什么)

1. 大多数段是轴向的(纯 X 或 Y 方向)
2. 与其分布相比，大多数分割市场都很小。

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

Answer 1

解决方案

我发现了一种启发式算法，它非常适合我的 BSP 树用途，而且分析起来也非常有趣。在下面的代码中，我首先尝试使用 AABB 树来询问“这条线与哪些线段相交”。但即使这样也太慢了，所以最后我只是采用了一个代价高昂的初始 O(N^2) 比较算法，该算法随着 BSP 树的构建而快速加速，使用了一个有点聪明的观察!

• 让每个 BSP 节点跟踪它仍留在其子空间内的线段(以及它必须从中选择下一个拆分器)。
• 让每个段有四个与之关联的值:posCount、negCount、introduced 和saved。让它也有一个对另一个片段的 partner 引用，以防它被拆分(否则它是 null)。
• 使用以下 O(N^2) 算法初始化根节点处的拆分器(即所有拆分器):

算法 calcRelationCounts(splitter 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;
}

我的优化算法使用了以下魔数(Magic Number):

#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。然后，将该节点处的所有 split 器分为三组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

我在这里意识到的聪明之处在于，通常，尤其是使用上述启发式方法进行的前几次拆分，会产生非常不平衡的拆分(但非常自由)。问题是你得到 "O(N^2) + O((N-n)^2)"+ ... 当 n 很小的时候，这是可怕的!相反，我意识到不这样做，我们可以硬重新计算最小的拆分，它采用 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 等，这样它们就和硬的时候一样了-再次计算!