任意两个四边形等价 算法实现

landsat99

算法说明：
1. 四边形等价。等价定义为：任意一个四边形经平移、旋转、翻转、镜像后，仍与原型等价。
2. 四边形等价算法。此算法为：判断四边形的边长集合相同；且隔点连线（两对角线）长度集合相同。
3. 此算法使用 集合判断。非序列判断。 四边长度序列，转化为长度集合（等同排序 并去除重复值）。

个人认为，以上是四边形等价的一组”充要条件“。即：
四边边长的集合相等 且两对角线长度的集合相等，则四边形等价； 四边形等价，则必然四边长的集合、对角长集合相等。
目前未发现反例。

不严谨之处，多多交流。

1. # EquRec.py
   
2. def Dist(P1, P2):
   
3.     return (P2[0] - P1[0])**2 + (P2[1] - P1[1])**2
   
4. 
   
5. def LenList(PoiArr):
   
6.     dist1 = Dist(PoiArr[0], PoiArr[1])
   
7.     dist2 = Dist(PoiArr[1], PoiArr[2])
   
8.     dist3 = Dist(PoiArr[2], PoiArr[3])
   
9.     dist4 = Dist(PoiArr[3], PoiArr[0])
   
10.     crs1 = Dist(PoiArr[0], PoiArr[2])
    
11.     crs2 = Dist(PoiArr[1], PoiArr[3])
    
12.     return [dist1, dist2, dist3, dist4], [crs1, crs2]
    
13. 
    
14. RecA = [[1, 1], [4, 1], [4, 2], [1, 2]]; RecB = [[1, 1], [2, 1], [2, 4], [1, 4]]
    
15. if set(LenList(RecA)[0])==set(LenList(RecB)[0]) and set(LenList(RecA)[1])==set(LenList(RecB)[1]):
    
16.     print("----两个四边形 完全相等----")
    
17. else:
    
18.     print("**两个四边形 不同")
    

# EquRec.py<br /> def Dist(P1, P2):<br />     return (P2[0] - P1[0])**2 + (P2[1] - P1[1])**2<br /> <br /> def LenList(PoiArr):<br />     dist1 = Dist(PoiArr[0], PoiArr[1])<br />     dist2 = Dist(PoiArr[1], PoiArr[2])<br />     dist3 = Dist(PoiArr[2], PoiArr[3])<br />     dist4 = Dist(PoiArr[3], PoiArr[0])<br />     crs1 = Dist(PoiArr[0], PoiArr[2])<br />     crs2 = Dist(PoiArr[1], PoiArr[3])<br />     return [dist1, dist2, dist3, dist4], [crs1, crs2]<br /> <br /> RecA = [[1, 1], [4, 1], [4, 2], [1, 2]]; RecB = [[1, 1], [2, 1], [2, 4], [1, 4]]<br /> if set(LenList(RecA)[0])==set(LenList(RecB)[0]) and set(LenList(RecA)[1])==set(LenList(RecB)[1]):<br />     print("----两个四边形 完全相等----")<br /> else:<br />     print("**两个四边形 不同")<br />

landsat99

测试配套的  坐标变换 平移 旋转 镜像附上。


比如：对一个Rectangle 同时进行了 旋转 平移 水平镜像加偏移，生成新的Rec。
然后新旧Rec 对比，判断是否等价。

1. # Vector.py
   
2. import numpy as np
   
3. import matplotlib.pyplot as plt
   
4. 
   
5. class Rec():
   
6.     def __init__(self, RecOri):
   
7.         self.Data = np.append(RecOri.T, [[1, 1, 1, 1]], axis=0)
   
8. 
   
9.     def Rotate(self, beta):  # 旋转 顺时针为正
   
10.         rad = beta / 180 * np.pi
    
11.         self.transform = np.array([[np.cos(rad), -np.sin(rad), 0],
    
12.                                    [np.sin(rad), np.cos(rad), 0],
    
13.                                    [0,              0,         1]])
    
14.         return self.Process()
    
15. 
    
16.     def Move(self, del_x, del_y):  # 平移 笛卡尔坐标方向
    
17.         self.transform = np.array(
    
18.             [[1, 0, del_x], [0, 1, del_y], [0, 0, 1]])
    
19.         return self.Process()
    
20. 
    
21.     def Hori(self, col=0):  # 水平镜像
    
22.         self.col = col  # 镜像竖向轴 偏移量
    
23.         self.transform = np.array(
    
24.             [[-1, 0, self.col], [0, 1, 0], [0, 0, 1]])
    
25.         return self.Process()
    
26. 
    
27.     def Vert(self, row=0):  # 垂直镜像
    
28.         self.row = row  # 镜像横向轴 偏移量
    
29.         self.transform = np.array(
    
30.             [[1, 0, 0], [0, -1, self.row], [0, 0, 1]])
    
31.         return self.Process()
    
32. 
    
33.     def Process(self):
    
34.         Re = np.dot(self.transform, self.Data)
    
