logo标签列表

使用Barnes-Hut算法进行图形布局时的优化问题

c++algorithmgraph
4
我一直在尝试解决我的图形可视化应用程序中的力导向图/巴恩斯-哈特问题。 我已经检查了八叉树创建，看起来正确（树由框表示，圆圈是我的图形节点）： Quadtree test 我的Quadtree中的字段如下：
class Quadtree
{
    public:
        int level;
        Quadtree* trees[2][2][2];
        glm::vec3 vBoundriesBox[8];
        glm::vec3 center;
        bool leaf;
        float combined_weight = 0;
        std::vector<Element*> objects;
        //Addition methods/fields
    private:
    //Additional methods/fields
    protected:
}

这是我如何递归地将元素添加到我的四叉树中:
#define MAX_LEVELS 5

void Quadtree::AddObject(Element* object)
{
    this->objects.push_back(object);
}

void Quadtree::Update()
{
    if(this->objects.size()<=1 || level > MAX_LEVELS)
    {
        for(Element* Element:this->objects)
        {
            Element->parent_group = this;
            this->combined_weight += Element->weight;
        }
        return;
    }

    if(leaf)
    {
        GenerateChildren();
        leaf = false;
    }

    while (!this->objects.empty())
    {
        Element* obj = this->objects.back();
        this->objects.pop_back();
        if(contains(trees[0][0][0],obj))
        {
            trees[0][0][0]->AddObject(obj);
            trees[0][0][0]->combined_weight += obj->weight;
        } else if(contains(trees[0][0][1],obj))
        {
            trees[0][0][1]->AddObject(obj);
            trees[0][0][1]->combined_weight += obj->weight;
        } else if(contains(trees[0][1][0],obj))
        {
            trees[0][1][0]->AddObject(obj);
            trees[0][1][0]->combined_weight += obj->weight;
        } else if(contains(trees[0][1][1],obj))
        {
            trees[0][1][1]->AddObject(obj);
            trees[0][1][1]->combined_weight += obj->weight;
        } else if(contains(trees[1][0][0],obj))
        {
            trees[1][0][0]->AddObject(obj);
            trees[1][0][0]->combined_weight += obj->weight;
        } else if(contains(trees[1][0][1],obj))
        {
            trees[1][0][1]->AddObject(obj);
            trees[1][0][1]->combined_weight += obj->weight;
        } else if(contains(trees[1][1][0],obj))
        {
            trees[1][1][0]->AddObject(obj);
            trees[1][1][0]->combined_weight += obj->weight;
        } else if(contains(trees[1][1][1],obj))
        {
            trees[1][1][1]->AddObject(obj);
            trees[1][1][1]->combined_weight += obj->weight;
        }
    }

    for(int i=0;i<2;i++)
    {
        for(int j=0;j<2;j++)
        {
            for(int k=0;k<2;k++)
            {
                trees[i][j][k]->Update();
            }
        }
    }
}

bool Quadtree::contains(Quadtree* child, Element* object)
{
    if(object->pos[0] >= child->vBoundriesBox[0][0] && object->pos[0] <= child->vBoundriesBox[1][0] &&
       object->pos[1] >= child->vBoundriesBox[4][1] && object->pos[1] <= child->vBoundriesBox[0][1] &&
       object->pos[2] >= child->vBoundriesBox[3][2] && object->pos[2] <= child->vBoundriesBox[0][2])
        return true;
    return false;
}

如您所见，图片上的节点非常密集。我一直在尝试寻找修复斥力计算方法的途径，但仍然无法解决问题，结果还是一样。

那么我是如何计算的呢：

首先，在我的主文件中，我通过循环运行所有图形节点：

for(auto& n_el:graph->node_vector)
{
    tree->CheckNode(&n_el);
}

在我的Qyadtree类中，(tree是该类的对象)，我有这个递归方法:
void Quadtree::CheckNode(Node* node)
{
    glm::vec3 diff = this->center - node->pos;

    double distance_sqr = (diff.x * diff.x) + (diff.y*diff.y) + (diff.z*diff.z);
    double width_sqr = (vBoundriesBox[1][0] - vBoundriesBox[0][0]) * (vBoundriesBox[1][0] - vBoundriesBox[0][0]);
    if(width_sqr/distance_sqr < 10.0f || leaf)
    {
        if(leaf)
        {
            for(auto& n: objects)
            {
                n->Repulse(&objects);
            }
        }
        else
        {
            node->RepulseWithGroup(this);
        }
    }
    else
    {
        for(int i=0; i<2; i++)
        {
            for(int j=0; j<2; j++)
            {
                for(int k=0; k<2; k++)
                {
                    trees[i][j][k]->CheckNode(node);
                }
            }
        }
    }
}

最后，我有两种方法可以计算排斥力，具体取决于它是在组和节点之间还是在两个节点之间：

