C语言 求平面上的 4 个点是否构成一个矩形？

find if 4 points on a plane form a rectangle?

提问by pete

Can somebody please show me in C-style pseudocode how to write a function (represent the points however you like) that returns true if 4-points (args to the function) form a rectangle, and false otherwise?

有人可以用 C 风格的伪代码告诉我如何编写一个函数（代表你喜欢的点），如果 4 个点（函数的参数）形成一个矩形，则返回 true，否则返回 false？

I came up with a solution that first tries to find 2 distinct pairs of points with equal x-value, then does this for the y-axis. But the code is rather long. Just curious to see what others come up with.

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

回答by Curd

• find the center of mass of corner points: cx=(x1+x2+x3+x4)/4, cy=(y1+y2+y3+y4)/4
• test if square of distances from center of mass to all 4 corners are equal

• 求角点的质心：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;
}

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;
}

(Of course in practice testing for equality of two floating point numbers a and b should be done with finite accuracy: e.g. abs(a-b) < 1E-6)

（当然，在实践中测试两个浮点数 a 和 b 的相等性应该以有限的精度完成：例如 abs(ab) < 1E-6）

回答by Vlad

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);
}

If the order is not known in advance, we need a slightly more complicated check:

如果订单事先不知道，我们需要稍微复杂一点的检查：

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);
}

回答by Andras Vass

• translate the quadrilateral so that one of its vertices now lies at the origin
• the three remaining points form three vectors from the origin
• one of them must represent the diagonal
• the other two must represent the sides
• by the parallelogram ruleif the sides form the diagonal, we have a parallelogram
• if the sides form a right angle, it is a parallelogram with a right angle
• opposite angles of a parallelogram are equal
• consecutive angles of a parallelogram are supplementary
• therefore all angles are right angles
• it is a rectangle

• it is much more concise in code, though :-)

  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);
  }
  

• (If you want to make it work with floating point values, please, do not just blindly replace the intdeclarations in the headers. It is bad practice. They are there for a reason. One should always work with some upper bound on the error when comparing floating point results.)

• 平移四边形，使其顶点之一现在位于原点
• 剩下的三个点从原点形成三个向量
• 其中之一必须代表对角线
• 另外两个必须代表双方
• 根据平行四边形规则，如果边形成对角线，我们有一个平行四边形
• 如果边成直角，它是一个有直角的平行四边形
• 平行四边形的对角相等
• 平行四边形的连续角是互补的
• 所以所有的角都是直角
• 它是一个矩形

• 不过，它在代码中更加简洁:-)

  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声明。这是不好的做法。它们存在是有原因的。人们应该始终使用错误的一些上限比较浮点结果时。）

回答by Carlos Gutiérrez

The distance from one point to the other 3 should form a right triangle:

从一个点到另一个 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

Simplifying:

简化：

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

回答by Vineet Kapoor

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.

Here, we are using geometric properties of rectangle/squareand Bit Magic.

在这里，我们使用了rectangle/square和Bit Magic 的几何属性。

Rectangle properties in play

正在播放的矩形属性

1. Opposite sides and diagonals of a rectangle are of equal length.
2. If the diagonal length of a rectangle is sqrt(2) times any of its length, then the rectangle is a square.

1. 长方形的对边和对角线的长度相等。
2. 如果矩形的对角线长度是 sqrt(2) 乘以它的任何长度，则该矩形是正方形。

Bit Magic

位魔法

1. XORing equal value numbers return 0.

1. 对等值数进行异或运算返回 0。

Since distances between 4 corners of a rectangle will always form 3 pairs, one for diagonal and two for each side of different length, XORing all the values will return 0 for a rectangle.

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

回答by Axel Gneiting

If the points are A, B, C & D and you know the order then you calculate the vectors:

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

x=B-A, y=C-B, z=D-C and w=A-D

x=BA, y=CB, z=DC 和 w=AD

Then take the dot products (x dot y), (y dot z), (z dot w) and (w dot x). If they are all zero then you have a rectangle.

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

回答by manugupt1

We know that two staright lines are perpendicular if product of their slopes is -1,since a plane is given we can find the slopes of three consecutive lines and then multiply them to check if they are really perpendicular or not. Suppose we have lines L1,L2,L3. Now if L1 is perpendicular to L2 and L2 perpendicular to L3, then it is a rectangle and slope of the m(L1)*m(L2)=-1 and m(L2)*m(L3)=-1, then it implies it is a rectangle. The code is as follows

我们知道如果两条直线的斜率乘积为-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;
}

回答by David Meister

taking the dot product suggestion a step further, check if two of the vectors made by any 3 of the points of the points are perpendicular and then see if the x and y match the fourth point.

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

If you have points [Ax,Ay] [Bx,By] [Cx,Cy] [Dx,Dy]

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

vector v = B-A vector u = C-A

向量 v = BA 向量 u = CA

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

v(点)u/|v||u| == cos（θ）

so if (v.u == 0) there's a couple of perpendicular lines right there.

所以如果 (vu == 0) 那里有几条垂直线。

I actually don't know C programming, but here's some "meta" programming for you :P

我实际上不知道 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}

there's no square roots in this, and no potential for a divide by zero. I noticed people mentioning these issues on earlier posts so I thought I'd offer an alternative.

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

So, computationally, you need four subtractions to get v and u, two multiplications, one addition and you have to check somewhere between 1 and 7 equalities.

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

maybe I'm making this up, but i vaguely remember reading somewhere that subtractions and multiplications are "faster" calculations. I assume that declaring variables/arrays and setting their values is also quite fast?

也许我是在编造这个，但我依稀记得在某处读到减法和乘法是“更快”的计算。我认为声明变量/数组并设置它们的值也很快？

Sorry, I'm quite new to this kind of thing, so I'd love some feedback to what I just wrote.

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

Edit: try this based on my comment below:

编辑：根据我下面的评论试试这个：

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}

回答by Mike M.

I recently faced a similar challenge, but in Python, this is what I came up with in Python, perhaps this method may be valuable. The idea is that there are six lines, and if created into a set, there should be 3 unique line distances remaining - the length, width, and diagonal.

我最近遇到了类似的挑战，但是在 Python 中，这是我在 Python 中提出的，也许这种方法可能很有价值。这个想法是有 6 条线，如果创建成一个集合，应该剩下 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

回答by Pedro Lopes

Here is my algorithm proposal, for an axis-aligned rectangle test, but in Python.

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

The idea is to grab the first point as a pivot, and that all the other points must conform to the same width and height, and checks that all points are distinct, via a set, to account for cases such as (1, 2), (1, 2), (10, 30), (10, 30).

这个想法是抓住第一个点作为枢轴，所有其他点必须符合相同的宽度和高度，并通过一组检查所有点是否不同，以解决诸如 (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)))