找到一个平面上的4个点是否形成一个矩形？

Question

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

我想出了一个解决方案,首先尝试找到具有相等x值的2对不同的点,然后对y轴进行此操作.但代码相当长.只是想知道其他人想出了什么.

Answer 1

• 找到角点的质心: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(ab)<1E-6)

Answer 2

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

Answer 3

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

Answer 4

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

x=BA、y=CB、z=DC 且 w=AD

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

Answer 5

• 平移四边形,使其顶点之一现在位于原点
• 剩下的三个点从原点形成三个向量
• 其中一个必须代表对角线
• 另外两个必须代表双方
• 通过平行四边形规则,如果边形成对角线,我们有一个平行四边形
• 如果两侧形成直角,则它是具有直角的平行四边形
• 平行四边形的相反角度相等
• 平行四边形的连续角度是补充的
• 因此所有角度都是直角
• 它是一个矩形

• 它在代码中更简洁,但是:-)

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

Answer 6

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.

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

正在播放的矩形属性

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

位魔法

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

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