明经CAD社区

 找回密码
 注册

QQ登录

只需一步,快速开始

搜索
查看: 1046|回复: 11

[其它] 任意两个四边形等价 算法实现

[复制链接]
发表于 2023-2-7 11:18 | 显示全部楼层 |阅读模式
本帖最后由 landsat99 于 2023-2-7 12:31 编辑

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

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

不严谨之处,多多交流。



  1. # EquRec.py
  2. def Dist(P1, P2):
  3.     return (P2[0] - P1[0])**2 + (P2[1] - P1[1])**2

  4. def LenList(PoiArr):
  5.     dist1 = Dist(PoiArr[0], PoiArr[1])
  6.     dist2 = Dist(PoiArr[1], PoiArr[2])
  7.     dist3 = Dist(PoiArr[2], PoiArr[3])
  8.     dist4 = Dist(PoiArr[3], PoiArr[0])
  9.     crs1 = Dist(PoiArr[0], PoiArr[2])
  10.     crs2 = Dist(PoiArr[1], PoiArr[3])
  11.     return [dist1, dist2, dist3, dist4], [crs1, crs2]

  12. RecA = [[1, 1], [4, 1], [4, 2], [1, 2]]; RecB = [[1, 1], [2, 1], [2, 4], [1, 4]]
  13. if set(LenList(RecA)[0])==set(LenList(RecB)[0]) and set(LenList(RecA)[1])==set(LenList(RecB)[1]):
  14.     print("----两个四边形 完全相等----")
  15. else:
  16.     print("**两个四边形 不同")







本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?注册

x
 楼主| 发表于 2023-2-8 17:11 | 显示全部楼层
本帖最后由 landsat99 于 2023-2-8 17:15 编辑

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


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



  1. # Vector.py
  2. import numpy as np
  3. import matplotlib.pyplot as plt

  4. class Rec():
  5.     def __init__(self, RecOri):
  6.         self.Data = np.append(RecOri.T, [[1, 1, 1, 1]], axis=0)

  7.     def Rotate(self, beta):  # 旋转 顺时针为正
  8.         rad = beta / 180 * np.pi
  9.         self.transform = np.array([[np.cos(rad), -np.sin(rad), 0],
  10.                                    [np.sin(rad), np.cos(rad), 0],
  11.                                    [0,              0,         1]])
  12.         return self.Process()

  13.     def Move(self, del_x, del_y):  # 平移 笛卡尔坐标方向
  14.         self.transform = np.array(
  15.             [[1, 0, del_x], [0, 1, del_y], [0, 0, 1]])
  16.         return self.Process()

  17.     def Hori(self, col=0):  # 水平镜像
  18.         self.col = col  # 镜像竖向轴 偏移量
  19.         self.transform = np.array(
  20.             [[-1, 0, self.col], [0, 1, 0], [0, 0, 1]])
  21.         return self.Process()

  22.     def Vert(self, row=0):  # 垂直镜像
  23.         self.row = row  # 镜像横向轴 偏移量
  24.         self.transform = np.array(
  25.             [[1, 0, 0], [0, -1, self.row], [0, 0, 1]])
  26.         return self.Process()

  27.     def Process(self):
  28.         Re = np.dot(self.transform, self.Data)
  29.         return np.delete(Re, 2, 0).T

  30. def plot2D(RecOri, RecNew):
  31.     x_ori = np.append(RecOri.T[0], [RecOri.T[0][0]])
  32.     y_ori = np.append(RecOri.T[1], [RecOri.T[1][0]])
  33.     x_new = np.append(RecNew.T[0], [RecNew.T[0][0]])
  34.     y_new = np.append(RecNew.T[1], [RecNew.T[1][0]])
  35.     plt.scatter(x_ori, y_ori, alpha=0.5)
  36.     ax = plt.gca()
  37.     ax.set_aspect(1)
  38.     ax.spines['right'].set_visible(False)
  39.     ax.spines['top'].set_visible(False)
  40.     ax.spines['left'].set_position(('data', 0))
  41.     ax.spines['bottom'].set_position(('data', 0))
  42.     plt.xlim(xmin=-5, xmax=10)
  43.     plt.ylim(ymin=-6, ymax=6)
  44.     plt.scatter(x_ori, y_ori)  # 画散点图
  45.     plt.plot(x_ori, y_ori)  # 画连线图
  46.     plt.scatter(x_new, y_new)
  47.     plt.plot(x_new, y_new)
  48.     plt.show()

  49. if __name__ == '__main__':
  50.     # 原始四边形 点集序列
  51.     RecOri = np.array([[1, 1], [3.5, 1], [4, 2], [2, 5]])
  52.     # 变换操作
  53.     RecObj_1 = Rec(RecOri)
  54.     RecNew = RecObj_1.Rotate(70)  # 旋转
  55.     RecNew = Rec(RecNew)
  56.     RecNew = RecNew.Move(3, -4)  # 平移
  57.     RecNew = Rec(RecNew)
  58.     RecNew = RecNew.Hori(2)  # 水平镜像
  59.     plot2D(RecOri, RecNew)


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

  1. # EquRec.py
  2. import matplotlib.pyplot as plt
  3. import numpy as np
  4. import Vector as ve

  5. def Dist(P1, P2):
  6.     return (P2[0] - P1[0])**2 + (P2[1] - P1[1])**2

  7. def LenList(PoiArr):
  8.     dist1 = round(Dist(PoiArr[0], PoiArr[1]), 4)
  9.     dist2 = round(Dist(PoiArr[1], PoiArr[2]), 4)
  10.     dist3 = round(Dist(PoiArr[2], PoiArr[3]), 4)
  11.     dist4 = round(Dist(PoiArr[3], PoiArr[0]), 4)
  12.     crs1 = round(Dist(PoiArr[0], PoiArr[2]), 4)
  13.     crs2 = round(Dist(PoiArr[1], PoiArr[3]), 4)
  14.     return [dist1, dist2, dist3, dist4], [crs1, crs2]

  15. RecA = np.array([[1, 1], [4, 1], [4, 2], [1, 2]])
  16. RectObj = ve.Rec(RecA)
  17. RecB = RectObj.Rotate(60)
  18. if set(LenList(RecA)[0]) == set(LenList(RecB)[0]) and set(LenList(RecA)[1]) == set(LenList(RecB)[1]):
  19.     print("----两个四边形 完全相等----")
  20. else:
  21.     print("**两个四边形 不同")

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?注册

