找出平面上的 4 个点是否形成一个矩形?

find if 4 points on a plane form a rectangle?

提问人:pete 提问时间:2/21/2010 最后编辑:Josh Leepete 更新时间:1/14/2021 访问量:45505

问:

有人可以用 C 风格的伪代码告诉我如何编写一个函数(以您喜欢的方式表示点),如果 4 个点(函数的参数)形成一个矩形,则返回 true,否则返回 false?

我想出了一个解决方案,首先尝试找到 2 对具有相等 x 值的不同点,然后对 y 轴执行此操作。但是代码很长。只是好奇地想看看别人想出了什么。

C 算法 几何

评论

2赞 Milan Babuškov 2/21/2010
你想出了解决方案?它在哪里?你可以在这里展示它,我们可以帮助你使它更短、更干净。
4赞 Christian Madsen 2/21/2010
相互交织的问题。我注意到您的解决方案仅在矩形与轴平行时才有效。
0赞 pete 2/21/2010
Gman - 是的,按任何顺序。米兰 - 这是在一次面试中被问到的,所以我没有我的代码(我不一定需要看代码。算法也很棒!克里斯蒂安 - 关于它必须与轴平行的好点。

答:

48赞 Vlad 2/21/2010 #1
struct point
{
    int x, y;
}

// tests if angle abc is a right angle
int IsOrthogonal(point a, point b, point c)
{
    return (b.x - a.x) * (b.x - c.x) + (b.y - a.y) * (b.y - c.y) == 0;
}

int IsRectangle(point a, point b, point c, point d)
{
    return
        IsOrthogonal(a, b, c) &&
        IsOrthogonal(b, c, d) &&
        IsOrthogonal(c, d, a);
}

如果事先不知道订单,我们需要稍微复杂的检查:

int IsRectangleAnyOrder(point a, point b, point c, point d)
{
    return IsRectangle(a, b, c, d) ||
           IsRectangle(b, c, a, d) ||
           IsRectangle(c, a, b, d);
}

评论

0赞 Timmy 2/21/2010
如果 A 和 B 是对角线怎么办?
0赞 Andras Vass 2/28/2010
@Vlad:您能否像@Curd一样,在最坏情况下用算术运算来解释一下您的方法的运行时复杂性?
0赞 Sumi 11/13/2020
按顺序输入的直角三角形作为矩形通过此三角形。isOrthogonal() 方法需要修改。
0赞 Harvey 11/14/2023
@TedLyngmo 是的,不见了。== 0
0赞 Harvey 11/14/2023
不确定它是否更快,但对点进行排序消除了测试三次的需要。对 where 进行排序。翻转最后两个排序点,使它们按周长顺序排列,points[4] = {a,b,c,d}qsort(points, 4, sizeof(points[0]), comp);comp = a->x != b->x ? a->x - b->x : a->y - b->yIsRectangle(points[0], points[1], points[3], points[2]);
74赞 Curd 2/21/2010 #2
  • 求角点质心:cx=(x1+x2+x3+x4)/4, cy=(y1+y2+y3+y4)/4
  • 检验从质心到所有 4 个角的距离的平方是否相等
bool isRectangle(double x1, double y1,
                 double x2, double y2,
                 double x3, double y3,
                 double x4, double y4)
{
  double cx,cy;
  double dd1,dd2,dd3,dd4;

  cx=(x1+x2+x3+x4)/4;
  cy=(y1+y2+y3+y4)/4;

  dd1=sqr(cx-x1)+sqr(cy-y1);
  dd2=sqr(cx-x2)+sqr(cy-y2);
  dd3=sqr(cx-x3)+sqr(cy-y3);
  dd4=sqr(cx-x4)+sqr(cy-y4);
  return dd1==dd2 && dd1==dd3 && dd1==dd4;
}

(当然,在实践中,两个浮点数 a 和 b 的相等性测试应该以有限的精度进行:例如 abs(a-b) < 1E-6)

评论

4赞 rlbond 2/21/2010
这是一个聪明的解决方案。它基本上找到了“矩形”的圆周,并验证所有四个角都位于其上。
9赞 Axel Gneiting 2/21/2010
这是非常低效的。使用 Vlad 提供的点积方法。平方根需要数百个时钟周期。此外,点积法在数值上更稳定。
6赞 Brett Pontarelli 2/21/2010
@Axel & @Curd:解决方案自最初发布以来是否进行了编辑?我没有看到任何平方根。我假设哪个均值实际上是从 到 的距离的平方。这应该非常快。sqr(x) == x*xddicxxi
5赞 Axel Gneiting 2/22/2010
好吧,那我需要道歉。我以为sqr代表平方根。
4赞 Curd 2/22/2010
关于性能的一些注意事项:此解决方案需要 20 次加法/减法/除法乘以常数 4 和 8 次乘法。如果第一次或第二次比较失败,它甚至可以优化为放弃剩余的平方距离计算。所以上面的数字是最坏的情况。即使是这种最坏的情况也与最好的情况一样好,比弗拉德的解决方案的最坏情况好 3 倍。
4赞 Axel Gneiting 2/21/2010 #3

如果点是 A、B、C 和 D,并且您知道顺序,那么您可以计算向量:

x=B-A、y=C-B、z=D-C 和 w=A-D

然后取点积 (x dot y)、(y dot z)、(z dot w) 和 (w dot x)。如果它们都为零,那么你就有一个矩形。

评论

0赞 Andras Vass 2/25/2010
如果您知道订单,请检查 |x|= |z|, |y|= |w|一个点积就足够了。(因为相对边的长度必须相等,然后有相当多的四边形的相对边长度相等。
2赞 manugupt1 2/21/2010 #4

我们知道,如果两条直线的斜率乘积为 -1,那么两条稳直线是垂直的,因为给定了一个平面,我们可以找到三条连续线的斜率,然后将它们相乘以检查它们是否真的垂直。假设我们有 L1、L2、L3 行。现在,如果 L1 垂直于 L2 并且 L2 垂直于 L3,那么它是 m(L1)*m(L2)=-1 和 m(L2)*m(L3)=-1 的矩形和斜率,那么它意味着它是一个矩形。代码如下

bool isRectangle(double x1,double y1,
        double x2,double y2,
        double x3,double y3,
        double x4,double y4){
    double m1,m2,m3;
    m1 = (y2-y1)/(x2-x1);
    m2 = (y2-y3)/(x2-x3);
    m3 = (y4-y3)/(x4-x3);

    if((m1*m2)==-1 && (m2*m3)==-1)
        return true;
    else
        return false;
}

评论

0赞 milesmeow 2/21/2010
我认为这在计算上是最有效的。
2赞 Andras Vass 2/21/2010
您还应该检查 m4,否则您最终可能会得到梯形。
5赞 Carlos Gutiérrez 2/21/2010 #5

从一个点到另一个 3 点的距离应形成一个直角三角形:

|   /      /|
|  /      / |
| /      /  |
|/___   /___|
d1 = sqrt( (x2-x1)^2 + (y2-y1)^2 ) 
d2 = sqrt( (x3-x1)^2 + (y3-y1)^2 ) 
d3 = sqrt( (x4-x1)^2 + (y4-y1)^2 ) 
if d1^2 == d2^2 + d3^2 then it's a rectangle

简化:

d1 = (x2-x1)^2 + (y2-y1)^2
d2 = (x3-x1)^2 + (y3-y1)^2
d3 = (x4-x1)^2 + (y4-y1)^2
if d1 == d2+d3 or d2 == d1+d3 or d3 == d1+d2 then return true

评论

0赞 Carlos Gutiérrez 2/22/2010
@andras - 测试了几个平行四边形,所有平行四边形都被评估为假。你在考虑一个特定的案例吗?
1赞 Andras Vass 2/22/2010
假设我们有点 x1=3, y1=3;x2=0, y2=0;x3=6,y3=0;x4=9,y4=3;现在 d1 = 18;d2 = 18;d3 = 36;不过,已经很晚了。:-)你能检查一下吗?
0赞 Carlos Gutiérrez 2/22/2010
@andras - 你是对的,看起来必须使用其中的 3 个点作为起点来重复测试。
1赞 Andras Vass 2/28/2010
那么,请做点什么。
0赞 Masoud Darzi 1/23/2021
这是错误的,最后一行必须是 d1^2 == d2^2+d3^2 或 d2^2 == d1^2 + d3^2 或 d3^2 == d1^2 + d2 ^2
2赞 David Meister 2/22/2010 #6

将点积建议更进一步,检查由点的任意 3 个点组成的两个向量是否垂直,然后查看 x 和 y 是否与第四个点匹配。

如果您有点 [Ax,Ay] [Bx,By] [Cx,Cy] [Dx,Dy]

向量 v = B-A 向量 u = C-A

v(点)u/|v||u|== cos(theta)

因此,如果 (v.u == 0) 那里有几条垂直线。

我实际上不懂 C 编程,但这里有一些“元”编程:P

if (v==[0,0] || u==[0,0] || u==v || D==A) {not a rectangle, not even a quadrilateral}

var dot = (v1*u1 + v2*u2); //computes the "top half" of (v.u/|v||u|)
if (dot == 0) { //potentially a rectangle if true

    if (Dy==By && Dx==Cx){
     is a rectangle
    }

    else if (Dx==Bx && Dy==Cy){
     is a rectangle
    }
}
else {not a rectangle}

这其中没有平方根,也没有除以零的可能性。我注意到人们在之前的帖子中提到了这些问题,所以我想我会提供一个替代方案。

因此,在计算上,你需要四次减法才能得到 v 和 u,两次乘法,一次加法,你必须检查 1 到 7 之间的某个等式。

也许我是在编造这个,但我隐约记得在某处读到减法和乘法是“更快”的计算。我假设声明变量/数组并设置它们的值也很快?

对不起,我对这种事情很陌生,所以我很想对我刚刚写的内容提供一些反馈。

编辑:根据我在下面的评论尝试一下:

A = [a1,a2];
B = [b1,b2];
C = [c1,c2];
D = [d1,d2];

u = (b1-a1,b2-a2);
v = (c1-a1,c2-a2);

if ( u==0 || v==0 || A==D || u==v)
    {!rectangle} // get the obvious out of the way

var dot = u1*v1 + u2*v2;
var pgram = [a1+u1+v1,a2+u2+v2]
if (dot == 0 && pgram == D) {rectangle} // will be true 50% of the time if rectangle
else if (pgram == D) {
    w = [d1-a1,d2-a2];

    if (w1*u1 + w2*u2 == 0) {rectangle} //25% chance
    else if (w1*v1 + w2*v2 == 0) {rectangle} //25% chance

    else {!rectangle}
}
else {!rectangle}

评论

0赞 David Meister 2/22/2010
啊,我刚刚意识到这有平行于轴的问题。因此,它应该测试 if (D == A + v + u),而不是末尾的 if 语句。我还注意到,如果您将对角线作为前 3 个点之一,它可能会给出假阴性,因此如果点积失败,它应该将 u 重新定义为 AD,然后重试。
7赞 Andras Vass 2/28/2010 #7
  • 平移四边形,使其一个顶点现在位于原点
  • 剩下的三个点从原点形成三个向量
  • 其中一个必须代表对角线
  • 另外两个必须代表双方
  • 根据平行四边形规则,如果边形成对角线,我们有一个平行四边
  • 如果边形成直角,则为直角平行四边形
  • 平行四边形的相反角相等
  • 平行四边形的连续角是补充的
  • 因此,所有角度都是直角
  • 它是一个矩形
  • 不过,它在代码中要简洁得多:-)

    static bool IsRectangle(
       int x1, int y1, int x2, int y2, 
       int x3, int y3, int x4, int y4)
    {
        x2 -= x1; x3 -= x1; x4 -= x1; y2 -= y1; y3 -= y1; y4 -= y1;
        return
            (x2 + x3 == x4 && y2 + y3 == y4 && x2 * x3 == -y2 * y3) ||
            (x2 + x4 == x3 && y2 + y4 == y3 && x2 * x4 == -y2 * y4) ||
            (x3 + x4 == x2 && y3 + y4 == y2 && x3 * x4 == -y3 * y4);
    }
    
  • (如果你想让它与浮点值一起工作,请不要盲目地替换标头中的 int 声明。这是不好的做法。他们在那里是有原因的。在比较浮点结果时,应始终使用误差的上限。

评论

0赞 Andras Vass 3/7/2010
最坏情况:15 次加法/减法,6 次乘法。
7赞 Vineet Kapoor 7/9/2018 #8
1. Find all possible distances between given 4 points. (we will have 6 distances)
2. XOR all distances found in step #1
3. If the result after XORing is 0 then given 4 points are definitely vertices of a square or a rectangle otherwise, return false (given 4 points do not form a rectangle).
4. Now, to differentiate between square and rectangle 
   a. Find the largest distance out of 4 distances found in step #1. 
   b. Check if the largest distance / Math.sqrt (2) is equal to any other distance.
   c. If answer is No, then given four points form a rectangle otherwise they form a square.

在这里,我们使用矩形/正方形Bit Magic 的几何属性。

起作用的矩形属性

  1. 矩形的相对边和对角线的长度相等。
  2. 如果矩形的对角线长度是其任意长度的 sqrt(2) 倍,则该矩形为正方形。

比特魔术

  1. 异或等值数返回 0。

由于矩形的 4 个角之间的距离将始终形成 3 对,一对用于对角线,两对用于不同长度的每条边,因此对所有值进行异或运算将返回矩形的 0。

评论

0赞 Ed Bordin 4/3/2019
很酷的想法,但如果您需要以较小的公差测试等式以考虑浮点精度,则可能不切实际。可能还值得补充的是,XOR 技巧之所以有效,是因为 XOR 是可交换的和关联的
0赞 diegoide 8/11/2019
6. .为什么不直接检查 4 个距离是否相等?
1赞 bob wong 8/5/2018 #9

如何验证这 4 个点可以先形成一个平行四边形,然后找出是否存在一个直角
1. 验证平行四边形

input 4 points A, B, C, D;

if(A, B, C, D are the same points), exit;// not a rectangle;

else form 3 vectors, AB, AC, AD, verify(AB=AC+AD || AC=AB+AD || AD=AB+AC), \\if one of them satisfied, this is a parallelogram;

2.验证直角

through the last step, we could find which two points are the adjacent points of A;

We need to find out if angle A is a right angle, if it is, then rectangle.

我不知道是否存在错误。如果有的话,请弄清楚。

评论

0赞 Jack Bashford 8/5/2018
请确保您的答案实际上是对OP问题的回答。他问如何确定点是否形成矩形,而不是它们是否形成平行四边形。此外,一个直角并不能确保矩形。
1赞 bob wong 8/6/2018
嗯,一个直角的平行四边形是一个矩形,所以我相信在上述两个步骤中验证它可能会起作用。
0赞 Jack Bashford 8/6/2018
对不起,我的想法不同了。
2赞 Mike M. 11/9/2018 #10

我最近也面临着类似的挑战,但是在Python中,这是我在Python中想出的,也许这种方法可能很有价值。这个想法是有六条线,如果创建成一个集合,应该还剩下 3 个唯一的线距离——长度、宽度和对角线。

def con_rec(a,b,c,d): 
        d1 = a.distanceFromPoint(b)
        d2 = b.distanceFromPoint(c)
        d3 = c.distanceFromPoint(d)
        d4 = d.distanceFromPoint(a)
        d5 = d.distanceFromPoint(b)
        d6 = a.distanceFromPoint(c)
        lst = [d1,d2,d3,d4,d5,d6] # list of all combinations 
        of point to point distances
        if min(lst) * math.sqrt(2) == max(lst): # this confirms a square, not a rectangle
            return False
        z = set(lst) # set of unique values in ck
        if len(lst) == 3: # there should be three values, length, width, diagonal, if a 
        4th, it's not a rectangle
            return True
        else: # not a rectangle
            return False
1赞 Pedro Lopes 5/29/2019 #11

这是我的算法建议,用于轴对齐的矩形测试,但在 Python 中。

这个想法是抓住第一个点作为枢轴,所有其他点必须符合相同的宽度和高度,并通过一个集合检查所有点是否不同,以解释诸如 (1, 2)、(1, 2)、(10, 30)、(10, 30) 等情况。

from collections import namedtuple

Point = namedtuple('Point', ('x', 'y'))

def is_rectangle(p1, p2, p3, p4) -> bool:
    width = None
    height = None

    # All must be distinct
    if (len(set((p1, p2, p3, p4))) < 4):
        return False

    pivot = p1

    for point in (p2, p3, p4):
        candidate_width = point.x - pivot.x
        candidate_height = point.y - pivot.y

        if (candidate_width != 0):
            if (width is None):
                width = candidate_width
            elif (width != candidate_width):
                return False

        if (candidate_height != 0):
            if (height is None):
                height = candidate_height
            elif (height != candidate_height):
                return False

    return width is not None and height is not None

# Some Examples
print(is_rectangle(Point(10, 50), Point(20, 50), Point(10, 40), Point(20, 40)))
print(is_rectangle(Point(100, 50), Point(20, 50), Point(10, 40), Point(20, 40)))
print(is_rectangle(Point(10, 10), Point(20, 50), Point(10, 40), Point(20, 40)))
print(is_rectangle(Point(10, 30), Point(20, 30), Point(10, 30), Point(20, 30)))
print(is_rectangle(Point(10, 30), Point(10, 30), Point(10, 30), Point(10, 30)))
print(is_rectangle(Point(1, 2), Point(10, 30), Point(1, 2), Point(10, 30)))
print(is_rectangle(Point(10, 50), Point(80, 50), Point(10, 40), Point(80, 40)))

评论

0赞 greybeard 5/29/2019
这似乎假设轴对齐的矩形(如问题所示,但没有明确指定)。(如果等向,为什么四个点作为参数?
0赞 Pedro Lopes 5/29/2019
@greybeard 4 点作为论据提供,如问题中要求的那样。是的,这里的假设是它正在检查轴对齐的矩形。我将用这句话更新答案