Ваш проект выглядит круто, поэтому я провожу несколько раз в поисках решения. Я придумал код ниже. Результат кода:
OUTPUT[XNOR[NOR[AND[B, A], OR[D, C]], XOR[NOT[G], NAND[E, F]]]]
Я сделал предположение, что если элемент находится левее, чем другой, то это предыдущий блок. Также я предположил, что в вашем наборе строк первая верна ... Это позволяет мне упростить ваш набор из нескольких строк в набор из 14 строк.
boxes = [['AND', (614, 98), (1146, 429)], ['NOT', (525, 1765), (1007, 1983)], ['NAND', (762, 1188), (1209, 1528)],
['NOR', (1323, 272), (1884, 682)], ['OR', (575, 599), (1225, 985)], ['XOR', (1393, 1368), (2177, 1842)],
['XNOR', (2136, 859), (2762, 1231)], ['A', (34, 50), (321, 224)], ['B', (12, 305), (344, 487)],
['C', (3, 581), (391, 779)], ['D', (0, 828), (400, 1060)], ['E', (0, 1143), (354, 1351)],
['F', (0, 1418), (313, 1615)], ['G', (0, 1753), (301, 1985)], ['OUTPUT', (2810, 940), (3069, 1184)]]
final_line_points = [[[(87, 1864), (625, 1869)]],
[[(623, 1815), (1354, 1855)], [(1343, 1660), (1770, 1655)], [(1348, 1656), (1348, 1869)]],
[[(102, 971), (531, 945)], [(518, 835), (892, 825)], [(521, 830), (526, 949)]],
[[(105, 1260), (494, 1254)], [(487, 1351), (891, 1340)], [(489, 1252), (491, 1356)]],
[[(107, 1533), (526, 1510)], [(516, 1432), (892, 1410)], [(521, 1433), (520, 1514)]],
[[(111, 432), (519, 396)], [(499, 313), (820, 299)], [(503, 310), (506, 402)]],
[[(123, 157), (496, 150)], [(493, 144), (498, 247)], [(495, 242), (815, 234)]],
[[(170, 692), (509, 687)], [(504, 771), (888, 764)], [(505, 685), (508, 775)]],
[[(936, 264), (1229, 261)], [(1227, 257), (1240, 485)], [(1234, 481), (1535, 458)]],
[[(985, 1361), (1343, 1347)], [(1341, 1344), (1348, 1578)], [(1345, 1575), (1773, 1571)]],
[[(991, 796), (1264, 778)], [(1240, 535), (1544, 520)], [(1247, 532), (1254, 783)]],
[[(1546, 582), (2156, 489)], [(2154, 488), (2148, 1021)]], [[(2153, 1087), (2164, 1581)]],
[[(2444, 1139), (3017, 1055)]]]
def dist(pt1, pt2):
return (pt1[0] - pt2[0]) ** 2 + (pt1[1] - pt2[1]) ** 2
def seg_dist(seg1, seg2):
distances = [dist(seg1[i], seg2[j]) for i in range(2) for j in range(2)]
return min(enumerate(distances), key=lambda x: x[1])
sorted_lines = []
for lines in final_line_points:
connected_part = lines[0]
non_connected = lines[1:]
while non_connected:
mat_dist = [seg_dist(connected_part, non_connected[i])[1] for i in range(len(non_connected))]
i, min_dist = min(enumerate(mat_dist), key=lambda x: x[1])
seg_to_connect = non_connected.pop(i)
idx, real_dist = seg_dist(connected_part, seg_to_connect)
if idx == 0:
print("error: this case is not handled")
exit()
elif idx == 1:
print("error: this case is not handled")
exit()
elif idx == 2:
connected_part[1] = seg_to_connect[1]
elif idx == 3:
connected_part[1] = seg_to_connect[0]
sorted_lines.append(connected_part)
class node():
def __init__(self, name, box) -> None:
super().__init__()
self.name = name
self.box = [(min(box[0][0], box[1][0]), min(box[0][1], box[1][1])),
(max(box[0][0], box[1][0]), max(box[0][1], box[1][1]))]
self.args = []
self.outputs = []
def __contains__(self, item):
return self.box[0][0] <= item[0] <= self.box[1][0] and self.box[0][1] <= item[1] <= self.box[1][1]
def __str__(self) -> str:
if self.args:
return f"{self.name}{self.args}"
else:
return f"{self.name}"
def __repr__(self) -> str:
return self.__str__()
def center(self):
return (self.box[0][0] + self.box[1][0]) / 2, (self.box[0][1] + self.box[1][1]) / 2
nodes = [node(box[0], box[1:]) for box in boxes]
for line in sorted_lines:
start_point = line[0]
end_point = line[1]
try:
gate1 = next(node for node in nodes if start_point in node)
gate2 = next(node for node in nodes if end_point in node)
if gate1.center() < gate2.center():
source_gate = gate1
dest_gate = gate2
else:
source_gate = gate2
dest_gate = gate1
source_gate.outputs.append(dest_gate)
dest_gate.args.append(source_gate)
except StopIteration:
print(f"{start_point} or {end_point} not in any of the boxes")
print(next(node for node in nodes if node.name == "OUTPUT"))
Я могу объяснить больше в другой день, если нужно, или вы можете начать отсюда. В любом случае, получайте удовольствие от вашего проекта.
EDIT:
Моя цель состояла в том, чтобы построить график, где узлы - это прямоугольники, а края - линии. Проблема заключалась в том, что эти строки определяются только как набор закрытых линий. Также они были в беспорядке, но первый. Итак, первый шаг - превратить каждый набор линий в прямую. Это то, что я назвал sorted_lines.
Для построения этого списка я использовал следующую логику:
- Для каждого набора линий разбить его на связанную часть и не связанную часть
- Инициализация подключенной части - это первая строка набора. Как я уже сказал, здесь я предположил, что первая строка верна. Попробуйте улучшить это, потому что это предположение может быть неверным в других случаях.
Пока не подключена линия, сделайте следующее:
- Найдите сегмент, ближайший конец к соединенной части
- Удалите его из неподключенной части
- Проверьте, какой конец сегмента находится ближе всего к подключенной детали
- Если это первая точка отрезка, то последняя точка соединенной детали становится второй точкой отрезка, иначе первая точка становится последней точкой.
В проверке не обрабатываются случаи, когда соединяемый сегмент замыкается на первую точку соединенной детали, а не на последнюю точку. Это не обрабатывается, потому что я предположил, что первая строка верна. Еще раз, это может быть улучшено.
Теперь, когда у вас есть отсортированные строки, для каждого из них найдите узлы, содержащие каждый конец. Выберите самый последний в качестве шлюза источника и самый правый в качестве шлюза назначения. Поскольку ребра не ориентированы, я должен был принять ориентацию. Обновите входы шлюза назначения и выходы шлюза источника.
Наконец напечатайте последние ворота вашего графика.