c - C 递归中的 Barnes-Hut N-Body

Question

我正在为一个类的 n 体问题创建 barnes-hut 算法。

我正在构建树，如下所示，但是在第一次迭代之后，在第一次递归时，它应该将包含主体的节点分割开来。它似乎做得很好，但我遇到了一个问题， body 似乎在正确的象限中，但算法并没有把它们放在那里。有人可以看一下吗？我要疯了，这可能是因为我对 C 编程还比较陌生。象限按顺时针顺序排列。

struct Node * buildBHTree(double xmin, double xmax, double ymin, double ymax, struct Body *listOfBodies)
{
if (listOfBodies == NULL)
{
    return 0;
}
else if (listOfBodies->next == NULL)
{
    struct Node *singleNode = (struct Node *) malloc(sizeof(struct Node));
    initNewNode(singleNode);
    singleNode->xmin = xmin;
    singleNode->xmax = xmax;
    singleNode->ymin = ymin;
    singleNode->ymax = ymax;
    singleNode->body = listOfBodies;
    //calculateCenterOfMassForNode(singleNode);
    return singleNode;
}
else
{
    struct Node *list1 = (struct Node *) malloc(sizeof(struct Node));
    initNewNode(list1);
    list1->xmin = (xmin + xmax)/2;
    list1->xmax = xmax;
    list1->ymin = (ymin + ymax)/2;
    list1->ymax = ymax;

    struct Node *list2 = (struct Node *) malloc(sizeof(struct Node));
    initNewNode(list2);
    list2->xmin = (xmin + xmax)/2;
    list2->xmax = xmax;
    list2->ymin = ymin;
    list2->ymax = (ymin + ymax)/2;

    struct Node *list3 = (struct Node *) malloc(sizeof(struct Node));
    initNewNode(list3);
    list3->xmin = xmin;
    list3->xmax = (xmin + xmax)/2;
    list3->ymin = ymin;
    list3->ymax = (ymin + ymax)/2;

    struct Node *list4 = (struct Node *) malloc(sizeof(struct Node));
    initNewNode(list4);
    list4->xmin = xmin;
    list4->xmax = (xmin + xmax)/2;
    list4->ymin = (ymin + ymax)/2;
    list4->ymax = ymax;

    //printf("xpos: %f | ypos: %f\n", listOfBodies->pos_x, listOfBodies->pos_y);
    printf("QUADRANT 1: xmin: %f | xmax: %f | ymin: %f | ymax: %f\n", list1->xmin, list1->xmax, list1->ymin, list1->ymax);
    printf("QUADRANT 2: xmin: %f | xmax: %f | ymin: %f | ymax: %f\n", list2->xmin, list2->xmax, list2->ymin, list2->ymax);
    printf("QUADRANT 3: xmin: %f | xmax: %f | ymin: %f | ymax: %f\n", list3->xmin, list3->xmax, list3->ymin, list3->ymax);
    printf("QUADRANT 4: xmin: %f | xmax: %f | ymin: %f | ymax: %f\n", list4->xmin, list4->xmax, list4->ymin, list4->ymax);

    struct Body *rootBodyReference = (struct Body *) malloc(sizeof(struct Body));
    rootBodyReference = listOfBodies;
    while (listOfBodies->next != NULL)
    {
        //QUADRANT 1
        if (listOfBodies->pos_x >= list1->xmin &&
            listOfBodies->pos_x <= list1->xmax &&
            listOfBodies->pos_y >= list1->ymin &&
            listOfBodies->pos_y <= list1->ymax)
        {
            printf("FOUND IN QUADRANT 1\n");
            addBodyToLinkedList(list1, listOfBodies);
        }
        //QUADRANT 2
        else if (listOfBodies->pos_x >= list2->xmin &&
                 listOfBodies->pos_x <= list2->xmax &&
                 listOfBodies->pos_y <= list2->ymin &&
                 listOfBodies->pos_y >= list2->ymax)
        {
            printf("FOUND IN QUADRANT 2\n");
            addBodyToLinkedList(list2, listOfBodies);
        }
        //QUADRANT 3
        else if (listOfBodies->pos_x >= list3->xmin &&
                 listOfBodies->pos_x <= list3->xmax &&
                 listOfBodies->pos_y <= list3->ymin &&
                 listOfBodies->pos_y >= list3->ymax)
        {
            printf("FOUND IN QUADRANT 3\n");
            addBodyToLinkedList(list3, listOfBodies);
        }
        //QUADRANT 4
        else if (listOfBodies->pos_x >= list4->xmin &&
                 listOfBodies->pos_x <= list4->xmax &&
                 listOfBodies->pos_y >= list4->ymin &&
                 listOfBodies->pos_y <= list4->ymax)
        {
            printf("FOUND IN QUADRANT 4\n");
            addBodyToLinkedList(list4, listOfBodies);
        }
        else
        {
            printf("NO PLACE FOR THIS BODY WITH POSITION X: %f AND POSITION Y: %f\n", listOfBodies->pos_x, listOfBodies->pos_y);
        }

        listOfBodies = listOfBodies->next;
    }

    printf("\n");
    listOfBodies = rootBodyReference;

    bringNodeListBackToHeadNode(list1);
    bringNodeListBackToHeadNode(list2);
    bringNodeListBackToHeadNode(list3);
    bringNodeListBackToHeadNode(list4);

    struct Node *nodeTemp0 = buildBHTree(list1->xmin, list1->xmax, list1->ymin, list1->ymax, list1->body);
    struct Node *nodeTemp1 = buildBHTree(list2->xmin, list2->xmax, list2->ymin, list2->ymax, list2->body);
    struct Node *nodeTemp2 = buildBHTree(list3->xmin, list3->xmax, list3->ymin, list3->ymax, list3->body);
    struct Node *nodeTemp3 = buildBHTree(list4->xmin, list4->xmax, list4->ymin, list4->ymax, list4->body);

    struct Node *nodeTemp = (struct Node *) malloc(sizeof(struct Node));
    nodeTemp->body = listOfBodies;
    nodeTemp->node1 = nodeTemp0;
    nodeTemp->node2 = nodeTemp1;
    nodeTemp->node3 = nodeTemp2;
    nodeTemp->node4 = nodeTemp3;
    nodeTemp->xmin = xmin;
    nodeTemp->xmax = xmax;
    nodeTemp->ymin = ymin;
    nodeTemp->ymax = ymax;

    return nodeTemp;
}
}

