有人問是否能自動調整bondwire pt2的位置，避免bondwire重疊導致網格失敗。所以先簡化成2D直線問題。在已知die端的座標點及pkg端的座標點且Npkg>=Ndie的前提下，採用隨機算法+交叉判斷，七條以內的直線不交叉配對可以在1sec內完成。雖然不代表bond-wires不會碰撞(因立體且有厚度)，但是或許可以從這裡出發來探索一個可行的方法。
from itertools import combinations
from math import sqrt
import random
w = 0.1
def getparallel(A, B, d):
x1, y1 = A
x2, y2 = B
r = sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
deltax = (d / r) * (y1 - y2)
deltay = (d / r) * (x2 - x1)
x3 = x1 + deltax
y3 = y1 + deltay
x4 = x2 + deltax
y4 = y2 + deltay
return (x3, y3), (x4, y4)
def ccw(A, B, C):
Ax, Ay = A
Bx, By = B
Cx, Cy = C
return (Cy - Ay) * (Bx - Ax) > (By - Ay) * (Cx - Ax)
def intersect(A, B, C, D):
return ccw(A, C, D) != ccw(B, C, D) and ccw(A, B, C) != ccw(A, B, D)
def checkintersection(segments):
for (A, B), (C, D) in combinations(segments, 2):
_A, _B = getparallel(A, B, w / 2)
A_, B_ = getparallel(A, B, -w / 2)
_C, _D = getparallel(C, D, w / 2)
C_, D_ = getparallel(C, D, -w / 2)
if intersect(_A, _B, C_, D_) or intersect(A_, B_, _C, _D) or intersect(_A, B_, C_, _D) or intersect(A_, _B, _C,
D_):
return True
return False
import matplotlib.pyplot as plt
y0 = -2
die = [(0, i) for i in range(y0, y0 + 8)]
for i, j in die:
plt.scatter(i, j, marker='s')
x0, y0 = 3, 0
ds1 = [-1, -0.5, 0, 0.5]
ds2 = [-0.4, 0, 0.4, ]
pkg = [(x0 + i, y0 + j) for i in ds1 for j in ds2]
for i, j in pkg:
plt.scatter(i, j)
while (True):
segments = []
random.shuffle(pkg)
for (pt1, pt2) in zip(die, pkg[0:len(die)]):
segments.append((pt1, pt2))
if checkintersection(segments) == False:
break
for pt1, pt2 in segments:
x1, y1 = pt1
x2, y2 = pt2
plt.plot([x1, x2], [y1, y2])
plt.show()
