两个不同角度的旋转矩形之间的最小距离 [英] Minimum distance between two rotated rectangles with different angles

问题描述

如何计算两个矩形之间的最小距离？
对于没有角度的矩形（即 0 度数为1），对于旋转具有任何不同角度的矩形我不知道该怎么做。


您可以推荐任何方式吗？

WhiteFlare

解决方案

1. 检查它们是否首先相交（尝试从一个矩形中取点并检查它是否在其他矩形内）。有几种方法可以做到这一点。一种方法（不是最好的，但容易解释）如下。
   让 A1 ， A2 ， A3 ， A4 - 矩形点， T - 其他一点。然后计算三角形的平方：
S1 =（A1，A2，T）， S2 = S（A2，A3，T ）， S3 = S（A3，A4，T）， S4 = S（A4，A1，A2）。让 S_rectangle 为矩形正方形。
然后 T 位于矩形内<=> S1 + S2 + S3 + S4 = S_rectangle 。 >

如果矩形不相交，则执行这些步骤。


2. 计算2个矩形的所有8个点的坐标。
   

3. 在所有4 * 4 = 16对点（来自不同矩形的点）中取最小值。让我们表示它 min_1

然后，从第一个矩形中取一些点（4种方法来做到这一点）另一个矩形（4种方式），检查从该点垂直到该分段是否在内部分段。
以这种垂直分量的最小值为准。让我们表示它 min_2 。



4. 与 3 ，但从第二个矩形开始，从第一个行开始：您得到 min_3 。






How can I calculate the minimum distance between two rectangles?
It is easy for rectangles which have no angles (i.e. 0 degrees one), but for rotated rectangles with any different angles I do not know how to do it.

Can you recommend any way?

WhiteFlare

解决方案

1. Check either they intersect first (try to take point from one rectangle and check either it is inside other rectangle).
   There are several ways to do it. One method (not the best one, but easy to explain) is the following.
   Let A1, A2, A3, A4 - rectangle points, T - some other point.
   Then count squares for triangles:
   S1 = (A1,A2,T), S2 = S(A2,A3,T), S3 = S(A3, A4, T), S4 = S(A4, A1, A2).
   Let S_rectangle be reactangle square.
   Then T lies inside rectangle <=> S1 + S2 + S3 + S4 = S_rectangle.
   
   If reactangles don't intersect each other, then do these steps.

2. Calculate coordinates of all 8 points of 2 rectangles.

3. Take minimum among all 4 * 4 = 16 pairs of points (points from different rectangles).
   Let's denote it min_1.

4. Then, take some point from the first rectangle (4 ways to do it),
   take 4 segments of another rectangle (4 ways),
   check either perpendicular from that point to that segment gets inside segment.
   Take the mininmum of such perpendiculars. Let's denote it min_2.

5. The same as in 3, but take point from the second rectangle, lines from the first:
   you get min_3.

6. result = min(min_1, min_2, min_3)

这篇关于两个不同角度的旋转矩形之间的最小距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！