double Node::Repulse(std::vector<Node*>* nodes)
{
    double dx;
    double dy;
    double dz;
    double force = 0.0;
    double distance_between;
    double delta_weights;
    double temp;
    for(auto& element_node:*nodes)
    {
        if(this->name == element_node->name)
        {
            continue;
        }
        if(!element_node->use) continue;
        delta_weights = 0.5 + abs(this->weight - element_node->weight);
        dx = this->pos[0] - element_node->pos[0];
        dy = this->pos[1] - element_node->pos[1];
        dz = this->pos[2] - element_node->pos[2];
        distance_between = dx * dx + dy * dy + dz * dz;
        force = 0.19998 * delta_weights/(distance_between * distance_between);
        temp = std::min(1.0, force);
        if(temp<0.0001)
        {
            temp = 0;
        }
        double mx = temp * dx;
        double my = temp * dy;
        double mz = temp * dz;
        this->pos[0] += mx;
        this->pos[1] += my;
        this->pos[2] += mz;
        element_node->pos[0] -= mx;
        element_node->pos[1] -= my;
        element_node->pos[2] -= mz;
    }
}

void Node::RepulseWithGroup(Quadtree* tree)
{
    double dx;
    double dy;
    double dz;
    double force = 0.0;
    double distance_between;
    double delta_weights;
    double temp;

    delta_weights = 0.5 + abs(this->weight - tree->combined_weight);
    dx = this->pos[0] - tree->center.x;
    dy = this->pos[1] - tree->center.y;
    dz = this->pos[2] - tree->center.z;
    distance_between = dx * dx + dy * dy + dz * dz;
    force = 0.19998 * delta_weights/(distance_between * distance_between);
    temp = std::min(1.0, force);
    if(temp<0.0001)
    {
        temp = 0;
    }
    double mx = temp * dx;
    double my = temp * dy;
    double mz = temp * dz;
    this->pos[0] += mx + this->parent_group->repulsion_force.x;
    this->pos[1] += my + this->parent_group->repulsion_force.y;
    this->pos[2] += mz + this->parent_group->repulsion_force.z;
}

如果这个想法：

if(width_sqr/distance_sqr < 10.0f || leaf)
    {
        if(leaf)
        {
            for(auto& n: objects)
            {
                n->Repulse(&objects);
            }
        }
        else
        {
            node->RepulseWithGroup(this);
        }
    }

如果不清楚，可能是因为我已经发现一个树叶中可能会有多个元素。如果已经达到了最大层数，但仍然有元素在一个框里，则还需要计算盒内与节点内部之间的力。
让我更烦恼的是这种方法的速度（并且它表明八叉树没有正常工作）是速度。这是表示时间/节点数量的简单图： Plot 据我所知，原始的强制定向图算法具有复杂度O(n^2)，但是通过Barnes-Hut，它应该是O(nlogn)。然而，这个图形甚至没有接近nlogn。
有人能告诉我我在这里做错了什么吗？我已经看了这段代码很长时间了，但我不知道我错过了什么。
编辑：
基于@Ilmari Karonen的答案，我对MAX_LEVELS进行了5、20、50、100的测试。结果如下。我想说似乎没有实质性的区别（不幸的是） times
1个回答
3

就我个人而言，

#define MAX_LEVELS 5

似乎非常低。你可能只是在八叉树中运行出深度，导致你的算法退化成O（n²）直接求和。您可以尝试将MAX_LEVELS增加到更高的值（至少为10或20），看看是否会提高性能。
我没有测试过您的代码，因此无法确定这是否是真正的问题或唯一的问题。但这绝对是我首先检查的问题。
仔细查看您的代码，我还发现了其他一些潜在问题。虽然严格来说可能不会影响性能，但它们可能会影响结果的正确性。
首先，在您的Quadtree类中有一个center向量，可能表示子树内节点的质心，但您似乎从未在添加节点到树中时更新该向量。由于您使用该向量进行计算，因此可能会由于此而产生错误结果。
（实际上，由于您使用center向量的一件事是计算节点与子树之间的距离，并决定是否进一步进入子树，因此这也可能破坏您的性能。）
另外，您似乎正在遍历树时直接更新位置，这意味着由算法生成的轨迹将取决于节点遍历和树展开的顺序。为了获得更一致和可重复的结果，您可能希望首先计算每个节点在当前迭代中的位移，将其存储在单独的向量中，然后再对节点运行第二遍以将位移添加到它们的位置（并将其重置为下一个迭代）。
此外，你的类名为Quadtree却实现了八叉树，我肯定不是唯一一个感到困扰的人吧？ :)
非常感谢您提供的所有建议！我已经运行了额外的测试并更新了我的问题。至于您的其余建议：1）我需要检查计算质心的方法。2）这是个好主意。我需要测试一下，因为现在想起来确实可能会引起一些问题。3）我同意名称不是100％正确，但那只是因为我当时正在阅读关于四叉树的内容，后来完全忘记更改名称 :) - sebap123
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接