寻找两个AABB区域之间的边缘连接点

Question

假设我有两个基于AABB的区域，每个区域由两个坐标mins{x, y}和maxs{x, y}定义，我想找到它们之间的中间连接点。

由于我的英语不好，我无法用我的话来解释，为了更容易理解，请看下面的图片：.com/WokivEe.png

我只需要找到红点坐标。

因此，如果我们将其转化为编程问题，实际的数据结构将如下所示：

struct Vec2D {
    float x, y;
}

struct Rectangle {
    Vec2D min;
    Vec2D max;
}

Rectangle obj[2]

有人想出算法了吗？

Answer 1

沿着X轴或Y轴，对接触到的边的坐标进行排序。然后平均第二和第三个在该列表中，以找到他们的中点。我希望这能充分回答这个问题。

Answer 2

这里有一个小算法，它首先找出对象的哪一边是最近的，然后使用沿着公共侧的4个点创建一个列表，并按照公共轴排序。排序列表中两个中间点的平均值是答案。这将适用于水平和垂直两面。我将访问器函数添加到数据结构中，以便对它们进行索引；例如，对于Vec2D，坐标(0)是x值，坐标(1)是y值。

#include <math.h>
#include <iostream>
#include <limits>

struct Vec2D {
    float x, y;
    float coordinate(int axis)
    {
        return (axis & 1) ? y : x;
    }
};

struct Rectangle {
    Vec2D min;
    Vec2D max;
    Vec2D corner(int j)
    {
        return (j & 1) ? max : min;
    }

    // Get the other corner along the given axis
    Vec2D along(int j, int ax)
    {
        Vec2D p = corner(j);
        if (0 == ax)
        {
            p.x = corner(1-j).x;
        }
        else
        {
            p.y = corner(1-j).y;
        }
        return p;
    }
};

using namespace std;

inline Vec2D* vp(const void* p)
{
    return (Vec2D*) p;
}

static int compare_x(const void*a, const void*b)
{
    if (vp(a)->x < vp(b)->x)
    {
        return -1;
    }
    else
    if (vp(a)->x > vp(b)->x)
    {
        return 1;
    }
    return 0;
}

static int compare_y(const void*a, const void*b)
{
    if (vp(a)->y < vp(b)->y)
    {
        return -1;
    }
    else
    if (vp(a)->y > vp(b)->y)
    {
        return 1;
    }
    return 0;
}


int main(void) {
    int ax; // axis index
    int c0, c1;
    float gap = numeric_limits<float>::max();
    struct Rectangle obj[2] = {0,2,10,10,10,5,15,20};
    struct
    {
        int ax,c0,c1;
    } closest;

    // Find out which sides are the closest to each other
    for(ax = 0; 2 > ax; ++ax) // Look at x axis and y axis
    {
        for(c0 = 0; 2 > c0; ++c0) // Look at both corners of obj[0]
        {
            for(c1 = 0; 2 > c1; ++c1) // Look at both corners of obj[1]
            {
                float dist = fabs(obj[0].corner(c0).coordinate(ax) - obj[1].corner(c1).coordinate(ax));
                if (dist < gap)
                {
                    gap = dist;
                    closest.ax = ax;
                    closest.c0 = c0;
                    closest.c1 = c1;
                }
            }
        }
    }

    int other = 1 - closest.ax; // The other axis
    cout << "The closest gap is along the " << (closest.ax ? 'y' : 'x') << " axis\n";
    cout << "The common side is along the " << (other ? 'y' : 'x') << " direction\n";


    // Make a list of the 4 points along the common side
    Vec2D list[4];
    list[0] = obj[0].corner(closest.c0);
    list[1] = obj[0].along(closest.c0, other);
    list[2] = obj[1].corner(closest.c1);
    list[3] = obj[1].along(closest.c1, other);

    // Sort them into order along the common axis
    qsort(list, 4, sizeof(Vec2D), closest.ax ? compare_x : compare_y);

    // Get the average of the 2 middle points along the common axis.
    Vec2D answer = {
        (list[1].x + list[2].x) / 2,
        (list[1].y + list[2].y) / 2
    };

    cout << "(" << answer.x << "," << answer.y << ")\n";
}