2007-09-06

 

算法学习: 判读四点是否构成矩形

需求:

给定4个点的坐标,判断这4点是否构成一个矩形.

讨论:

这是我遇到的一个笔试题,在这里给出一个自己想的算法:

在四个点中取第一点为基点,分别算出到其它三点的距离.如果这三个值满足勾股定理,则:
1.该四点构成矩形
2.该四点构成平行四边形

对于第二种情况,再进行判读,如果其中心与重心重回,即四点在一个圆上,则该四点构成矩形.

程序如下:

def IsSquire(*arg):
    x1,y1 = arg[0]
    x2,y2 = arg[1]
    x3,y3 = arg[2]
    x4,y4 = arg[3]
    line1 = (x1-x2)**2 + (y1-y2)**2
    line2 = (x1-x3)**2 + (y1-y3)**2
    line3 = (x1-x4)**2 + (y1-y4)**2
    if (abs(line1-line2))==line3 or (line1+line2)==line3:
        x0 = (x1+x2+x3+x4)/4
        y0 = (y1+y2+y3+y4)/4
        if (x1-x0)**2+(y1-y0)**2 == (x2-x0)**2+(y2-y0)**2 == (x3-x0)**2+(y3-y0)**2 == (x4-x0)**2+(y4-y0)**2:
            return True
    return False
if __name__=="__main__":
    print IsSquire((0,0),(1,0),(0,1),(-1,1))

其实更简单一些的方法是判断中心是否在较长的边上即可,不过那样代码要些很多if.

Comments: 发表评论



<< Home

This page is powered by Blogger. Isn't yours?