35.         return np.delete(Re, 2, 0).T
    
36. 
    
37. def plot2D(RecOri, RecNew):
    
38.     x_ori = np.append(RecOri.T[0], [RecOri.T[0][0]])
    
39.     y_ori = np.append(RecOri.T[1], [RecOri.T[1][0]])
    
40.     x_new = np.append(RecNew.T[0], [RecNew.T[0][0]])
    
41.     y_new = np.append(RecNew.T[1], [RecNew.T[1][0]])
    
42.     plt.scatter(x_ori, y_ori, alpha=0.5)
    
43.     ax = plt.gca()
    
44.     ax.set_aspect(1)
    
45.     ax.spines['right'].set_visible(False)
    
46.     ax.spines['top'].set_visible(False)
    
47.     ax.spines['left'].set_position(('data', 0))
    
48.     ax.spines['bottom'].set_position(('data', 0))
    
49.     plt.xlim(xmin=-5, xmax=10)
    
50.     plt.ylim(ymin=-6, ymax=6)
    
51.     plt.scatter(x_ori, y_ori)  # 画散点图
    
52.     plt.plot(x_ori, y_ori)  # 画连线图
    
53.     plt.scatter(x_new, y_new)
    
54.     plt.plot(x_new, y_new)
    
55.     plt.show()
    
56. 
    
57. if __name__ == '__main__':
    
58.     # 原始四边形 点集序列
    
59.     RecOri = np.array([[1, 1], [3.5, 1], [4, 2], [2, 5]])
    
60.     # 变换操作
    
61.     RecObj_1 = Rec(RecOri)
    
62.     RecNew = RecObj_1.Rotate(70)  # 旋转
    
63.     RecNew = Rec(RecNew)
    
64.     RecNew = RecNew.Move(3, -4)  # 平移
    
65.     RecNew = Rec(RecNew)
    
66.     RecNew = RecNew.Hori(2)  # 水平镜像
    
67.     plot2D(RecOri, RecNew)
    

# Vector.py<br /> import numpy as np<br /> import matplotlib.pyplot as plt<br /> <br /> class Rec():<br />     def __init__(self, RecOri):<br />         self.Data = np.append(RecOri.T, [[1, 1, 1, 1]], axis=0)<br /> <br />     def Rotate(self, beta):  # 旋转 顺时针为正<br />         rad = beta / 180 * np.pi<br />         self.transform = np.array([[np.cos(rad), -np.sin(rad), 0],<br />                                    [np.sin(rad), np.cos(rad), 0],<br />                                    [0,              0,         1]])<br />         return self.Process()<br /> <br />     def Move(self, del_x, del_y):  # 平移 笛卡尔坐标方向<br />         self.transform = np.array(<br />             [[1, 0, del_x], [0, 1, del_y], [0, 0, 1]])<br />         return self.Process()<br /> <br />     def Hori(self, col=0):  # 水平镜像<br />         self.col = col  # 镜像竖向轴 偏移量<br />         self.transform = np.array(<br />             [[-1, 0, self.col], [0, 1, 0], [0, 0, 1]])<br />         return self.Process()<br /> <br />     def Vert(self, row=0):  # 垂直镜像<br />         self.row = row  # 镜像横向轴 偏移量<br />         self.transform = np.array(<br />             [[1, 0, 0], [0, -1, self.row], [0, 0, 1]])<br />         return self.Process()<br /> <br />     def Process(self):<br />         Re = np.dot(self.transform, self.Data)<br />         return np.delete(Re, 2, 0).T<br /> <br /> def plot2D(RecOri, RecNew):<br />     x_ori = np.append(RecOri.T[0], [RecOri.T[0][0]])<br />     y_ori = np.append(RecOri.T[1], [RecOri.T[1][0]])<br />     x_new = np.append(RecNew.T[0], [RecNew.T[0][0]])<br />     y_new = np.append(RecNew.T[1], [RecNew.T[1][0]])<br />     plt.scatter(x_ori, y_ori, alpha=0.5)<br />     ax = plt.gca()<br />     ax.set_aspect(1)<br />     ax.spines['right'].set_visible(False)<br />     ax.spines['top'].set_visible(False)<br />     ax.spines['left'].set_position(('data', 0))<br />     ax.spines['bottom'].set_position(('data', 0))<br />     plt.xlim(xmin=-5, xmax=10)<br />     plt.ylim(ymin=-6, ymax=6)<br />     plt.scatter(x_ori, y_ori)  # 画散点图<br />     plt.plot(x_ori, y_ori)  # 画连线图<br />     plt.scatter(x_new, y_new)<br />     plt.plot(x_new, y_new)<br />     plt.show()<br /> <br /> if __name__ == '__main__':<br />     # 原始四边形 点集序列<br />     RecOri = np.array([[1, 1], [3.5, 1], [4, 2], [2, 5]])<br />     # 变换操作<br />     RecObj_1 = Rec(RecOri)<br />     RecNew = RecObj_1.Rotate(70)  # 旋转<br />     RecNew = Rec(RecNew)<br />     RecNew = RecNew.Move(3, -4)  # 平移<br />     RecNew = Rec(RecNew)<br />     RecNew = RecNew.Hori(2)  # 水平镜像<br />     plot2D(RecOri, RecNew)<br />

