Bondwire直線連接問題探索

有人問是否能自動調整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()