运行时我也一直得到以下输出(请注意，第一个打印输出是在第一次运行时，第二个是递归第一次重新运行该方法时):

QUADRANT 1: xmin: 0.000000 | xmax: 250000000000.000000 | ymin: 0.000000 | ymax: 250000000000.000000
QUADRANT 2: xmin: 0.000000 | xmax: 250000000000.000000 | ymin: -250000000000.000000 | ymax: 0.000000
QUADRANT 3: xmin: -250000000000.000000 | xmax: 0.000000 | ymin: -250000000000.000000 | ymax: 0.000000
QUADRANT 4: xmin: -250000000000.000000 | xmax: 0.000000 | ymin: 0.000000 | ymax: 250000000000.000000
FOUND IN QUADRANT 1
FOUND IN QUADRANT 1
FOUND IN QUADRANT 1
FOUND IN QUADRANT 1
FOUND IN QUADRANT 1

QUADRANT 1: xmin: 125000000000.000000 | xmax: 250000000000.000000 | ymin: 125000000000.000000 | ymax: 250000000000.000000
QUADRANT 2: xmin: 125000000000.000000 | xmax: 250000000000.000000 | ymin: 0.000000 | ymax: 125000000000.000000
QUADRANT 3: xmin: 0.000000 | xmax: 125000000000.000000 | ymin: 0.000000 | ymax: 125000000000.000000
QUADRANT 4: xmin: 0.000000 | xmax: 125000000000.000000 | ymin: 125000000000.000000 | ymax: 250000000000.000000
NO PLACE FOR THIS BODY WITH POSITION X: 0.000000 AND POSITION Y: 0.000000
NO PLACE FOR THIS BODY WITH POSITION X: 57900000000.000000 AND POSITION Y: 0.000000
NO PLACE FOR THIS BODY WITH POSITION X: 108200000000.000000 AND POSITION Y: 0.000000
NO PLACE FOR THIS BODY WITH POSITION X: 149600000000.000000 AND POSITION Y: 0.000000

Answer 1

第一个问题是一些检查被关闭了，就像这里

    //QUADRANT 2
    else if (listOfBodies->pos_x >= list2->xmin &&
             listOfBodies->pos_x <= list2->xmax &&
             listOfBodies->pos_y <= list2->ymin && // should be >=
             listOfBodies->pos_y >= list2->ymax)   // should be <=
    {
        printf("FOUND IN QUADRANT 2\n");
        addBodyToLinkedList(list2, listOfBodies);
    }

第二个问题是你没有处理象限碰撞的特殊情况

QUADRANT 1: xmin: 0.0 | xmax: 250000000000.0  | ymin: 0.0 | ymax: 250000000000.0
QUADRANT 2: xmin: 0.0 | xmax: 250000000000.0  | ymin: -250000000000.0 | ymax: 0.0
QUADRANT 3: xmin: -250000000000.0 | xmax: 0.0 | ymin: -250000000000.0 | ymax: 0.0
QUADRANT 4: xmin: -250000000000.0 | xmax: 0.0 | ymin: 0.0 | ymax: 250000000000.0

因为你的检查是全包的，点 0,0 存在于所有 4 个象限中，为了解决这个问题，你可以将最小值视为包含而将最大值视为不包含，像这样

    //QUADRANT 1
    if (listOfBodies->pos_x >= list1->xmin &&
        listOfBodies->pos_x <  list1->xmax &&
        listOfBodies->pos_y >= list1->ymin &&
        listOfBodies->pos_y <  list1->ymax)
    {
        printf("FOUND IN QUADRANT 1\n");
        addBodyToLinkedList(list1, listOfBodies);
    }

我的建议是你可以使用两个int (代表小数部分和整数部分)而不是double来提高性能并在比较 float 时避免出现问题。