@[toc]
论文来源：（1998）无网格线探索布线算法
作者：杨瑞元
一、摘要
- 提出的一种高效快速的无网格线探索布线算法
- 适用于焊盘外形尺寸不一，线宽及线间距离可变的印制电路板及MCM 电路布线
- 精心设计的数据结构及灵活的绕障探索方式可大大地提高搜索效率
- 多级多遍优化策略为改善布线结果提供了可靠的保证
- 该算法已成功地应用于通用印制电路板设计系统MPCB，取得了令人满意的效果
二、单层无网格线探索算法
2.1 形式描述
2.1.1 探索线
- 探索线是一条以当前点为起点，有预定终点和一定宽度的水平、垂直或斜向射线
- 探索线的宽度即用来连接待连点对的连线宽度
2.1.2 探索过程
探索过程实质上是一个检查计算过程，就是按照从起点至预定终点的方向，逐一检查前面或两侧是否有焊盘、过孔或已布连线等障碍物阻碍探索线直通预定终点的过程
2.1.3 绕障偏移量
为了绕过障碍，同一方向的下一探索线必须偏离当前线探索的中心距离，称为绕障偏离量
相对每一障碍，可有正负两个绕障偏移量，其计算公式如下：
$$负偏移量I_{off}=Y_1-Y_c<0$$ $$正偏移量L_{off}=Y_2-Y_c>0$$
2.2 变量说明
| 变量名 | 含义 |
|---|---|
| L | 布线栈顶指针，其值为栈中探索线数+1 |
| L1 | 探索方向控制变量，根据其值为0或1来决定下一步探索为横向或竖向 |
| KC | 当前探索方向 |
| KF | 上一段探索方向 |
| KP | 当前探索状态标志。KP＝0表示当前方向探索成功，可以产生探索线段（ 但不一定到达预定终点） ；如KP＞0，表示当前探索失败，不能产生探索线段 |
| KB | 布通标志。KB＝0，表示探索线抵达预定终点；KB＝2，表示探索线遇阻，未抵达预定终点；KB＝1，表示探索线到达目标点，或与本信号组已布连线连通 |
| IB | 上一探索线段的布通标志 |
| (Xc,Yc) | 当前点坐标 |
| (Xs,Ys) | 起点坐标 |
| (Xt,Yt) | 终点坐标 |
2.3 启发式规则
下面的启发式规则是根据我自己理解来的，并加入了一些改进（仅供参考）
2.3.1 I型绕障
2.3.2 L型绕障
暂未理解：我采用逐步试探，正常递归
2.3.3 U型绕障
暂未理解：我采用逐步试探，正常递归
2.3.4 启发式阻停
由于无网格线探索算法中，每一步的行走都是有固定步长的，如果步长过大，就会导致 线在终点来回搜索的情况出现。为了避免这个情况，特设定此规则， 在行进过程中会被终点坐标“阻停”。
2.4 Python代码实现
下图展示了需要设置的参数
下图展示了运行的示例
下图展示了路径可视化图：
# -*-coding:utf-8-*-
# Author: WSKH
# Blog: wskh0929.blog.csdn.net
# Time: 2022/10/12 14:54
# 无网格线探索模型
import time
# 线对象
class Line:
def __init__(self, startPos, tempObstacleList):
self.lineArr = [[startPos[0], startPos[1]]]
self.length = 0
self.tempObstacleList = tempObstacleList
self.flags = [0, 0, 0, 0]
def append(self, pos):
lastPos = self.lineArr[len(self.lineArr) - 1]
self.lineArr.append(pos)
self.length += abs(lastPos[0] - pos[0]) if abs(lastPos[0] - pos[0]) else abs(lastPos[1] - pos[1])
def getAllAttributeByLine(self, line):
self.lineArr = line.lineArr.copy()
self.tempObstacleList = line.tempObstacleList.copy()
self.length = line.length
self.L1 = line.L1
self.Xd = line.Xd
self.Yd = line.Yd
self.Xc = line.Xc
self.Yc = line.Yc
self.KP = line.KP
self.flags = line.flags.copy()
self.L = line.L
self.IB = line.IB
self.KC = line.KC
self.KB = line.KB
self.exploreRange = line.exploreRange
self.lineWidth = line.lineWidth
self.lineItemEdge = line.lineItemEdge
self.lineEdge = line.lineEdge
self.obstacle = line.obstacle.copy() if line.obstacle is not None else None
self.KF = line.KF
self.flags = line.flags.copy()
def resetFlags(self):
self.flags = [0, 0, 0, 0]
# 矩形模块类（程序会将L型、T型划分为此类）
class RectItem:
def __init__(self, left_bottom_point, w, h, name):
self.left_bottom_point = left_bottom_point.copy()
self.w, self.h = w, h
self.name = name
# 模块类
class Item:
def __init__(self, name, boundary):
self.name = name
self.standardBoundary = boundary.copy()
min_x = min_y = None
for p in self.standardBoundary:
if min_x is None or min_x > p[0]:
min_x = p[0]
if min_y is None or min_y > p[1]:
min_y = p[1]
self.standardBoundary = [[p[0] - min_x, p[1] - min_y] for p in self.standardBoundary]
self.left_bottom_point = [min_x, min_y]
self.boundary = boundary
self.init_item()
def to_string(self):
return 'Item', {
'name': self.name,
'boundary': self.boundary,
}
def init_item(self):
# 计算其包络矩形的宽和高
self.w, self.h = calc_envelope_rectangle_w_h(self.standardBoundary)
# 计算所有竖着线段(x,y,l)
self.vertical_line_list = calc_vertical_line_list(self.standardBoundary)
# 计算所有水平线段(x,y,l)
self.horizontal_line_list = calc_horizontal_line_list(self.standardBoundary)
# 获取着地水平线段(x,y,l)
for horizontal_line in self.horizontal_line_list:
if horizontal_line[1] == 0:
self.floor_horizontal_line = horizontal_line
break
# 计算放入当前模块将会新增的天际线(x,y,l)
self.add_sky_line_list = calc_add_sky_line_list(self.horizontal_line_list)
# 找到第二高度
self.sec_y = None
for x, y in self.standardBoundary:
if y != 0 and (self.sec_y is None or self.sec_y > y):
self.sec_y = y
# 计算对标点
self.aim_point_list = calc_aim_point_list(self.standardBoundary)
# 获取当前模块type
if len(self.standardBoundary) == 4:
self.rect_list = [[0, 0, self.w, self.h]]
elif len(self.standardBoundary) == 6:
# L型
if len(self.add_sky_line_list) == 1:
if len(self.aim_point_list) == 2:
self.type = '180'
self.w2 = self.floor_horizontal_line[2]
self.w1 = self.w - self.w2
self.h2 = self.sec_y
self.h1 = self.h - self.h2
self.rect_list = [[0, self.h2, self.w1, self.h1], [self.w1, 0, self.w2, self.h]]
elif len(self.aim_point_list) == 1:
self.type = '90'
self.w1 = self.floor_horizontal_line[2]
self.w2 = self.w - self.w1
self.h1 = self.sec_y
self.h2 = self.h - self.h1
self.rect_list = [[0, 0, self.w1, self.h], [self.w1, self.h1, self.w2, self.h2]]
elif len(self.add_sky_line_list) == 2:
# 找到(0,0)这个点，通过判断其两边的情况，判断是0度还是270度
i = 0
while i < 6:
if self.standardBoundary[i][0] == 0 and self.standardBoundary[i][1] == 0:
i_f = i - 1 if i - 1 >= 0 else 5
i_b = i + 1 if i + 1 < 6 else 0
if self.standardBoundary[i_f][1] == self.h or self.standardBoundary[i_b][1] == self.h:
self.type = '0'
for add_sky_line in self.add_sky_line_list:
if add_sky_line[0] == 0:
self.w1 = add_sky_line[2]
elif add_sky_line[0] + add_sky_line[2] == self.w:
self.w2 = add_sky_line[2]
self.h2 = add_sky_line[1]
self.h1 = self.h - self.h2
self.rect_list = [[0, 0, self.w1, self.h], [self.w1, 0, self.w2, self.h2]]
else:
self.type = '270'
for add_sky_line in self.add_sky_line_list:
if add_sky_line[0] == 0:
self.w1 = add_sky_line[2]
self.h1 = add_sky_line[1]
self.h2 = self.h - self.h1
elif add_sky_line[0] + add_sky_line[2] == self.w:
self.w2 = add_sky_line[2]
self.rect_list = [[0, 0, self.w1, self.h1], [self.w1, 0, self.w2, self.h]]
break
i += 1
elif len(self.standardBoundary) == 8:
# T型
if len(self.add_sky_line_list) == 1:
self.type = '180'
self.w2 = self.floor_horizontal_line[2]
for horizontal_line in self.horizontal_line_list:
if horizontal_line[0] == 0 and horizontal_line[2] < self.w:
self.w1 = horizontal_line[2]
self.h2 = self.h - horizontal_line[1]
self.h1 = self.h - self.h2
elif horizontal_line[0] != 0 and horizontal_line[0] + horizontal_line[2] == self.w:
self.w3 = horizontal_line[2]
self.h3 = horizontal_line[1]
self.h4 = self.h - self.h3
self.rect_list = [[0, self.h2, self.w1, self.h], [self.w1, 0, self.w2, self.h],
[self.w1 + self.w2, self.h3, self.w3, self.h4]]
elif len(self.add_sky_line_list) == 2:
if len(self.aim_point_list) == 2:
self.type = '270'
self.w1 = self.floor_horizontal_line[2]
for add_sky_line in self.add_sky_line_list:
if add_sky_line[0] == 0:
self.w3 = add_sky_line[2]
self.h3 = self.h - add_sky_line[1]
else:
self.w4 = add_sky_line[2]
for horizontal_line in self.horizontal_line_list:
if horizontal_line[0] == 0 and horizontal_line[1] < self.h - self.h3:
self.w2 = horizontal_line[2]
self.h1 = horizontal_line[1]
self.h2 = self.h - self.h1 - self.h3
break
self.rect_list = [[self.w2, 0, self.w1, self.h1], [0, self.h1, self.w, self.h2],
[self.w3, self.h1 + self.h2, self.w4, self.h3]]
elif len(self.aim_point_list) == 1:
self.type = '90'
self.w1 = self.floor_horizontal_line[2]
for add_sky_line in self.add_sky_line_list:
if add_sky_line[0] == 0:
self.w4 = add_sky_line[2]
else:
self.w3 = add_sky_line[2]
self.h1 = self.h - add_sky_line[1]
for horizontal_line in self.horizontal_line_list:
if horizontal_line[0] + horizontal_line[2] == self.w and horizontal_line[1] < self.h - self.h1:
self.w2 = horizontal_line[2]
self.h3 = horizontal_line[1]
self.h2 = self.h - self.h1 - self.h3
break
self.rect_list = [[0, 0, self.w1, self.h3], [0, self.h3, self.w, self.h2],
[0, self.h2 + self.h3, self.w4, self.h1]]
elif len(self.add_sky_line_list) == 3:
self.type = '0'
for asl in self.add_sky_line_list:
if asl[0] == 0:
self.h1 = asl[1]
self.w1 = asl[2]
self.h2 = self.h - self.h1
elif asl[0] + asl[2] == self.w:
self.h4 = asl[1]
self.w3 = asl[2]
self.h3 = self.h - self.h4
self.w2 = self.w - self.w1 - self.w3
self.rect_list = [[0, 0, self.w1, self.h1], [self.w1, 0, self.w2, self.h],
[self.w1 + self.w2, 0, self.w3, self.h4]]
class NoGridLineExploreModel:
def __init__(self, items_list, area):
self.items_list = items_list
self.area = area
self.rect_items_list = []
for item in self.items_list:
for rect in item.rect_list:
self.rect_items_list.append(
RectItem([rect[0] + item.left_bottom_point[0], rect[1] + item.left_bottom_point[1]], rect[2],
rect[3], item.name))
self.areaMinX, self.areaMaxX, self.areaMinY, self.areaMaxY = None, None, None, None
for a in area:
if self.areaMinX is None or self.areaMinX > a[0]:
self.areaMinX = a[0]
if self.areaMaxX is None or self.areaMaxX < a[0]:
self.areaMaxX = a[0]
if self.areaMinY is None or self.areaMinY > a[1]:
self.areaMinY = a[1]
if self.areaMaxY is None or self.areaMaxY < a[1]:
self.areaMaxY = a[1]
def solve(self, instanceArr):
# 算法参数
self.error = 1e-6 # 浮点数误差
self.exploreRange = 20 # 步长（探索范围）
self.maxLineLength = 150 # 最大递归深度
self.lineWidth, self.lineEdge = 5, 5
self.LIE = 0.5 # 线和模块的间距约束
self.lineItemEdge = self.lineWidth / 2.0 + self.LIE # 转化后的线和模块的间距约束
self.maxTime = 15
self.dis = self.lineWidth / 2.0 + self.lineEdge - self.LIE
# 临时障碍物列表
self.tempObstacleList = []
# 所有连线的列表
self.lineList = []
# 开始探索
for Xs, Ys, Xt, Yt in instanceArr:
self.Xs, self.Ys, self.Xt, self.Yt = Xs, Ys, Xt, Yt
self.startTime = time.time()
self.LineToExplore(Line([self.Xs, self.Ys], self.tempObstacleList.copy()))
print(str([self.Xs, self.Ys, self.Xt, self.Yt]) + " SUCCESS %.4f s" % (time.time() - self.startTime))
# 返回成功布线的线列表
return self.lineList
# 指定起点，指定目的地，开始线探索
def LineToExplore(self, line):
# 开始进入探索
self.step01(line)
self.step02(line)
return self.step03(line)
def step01(self, line):
self.counter = 1
line.L = 1
line.KB = 0
line.KF = 0
line.IB = 0
line.Xc, line.Yc = self.Xs, self.Ys
def step02(self, line):
line.exploreRange = self.exploreRange
line.lineWidth, line.lineEdge = self.lineWidth, self.lineEdge
line.lineItemEdge = self.lineItemEdge
def step03(self, line):
if abs(self.Xt - self.Xs) < self.error:
tempLine = copyLine2(line)
tempLine.flags = [0, 0, 1, 1]
tempLine = self.step05(tempLine)
if tempLine is not None:
return tempLine
line.flags = [1, 1, 0, 0]
return self.step04(line)
elif abs(self.Yt - self.Ys) < self.error:
tempLine = copyLine2(line)
tempLine.flags = [1, 1, 0, 0]
tempLine = self.step04(tempLine)
if tempLine is not None:
return tempLine
line.flags = [0, 0, 1, 1]
return self.step05(line)
elif abs(self.Xt - self.Xs) >= abs(self.Yt - self.Ys):
tempLine = copyLine2(line)
tempLine.flags = [0, 0, 1, 1]
tempLine = self.step05(tempLine)
if tempLine is not None:
return tempLine
line.flags = [1, 1, 0, 0]
return self.step04(line)
else:
tempLine = copyLine2(line)
tempLine.flags = [1, 1, 0, 0]
tempLine = self.step04(tempLine)
if tempLine is not None:
return tempLine
line.flags = [0, 0, 1, 1]
return self.step05(line)
def step04(self, line):
line.obstacle = None
if line.flags[2] == 0 and line.flags[3] == 0:
if self.Xt > line.Xc:
tempLine = copyLine(line)
self.rightExplore(tempLine)
if self.step06(tempLine) is not None:
line.getAllAttributeByLine(tempLine)
return line
self.leftExplore(line)
return self.step06(line)
else:
tempLine = copyLine(line)
self.leftExplore(tempLine)
if self.step06(tempLine) is not None:
line.getAllAttributeByLine(tempLine)
return line
self.rightExplore(line)
return self.step06(line)
elif line.flags[2] == 0:
self.leftExplore(line)
return self.step06(line)
elif line.flags[3] == 0:
self.rightExplore(line)
return self.step06(line)
return None
# raise RuntimeError("self.Yt == line.Yc , " + str(line.flags))
def step05(self, line):
line.obstacle = None
if line.flags[0] == 0 and line.flags[1] == 0:
if self.Yt > line.Yc:
tempLine = copyLine(line)
self.upExplore(tempLine)
if self.step06(tempLine) is not None:
line.getAllAttributeByLine(tempLine)
return line
self.downExplore(line)
return self.step06(line)
else:
tempLine = copyLine(line)
self.downExplore(tempLine)
if self.step06(tempLine) is not None:
line.getAllAttributeByLine(tempLine)
return line
self.upExplore(line)
return self.step06(line)
elif line.flags[0] == 0:
self.upExplore(line)
return self.step06(line)
elif line.flags[1] == 0:
self.downExplore(line)
return self.step06(line)
return None
# raise RuntimeError("self.Yt == line.Yc , " + str(line.flags))
def step06(self, line):
if line.KP > 0:
# 1：横向探索遇障碍点
# 2：竖向探索遇障碍点
return self.step10(line)
else:
return self.step07(line)
def step07(self, line):
# 其他参数更新
if abs(line.Xc - line.Xd) < self.error and abs(line.Yc - line.Yd) < self.error:
return None
else:
# 增加临时障碍 [w,h,l_x,l_y]
if line.KC == 1:
line.tempObstacleList.append([line.Xd - line.Xc + 2 * self.dis, 2 * self.dis,
line.Xc - self.dis,
line.Yc - self.dis])
elif line.KC == 5:
line.tempObstacleList.append([line.Xc - line.Xd + 2 * self.dis, 2 * self.dis,
line.Xd - self.dis,
line.Yd - self.dis])
elif line.KC == 3:
line.tempObstacleList.append([2 * self.dis, line.Yd - line.Yc + 2 * self.dis,
line.Xc - self.dis,
line.Yc - self.dis])
elif line.KC == 7:
line.tempObstacleList.append([2 * self.dis, line.Yc - line.Yd + 2 * self.dis,
line.Xd - self.dis,
line.Yd - self.dis])
else:
raise RuntimeError("line.KC = " + str(line.KC))
line.L += 1
line.Xc, line.Yc = line.Xd, line.Yd
if self.isArriveDestination(line.Xc, line.Yc):
line.KB = 1
line.append([line.Xd, line.Yd])
line.KF = line.KC
line.IB = line.KB
if line.KC == 1:
line.flags = [0, 0, 1, 0]
elif line.KC == 3:
line.flags = [0, 1, 0, 0]
elif line.KC == 5:
line.flags = [0, 0, 0, 1]
elif line.KC == 7:
line.flags = [1, 0, 0, 0]
return self.step08(line)
def step08(self, line):
if time.time() - self.startTime > self.maxTime or len(line.lineArr) > self.maxLineLength:
return None
elif line.KB == 1:
# 出口
self.lineList.append(copyLine(line))
self.tempObstacleList = line.tempObstacleList.copy()
return line
else:
# if len(self.lineList) == 0:
# print("lineList:" + str([line.lineArr]) + ",")
# # print(str(line.flags) + " , lineList:" + str([line.lineArr]) + ",")
# if str(line.lineArr) == "[[350, 480], [350, 487.0]]":
# print("e")
# if str([self.Xs, self.Ys, self.Xt, self.Yt, self.startPointFlag,
# self.endPointFlag]) == "[84.5, 611.5, 123.5, 426.5, 'M2-2', 'M1-2']":
# print("lineList:" + str([line.lineArr]) + ",")
# TODO:可优化，不必每次都计算，可以随着点链lineArr的更新而更新
if len(line.lineArr) >= 2:
# flag = vertical 或 horizontal
lastLongestDistance, flag = self.calcLastLongestDistance(line.lineArr)
if lastLongestDistance < line.lineWidth + line.lineEdge:
if flag == "vertical":
line.flags[2] = 1
line.flags[3] = 1
elif flag == "horizontal":
line.flags[0] = 1
line.flags[1] = 1
else:
raise RuntimeError("flag = " + flag)
return self.step09(line)
def step09(self, line):
if line.KB == 2 and line.obstacle is not None and (line.KF == 3 or line.KF == 7):
# 竖向受阻且终点在障碍物的水平维度内
return self.horizontalPassObstacles(line)
elif line.KB == 2 and line.obstacle is not None and (line.KF == 1 or line.KF == 5):
# 横向受阻且终点在障碍物的竖直维度内
return self.verticalPassObstacles(line)
elif abs(line.Xc - self.Xt) < self.error:
tempLine = copyLine(line)
r = self.step05(tempLine)
if r is None:
return self.step04(line)
line.getAllAttributeByLine(tempLine)
return r
elif abs(line.Yc - self.Yt) < self.error:
tempLine = copyLine(line)
r = self.step04(tempLine)
if r is None:
return self.step05(line)
line.getAllAttributeByLine(tempLine)
return r
else:
if line.L1 == 0:
if line.KF == 1 and self.Xt < line.Xc:
line.L1 = 1
elif line.KF == 5 and self.Xt > line.Xc:
line.L1 = 1
else:
if line.KF == 3 and self.Yt < line.Yc:
line.L1 = 0
elif line.KF == 7 and self.Yt > line.Yc:
line.L1 = 0
# line.L1 = 1 - line.L1
if line.L1 == 0:
tempLine = copyLine(line)
r = self.step04(tempLine)
if r is None:
return self.step05(line)
line.getAllAttributeByLine(tempLine)
return r
else:
tempLine = copyLine(line)
r = self.step05(tempLine)
if r is None:
return self.step04(line)
line.getAllAttributeByLine(tempLine)
return r
def step10(self, line):
line.obstacle = None
# KP = 1：横向探索遇障碍点
# KP = 2：竖向探索遇障碍点
if line.KP == 1:
if line.KF == 3:
if line.flags[0] == 0:
# 上次探索为向上，则这次只能向上
self.upExplore(line)
return self.step06(line)
return None
elif line.KF == 7:
if line.flags[1] == 0:
# 上次探索为向下，则这次只能向下
self.downExplore(line)
return self.step06(line)
return None
else:
# 上次探索是横向的，则这次又可以向上也可以向下
return self.step05(line)
elif line.KP == 2:
if line.KF == 1:
if line.flags[3] == 0:
# 上次探索为向右，则这次只能向右
self.rightExplore(line)
return self.step06(line)
return None
elif line.KF == 5:
if line.flags[2] == 0:
# 上次探索为向左，则这次只能向左
self.leftExplore(line)
return self.step06(line)
return None
else:
# 上次探索是竖向的，则这次又可以向左也可以向右
return self.step04(line)
else:
raise RuntimeError("line.KP = " + str(line.KP))
# 横向绕障
def horizontalPassObstacles(self, line):
line.L1 = 0
w, h, x, y = line.obstacle
le = line.exploreRange
if line.flags[2] == 0 and line.flags[3] == 0:
if line.obstacle[
2] < self.Xt < line.obstacle[2] + \
line.obstacle[0]:
b = line.Xc - x + h + self.Xt - x <= x + w - line.Xc + h + x + w - self.Xt
else:
b = line.Xc >= self.Xt
if b is True:
tempLine = copyLine(line)
# 首先向左绕障碍试试
tempLine.exploreRange = tempLine.Xc - x + tempLine.lineItemEdge
moveDis = self.leftExplore(tempLine, isSmart=False)
if abs(moveDis - tempLine.exploreRange) < self.error:
tempLine.exploreRange = le
line.getAllAttributeByLine(tempLine)
return self.step06(line)
# 向左不行 向右试试
line.exploreRange = x + w + line.lineItemEdge - line.Xc
self.rightExplore(line, isSmart=False)
line.exploreRange = le
return self.step06(line)
else:
tempLine = copyLine(line)
# 首先向右绕障碍试试
tempLine.exploreRange = x + w + tempLine.lineItemEdge - tempLine.Xc
moveDis = self.rightExplore(tempLine, isSmart=False)
if abs(moveDis - tempLine.exploreRange) < self.error:
tempLine.exploreRange = le
line.getAllAttributeByLine(tempLine)
return self.step06(line)
# 向右不行 向左试试
line.exploreRange = line.Xc - x + line.lineItemEdge
self.leftExplore(line, isSmart=False)
line.exploreRange = le
return self.step06(line)
elif line.flags[2] == 0:
# 向左
line.exploreRange = line.Xc - x + line.lineItemEdge
self.leftExplore(line, isSmart=False)
line.exploreRange = le
return self.step06(line)
elif line.flags[3] == 0:
# 向右
line.exploreRange = x + w + line.lineItemEdge - line.Xc
self.rightExplore(line, isSmart=False)
line.exploreRange = le
return self.step06(line)
return None
# 竖向绕障
def verticalPassObstacles(self, line):
line.L1 = 1
w, h, x, y = line.obstacle
le = line.exploreRange
if line.flags[0] == 0 and line.flags[1] == 0:
if line.obstacle[
3] < self.Yt < line.obstacle[3] + \
line.obstacle[1]:
b = line.Yc - y + w + self.Yt - y <= y + h - line.Yc + w + y + h - self.Yt
else:
b = line.Yc >= self.Yt
if b is True:
tempLine = copyLine(line)
# 首先向下绕障碍试试
tempLine.exploreRange = tempLine.Yc - y + tempLine.lineItemEdge
moveDis = self.downExplore(tempLine, isSmart=False)
if abs(moveDis - tempLine.exploreRange) < self.error:
tempLine.exploreRange = le
line.getAllAttributeByLine(tempLine)
return self.step06(line)
# 向下不行 向上试试
line.exploreRange = y + h + line.lineItemEdge - line.Yc
self.upExplore(line, isSmart=False)
line.exploreRange = le
return self.step06(line)
else:
tempLine = copyLine(line)
# 首先向上绕障碍试试
tempLine.exploreRange = y + h + line.lineItemEdge - line.Yc
moveDis = self.upExplore(tempLine, isSmart=False)
if abs(moveDis - tempLine.exploreRange) < self.error:
tempLine.exploreRange = le
line.getAllAttributeByLine(tempLine)
return self.step06(line)
# 向上不行 向下试试
line.exploreRange = line.Yc - y + line.lineItemEdge
self.downExplore(line, isSmart=False)
line.exploreRange = le
return self.step06(line)
elif line.flags[0] == 0:
# 向上
line.exploreRange = y + h + line.lineItemEdge - line.Yc
self.upExplore(line, isSmart=False)
line.exploreRange = le
return self.step06(line)
elif line.flags[1] == 0:
# 向下
line.exploreRange = line.Yc - y + line.lineItemEdge
self.downExplore(line, isSmart=False)
line.exploreRange = le
return self.step06(line)
return None
# 向右探索
def rightExplore(self, line, isSmart=True):
if line.flags[3] == 1:
raise RuntimeError
if sum(line.flags) == 3:
isSmart = False
line.L1 = 0
line.flags[3] = 1
# 往右探索
line.KC = 1
step = min(line.exploreRange, self.areaMaxX - line.Xc - line.lineWidth / 2.0)
if step < 0:
return 0
for item in self.rect_items_list:
# 在当前点的右边才进行判断，且在判断范围内
if line.Xc + line.lineItemEdge <= item.left_bottom_point[0] <= line.Xc + step + line.lineItemEdge:
# 如果不满足安全距离
if item.left_bottom_point[1] - line.lineItemEdge < line.Yc < item.left_bottom_point[
1] + item.h + line.lineItemEdge:
if item.left_bottom_point[0] - line.lineItemEdge - line.Xc < step:
line.obstacle = [item.w, item.h, item.left_bottom_point[0], item.left_bottom_point[1]]
step = item.left_bottom_point[0] - line.lineItemEdge - line.Xc
# 遇到死点
if step < self.error:
line.KP = 1
return 0
for tempObstacle in line.tempObstacleList:
# 在当前点的右边才进行判断，且在判断范围内
if line.Xc + line.lineItemEdge <= tempObstacle[2] <= line.Xc + step + line.lineItemEdge:
# 如果不满足安全距离
if tempObstacle[3] - line.lineItemEdge < line.Yc < \
tempObstacle[3] + tempObstacle[1] + line.lineItemEdge:
if tempObstacle[2] - line.lineItemEdge - line.Xc < step:
step = tempObstacle[2] - line.lineItemEdge - line.Xc
line.obstacle = [tempObstacle[0], tempObstacle[1], tempObstacle[2],
tempObstacle[3]]
# 遇到死点
if step < self.error:
line.KP = 1
return 0
if isSmart is True and line.Xc <= self.Xt <= line.Xc + step:
line.Xd = self.Xt
line.obstacle = None
else:
line.Xd = line.Xc + step
line.Yd = line.Yc
if self.isArriveDestination(line.Xd, line.Yd):
# line.KB = 1
pass
elif abs(step - line.exploreRange) < self.error:
line.KB = 0
else:
line.KB = 2
line.KP = 0
return abs(line.Xd - line.Xc)
# 向左探索
def leftExplore(self, line, isSmart=True):
if line.flags[2] == 1:
raise RuntimeError
if sum(line.flags) == 3:
isSmart = False
line.L1 = 0
line.flags[2] = 1
# 往左探索
line.KC = 5
step = min(line.exploreRange, line.Xc - self.areaMinX - line.lineWidth / 2.0)
if step < 0:
return 0
for item in self.rect_items_list:
# 在当前点的左边才进行判断，且在判断范围内
if line.Xc - step - line.lineItemEdge <= item.left_bottom_point[
0] + item.w <= line.Xc - line.lineItemEdge:
# 如果不满足安全距离，则进行step限制
if item.left_bottom_point[1] - line.lineItemEdge < line.Yc < item.left_bottom_point[
1] + item.h + line.lineItemEdge:
if line.Xc - (item.w + item.left_bottom_point[0]) - line.lineItemEdge < step:
step = line.Xc - (item.w + item.left_bottom_point[0]) - line.lineItemEdge
line.obstacle = [item.w, item.h, item.left_bottom_point[0], item.left_bottom_point[1]]
# 遇到死点
if step < self.error:
line.KP = 1
return 0
for tempObstacle in line.tempObstacleList:
# 在当前点的左边才进行判断，且在判断范围内
if line.Xc - step - line.lineItemEdge <= tempObstacle[2] + tempObstacle[0] <= line.Xc - line.lineItemEdge:
# 如果不满足安全距离，则进行step限制
if tempObstacle[3] - line.lineItemEdge < line.Yc < \
tempObstacle[3] + tempObstacle[1] + line.lineItemEdge:
if line.Xc - (tempObstacle[0] + tempObstacle[2]) - line.lineItemEdge < step:
line.obstacle = [tempObstacle[0], tempObstacle[1], tempObstacle[2],
tempObstacle[3]]
step = line.Xc - (tempObstacle[0] + tempObstacle[2]) - line.lineItemEdge
# 遇到死点
if step < self.error:
line.KP = 1
return 0
if isSmart is True and line.Xc - step <= self.Xt <= line.Xc:
line.Xd = self.Xt
line.obstacle = None
else:
line.Xd = line.Xc - step
line.Yd = line.Yc
if self.isArriveDestination(line.Xd, line.Yd):
# line.KB = 1
pass
elif abs(step - line.exploreRange) < self.error:
line.KB = 0
else:
line.KB = 2
line.KP = 0
return abs(line.Xd - line.Xc)
# 向上探索
def upExplore(self, line, isSmart=True):
if line.flags[0] == 1:
raise RuntimeError
if sum(line.flags) == 3:
isSmart = False
line.L1 = 1
line.flags[0] = 1
# 往上探索
line.KC = 3
step = min(line.exploreRange, self.areaMaxY - line.Yc - line.lineWidth / 2.0)
if step < 0:
return 0
for item in self.rect_items_list:
# 在当前点的上边才进行判断，且在判断范围内
if line.Yc + line.lineItemEdge <= item.left_bottom_point[1] <= line.Yc + step + line.lineItemEdge:
# 如果不满足安全距离，则进行step限制
if item.left_bottom_point[0] - line.lineItemEdge < line.Xc < item.left_bottom_point[
0] + item.w + line.lineItemEdge:
if item.left_bottom_point[1] - line.lineItemEdge - line.Yc < step:
line.obstacle = [item.w, item.h, item.left_bottom_point[0], item.left_bottom_point[1]]
step = item.left_bottom_point[1] - line.lineItemEdge - line.Yc
# 遇到死点
if step < self.error:
line.KP = 2
return 0
for tempObstacle in line.tempObstacleList:
# 在当前点的上边才进行判断，且在判断范围内
if line.Yc + line.lineItemEdge <= tempObstacle[3] <= line.Yc + step + line.lineItemEdge:
# 如果不满足安全距离，则进行step限制
if tempObstacle[2] - line.lineItemEdge < line.Xc < tempObstacle[2] + tempObstacle[
0] + line.lineItemEdge:
if tempObstacle[3] - line.lineItemEdge - line.Yc < step:
step = tempObstacle[3] - line.lineItemEdge - line.Yc
line.obstacle = [tempObstacle[0], tempObstacle[1], tempObstacle[2],
tempObstacle[3]]
# 遇到死点
if step < self.error:
line.KP = 2
return 0
if isSmart is True and line.Yc <= self.Yt <= line.Yc + step:
line.Yd = self.Yt
line.obstacle = None
else:
line.Yd = line.Yc + step
line.Xd = line.Xc
if self.isArriveDestination(line.Xd, line.Yd):
# line.KB = 1
pass
elif abs(step - line.exploreRange) < self.error:
line.KB = 0
else:
line.KB = 2
line.KP = 0
return abs(line.Yd - line.Yc)
# 向下探索
def downExplore(self, line, isSmart=True):
if line.flags[1] == 1:
raise RuntimeError
if sum(line.flags) == 3:
isSmart = False
line.L1 = 1
line.flags[1] = 1
# 往下探索
line.KC = 7
step = min(line.exploreRange, line.Yc - self.areaMinY - line.lineWidth / 2.0)
if step < 0:
return 0
for item in self.rect_items_list:
# 在当前点的左边才进行判断，且在判断范围内
if line.Yc - step - line.lineItemEdge <= item.left_bottom_point[
1] + item.h <= line.Yc - line.lineItemEdge:
# 如果不满足安全距离
if item.left_bottom_point[0] - line.lineItemEdge < line.Xc < item.left_bottom_point[
0] + item.w + line.lineItemEdge:
if line.Yc - (item.h + item.left_bottom_point[1]) - line.lineItemEdge < step:
step = line.Yc - (item.h + item.left_bottom_point[1]) - line.lineItemEdge
line.obstacle = [item.w, item.h, item.left_bottom_point[0], item.left_bottom_point[1]]
# 遇到死点
if step < self.error:
line.KP = 2
return 0
for tempObstacle in line.tempObstacleList:
# 在当前点的左边才进行判断，且在判断范围内
if line.Yc - step - line.lineItemEdge <= tempObstacle[3] + tempObstacle[1] <= line.Yc - line.lineItemEdge:
# 如果不满足安全距离
if tempObstacle[2] - line.lineItemEdge < line.Xc < tempObstacle[2] + tempObstacle[
0] + line.lineItemEdge:
if line.Yc - (tempObstacle[1] + tempObstacle[3]) - line.lineItemEdge < step:
step = line.Yc - (tempObstacle[1] + tempObstacle[3]) - line.lineItemEdge
line.obstacle = [tempObstacle[0], tempObstacle[1], tempObstacle[2],
tempObstacle[3]]
# 遇到死点
if step < self.error:
line.KP = 2
return 0
if isSmart is True and line.Yc - step <= self.Yt <= line.Yc:
line.Yd = self.Yt
line.obstacle = None
else:
line.Yd = line.Yc - step
line.Xd = line.Xc
if self.isArriveDestination(line.Xd, line.Yd):
# line.KB = 1
pass
elif abs(step - line.exploreRange) < self.error:
line.KB = 0
else:
line.KB = 2
line.KP = 0
return abs(line.Yd - line.Yc)
# 判断点是否到达终点
def isArriveDestination(self, x, y):
return abs(x - self.Xt) < self.error and abs(y - self.Yt) < self.error
# 传入点链，计算上一段水平或垂直的最长距离
def calcLastLongestDistance(self, lineArr):
lastLongestDistance = 0
flag = None # vertical horizontal
for i in range(len(lineArr) - 1):
i = len(lineArr) - i - 1
j = i - 1
if flag is None:
if lineArr[i][0] == lineArr[j][0]:
flag = "vertical"
lastLongestDistance += abs(lineArr[i][1] - lineArr[j][1])
else:
flag = "horizontal"
lastLongestDistance += abs(lineArr[i][0] - lineArr[j][0])
elif flag == "horizontal":
if lineArr[i][0] == lineArr[j][0]:
break
lastLongestDistance += abs(lineArr[i][0] - lineArr[j][0])
elif flag == "vertical":
if lineArr[i][1] == lineArr[j][1]:
break
lastLongestDistance += abs(lineArr[i][1] - lineArr[j][1])
return lastLongestDistance, flag
def copyLine(line):
copyLine = Line(line.lineArr[0], line.tempObstacleList.copy())
copyLine.lineArr = line.lineArr.copy()
copyLine.length = line.length
try:
copyLine.L1 = line.L1
except:
copyLine.L1 = 0
try:
copyLine.Xd = line.Xd
except:
copyLine.Xd = line.Xc
try:
copyLine.Yd = line.Yd
except:
copyLine.Yd = line.Yc
copyLine.Xc = line.Xc
copyLine.Yc = line.Yc
copyLine.flags = line.flags.copy()
copyLine.L = line.L
try:
copyLine.KC = line.KC
except:
copyLine.KC = 0
copyLine.KB = line.KB
try:
copyLine.KP = line.KP
except:
copyLine.KP = 0
copyLine.IB = line.IB
copyLine.exploreRange = line.exploreRange
copyLine.lineWidth = line.lineWidth
copyLine.lineItemEdge = line.lineItemEdge
copyLine.lineEdge = line.lineEdge
copyLine.obstacle = line.obstacle.copy() if line.obstacle is not None else None
copyLine.KF = line.KF
copyLine.flags = line.flags.copy()
return copyLine
def copyLine2(line):
copyLine = Line(line.lineArr[0], line.tempObstacleList.copy())
copyLine.lineArr = line.lineArr.copy()
copyLine.length = line.length
copyLine.Xc = line.Xc
copyLine.Yc = line.Yc
copyLine.flags = line.flags.copy()
copyLine.L = line.L
copyLine.KB = line.KB
copyLine.IB = line.IB
copyLine.exploreRange = line.exploreRange
copyLine.lineWidth = line.lineWidth
copyLine.lineItemEdge = line.lineItemEdge
copyLine.lineEdge = line.lineEdge
copyLine.KF = line.KF
copyLine.flags = line.flags.copy()
return copyLine
# 计算包络矩形的宽和高
def calc_envelope_rectangle_w_h(boundary):
min_x = None
max_x = None
min_y = None
max_y = None
for x, y in boundary:
if min_x is None:
min_x = x
max_x = x
min_y = y
max_y = y
else:
min_x = min(min_x, x)
max_x = max(max_x, x)
min_y = min(min_y, y)
max_y = max(max_y, y)
return max_x - min_x, max_y - min_y
# 传入多边形顶点列表，返回该多边形所有垂直线段(x,y,l)（只适用于正交多边形）
def calc_vertical_line_list(boundary):
vertical_line_list = []
l = len(boundary)
for index in range(l):
x, y = boundary[index]
x_f, y_f = boundary[index - 1 if index - 1 >= 0 else l - 1]
if x_f == x:
if y < y_f:
vertical_line_list.append((x, y, y_f - y))
continue
x_b, y_b = boundary[index + 1 if index + 1 < l else 0]
if x_b == x:
if y < y_b:
vertical_line_list.append((x, y, y_b - y))
return vertical_line_list
# 传入多边形顶点列表，返回该多边形所有水平线段(x,y,l)（只适用于正交多边形）
def calc_horizontal_line_list(boundary):
horizontal_line_list = []
l = len(boundary)
for index in range(l):
x, y = boundary[index]
x_f, y_f = boundary[index - 1 if index - 1 >= 0 else l - 1]
if y_f == y:
if x < x_f:
horizontal_line_list.append((x, y, x_f - x))
continue
x_b, y_b = boundary[index + 1 if index + 1 < l else 0]
if y_b == y:
if x < x_b:
horizontal_line_list.append((x, y, x_b - x))
return horizontal_line_list
# 传入多边形所有水平线段，返回放入当前多边形将会新增的天际线(x,y,l)
def calc_add_sky_line_list(horizontal_line_list):
add_sky_line_list = []
for i in range(len(horizontal_line_list)):
x_i, y_i, l_i = horizontal_line_list[i]
b = True
for j in range(len(horizontal_line_list)):
x_j, y_j, l_j = horizontal_line_list[j]
if i != j and y_j > y_i and line_is_intersect((x_i, x_i + l_i), (x_j, x_j + l_j)):
b = False
break
if b:
add_sky_line_list.append((x_i, y_i, l_i))
return add_sky_line_list
# 传入两条线段，返回两条线段是否相交，线段格式：(线段左端点坐标，线段右端点坐标)
def line_is_intersect(line1, line2):
real_len = max(line1[0], line1[1], line2[0], line2[1]) - min(line1[0], line1[1], line2[0], line2[1])
ideal_len = line1[1] - line1[0] + line2[1] - line2[0]
return real_len < ideal_len
# 传入多边形顶点列表，计算可能的放置对标点
def calc_aim_point_list(boundary):
aim_point_list = [(0, 0)]
min_x = None
for x, y in boundary:
if y == 0:
if min_x is None or min_x > x:
min_x = x
if min_x != 0:
aim_point_list.append((min_x, 0))
return aim_point_list
if __name__ == '__main__':
# 构建边界顶点坐标（只支持矩形边界）
area = [[-20.0, -20.0], [524.0, -20.0], [524.0, 742.0], [-20.0, 742.0]]
# 构建模块（障碍物） 模块支持矩形、L型、T型
item_boundary_list = [
[[294.0, 20.0], [423.5, 20.0], [423.5, 60.5], [475.0, 60.5], [475.0, 155.0], [294.0, 155.0]],
[[98.0, 231.0], [98.0, 307.0], [90.0, 307.0], [90.0, 322.0], [30.0, 322.0], [30.0, 231.0]],
[[212.0, 372.0], [212.0, 465.5], [202.0, 465.5], [202.0, 481.0], [20.0, 481.0], [20.0, 372.0]],
[[254.0, 20.0], [254.0, 131.5], [242.0, 131.5], [242.0, 147.0], [151.0, 147.0], [151.0, 20.0]],
[[134.0, 521.0], [134.0, 596.5], [76.1, 596.5], [76.1, 702.0], [20.0, 702.0], [20.0, 521.0]],
[[466.0, 205.0], [466.0, 280.5], [394.2, 280.5], [394.2, 440.0], [279.0, 440.0], [279.0, 205.0]],
[[339.0, 490.0], [468.5, 490.0], [468.5, 504.0], [484.0, 504.0], [484.0, 680.0], [339.0, 680.0]],
[[20.0, 20.0], [96.0, 20.0], [96.0, 28.0], [111.0, 28.0], [111.0, 181.0], [20.0, 181.0]],
[[299.0, 521.0], [299.0, 650.5], [285.0, 650.5], [285.0, 666.0], [174.0, 666.0], [174.0, 521.0]],
[[229.0, 187.0], [229.0, 316.5], [215.0, 316.5], [215.0, 332.0], [151.0, 332.0], [151.0, 187.0]],
]
# 构建每个模型（障碍物）的名字
item_name_list = ["M" + str(i+1) for i in range(len(item_boundary_list))]
# 求解对象声明
model = NoGridLineExploreModel(
[Item(item_name_list[index], boundary) for
index, boundary in
enumerate(item_boundary_list)], area)
# 构建实例 [起点x，起点y，终点x，终点y] 注意起点和终点不能在模块（障碍物）内部，否则会出现重叠问题、无法到达终点问题等
instanceArr = [
[350, 470, 40, 710],
[120, 100, 330, 580],
]
# 求解
print("=" * 50 + " 程序开始运行 " + "=" * 50)
startTime = time.time()
lineList = model.solve(instanceArr)
print("=" * 50 + " 程序结束，共用时：" + str(time.time() - startTime) + " s " + "=" * 50)
# 输出
totalLen = 0
for line in lineList:
totalLen += line.length
print("lineLength: " + str(line.length) + " , lineList:" + str([line.lineArr]))
print("成功布线数: ", len(lineList))
lineArrList = [line.lineArr for line in lineList]
lineListStr = "lineList:" + str(lineArrList) + ","
print("总线长:", totalLen)
print(lineListStr)
三、多层无网格线探索算法
无网格线探索法同样可以推广至多层印制电路板布线。
为改善布线结果，对连线路径进行的优化分别在三个层次上进行：
（1） 对单层无网格探索的局部路径优化；
（2） 对多层布线路径的全局优化；
（3） 整板布线完成后，对各线网路径的整体优化．