对比等价算法 （浮点精度 此处设为4位）

1. # EquRec.py
   
2. import matplotlib.pyplot as plt
   
3. import numpy as np
   
4. import Vector as ve
   
5. 
   
6. def Dist(P1, P2):
   
7.     return (P2[0] - P1[0])**2 + (P2[1] - P1[1])**2
   
8. 
   
9. def LenList(PoiArr):
   
10.     dist1 = round(Dist(PoiArr[0], PoiArr[1]), 4)
    
11.     dist2 = round(Dist(PoiArr[1], PoiArr[2]), 4)
    
12.     dist3 = round(Dist(PoiArr[2], PoiArr[3]), 4)
    
13.     dist4 = round(Dist(PoiArr[3], PoiArr[0]), 4)
    
14.     crs1 = round(Dist(PoiArr[0], PoiArr[2]), 4)
    
15.     crs2 = round(Dist(PoiArr[1], PoiArr[3]), 4)
    
16.     return [dist1, dist2, dist3, dist4], [crs1, crs2]
    
17. 
    
18. RecA = np.array([[1, 1], [4, 1], [4, 2], [1, 2]])
    
19. RectObj = ve.Rec(RecA)
    
20. RecB = RectObj.Rotate(60)
    
21. if set(LenList(RecA)[0]) == set(LenList(RecB)[0]) and set(LenList(RecA)[1]) == set(LenList(RecB)[1]):
    
22.     print("----两个四边形 完全相等----")
    
23. else:
    
24.     print("**两个四边形 不同")
    

# EquRec.py<br /> import matplotlib.pyplot as plt<br /> import numpy as np<br /> import Vector as ve<br /> <br /> def Dist(P1, P2):<br />     return (P2[0] - P1[0])**2 + (P2[1] - P1[1])**2<br /> <br /> def LenList(PoiArr):<br />     dist1 = round(Dist(PoiArr[0], PoiArr[1]), 4)<br />     dist2 = round(Dist(PoiArr[1], PoiArr[2]), 4)<br />     dist3 = round(Dist(PoiArr[2], PoiArr[3]), 4)<br />     dist4 = round(Dist(PoiArr[3], PoiArr[0]), 4)<br />     crs1 = round(Dist(PoiArr[0], PoiArr[2]), 4)<br />     crs2 = round(Dist(PoiArr[1], PoiArr[3]), 4)<br />     return [dist1, dist2, dist3, dist4], [crs1, crs2]<br /> <br /> RecA = np.array([[1, 1], [4, 1], [4, 2], [1, 2]])<br /> RectObj = ve.Rec(RecA)<br /> RecB = RectObj.Rotate(60)<br /> if set(LenList(RecA)[0]) == set(LenList(RecB)[0]) and set(LenList(RecA)[1]) == set(LenList(RecB)[1]):<br />     print("----两个四边形 完全相等----")<br /> else:<br />     print("**两个四边形 不同")<br />

landsat99

chixun99 发表于 2023-2-9 10:53
哦，原来是这个语言。这个判断等价的图形能不能做到更复杂呢？例如多边形，或者任意形状多段线的图形这种 ...

算法基本一致。差别是，集合匹配改为链表匹配。

n>=5必须是链表匹配。n=3,4可用效率优先的集合算法

zml84

chixun99 发表于 2023-2-9 10:53
哦，原来是这个语言。这个判断等价的图形能不能做到更复杂呢？例如多边形，或者任意形状多段线的图形这种 ...

当然可以，任意多边形。
不仅等价，缩放也可以一并判断的。

landsat99

需要说明，，

需要判断两组对角线，而不是仅一组。 两组判断是必要的！
例图片中第二类，其一角可分处虚线两侧.。四边长相同且一组对角线相同，但图形完全不同。

中国梦

不错，不错

mahuan1279

能否将平移，旋转，镜像整合到一个判别式中？

chixun99

这是什么语言的代码？好像又能看懂，跟熟悉的又不完全一样？

landsat99

chixun99 发表于 2023-2-8 10:09
这是什么语言的代码？好像又能看懂，跟熟悉的又不完全一样？

是个python算法

landsat99

mahuan1279 发表于 2023-2-8 10:00
能否将平移，旋转，镜像整合到一个判别式中？

是指一个命令 同时完成旋转 平移 镜像操作？ 接口设计成需要的格式就ok了，这个没问题的。，

chixun99

  楼主| 发表于 2023-2-8 16:49
是个python算法

哦，原来是这个语言。这个判断等价的图形能不能做到更复杂呢？例如多边形，或者任意形状多段线的图形这种。