请有人以C风格伪代码展示如何编写一个函数（无论您喜欢哪种表示点的方式），该函数返回true，如果4个点（作为函数参数）形成一个矩形，否则返回false？
我想出了一种解决方案，首先尝试找到两个具有相等x值的不同点对，然后对y轴做同样处理。 但是代码相当冗长。 只是好奇看看别人会想出什么。
11个回答
74
- 查找角点的质心：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;
}
- Curd
18
4这是一个聪明的解决方案。它基本上是找到“矩形”的外接圆并验证所有四个角点是否位于其上。 - rlbond
9这非常低效。使用Vlad提供的点积法。平方根需要数百个时钟周期。此外，点积法在数值上更稳定。 - Axel Gneiting
6@Axel和@Curd：解决方案自最初发布以来是否已被编辑？我没有看到任何平方根。我假设
sqr(x)==x*x，这意味着ddi实际上是从cx到xi的距离的平方。这应该非常快速。 - Brett Pontarelli5好的，那我需要道歉。我以为"sqr"代表平方根。 - Axel Gneiting
4关于性能的一些注意事项：
此解决方案需要进行20次常量4的加、减、除以及8次乘法运算。
如果第一或第二次比较失败，甚至可以优化以消除余下的平方距离计算。因此上述数字代表最坏情况。
即使是最坏情况，也和Vlad的解决方案的最优情况一样好，并且比其最坏情况快3倍。 - Curd
显示剩余13条评论
48
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);
}
- Vlad
10
@Larry：你的测试只是为了检测是否为平行四边形。 - Vlad
@Larry：现在检查对角线是正确的，但你的测试需要进行6次平方根运算。 - Vlad
1@Timmy：在这种情况下，需要进行更复杂的检查：
if (IsOrthogonal(a, b, c)) return IsRectangle(a, b, c, d); else if (IsOrthogonal(a, b, d)) return IsRectangle(a, b, d, c); else return false; - Vlad1IsOrthogonal((10,9),(15,9),(15,6)) = 0或False。
(15-10)(15-15)+(9-9)(9-6)=0。
是否缺少一个！？ - Harvey
@Vlad：你能否像@Curd一样，解释一下你的方法在最坏情况下的运行时间复杂度，以算术操作为单位？ - Andras Vass
显示剩余5条评论
7
- 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 rule if 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 int declarations 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.)
- Andras Vass
1
最坏情况：15次加减法，6次乘法。 - Andras Vass
7
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.
在这里，我们使用了矩形/正方形的几何性质和位运算魔术。
发挥作用的矩形属性：
1. 矩形的对边和对角线长度相等。 2. 如果矩形的对角线长度是其任意一条边长的sqrt(2)倍，则该矩形为正方形。
位运算魔术：
1. XOR等值数的结果为0。
由于矩形4个角之间的距离总是形成3组，一组为对角线，另外两组为不同长度的每条边。对所有值进行XOR操作将会对矩形返回0。
- Vineet Kapoor
2
很酷的想法，但如果您需要测试相等性并考虑浮点精度的小容差，则可能不切实际。另外，值得补充的是，异或技巧之所以有效，是因为异或运算是可交换和可结合的。 - Ed Bordin
为什么不直接检查4个距离是否相等呢？ - diegoide
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
- Carlos Gutiérrez
5
@andras - 测试了几个平行四边形，全部都被评估为假。你在考虑特定的情况吗？ - Carlos Gutiérrez
1假设我们有点x1=3，y1=3；x2=0，y2=0；x3=6，y3=0；x4=9，y4=3；
现在d1 = 18; d2 = 18; d3 = 36; 不过时间已经很晚了。 :-)
请您检查一下？ - Andras Vass
@andras - 你说得对，看起来测试必须使用3个点作为起点重复进行。 - Carlos Gutiérrez
1请你对此采取行动。 - Andras Vass
这是错误的，最后一行必须是 d1^2 == d2^2+d3^2 或 d2^2 == d1^2 + d3^2 或 d3^2 == d1^2 + d2 ^2。 - Masoud Darzi
4
如果给定点A、B、C和D，并且你知道它们的顺序，那么可以计算出向量：
x=B-A，y=C-B，z=D-C，w=A-D
然后进行点积运算(x·y)，(y·z)，(z·w)和(w·x)。如果它们都为零，则表示这是一个矩形。
x=B-A，y=C-B，z=D-C，w=A-D
然后进行点积运算(x·y)，(y·z)，(z·w)和(w·x)。如果它们都为零，则表示这是一个矩形。
- Axel Gneiting
1
如果您知道顺序，那么检查 |x| = |z|，|y| = |w| 和一个点积就足够了。（因为相反的边必须长度相等，所以有不少四边形的相反边长度相等。） - Andras Vass
2
我们知道，如果两条直线的斜率的乘积为-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;
}
- manugupt1
2
我认为这是计算效率最高的。 - milesmeow
2你也应该检查m4，否则可能会得到一个梯形。 - Andras Vass
2
进一步推荐采用点积方法，检查由任意3个点组成的向量中是否有两个互相垂直，并查看它们的x和y是否与第四个点匹配。
如果你有点[Ax,Ay] [Bx,By] [Cx,Cy] [Dx,Dy]
向量v = B-A 向量u = C-A
v(dot)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}
- David Meister
1
啊，我刚意识到这个问题与轴平行。所以，不应该在结尾处使用if语句，而是应该测试是否为(D == A + v + u)。我还注意到，如果你的前三个点中有对角线，它可能会给出错误的结果，因此如果点积失败，应该将u重新定义为AD并重试。 - David Meister
2
我最近也遇到了类似的挑战，但是在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
- Mike M.
1
首先验证这四个点是否能够构成平行四边形，然后再找出是否存在一个直角。
1. 验证平行四边形
输入4个点A、B、C、D;
如果(A、B、C、D是同一个点)，退出;// 不是矩形;
否则，形成3个向量AB、AC、AD，验证(AB=AC+AD || AC=AB+AD || AD=AB+AC)，\\如果其中一个满足，则为平行四边形;
2.验证直角
通过上一步，我们可以找到哪两个点是A的相邻点;
我们需要找出角A是否为直角，如果是，则为矩形。
我不知道是否存在错误。请查找并纠正。
- bob wong
3
请确保您的回答实际上是 OP 问题的答案。他问如何找出点是否形成矩形，而不是是否形成平行四边形。此外，一个直角并不能保证是矩形。 - user9945700
1嗯，一个有直角的平行四边形是一个矩形，所以我相信在上述两个步骤中验证它可能会起作用。 - bob wong
抱歉，是我的错，我想错了。 - user9945700
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接