如何计算两个矩形之间的距离？（背景：Lua游戏）

Question

如何计算两个矩形之间的距离？（背景：Lua游戏）

27

给定两个矩形，具有以像素为单位的 x、y、宽度、高度和旋转值（以度为单位）-如何计算它们之间轮廓的最近距离？

背景：在一个用Lua编写的游戏中，我正在随机生成地图，但希望确保某些矩形彼此之间不太接近-这是必需的，因为如果矩形进入某些接近距离的位置，地图将变得无解，因为球需要在它们之间通过。速度不是很重要，因为我没有很多矩形，并且每个级别的地图只生成一次。我在StackOverflow上找到的以前的链接是this和this

非常感谢您提前的帮助！

- Philipp Lenssen

你发布的第二个链接中有你正在寻找的确切答案。特别是这个链接：http://cgm.cs.mcgill.ca/~orm/mind2p.html。你关于Lua /像素的额外细节只是噪音。 - deft_code

可能是重复的问题：如何快速找到两个多边形之间的最短笛卡尔距离。 - deft_code

类似问题：如何检测两条线段的交点？ - Martin Thoma

10个回答

13

编辑:正如OK所指出的那样，此解决方案假定所有矩形都是直立的。要使其适用于旋转的矩形，如OP所询问的那样，还必须计算每个矩形的角落到另一个矩形最近边缘的距离。但是，在大多数情况下，如果该点位于线段两个端点的上方或下方，并且在两条线段的左侧或右侧（相对于线段的电话位置1、3、7或9），则可以避免进行该计算。

Agnius的答案依赖于DistanceBetweenLineSegments()函数。以下是一个不依赖该函数的案例分析:

(1) Check if the rects intersect. If so, the distance between them is 0.
(2) If not, think of r2 as the center of a telephone key pad, #5.
(3) r1 may be fully in one of the extreme quadrants (#1, #3, #7, or #9). If so
    the distance is the distance from one rect corner to another (e.g., if r1 is
    in quadrant #1, the distance is the distance from the lower-right corner of
    r1 to the upper-left corner of r2).
(4) Otherwise r1 is to the left, right, above, or below r2 and the distance is
    the distance between the relevant sides (e.g., if r1 is above, the distance
    is the distance between r1's low y and r2's high y).

- M Katz

1

这个缺少旋转方面的考虑，例如如果r1被旋转，使得与r2左上角的最短连接在r1的一条线上开始而不是一个角落。 - OK.

@好的，你说得对。我没注意到原帖中提到矩形可以旋转。因为解决未旋转的矩形问题是一个如此常见的问题，所以我就想当然地认为矩形没有被旋转。 - M Katz

我来这里是为了寻找矩形不旋转的解决方案，所以谢谢你 :) - undefined

5

事实上，有一个快速的数学解决方案。

Length(Max((0, 0), Abs(Center - otherCenter) - (Extent + otherExtent)))

其中Center = ((Maximum - Minimum) / 2) + Minimum，Extent = (Maximum - Minimum) / 2。基本上，代码将重叠的零轴置为零，因此距离始终正确。

在许多情况下（如旋转），保持矩形格式是首选。

- Felix K.

这个公式对我来说不太清楚。你是如何计算向量的平方的？你是指向量自身的点积吗？ - Suma

@Suma 这是向量中每个数字的指数运算符（别名为平方）。 - Felix K.

1

@Suma 抱歉，我有些困惑，因为我很久以前就写了这段代码。Max((0, 0), Abs(Center - otherCenter) - (Extent + otherExtent))计算每个组件的距离。然后，你基本上要计算出向量的长度，这是 Sqrt((x * x) + (y * y))。 - Felix K.

@user19283043 很抱歉回复晚了。Minimum是x和y轴上的最小值，例如(-2,-2)，而Maximum则是(3,2)，在这种情况下Extend为(2.5,2)。长度已在上面的注释中描述。 - Felix K.

1

这似乎也忽略了矩形的旋转。 - oarfish

显示剩余3条评论

3

伪代码:

矩形间的距离=一些可怕的大数字;
对于矩形1中的每条边：
    对于矩形2中的每条边：
        距离=计算边1和边2之间的最短距离
        如果(距离 < 矩形间的距离)
            矩形间的距离=距离

- Agnius Vasiliauskas

2