x
 楼主| 发表于 2023-2-9 13:48 来自手机 | 显示全部楼层
chixun99 发表于 2023-2-9 10:53
哦,原来是这个语言。这个判断等价的图形能不能做到更复杂呢?例如多边形,或者任意形状多段线的图形这种 ...

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

n>=5必须是链表匹配。n=3,4可用效率优先的集合算法
发表于 2023-2-9 11:48 来自手机 | 显示全部楼层
chixun99 发表于 2023-2-9 10:53
哦,原来是这个语言。这个判断等价的图形能不能做到更复杂呢?例如多边形,或者任意形状多段线的图形这种 ...

当然可以,任意多边形。
不仅等价,缩放也可以一并判断的。
 楼主| 发表于 2023-2-7 12:46 | 显示全部楼层
需要说明,,

需要判断两组对角线,而不是仅一组。 两组判断是必要的!
例图片中第二类,其一角可分处虚线两侧.。四边长相同且一组对角线相同,但图形完全不同。
发表于 2023-2-8 10:00 来自手机 | 显示全部楼层
能否将平移,旋转,镜像整合到一个判别式中?
发表于 2023-2-8 10:09 | 显示全部楼层
这是什么语言的代码?好像又能看懂,跟熟悉的又不完全一样?
 楼主| 发表于 2023-2-8 16:49 | 显示全部楼层
chixun99 发表于 2023-2-8 10:09
这是什么语言的代码?好像又能看懂,跟熟悉的又不完全一样?

是个python算法
 楼主| 发表于 2023-2-8 16:59 | 显示全部楼层
mahuan1279 发表于 2023-2-8 10:00
能否将平移,旋转,镜像整合到一个判别式中?

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






发表于 2023-2-9 10:53 | 显示全部楼层
  楼主| 发表于 2023-2-8 16:49
是个python算法

哦,原来是这个语言。这个判断等价的图形能不能做到更复杂呢?例如多边形,或者任意形状多段线的图形这种。
您需要登录后才可以回帖 登录 | 注册

本版积分规则

小黑屋|手机版|CAD论坛|CAD教程|CAD下载|联系我们|关于明经|明经通道 ( 粤ICP备05003914号 )  
©2000-2023 明经通道 版权所有 本站代码,在未取得本站及作者授权的情况下,不得用于商业用途

GMT+8, 2024-3-29 13:33 , Processed in 0.180968 second(s), 25 queries , Gzip On.

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表