如何计算两个矩形之间的距离？ （上下文：Lua 中的游戏。）

Question

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

背景：在用 Lua 编写的游戏中，我随机生成地图，但希望确保某些矩形彼此之间距离不太近——这是必需的，因为如果矩形进入某个近距离位置，地图将变得无法解析，如下所示需要有一个球在它们之间通过。速度不是一个大问题，因为我没有很多矩形，而且地图每个级别只生成一次。我之前在 StackOverflow 上找到的链接是 this 和 < a href="https://stackoverflow.com/questions/84034/what-is-the-quickest-way-to-find-the-shortest-cartesian-distance- Between-two-poly">这个

非常感谢！

Answer 1

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 是点 rect 之间的欧几里得距离
• 。 1 由点 (x1, y1) 和 (x1b, y1b) 矩形组成
• 。 2 由点 (x2, y2) 和 (x2b, y2b) 组成

Answer 2

编辑：正如 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).

Answer 3

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

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

其中中心 = ((最大值 - 最小值)/2) + 最小值 和范围 = (最大值 - 最小值)/2。
基本上，零轴上方的代码是重叠的，因此距离始终是正确的。

最好将矩形保留为这种格式，因为它在许多情况下更可取（ae 旋转更容易）。

Answer 4

伪代码：

distance_ Between_rectangles = some_scary_big_number；

对于 Rectangle1 中的每条边 1：
    对于 Rectangle2 中的每条边 2：
       距离=计算最短边1和边2之间的距离
       if（距离
         矩形之间的距离 = 距离

Answer 5

我解决问题的方法：

1. 将两个矩形合并为一个大矩形 从
2. 大矩形中减去第一个矩形和第二个矩形
   矩形
3. 相减后剩下的是两者之间的
   矩形，该矩形的对角线是之间的距离
   两个矩形。

这是一个 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);
}

Answer 6

有很多算法可以解决这个问题，Agnius 算法效果很好。不过，我更喜欢下面的，因为它看起来更直观（您可以在一张纸上完成），并且它们不依赖于找到线之间的最小距离，而是依赖于点和线之间的距离。

困难的部分是实现数学函数来查找直线和点之间的距离，以及查找点是否面向直线。不过，您可以用简单的三角函数来解决所有这些问题。我有以下方法来做到这一点。

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

1. 如果多边形重叠，则返回 0
2. 在两个多边形的中心之间画一条线。
3. 从每个多边形中选择相交的边。 （这里我们把问题简化了）
4. 求这两条边的最小距离。 （您可以循环遍历每 4 个点并寻找到另一个形状边缘的最小距离）。

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

边与点之间的最小距离

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

检查一个点是否面向一条边

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

如果您有兴趣，我在此处提供了所有这些内容的 Python 实现。

Answer 7

这个问题取决于什么样的距离。您想要中心距离、边缘距离还是最近角点距离？

我猜你指的是最后一个。如果 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) ）。

我希望这对你有帮助

Answer 8

我刚刚编写了 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://i.sstatic.net/EKJmr.png

Answer 9

请检查 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);
   }

Answer 10

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

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

缺点：准确度稍差，速度较慢。

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