有许多算法可以解决这个问题，Agnius算法很好用。但我更喜欢下面的算法，因为它更直观（你可以在纸上完成），而且它们不依赖于找到线之间最小距离，而是依赖于点和线之间的距离。

难点在于实现数学函数以找到线和点之间的距离，并找出点是否朝向一条线。不过，你可以用简单的三角函数来解决所有这些问题。下面是我使用的方法。

对于任意角度的多边形（三角形、矩形、六边形等）

如果多边形重叠，则返回 0
在两个多边形的中心之间画一条线。
从每个多边形中选择相交的边。（这里我们缩小了问题范围）
找到这两条边之间的最小距离。（你可以循环遍历每个四个点并查找到另一个形状的边的最小距离）。

只要形状的任意两条边不形成大于180度的角度，这些算法就能起作用。原因是，如果某些角度超过180度，则意味着某些角落会膨胀到内部，就像一个星形。

边缘和点之间的最小距离

如果点不朝向面，那么返回点和边角之间的两个距离中的最小值。
从三个点（边的点加上单独的点）绘制一个三角形。
我们可以使用勾股定理轻松获得三条线之间的距离。
使用海伦公式获取三角形的面积。
现在使用 Area = 12⋅base⋅height 计算高度，其中 base 是边的长度。

检查点是否朝向边缘

与之前一样，从边缘和一个点绘制三角形。现在使用余弦定律，只需知道边缘距离即可找到所有角度。只要从边缘到点的每个角度都低于90度，该点就朝向边缘。

如果您有兴趣，我在Python中实现了所有这些内容这里。

- Pithikos

2

我解决问题的方法：

将两个矩形合并成一个大矩形
从大矩形中减去第一个矩形和第二个矩形
减法后剩下的是两个矩形之间的矩形，该矩形的对角线就是两个矩形之间的距离。

以下是C#的示例：

public static double GetRectDistance(this System.Drawing.Rectangle rect1, System.Drawing.Rectangle rect2)
{
    if (rect1.IntersectsWith(rect2))
    {
        return 0;
    }

    var rectUnion = System.Drawing.Rectangle.Union(rect1, rect2);
    rectUnion.Width -= rect1.Width + rect2.Width;
    rectUnion.Width = Math.Max(0, rectUnion.Width);

    rectUnion.Height -= rect1.Height + rect2.Height;
    rectUnion.Height = Math.Max(0, rectUnion.Height);

    return rectUnion.Diagonal();
}

public static double Diagonal(this System.Drawing.Rectangle rect)
{
    return Math.Sqrt(rect.Height * rect.Height + rect.Width * rect.Width);
}

- google dev

0

这个问题取决于你想要哪种距离。你是想要中心的距离，边缘的距离还是最近角落的距离？

我猜你指的是最后一种。如果X和Y值表示矩形的中心，则可以通过应用此技巧找到每个角落。

//Pseudo code
Vector2 BottomLeftCorner = new Vector2(width / 2, heigth / 2);
BottomLeftCorner = BottomLeftCorner * Matrix.CreateRotation(MathHelper.ToRadians(degrees));
//If LUA has no built in Vector/Matrix calculus search for "rotate Vector" on the web.
//this helps: http://www.kirupa.com/forum/archive/index.php/t-12181.html

BottomLeftCorner += new Vector2(X, Y); //add the origin so that we have to world position.

对于所有矩形的所有角落都要这样做，然后只需循环遍历所有角落并计算距离（只需 abs(v1 - v2)）。

希望这可以帮助你。

- Roy T.

谢谢Roy。澄清一下，我指的是每个矩形轮廓之间的距离，而不是最近的角落——我的目标是要知道一个特定半径的球是否仍然可以在它们之间的任何位置放置。想象一下这两个矩形像石头一样（都随机旋转，但从未旋转到零度），世界上有重力——我想找出是否存在理论上的机会，让从上方掉下来的球卡在两块石头之间。 - Philipp Lenssen

好的，嗯，这个计算起来要困难得多，我会点赞这个问题。我很好奇是否有人能够提出一个好的算法来解决它，应该是可以做到的。 - Roy T.

0

我刚刚在n维空间中编写了该代码。我很难找到一个通用的解决方案。

