0 引言
机构创新设计可分为机构型综合和机构尺度综合
[1-2]。型综合作为机构设计理论构建的重要基础,能够系统地得到完整的结构构型图谱,有助于推动新型机构的创造与发展
[3-4]。目前已有许多成功应用于运动链型综合的方法,但型综合结果往往极为庞大。例如,MANIKANDAN等
[5]综合出12构件、3自由度全铰链运动链,共有25 125种不同构型。采用拓扑图表达运动链结构,便于建立数学模型与计算机生成
[6-7],但拓扑图绘制需解决线条交叉、多边形凹进、结构对称美观性等问题
[8],因此,研究更加简洁易懂的拓扑图绘制方法是机构综合的一个重要分支。
OLSON等
[9]首次提出将拓扑图转化为点、线的自动绘制方法,适用于简单运动链,但复杂运动链易产生连杆交叉。此后,研究者不断优化绘制方法,以提高图形的可视性和对称性。BEFIORE等
[10]提出将回路绘制成凸多边形,避免边交叉,成功实现8连杆和10连杆平面运动链的自动绘制。MAUSKAR等
[11]利用邻接矩阵提取独立环路并优化布局,可绘制出最多12杆非交叉运动链,但复杂度较高且未充分考虑对称性。LIU等
[12]在此基础上进行改进,参考循环配置的概念,提出基于标准化环路的绘制方法,一定程度上简化了环路生成和配置。NIE等
[13]利用收缩连杆邻接矩阵生成独立回路,结合环路加减法运算获取最大环路,绘制拓扑图。NIE等
[14]提出两杆三副加法方法,通过添加连杆生成新运动链,实现了最多12连杆及部分13、14连杆运动链的绘制。PUCHETA等
[15-16]提出基于回路置换的优化布局法,结合线形图和校正算法,实现了平面和非平面运动链的绘制。YAN等
[17]和CHU等
[18]基于邻接矩阵和收缩图,提出适用于最多16连杆广义运动链的自动绘制算法。DING等
[19-20]基于周长拓扑图及其特征描述代码实现拓扑图的自动生成,并建立图谱库。随后,YANG等
[21]引入移动标志和标志字符串的概念,设计优化算法,最大程度减少边缘交叉,简化复杂运动链的可视化过程。YANG等
[22]提出关节内角的概念与新校正算法,优化多连杆形态,绘制出6到19连杆及多回路运动链。SUN等
[23-24]提出基于关节-关节邻接矩阵的多关节平面运动链自动绘制方法,将型综合结果自动转换为可视化的运动链图。YU等
[25]提出基于弧回路、叉乘操作、同心圆的优化布局算法,实现了多连杆运动链的自动绘制。
本文采用树状结构图描述运动链结构信息,依据连接关系分离出支链生成支链矩阵。运用支链间的亲密度概念和交叉判定定理进行优化排列,最终在优化支链矩阵的基础上,提出了一种自动绘制出无交叉或最少交叉的拓扑图的新方法。
1 树状结构图与支链矩阵
LOHUMI等
[26]采用层次聚类算法将运动链转换为树状图并用于同构判定,以共生相关系数作为判定指标。该树状图属于聚集型或分裂型的无环层次结构,不包含闭合环路、多元复铰等结构。但运动链中通常存在多个闭合环路、多元构件和复铰,传统树状图难以有效表征。因此,本文引入相关定义,进一步完善树状图对运动链结构信息的描述。
图1a为包含四元构件、三元构件和复铰的11杆运动链结构图,本文结合案例给出以下定义。
1)根节点。树状结构图的第一层定义为根节点,选取运动链中的最大多元构件或复铰作为根节点,以减少层数。若存在多个最大多元构件或复铰,则随机选择;若元数一致,优先选择最大多元构件作为根节点。
图1a中,最大多元构件为四元构件11和1,选取构件11作为根节点,得到
图1b所示树状结构图。根节点只有一个,选择不同的根节点会产生不同的树状结构图。以运动链1为例,
图1b和
图1c分别为以构件11和1为根节点的树状结构图。
2)复铰。在树状结构图中,将复铰视为杆长为0的构件,用
Ji (
i=1,2,…)表示,与构件共同作为子节点。
图1a中,复铰
J1连接了构件3、7和4。
3)同层连接符。在树状结构图中,若同层子节点之间存在连接关系,用同层连接符
Bi 表示。
图1b中,复铰
J1和构件3存在同层连接关系,用同层连接符
B1进行描述。
4)主链。将根节点与第二层子节点间的连接关系称为主链。主链的数量取决于作为根节点的多元构件或复铰的元数。
图1b中,作为根节点,四元构件11有4条主链:11-7、11-8、11-10、11-6。
5)支链。从根节点开始,沿各层子节点向下或同层检索,直至最末端子节点,构成的连接关系称为支链。支链的最末端有两种情况:一是到达某子节点,该子节点没有下层子节点且与同层其他子节点没有连接关系;二是到达同层连接符
Bi。
图1b中,支链11-7-
J1-4末端为构件4,构件4无下层子节点且与同层子节点无连接关系。支链11-7-
J1-
B1中,复铰
J1与同层构件3存在连接关系,增加
B1描述该连接关系。树状结构图虽然能够直观地描述各构件和复铰之间的连接关系,但不便于计算机进行存储,由此引入了支链矩阵的概念。
6)支链矩阵。以树状结构图中的各支链依次作为矩阵行元素,行数为支链总数量,列数为最长支链的长度,构成的矩阵称为支链矩阵。对于较短支链,末尾用0补齐。
图1c树状结构图共有12个支链,由此支链矩阵行数为12,其中最长的支链涉及5层子节点,列数为5。
根据上述定义与规则,
图1a中以四元构件11和1作为根节点,生成的支链矩阵
M1和
M2如下:
对比两个支链矩阵发现,根节点的选取不同,树状结构图不同,支链矩阵的数字分布也不同。同时,支链矩阵和树状结构图具有唯一对应关系,即支链矩阵可推导出结构唯一确定的树状结构图,且由树状结构图按支链从左到右的顺序推导出的支链矩阵也有唯一性,如通过支链矩阵
M1可推导出树状结构图和结构图(
图1b和
图1a)。
2 优化支链矩阵
支链矩阵中,每行元素是依据从根节点到末端元素的连接顺序确定的,由此行内元素之间的相对位置固定。一旦根节点确定,每一个支链的信息确定,但支链矩阵中各个支链对应的行的排列顺序是可调整的。
如
图1b所示,运动链1对应的树状结构存在3次线条交叉,生成支链矩阵
M1,通过调整矩阵
M1行排列顺序,得到新的支链矩阵
M3:
根据
M3顺序进行绘制,得到
图2所示无交叉的树状结构图。本文提出支链之间的亲密度的定义和基于支链矩阵的交叉判定定理,进一步优化支链矩阵的行排列,得到无交叉或最少交叉的支链矩阵。
2.1 支链的亲密度
亲密度的定义:在支链矩阵中,第一列均为根节点。从第二列开始检索,若两个支链在第j列有相同子节点,则列数j表示两支链之间的亲密度。j值越大,亲密度越小。
按亲密度对支链矩阵进行优化排列时,若某支链被选为首选支链,在判断对比其他支链与其亲密度的过程中可能出现以下情况:
1)若存在两个或以上支链与首选支链在某列具有相同亲密度,则继续检索比较后续列元素,确定多个支链之间的排列顺序。如果后续列不存在相同的子节点,则随机排列,并记录所有可能的排列顺序。例如,在支链矩阵 M1中,若将支链a:11-8-J2-4作为首选支链,从第二列开始与其他支链进行检索对比,发现支链b:11-8-J2-5和支链c:11-8-9-B2在第二列与支链a有相同元素8。依次检索第三列,支链a与b在第三列有相同元素J2,而与支链c无相同元素。因此,支链a和b的亲密度更大,排列顺序应为先支链b,再支链c。
2)若存在两个或以上的支链与排序已经确定的支链具有相同亲密度,在优化过程中随机挑选其中一个支链进行排序,但后续支链的排列顺序依赖于前一个已排序支链的亲密度,因此,最初的随机选择直接影响后续支链的整体排列结果。例如,若选定 M1中支链a:11-6-1-2作为首选支链,支链b:11-6-1-5与支链c:11-6-1-B2与其具有相同亲密度。可能存在多种排列方式,如abc、bca、cab、bac、acb等,但abc与bac排列实际上是等效的,仅需考虑一种排列,最终产生以下三种不同矩阵:
其他支链则按亲密度依次排列。
2.2 交叉判定
交叉判定的定义:在支链矩阵中,除第一列根节点相同外,若存在两对不相邻的支链X1和X2、Y1和Y2在同一列或不同列中分别存在相同元素a和b,并且呈现交替排列形式(如a...b...a...b...),则判定这两对支链之间存在一次交叉。
如支链矩阵
M1中,第一行支链:11-7-
J1-4与第三行支链:11-8-
J2-4在第4列有相同元素4,第二行支链:11-7-
J1-
B1与第七行支链:11-6-3-
B1在第4列有相同元素
B1,形成了
图1b中的交叉。
如果两对不相邻支链X1、X2与Y1、Y2存在亲密度,且矩阵中相同元素呈现a...b...b...a...的排列,因为支链Y1、Y2的连接关系存在于X1、X2连接关系内部,故认为该情况不存在交叉。
例如,在支链矩阵 M1中,支链2:11-7-J1-B1、支链5:11-8-9-B2、支链6:11-10-9-B2和支链7:11-6-3-B1,支链2和支链7中的相同元素B1与支链5和支链6中的相同元素B2,呈现出a...b...b...a...的排列关系,由此不判定为交叉。
图的交叉数量:在运动链的树状结构图或拓扑图中,若描述构件之间连接关系的线条出现交叉,则所有交叉数量之和称为图的交叉数量。
图1b中,支链11-7-
J1-
B1与支链11-8-
J2-4存在一处交叉,支链11-6-3-
B1与11-10-9-
B2、11-6-1-5存在两处交叉,由此总交叉数量为3。
交叉判定规则:从支链矩阵的第j列(j≥2)开始检索,标记并记录同列中不相邻但相同的数字组合。若第j列第i行与第n行存在相同元素(且i+1< n),则记录组合(j,i,n)。对记录的数字组合进行判定,以第一个记录组合(j,i,n)中的(i,n)为基准,与第二个组合(m,g,h)中的(g,h)比较。当满足以下条件时,计为一次交叉:i < g< n且n < h或i < h< n且g < i;否则不计入交叉。若记录k组信息,两两进行判别,共进行次,最后统计交叉总数量。
如支链矩阵 M1中,第4列第1行和第3行出现不相邻但相同的元素4,记录为(4,1,3);第4列第2、7行出现了不相邻但相同的元素B1,记录为(4,2,7),根据规则判定,符合存在交叉的条件。
支链矩阵中两构件之间的连接关系可能出现多次,而对应的树状结构图中可能仅描述为一次连接,这种重复源于支链矩阵中不同行中同一连接关系的多次出现。因此,优化排列后,需进一步将重复出现的元素赋值为0,以避免在交叉判定时产生偏差。
具体赋值规则:从优化支链矩阵最后一列开始向左逐列检索,若第j列中元素a出现3次及以上且不相邻,则进一步检索重复元素a所在行的第j1列元素。若重复元素a与第j1列元素b存在两次及以上的连接关系,则保留与元素b的第一次连接关系,将其余与元素b存在连接关系的重复元素a赋值为0。
例如:在支链矩阵 M1中,第4列第5、6、10行出现不相邻但相同的重复元素B2,其对应的第3列元素为9、9、1,这表明9-B2的连接关系出现两次,由此需将第4列第6行的元素B2赋值为0,生成新的矩阵 M4:
2.3 支链矩阵的优化
基于亲密度的概念和交叉判定的分析,对支链矩阵进行优化排列,具体步骤如下:
1)选取主链下支链数量最少的支链作为首选支链。若存在多个满足条件的支链,随机选取一个。此步骤旨在减少多个支链与首选支链具有相同亲密度的情况,从而控制后续矩阵的生成数量。以支链矩阵 M1为例,选取支链11-10-9-B2作为首选支链。
2)根据亲密度,在首选支链下方排列亲密度最大的支链。若存在多个支链与首选支链具有相同的亲密度,则记录所有可能的排列情况。支链矩阵 M1中,仅有支链11-8-9-B2与首选支链亲密度最大,将其排列在第2行,生成新的矩阵:
3)对剩余支链,重复操作步骤2),记录所有可能的支链矩阵,直至所有行排列完成。如果已存在排列顺序abcde,且支链e与支链f、g具有相同亲密度,则可能生成abcdefg和abcdegf两种排列方式。这表明,第一步选择亲密关系少的支链作为首选支链,可以有效减少后续生成矩阵的数量。例如:在矩阵 M1中,支链11-8-9-B2分别与支链11-8-J2-5、11-8-J2-4具有相同的亲密度,由此产生了两种不同的支链矩阵:
重复上述操作,将余下的支链按亲密度依次排列,一共可以得到6个不同排列的矩阵:
4)步骤3)生成的所有支链矩阵按主链分块,并保持同一个主链下支链的相对位置不变,将第一个主链对应块移动至矩阵末尾,生成一个新矩阵。依此类推,直至最后一个主链对应块移至矩阵首位,记录所有衍生矩阵。此操作旨在解决首个支链选择的随机性对交叉问题的影响。由于首个支链的选择会直接影响后续支链的优化排列,且优化后的支链矩阵对应的树状结构图中,每一层子节点的位置,尤其是首个子节点的位置不能随意分布,故对于步骤3)生成的所有支链矩阵,需将不同主链下的首个支链轮流置于矩阵首位,以便得到无交叉或最小交叉的支链矩阵及其对应的树状结构图。支链矩阵
M1包含4个主链,如
图3可分为四块,涵盖11个支链:
a、b、c、d、e、f、g、h、i、j、k。具体划分如下:第1块对应主链11-10,支链
a;第2块对应主链11-8,支链
b、c、d;第3块对应主链11-7,支链
e、f;第4块对应主链11-6,支链
g、h、i、j、k。保持各主链内支链的相对位置不变,该矩阵可产生四种排列方式:1234、2341、3412、4123。若步骤3)共生成
p个矩阵,每个矩阵有
q个主链,则共衍生出
p×q个支链矩阵。例如,支链矩阵
M1生成6个支链矩阵,每个矩阵包含4个主链,由此共衍生出24种排列,具体结果见篇首二维码中附录。
5)对于步骤4)生成的所有矩阵,依次对每个矩阵进行重复元素赋0并计算交叉数量。其中,支链矩阵 M5为
对其中支链矩阵 M3、 M5中的重复元素进行赋0处理,得到新矩阵 M7和 M6:
完成赋0操作后,对新生成的支链矩阵进行交叉计算。从第
j列(
j≥2)开始检索,记录同一列中不相邻但相同的数字组合。例如,矩阵
M6中,第4列第1行和第10行存在不相邻但相同的元素
B2,记录为(4,1,10);第4列的第3、11行出现了相同不相邻的元素5,记录为(4,3,11)。对数组中(1,10)与(3、11)进行交叉判定,满足交叉条件,矩阵
M6的总交叉数为1。对支链矩阵
M7进行交叉计算,总交叉数为0,
图2为矩阵
M7对应的无交叉的树状结构图。
在交叉计算过程中,如果某矩阵的总交叉数为0,则视为最优支链矩阵,无需继续进行计算;若所有支链矩阵计算完毕,未出现交叉数为0的矩阵,则随机选取交叉数最小的矩阵作为优化支链矩阵。
3 运动链拓扑图的自动绘制
采用树状结构图描述运动链信息,根据连接关系生成支链矩阵,利用亲密度和交叉判定进行优化,得到无交叉或少交叉的优化支链矩阵。本文提出一种拓扑图绘制的新方法——基于优化支链矩阵的拓扑图矩阵连线绘制。以
图1a所示的运动链1为例,具体绘制步骤如下:
1)选择最大多元构件或复铰作为根节点,生成支链矩阵。选择最大多元构件4元构件11作为根节点,获得支链矩阵 M1。
2)基于亲密度和交叉判定,得到优化支链矩阵。对所有衍生支链矩阵进行交叉计算,得到交叉数为0的优化支链矩阵 M7。
3)简化优化支链矩阵中的元素信息。
通过删除矩阵中的重复连接和多余元素,实现对优化支链矩阵的简化。在此过程中,删除的元素位置保持为空,其余元素不做任何移动或填补。具体操作如下:
1)删除支链矩阵中的同层连接符Bi 和零值。在优化支链矩阵 M7中,首先删除第4列中的同层连接符B2、B1和0,得到矩阵 M8:
2)从支链矩阵的最后一列开始,向左逐列检索,如果第j列(j≥2)中存在相同元素,则进一步检索相同行第j1列元素。若构成n次(n≥2)重复连接,则j列中仅保留一个元素,删除其余相同元素;否则不进行删除。具体删除规则:若第j列相同元素位于支链矩阵第一行或最后一行,优先保留;否则保留第j列位于中间位置的元素,同时删除其余相同元素。中间位置的定义:若n为偶数,保留第n/2次出现的元素;若n为奇数,保留第()/2次出现的元素。从支链矩阵 M8的第4列开始逐列向左检索:
a.第4列第3、10行均为元素5,但同行第3列元素分别为J2和1,不构成重复连接,由此第4列元素5均保留。第4列中相同元素2、4与其对应行第3列元素亦未构成重复连接,同样保留。
b.第3列中,第1、2行元素9与同行第2列元素10、8未构成重复连接,由此保留;第3、4行元素J2与同行第2列元素8形成2次重复连接,依据规则,保留第3列中第一次出现的元素,即第3行的J2,删除第4行的J2。依次类推,删除第6行的J1和第8行的元素3。第9至11行均为元素1,同行第2列均为元素6,形成了3次重复连接,按照规则,优先保留位于矩阵最后一行的元素,即第11行的元素1,删除第9、10行元素1。
c.第2列按上述规则进行处理,删除第2行和第4行的元素8、第6行的元素7以及第7至10行的元素6,得到矩阵 M9:
3)当检索至第一列时,仅保留位于中间位置的根节点,删除其他根节点,以确保布局规整。在矩阵 M9中,第1列元素均为根节点11,仅保留第6行的11,删除其余根节点,得到矩阵 M10:
4)检索支链矩阵中各构件、复铰的位置,进行适当调整。为避免绘制拓扑图时出现不必要的线条交叉,需要调整矩阵中元素的位置。主要针对以下两种情况:一是具有同层连接关系的元素之间存在其他元素。二是相同列元素之间存在其他元素。从支链矩阵的第一列开始检索,在不改变相关元素所在行数的前提下,将相关构件或复铰平移至矩阵最右侧的新增列。如果上述情况同时存在或单个情况多次出现,根据相关元素之间行间距的大小,优先处理行间距小的情况。在矩阵 M10中,从第1列开始检索,第3列第1、2行元素9与第11行的元素1存在同层连接关系,且两者之间含有其他元素;第4列第3、10行元素5之间也存在其他元素。根据行间距,优先处理第4列相同元素5,将其平移至新增第5列的第3、10行;再将第3列元素9和1平移至新增第6列第1、2行及第11行,得到矩阵 M11:
5)检索调整后的支链矩阵,删除重复元素。经过上述操作,支链矩阵中可能仍存在重复元素。为确保各构件和复铰位置的唯一性,需进一步删除重复项。具体操作如下:①若重复元素位于矩阵第一行或最后一行,优先保留,删除其余重复元素;②若重复元素不位于矩阵首尾行,优先保留所在行中含有其他元素的重复项,删除其余重复元素;③若上述两种情况均不适用,则随机保留一个重复项,删除其余重复元素。以矩阵 M11为例,第4列存在重复元素4和2,对于元素4,由于第5行中同时存在其他元素7和J1,故优先保留第4列第5行元素4,删除第4行的元素4;对于第8、9行的元素2,由于所在行均无其他元素,随机选择一个保留。第6列第1、2行存在重复元素9,按照优先保留首行元素的原则,保留第6列第1行的元素9,删除第2行的元素9。最终得到矩阵 M12:
6)采用双色拓扑图法,完成运动链拓扑图的绘制。根据支链矩阵
M12中每行元素之间特定的连接关系,用实心点(“●”)表示构件,用空心点(“○”)表示复铰,完成运动链1的拓扑图绘制,如
图4所示。
图5为根据拓扑图绘制的流程图。
4 典型案例分析
分析文献[
21]中14杆运动链2的拓扑图(
图6a),图中存在3次交叉。运用上述方法,随机选择最大四元构件2作为根节点,用
Bi (
i=1,2,...)描述同层子节点之间连接关系,其随机排列的树状结构图见
图6b。具体过程如下:
1)随机选择最大四元构件2作为根节点,得到初始矩阵 M13:
2)选择支链2-3-4-B2作为支链矩阵的首选支链,余下支链按亲密度排列,共生成以下4个支链矩阵:
3)利用交叉判定定理,计算所有支链矩阵的交叉数。基于步骤2)生成的支链矩阵,调整主链位置,衍生出16个新的支链矩阵(详见附录)。对所有矩阵进行交叉判定,得到交叉数为0的优化支链矩阵 M14:
4)检索优化后的支链矩阵,删除重复连接和多余元素。首先删除矩阵第4、5列的同层连接符和零值。从第5列向左逐列检索,第3列重复元素4、12与同行第2列元素均未构成重复连接,第3列元素均保留。第2列重复1、11、6均与第1列根节点2构成重复连接,保留第2列第3行的1、第5行的11以及第9行的6,删除其余重复元素。对于第1列根节点,仅保留位于第5行的根节点2。删除后的矩阵如
图7a所示。
5)对支链矩阵中元素位置进行适当调整。检索步骤4)得到的支链矩阵,第3列中第1、2行元素4与第9行的元素5,第3行元素13与第8行的元素14,分别存在同层连接关系,且两者之间含有其他元素。根据行间距,优先将第3列元素13和14平移至新增的第5列,再将元素4和5平移至新增的第6列。调整后的矩阵见
图7b。
6)删除重复元素,确保支链矩阵中元素位置的唯一性。检索调整后的矩阵,仍存在重复元素12和4。根据规则,删除第6列第2行的元素4和第3列第4行的元素12,最终的支链矩阵如
图7c所示。
7)根据支链矩阵每行元素之间特定的连接关系,完成运动链拓扑图绘制。
图8为运动链2的拓扑图。
由上述案例分析可知,基于优化支链矩阵完成运动链拓扑图的绘制,具有以下特点:①有效解决了线条交叉的问题。通过交叉判定理论,基于交叉计算,实现了线条之间无交叉或最少交叉布局;②可操作性强。支链矩阵的生成、优化和拓扑图绘制过程,均基于各构件及复铰的连接关系和相同列元素的检索对比,操作规则明确清晰,步骤易于执行;③环路信息清晰。基于优化支链矩阵,通过直接对矩阵元素进行删除、位置调整,以及新增列与元素平移的操作,使得生成的拓扑图布局规整,连接关系清晰可见。
5 结论
1)本文用树状结构图描述运动链结构信息,并生成支链矩阵。通过亲密度对支链矩阵优化排列,结合交叉判定理论和计算方法,获得无交叉或最少交叉的支链矩阵及其对应的图和运动链。
2)在优化支链矩阵的基础上,提出一种拓扑图绘制的新方法,通过删除重复元素、采用新增列与元素平移的方式确定元素位置,并连线生成拓扑图。本文方法生成的拓扑图具有规则简单、环路信息清晰等优点。
国家自然科学基金(51875418)
湖北省自然科学基金(2025AFB126)
湖北省自然科学基金(2025AFC004)