任意两个四边形等价 算法实现
本帖最后由 landsat99 于 2023-2-7 12:31 编辑算法说明：
1. 四边形等价。等价定义为：任意一个四边形经平移、旋转、翻转、镜像后，仍与原型等价。
2. 四边形等价算法。此算法为：判断四边形的边长集合相同；且隔点连线（两对角线）长度集合相同。
3. 此算法使用 集合判断。非序列判断。 四边长度序列，转化为长度集合（等同排序 并去除重复值）。
个人认为，以上是四边形等价的一组”充要条件“。即：
四边边长的集合相等 且两对角线长度的集合相等，则四边形等价； 四边形等价，则必然四边长的集合、对角长集合相等。
目前未发现反例。
不严谨之处，多多交流。
# EquRec.py
def Dist(P1, P2):
return (P2 - P1)**2 + (P2 - P1)**2
def LenList(PoiArr):
dist1 = Dist(PoiArr, PoiArr)
dist2 = Dist(PoiArr, PoiArr)
dist3 = Dist(PoiArr, PoiArr)
dist4 = Dist(PoiArr, PoiArr)
crs1 = Dist(PoiArr, PoiArr)
crs2 = Dist(PoiArr, PoiArr)
return ,
RecA = [, , , ]; RecB = [, , , ]
if set(LenList(RecA))==set(LenList(RecB)) and set(LenList(RecA))==set(LenList(RecB)):
print("----两个四边形 完全相等----")
else:
print("**两个四边形 不同")
本帖最后由 landsat99 于 2023-2-8 17:15 编辑
测试配套的坐标变换 平移 旋转 镜像附上。
比如：对一个Rectangle 同时进行了 旋转 平移 水平镜像加偏移，生成新的Rec。
然后新旧Rec 对比，判断是否等价。
# Vector.py
import numpy as np
import matplotlib.pyplot as plt
class Rec():
def __init__(self, RecOri):
self.Data = np.append(RecOri.T, [], axis=0)
def Rotate(self, beta):# 旋转 顺时针为正
rad = beta / 180 * np.pi
self.transform = np.array([,
,
])
return self.Process()
def Move(self, del_x, del_y):# 平移 笛卡尔坐标方向
self.transform = np.array(
[, , ])
return self.Process()
def Hori(self, col=0):# 水平镜像
self.col = col# 镜像竖向轴 偏移量
self.transform = np.array(
[[-1, 0, self.col], , ])
return self.Process()
def Vert(self, row=0):# 垂直镜像
self.row = row# 镜像横向轴 偏移量
self.transform = np.array(
[, , ])
return self.Process()
def Process(self):
Re = np.dot(self.transform, self.Data)
return np.delete(Re, 2, 0).T
def plot2D(RecOri, RecNew):
x_ori = np.append(RecOri.T, ])
y_ori = np.append(RecOri.T, ])
x_new = np.append(RecNew.T, ])
y_new = np.append(RecNew.T, ])
plt.scatter(x_ori, y_ori, alpha=0.5)
ax = plt.gca()
ax.set_aspect(1)
ax.spines['right'].set_visible(False)
ax.spines['top'].set_visible(False)
ax.spines['left'].set_position(('data', 0))
ax.spines['bottom'].set_position(('data', 0))
plt.xlim(xmin=-5, xmax=10)
plt.ylim(ymin=-6, ymax=6)
plt.scatter(x_ori, y_ori)# 画散点图
plt.plot(x_ori, y_ori)# 画连线图
plt.scatter(x_new, y_new)
plt.plot(x_new, y_new)
plt.show()
if __name__ == '__main__':
# 原始四边形 点集序列
RecOri = np.array([, , , ])
# 变换操作
RecObj_1 = Rec(RecOri)
RecNew = RecObj_1.Rotate(70)# 旋转
RecNew = Rec(RecNew)
RecNew = RecNew.Move(3, -4)# 平移
RecNew = Rec(RecNew)
RecNew = RecNew.Hori(2)# 水平镜像
plot2D(RecOri, RecNew)
对比等价算法 （浮点精度 此处设为4位）
# EquRec.py
import matplotlib.pyplot as plt
import numpy as np
import Vector as ve
def Dist(P1, P2):
return (P2 - P1)**2 + (P2 - P1)**2
def LenList(PoiArr):
dist1 = round(Dist(PoiArr, PoiArr), 4)
dist2 = round(Dist(PoiArr, PoiArr), 4)
dist3 = round(Dist(PoiArr, PoiArr), 4)
dist4 = round(Dist(PoiArr, PoiArr), 4)
crs1 = round(Dist(PoiArr, PoiArr), 4)
crs2 = round(Dist(PoiArr, PoiArr), 4)
return ,
RecA = np.array([, , , ])
RectObj = ve.Rec(RecA)
RecB = RectObj.Rotate(60)
if set(LenList(RecA)) == set(LenList(RecB)) and set(LenList(RecA)) == set(LenList(RecB)):
print("----两个四边形 完全相等----")
else:
print("**两个四边形 不同")
chixun99 发表于 2023-2-9 10:53
哦，原来是这个语言。这个判断等价的图形能不能做到更复杂呢？例如多边形，或者任意形状多段线的图形这种 ...
算法基本一致。差别是，集合匹配改为链表匹配。
n>=5必须是链表匹配。n=3,4可用效率优先的集合算法 chixun99 发表于 2023-2-9 10:53
哦，原来是这个语言。这个判断等价的图形能不能做到更复杂呢？例如多边形，或者任意形状多段线的图形这种 ...
当然可以，任意多边形。
不仅等价，缩放也可以一并判断的。 需要说明，，
需要判断两组对角线，而不是仅一组。 两组判断是必要的！
例图片中第二类，其一角可分处虚线两侧.。四边长相同且一组对角线相同，但图形完全不同。 不错，不错 能否将平移，旋转，镜像整合到一个判别式中？ 这是什么语言的代码？好像又能看懂，跟熟悉的又不完全一样？ chixun99 发表于 2023-2-8 10:09
这是什么语言的代码？好像又能看懂，跟熟悉的又不完全一样？
是个python算法 mahuan1279 发表于 2023-2-8 10:00
能否将平移，旋转，镜像整合到一个判别式中？
是指一个命令 同时完成旋转 平移 镜像操作？ 接口设计成需要的格式就ok了，这个没问题的。，
楼主| 发表于 2023-2-8 16:49
是个python算法
哦，原来是这个语言。这个判断等价的图形能不能做到更复杂呢？例如多边形，或者任意形状多段线的图形这种。
页:
[1]
2