// considering a rectangle object that contains two points (min and max)
double distance(const rectangle& a, const rectangle& b) const {
    // whatever type you are using for points
    point_type closest_point;
    for (size_t i = 0; i < b.dimensions(); ++i) {
        closest_point[i] = b.min[i] > a.min[i] ? a.max[i] : a.min[i];
    }
    // use usual euclidian distance here
    return distance(a, closest_point);
}

计算矩形和点之间的距离，你可以：

double distance(const rectangle& a, const point_type& p) const {
    double dist = 0.0;
    for (size_t i = 0; i < dimensions(); ++i) {
        double di = std::max(std::max(a.min[i] - p[i], p[i] - a.max[i]), 0.0);
        dist += di * di;
    }
    return sqrt(dist);
}

如果您想旋转其中一个矩形，您需要旋转坐标系。

如果您想旋转两个矩形，您可以旋转矩形 a 的坐标系。然后我们需要更改这一行：

closest_point[i] = b.min[i] > a.min[i] ? a.max[i] : a.min[i];

因为这个假设只有一个候选点是最接近b的顶点。你需要将其更改为检查到b中所有顶点的距离。它总是其中一个顶点。

参见：https://istack.dev59.com/EKJmr.webp

- alandefreitas

-1

请检查这个Java程序，它有一个限制条件，即所有矩形都是平行的，对于所有相交的矩形返回0：

   public static double findClosest(Rectangle rec1, Rectangle rec2) {
      double x1, x2, y1, y2;
      double w, h;
      if (rec1.x > rec2.x) {
         x1 = rec2.x; w = rec2.width; x2 = rec1.x;
      } else {
         x1 = rec1.x; w = rec1.width; x2 = rec2.x;
      }
      if (rec1.y > rec2.y) {
         y1 = rec2.y; h = rec2.height; y2 = rec1.y;
      } else {
         y1 = rec1.y; h = rec1.height; y2 = rec2.y;
      }
      double a = Math.max(0, x2 - x1 - w);
      double b = Math.max(0, y2 - y1 - h);
      return Math.sqrt(a*a+b*b);
   }

- Thomas

-1

另一种解决方案是计算矩形上的若干点，并选择距离最小的一对点。

优点：适用于所有多边形。

缺点：精度稍低，速度较慢。

import numpy as np
import math

POINTS_PER_LINE = 100

# get points on polygon outer lines
# format of polygons: ((x1, y1), (x2, y2), ...)
def get_points_on_polygon(poly, points_per_line=POINTS_PER_LINE):

    all_res = []

    for i in range(len(poly)):

        a = poly[i]

        if i == 0:
            b = poly[-1]

        else:
            b = poly[i-1]

        res = list(np.linspace(a, b, points_per_line))

        all_res += res

    return all_res



# compute minimum distance between two polygons
# format of polygons: ((x1, y1), (x2, y2), ...)
def min_poly_distance(poly1, poly2, points_per_line=POINTS_PER_LINE):

    poly1_points = get_points_on_polygon(poly1, points_per_line=points_per_line)

    poly2_points = get_points_on_polygon(poly2, points_per_line=points_per_line)

    distance = min([math.sqrt((a[0] - b[0])**2 + (a[1] - b[1])**2) for a in poly1_points for b in poly2_points])

    # slower
    # distance = min([np.linalg.norm(a - b) for a in poly1_points for b in poly2_points])

    return distance

- Tom Atix

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Maxim · Accepted Answer

不是Lua，而是基于M Katz的建议的Python代码：

def rect_distance((x1, y1, x1b, y1b), (x2, y2, x2b, y2b)):
    left = x2b < x1
    right = x1b < x2
    bottom = y2b < y1
    top = y1b < y2
    if top and left:
        return dist((x1, y1b), (x2b, y2))
    elif left and bottom:
        return dist((x1, y1), (x2b, y2b))
    elif bottom and right:
        return dist((x1b, y1), (x2, y2b))
    elif right and top:
        return dist((x1b, y1b), (x2, y2))
    elif left:
        return x1 - x2b
    elif right:
        return x2 - x1b
    elif bottom:
        return y1 - y2b
    elif top:
        return y2 - y1b
    else:             # rectangles intersect
        return 0.

其中

dist 是点之间的欧几里得距离
矩形1由点 (x1, y1) 和 (x1b, y1b) 组成
矩形2由点 (x2, y2) 和 (x2b, y2b) 组成