给定两个具有 x、y、宽度、高度（以像素为单位）和以度为单位的旋转值的矩形——我如何计算它们的轮廓彼此之间的最近距离？
背景：在一个用 Lua 编写的游戏中，我随机生成地图，但希望确保某些矩形彼此不会太近——这是必需的，因为如果矩形进入某个近距离位置，地图将变得无法解决，如一个球需要在他们之间传递。速度不是一个大问题，因为我没有很多矩形，并且每个级别只生成一次地图。我在 StackOverflow 上找到的以前的链接是这个和这个
提前谢谢了！
问问题
26779 次
9 回答
28
不在 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)
于 2014-10-03T11:17:57.387 回答
11
编辑：正如 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).
于 2014-03-20T07:22:13.263 回答
4
实际上有一个快速的数学解决方案。
Length(Max((0, 0), Abs(Center - otherCenter) - (Extent + otherExtent)))
哪里Center = ((Maximum - Minimum) / 2) + Minimum和Extent = (Maximum - Minimum) / 2。基本上零轴上方的代码是重叠的，因此距离总是正确的。
最好将矩形保持为这种格式，因为它在许多情况下更可取（ae 旋转更容易）。
于 2016-01-28T15:56:51.210 回答
3
伪代码：
distance_between_rectangles = some_scary_big_number;
对于 Rectangle1 中
的每个 edge1： 对于 Rectangle2 中的每个 edge2：
distance = 计算edge1 和 edge2 之间的最短距离
if (distance < distance_between_rectangles)
distance_between_rectangles = distance
于 2011-02-23T10:40:11.487 回答
1
有很多算法可以解决这个问题，Agnius 算法可以正常工作。但是我更喜欢下面的，因为它看起来更直观（你可以在一张纸上做）并且它们不依赖于找到线之间的最小距离，而是依赖于点和线之间的距离。
困难的部分是实现数学函数来找到一条线和一个点之间的距离，并确定一个点是否面向一条线。不过，您可以使用简单的三角函数来解决所有这些问题。我有以下方法来做到这一点。
对于任意角度的多边形（三角形、矩形、六边形等）
- 如果多边形重叠，则返回 0
- 在两个多边形的中心之间画一条线。
- 从每个多边形中选择相交边。（这里我们减少问题）
- 找到这两条边的最小距离。（您可以遍历每 4 个点并寻找到另一个形状边缘的最小距离）。
只要形状的任何两个边缘不产生超过 180 度的角度，这些算法就可以工作。原因是，如果某物高于 180 度，则意味着某些角在内部膨胀，就像在星星中一样。
边缘和点之间的最小距离
- 如果点不面向面，则返回点和边角之间的两个距离中的最小值。
- 从三个点（边缘点加上独奏点）绘制一个三角形。
- 我们可以很容易地用勾股定理得到三条画线之间的距离。
- 用Heron 公式得到三角形的面积。
Area = 12⋅base⋅height现在用base边缘的长度计算高度。
检查一个点是否面向边缘
和之前一样，你从一个边和一个点制作一个三角形。现在使用余弦定律，您只需知道边缘距离即可找到所有角度。只要从边缘到点的每个角度都在 90 度以下，该点就朝向边缘。
如果你有兴趣，我在这里有一个 Python 实现。
于 2014-09-24T14:28:35.340 回答
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)）。
我希望这可以帮助你
于 2011-02-12T14:27:36.747 回答
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。它始终是顶点之一。
于 2020-06-13T16:54:46.567 回答
0
Another solution, which calculates a number of points on the rectangle and choses the pair with the smallest distance.
Pros: works for all polygons.
Cons: a little bit less accurate and slower.
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
于 2021-09-02T14:39:45.520 回答
-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);
}
于 2016-07-31T18:48:01.623 回答