Spaces:
Runtime error
Runtime error
| import copy | |
| import random | |
| import networkx as nx | |
| import numpy as np | |
| import torch | |
| from util.geom_utils import ( | |
| get_quadrant, | |
| is_clockwise_or_not, | |
| poly_area, | |
| rotate_degree_counterclockwise_from_counter_degree, | |
| x_axis_angle, | |
| ) | |
| from util.metric_utils import get_results, get_results_float_with_semantic | |
| def graph_to_tensor(graph): | |
| t_l = [] | |
| for k, v in graph.items(): | |
| a = [] | |
| a.append(k) | |
| a.extend(v) | |
| b = [list(i) for i in a] | |
| c = torch.tensor(b) | |
| t_l.append(c) | |
| return torch.stack(t_l, dim=0) | |
| def tensor_to_graph(tensor): | |
| gr = {} | |
| for kv in tensor: | |
| k = tuple([i.item() for i in kv[0]]) | |
| v = kv[1:5] | |
| v = v.tolist() | |
| v = [tuple(i) for i in v] | |
| gr[k] = v | |
| return gr | |
| def tensors_to_graphs_batch(tensors): | |
| return [tensor_to_graph(ts) for ts in tensors] | |
| def get_cycle_basis_and_semantic_deprecated(best_result): | |
| output_points, output_edges = get_results_float_with_semantic(best_result) | |
| d = {} | |
| for output_point_index, output_point in enumerate(output_points): | |
| d[output_point] = output_point_index | |
| d_rev = {} | |
| for output_point_index, output_point in enumerate(output_points): | |
| d_rev[output_point_index] = output_point | |
| es = [] | |
| for output_edge in output_edges: | |
| es.append((d[output_edge[0]], d[output_edge[1]])) | |
| G = nx.Graph() | |
| for e in es: | |
| G.add_edge(e[0], e[1]) | |
| nx.draw(G) | |
| # plt.show() | |
| simple_cycles = nx.cycle_basis(G) | |
| results = [] | |
| for cycle_ind, cycle in enumerate(simple_cycles): | |
| points = [d_rev[ind] for ind in cycle] | |
| points.append(points[0]) | |
| is_clockwise = is_clockwise_or_not([(p[0], p[1]) for p in points]) | |
| if is_clockwise: | |
| points.reverse() | |
| cross_products = [] | |
| poses = [(p[0], p[1]) for p in points] | |
| for ind in range(len(poses) - 1): | |
| ei = [ | |
| poses[(ind + 1) % (len(poses) - 1)][0] - poses[ind][0], | |
| poses[(ind + 1) % (len(poses) - 1)][1] - poses[ind][1], | |
| ] | |
| eiplus1 = [ | |
| poses[(ind + 2) % (len(poses) - 1)][0] - poses[(ind + 1) % (len(poses) - 1)][0], | |
| poses[(ind + 2) % (len(poses) - 1)][1] - poses[(ind + 1) % (len(poses) - 1)][1], | |
| ] | |
| cross_products.append(np.cross(ei, eiplus1).tolist()) | |
| cross_products.insert(0, cross_products[-1]) | |
| cross_products.pop(-1) | |
| while 0 in cross_products: | |
| for point_ind, cross_product in enumerate(cross_products): | |
| if cross_product == 0: | |
| if point_ind == 0: | |
| p0 = copy.deepcopy(points[0]) | |
| points[0] = ( | |
| p0[0] + 0.000001 * random.random() * [-1, 1][random.randint(0, 1)], | |
| p0[1] + 0.000001 * random.random() * [-1, 1][random.randint(0, 1)], | |
| p0[2], | |
| p0[3], | |
| p0[4], | |
| p0[5], | |
| ) | |
| points[-1] = copy.deepcopy(points[0]) | |
| else: | |
| pi = copy.deepcopy(points[point_ind]) | |
| points[point_ind] = ( | |
| pi[0] + 0.000001 * random.random() * [-1, 1][random.randint(0, 1)], | |
| pi[1] + 0.000001 * random.random() * [-1, 1][random.randint(0, 1)], | |
| pi[2], | |
| pi[3], | |
| pi[4], | |
| pi[5], | |
| ) | |
| # print(points) | |
| cross_products = [] | |
| poses = [(p[0], p[1]) for p in points] | |
| for ind in range(len(poses) - 1): | |
| ei = [ | |
| poses[(ind + 1) % (len(poses) - 1)][0] - poses[ind][0], | |
| poses[(ind + 1) % (len(poses) - 1)][1] - poses[ind][1], | |
| ] | |
| eiplus1 = [ | |
| poses[(ind + 2) % (len(poses) - 1)][0] - poses[(ind + 1) % (len(poses) - 1)][0], | |
| poses[(ind + 2) % (len(poses) - 1)][1] - poses[(ind + 1) % (len(poses) - 1)][1], | |
| ] | |
| cross_products.append(np.cross(ei, eiplus1).tolist()) | |
| cross_products.insert(0, cross_products[-1]) | |
| cross_products.pop(-1) | |
| semantics = [[p[2], p[3], p[4], p[5]] for p in points] | |
| degrees = [] | |
| for ind in range(len(poses) - 1): | |
| ei_minus = [ | |
| -(poses[(ind + 1) % (len(poses) - 1)][0] - poses[ind][0]), | |
| -(poses[(ind + 1) % (len(poses) - 1)][1] - poses[ind][1]), | |
| ] | |
| eiplus1 = [ | |
| poses[(ind + 2) % (len(poses) - 1)][0] - poses[(ind + 1) % (len(poses) - 1)][0], | |
| poses[(ind + 2) % (len(poses) - 1)][1] - poses[(ind + 1) % (len(poses) - 1)][1], | |
| ] | |
| degrees.append((x_axis_angle(ei_minus), x_axis_angle(eiplus1))) | |
| degrees.insert(0, degrees[-1]) | |
| degrees.pop(-1) | |
| angles = [] | |
| for degree in degrees: | |
| angles.append(((min(degree), max(degree)), (max(degree), min(degree)))) | |
| angles_to_semantics = [] | |
| for angle_ind, angle in enumerate(angles): | |
| angle1 = angle[0] | |
| angle2 = angle[1] | |
| quadrant1 = get_quadrant(angle1) | |
| quadrant2 = get_quadrant(angle2) | |
| semantic1 = ( | |
| semantics[angle_ind][1] if quadrant1[0] >= 45 else -1, | |
| semantics[angle_ind][0] if quadrant1[1] >= 45 else -1, | |
| semantics[angle_ind][3] if quadrant1[2] >= 45 else -1, | |
| semantics[angle_ind][2] if quadrant1[3] >= 45 else -1, | |
| ) | |
| semantic2 = ( | |
| semantics[angle_ind][1] if quadrant2[0] >= 45 else -1, | |
| semantics[angle_ind][0] if quadrant2[1] >= 45 else -1, | |
| semantics[angle_ind][3] if quadrant2[2] >= 45 else -1, | |
| semantics[angle_ind][2] if quadrant2[3] >= 45 else -1, | |
| ) | |
| angle1_degree = sum(quadrant1) | |
| angle2_degree = sum(quadrant2) | |
| xproduct = cross_products[angle_ind] | |
| if xproduct < 0: | |
| if angle1_degree < angle2_degree: | |
| angles_to_semantics.append(semantic1) | |
| else: | |
| angles_to_semantics.append(semantic2) | |
| elif xproduct > 0: | |
| if angle1_degree < angle2_degree: | |
| angles_to_semantics.append(semantic2) | |
| else: | |
| angles_to_semantics.append(semantic1) | |
| else: | |
| assert 0 | |
| semantic_result = {} | |
| for semantic_label in range(0, 13): | |
| semantic_result[semantic_label] = 0 | |
| for everypoint_semantic in angles_to_semantics: | |
| everypoint_semantic = [s for s in everypoint_semantic if s != -1] | |
| for label in everypoint_semantic: | |
| semantic_result[label] += 1 / len(everypoint_semantic) | |
| this_cycle_semantic1 = sorted(semantic_result.items(), key=lambda d: d[1], reverse=True) | |
| this_cycle_result = None | |
| if this_cycle_semantic1[0][1] > this_cycle_semantic1[1][1]: | |
| this_cycle_result = this_cycle_semantic1[0][0] | |
| else: | |
| this_cycle_results = [i[0] for i in this_cycle_semantic1 if i[1] == this_cycle_semantic1[0][1]] | |
| this_cycle_result = this_cycle_results[random.randint(0, len(this_cycle_results) - 1)] | |
| results.append(this_cycle_result) | |
| return d_rev, simple_cycles, results | |
| def get_cycle_basis_and_semantic(best_result): | |
| output_points, output_edges = get_results_float_with_semantic(best_result) | |
| output_points = copy.deepcopy(output_points) | |
| output_edges = copy.deepcopy(output_edges) | |
| d = {} | |
| for output_point_index, output_point in enumerate(output_points): | |
| d[output_point] = output_point_index | |
| d_rev = {} | |
| for output_point_index, output_point in enumerate(output_points): | |
| d_rev[output_point_index] = output_point | |
| es = [] | |
| for output_edge in output_edges: | |
| es.append((d[output_edge[0]], d[output_edge[1]])) | |
| # print(d) | |
| G = nx.Graph() | |
| for e in es: | |
| G.add_edge(e[0], e[1]) | |
| simple_cycles = [] | |
| simple_cycles_number = [] | |
| simple_cycles_semantics = [] | |
| bridges = list(nx.bridges(G)) | |
| for b in bridges: | |
| if (d_rev[b[0]], d_rev[b[1]]) in output_edges: | |
| output_edges.remove((d_rev[b[0]], d_rev[b[1]])) | |
| es.remove((b[0], b[1])) | |
| G.remove_edge(b[0], b[1]) | |
| if (d_rev[b[1]], d_rev[b[0]]) in output_edges: | |
| output_edges.remove((d_rev[b[1]], d_rev[b[0]])) | |
| es.remove((b[1], b[0])) | |
| G.remove_edge(b[1], b[0]) | |
| connected_components = list(nx.connected_components(G)) | |
| for c in connected_components: | |
| if len(c) == 1: | |
| pass | |
| else: | |
| simple_cycles_c = [] | |
| simple_cycles_number_c = [] | |
| simple_cycle_semantics_c = [] | |
| # output_points_c = [p for p in output_points if d[p] in c] | |
| output_edges_c = [e for e in output_edges if d[e[0]] in c or d[e[1]] in c] | |
| output_edges_c_copy_for_traversing = copy.deepcopy(output_edges_c) | |
| for edge_c in output_edges_c: | |
| if edge_c not in output_edges_c_copy_for_traversing: | |
| pass | |
| else: | |
| simple_cycle_semantics = [] | |
| simple_cycle = [] | |
| simple_cycle_number = [] | |
| point1 = edge_c[0] | |
| point2 = edge_c[1] | |
| point1_number = d[point1] | |
| point2_number = d[point2] | |
| initial_point = None | |
| initial_point_number = None | |
| if point1_number < point2_number: | |
| initial_point = point1 | |
| initial_point_number = point1_number | |
| else: | |
| initial_point = point2 | |
| initial_point_number = point2_number | |
| simple_cycle.append(initial_point) | |
| simple_cycle_number.append(initial_point_number) | |
| last_point = initial_point | |
| current_point = None | |
| current_point_number = None | |
| if point1_number < point2_number: | |
| current_point = point2 | |
| current_point_number = point2_number | |
| else: | |
| current_point = point1 | |
| current_point_number = point1_number | |
| simple_cycle.append(current_point) | |
| simple_cycle_number.append(current_point_number) | |
| next_initial_point = copy.deepcopy(current_point) | |
| next_point = None | |
| next_point_number = None | |
| while next_point != next_initial_point: | |
| relevant_edges = [] | |
| for edge in output_edges_c: | |
| if edge[0] == current_point or edge[1] == current_point: | |
| relevant_edges.append(edge) | |
| relevant_edges_degree = [] | |
| for relevant_edge in relevant_edges: | |
| vec = None | |
| if relevant_edge[0] == current_point: | |
| vec = ( | |
| relevant_edge[1][0] - relevant_edge[0][0], | |
| relevant_edge[1][1] - relevant_edge[0][1], | |
| ) | |
| elif relevant_edge[1] == current_point: | |
| vec = ( | |
| relevant_edge[0][0] - relevant_edge[1][0], | |
| relevant_edge[0][1] - relevant_edge[1][1], | |
| ) | |
| else: | |
| assert 0 | |
| vec_degree = x_axis_angle(vec) | |
| relevant_edges_degree.append(vec_degree) | |
| vec_from_current_point_to_last_point_degree = None | |
| for relevant_edge_ind, relevant_edge in enumerate(relevant_edges): | |
| if relevant_edge == (current_point, last_point): | |
| vec_from_current_point_to_last_point_degree = relevant_edges_degree[relevant_edge_ind] | |
| relevant_edges.remove(relevant_edge) | |
| relevant_edges_degree.remove(vec_from_current_point_to_last_point_degree) | |
| elif relevant_edge == (last_point, current_point): | |
| vec_from_current_point_to_last_point_degree = relevant_edges_degree[relevant_edge_ind] | |
| relevant_edges.remove(relevant_edge) | |
| relevant_edges_degree.remove(vec_from_current_point_to_last_point_degree) | |
| else: | |
| continue | |
| rotate_deltas_counterclockwise = [] | |
| interior_angles = [] | |
| for relevant_edge_degree in relevant_edges_degree: | |
| rotate_delta = rotate_degree_counterclockwise_from_counter_degree( | |
| vec_from_current_point_to_last_point_degree, relevant_edge_degree | |
| ) | |
| rotate_deltas_counterclockwise.append(rotate_delta) | |
| interior_angles.append((relevant_edge_degree, vec_from_current_point_to_last_point_degree)) | |
| # print(rotate_deltas_counterclockwise) | |
| max_rotate_index = rotate_deltas_counterclockwise.index(max(rotate_deltas_counterclockwise)) | |
| interior_angle_counterclockwise = interior_angles[max_rotate_index] | |
| current_point_semantic = [ | |
| current_point[3], | |
| current_point[2], | |
| current_point[5], | |
| current_point[4], | |
| ] | |
| interior_angle_counterclockwise_degree_smaller = min(interior_angle_counterclockwise) | |
| interior_angle_counterclockwise_degree_bigger = max(interior_angle_counterclockwise) | |
| quadrant_smaller_to_bigger_counterclockwise = get_quadrant( | |
| ( | |
| interior_angle_counterclockwise_degree_smaller, | |
| interior_angle_counterclockwise_degree_bigger, | |
| ) | |
| ) | |
| # print(quadrant_smaller_to_bigger_counterclockwise) | |
| if interior_angle_counterclockwise.index(interior_angle_counterclockwise_degree_smaller) == 0: | |
| pass | |
| elif ( | |
| interior_angle_counterclockwise.index(interior_angle_counterclockwise_degree_smaller) == 1 | |
| ): | |
| quadrant_smaller_to_bigger_counterclockwise = ( | |
| 90 - quadrant_smaller_to_bigger_counterclockwise[0], | |
| 90 - quadrant_smaller_to_bigger_counterclockwise[1], | |
| 90 - quadrant_smaller_to_bigger_counterclockwise[2], | |
| 90 - quadrant_smaller_to_bigger_counterclockwise[3], | |
| ) | |
| else: | |
| assert 0 | |
| current_point_semantic_valid = [] | |
| for qd, seman in enumerate(current_point_semantic): | |
| if quadrant_smaller_to_bigger_counterclockwise[qd] >= 45: | |
| current_point_semantic_valid.append(seman) | |
| else: | |
| current_point_semantic_valid.append(-1) | |
| simple_cycle_semantics.append(current_point_semantic_valid) | |
| max_rotate_edge = relevant_edges[max_rotate_index] | |
| if max_rotate_edge[0] == current_point: | |
| next_point = max_rotate_edge[1] | |
| next_point_number = d[next_point] | |
| elif max_rotate_edge[1] == current_point: | |
| next_point = max_rotate_edge[0] | |
| next_point_number = d[next_point] | |
| else: | |
| assert 0 | |
| last_point = current_point | |
| current_point = next_point | |
| current_point_number = next_point_number | |
| simple_cycle.append(current_point) | |
| simple_cycle_number.append(current_point_number) | |
| for point_number_ind, point_number in enumerate(simple_cycle_number): | |
| if point_number_ind < len(simple_cycle_number) - 1: | |
| edge_number = (point_number, simple_cycle_number[point_number_ind + 1]) | |
| # print(simple_cycle_number) | |
| if edge_number[0] < edge_number[1]: | |
| if ( | |
| d_rev[edge_number[0]], | |
| d_rev[edge_number[1]], | |
| ) in output_edges_c_copy_for_traversing: | |
| output_edges_c_copy_for_traversing.remove( | |
| (d_rev[edge_number[0]], d_rev[edge_number[1]]) | |
| ) | |
| elif ( | |
| d_rev[edge_number[1]], | |
| d_rev[edge_number[0]], | |
| ) in output_edges_c_copy_for_traversing: | |
| output_edges_c_copy_for_traversing.remove( | |
| (d_rev[edge_number[1]], d_rev[edge_number[0]]) | |
| ) | |
| simple_cycle.pop(-1) | |
| simple_cycle_number.pop(-1) | |
| polygon_counterclockwise = [(int(p[0]), -int(p[1])) for p in simple_cycle] | |
| polygon_counterclockwise.pop(-1) | |
| # print('poly_area(polygon_counterclockwise)', poly_area(polygon_counterclockwise)) | |
| if poly_area(polygon_counterclockwise) > 0: | |
| simple_cycles_c.append(simple_cycle) | |
| simple_cycles_number_c.append(simple_cycle_number) | |
| semantic_result = {} | |
| for semantic_label in range(0, 13): | |
| semantic_result[semantic_label] = 0 | |
| for everypoint_semantic in simple_cycle_semantics: | |
| everypoint_semantic = [s for s in everypoint_semantic if s != -1] | |
| for label in everypoint_semantic: | |
| semantic_result[label] += 1 / len(everypoint_semantic) | |
| # print(semantic_result) | |
| del semantic_result[11] | |
| del semantic_result[12] | |
| this_cycle_semantic = sorted(semantic_result.items(), key=lambda d: d[1], reverse=True) | |
| # print(this_cycle_semantic) | |
| this_cycle_result = None | |
| if this_cycle_semantic[0][1] > this_cycle_semantic[1][1]: | |
| this_cycle_result = this_cycle_semantic[0][0] | |
| else: | |
| this_cycle_results = [ | |
| i[0] for i in this_cycle_semantic if i[1] == this_cycle_semantic[0][1] | |
| ] | |
| this_cycle_result = this_cycle_results[random.randint(0, len(this_cycle_results) - 1)] | |
| # print(this_cycle_result) | |
| simple_cycle_semantics_c.append(this_cycle_result) | |
| simple_cycles.extend(simple_cycles_c) | |
| simple_cycles_number.extend(simple_cycles_number_c) | |
| simple_cycles_semantics.extend(simple_cycle_semantics_c) | |
| # print([[(int(j[0]), int(j[1])) for j in i] for i in simple_cycles]) | |
| # print(len(simple_cycles_number)) | |
| # print(simple_cycles_semantics) | |
| return d_rev, simple_cycles, simple_cycles_semantics | |
| def get_cycle_basis_and_semantic_2(best_result): | |
| output_points, output_edges = get_results_float_with_semantic(best_result) | |
| output_points = copy.deepcopy(output_points) | |
| output_edges = copy.deepcopy(output_edges) | |
| # print(output_points) | |
| # print(output_edges) | |
| # assert 0 | |
| d = {} | |
| for output_point_index, output_point in enumerate(output_points): | |
| d[output_point] = output_point_index | |
| d_rev = {} | |
| for output_point_index, output_point in enumerate(output_points): | |
| d_rev[output_point_index] = output_point | |
| es = [] | |
| for output_edge in output_edges: | |
| es.append((d[output_edge[0]], d[output_edge[1]])) | |
| # print(d) | |
| G = nx.Graph() | |
| for e in es: | |
| G.add_edge(e[0], e[1]) | |
| simple_cycles = [] | |
| simple_cycles_number = [] | |
| simple_cycles_semantics = [] | |
| bridges = list(nx.bridges(G)) | |
| for b in bridges: | |
| if (d_rev[b[0]], d_rev[b[1]]) in output_edges: | |
| output_edges.remove((d_rev[b[0]], d_rev[b[1]])) | |
| es.remove((b[0], b[1])) | |
| G.remove_edge(b[0], b[1]) | |
| if (d_rev[b[1]], d_rev[b[0]]) in output_edges: | |
| output_edges.remove((d_rev[b[1]], d_rev[b[0]])) | |
| es.remove((b[1], b[0])) | |
| G.remove_edge(b[1], b[0]) | |
| connected_components = list(nx.connected_components(G)) | |
| for c in connected_components: | |
| if len(c) == 1: | |
| pass | |
| else: | |
| simple_cycles_c = [] | |
| simple_cycles_number_c = [] | |
| simple_cycle_semantics_c = [] | |
| output_edges_c = [e for e in output_edges if d[e[0]] in c or d[e[1]] in c] | |
| output_edges_c_copy_for_traversing = copy.deepcopy(output_edges_c) | |
| for edge_c in output_edges_c: | |
| if edge_c not in output_edges_c_copy_for_traversing: | |
| pass | |
| else: | |
| simple_cycle_semantics = [] | |
| simple_cycle = [] | |
| simple_cycle_number = [] | |
| point1 = edge_c[0] | |
| point2 = edge_c[1] | |
| point1_number = d[point1] | |
| point2_number = d[point2] | |
| initial_point = None | |
| initial_point_number = None | |
| if point1_number < point2_number: | |
| initial_point = point1 | |
| initial_point_number = point1_number | |
| else: | |
| initial_point = point2 | |
| initial_point_number = point2_number | |
| simple_cycle.append(initial_point) | |
| simple_cycle_number.append(initial_point_number) | |
| last_point = initial_point | |
| current_point = None | |
| current_point_number = None | |
| if point1_number < point2_number: | |
| current_point = point2 | |
| current_point_number = point2_number | |
| else: | |
| current_point = point1 | |
| current_point_number = point1_number | |
| simple_cycle.append(current_point) | |
| simple_cycle_number.append(current_point_number) | |
| next_initial_point = copy.deepcopy(current_point) | |
| next_point = None | |
| next_point_number = None | |
| while next_point != next_initial_point: | |
| relevant_edges = [] | |
| for edge in output_edges_c: | |
| if edge[0] == current_point or edge[1] == current_point: | |
| relevant_edges.append(edge) | |
| relevant_edges_degree = [] | |
| for relevant_edge in relevant_edges: | |
| vec = None | |
| if relevant_edge[0] == current_point: | |
| vec = ( | |
| relevant_edge[1][0] - relevant_edge[0][0], | |
| relevant_edge[1][1] - relevant_edge[0][1], | |
| ) | |
| elif relevant_edge[1] == current_point: | |
| vec = ( | |
| relevant_edge[0][0] - relevant_edge[1][0], | |
| relevant_edge[0][1] - relevant_edge[1][1], | |
| ) | |
| else: | |
| assert 0 | |
| vec_degree = x_axis_angle(vec) | |
| relevant_edges_degree.append(vec_degree) | |
| vec_from_current_point_to_last_point_degree = None | |
| for relevant_edge_ind, relevant_edge in enumerate(relevant_edges): | |
| if relevant_edge == (current_point, last_point): | |
| vec_from_current_point_to_last_point_degree = relevant_edges_degree[relevant_edge_ind] | |
| relevant_edges.remove(relevant_edge) | |
| relevant_edges_degree.remove(vec_from_current_point_to_last_point_degree) | |
| elif relevant_edge == (last_point, current_point): | |
| vec_from_current_point_to_last_point_degree = relevant_edges_degree[relevant_edge_ind] | |
| relevant_edges.remove(relevant_edge) | |
| relevant_edges_degree.remove(vec_from_current_point_to_last_point_degree) | |
| else: | |
| continue | |
| rotate_deltas_counterclockwise = [] | |
| interior_angles = [] | |
| for relevant_edge_degree in relevant_edges_degree: | |
| rotate_delta = rotate_degree_counterclockwise_from_counter_degree( | |
| vec_from_current_point_to_last_point_degree, relevant_edge_degree | |
| ) | |
| rotate_deltas_counterclockwise.append(rotate_delta) | |
| interior_angles.append((relevant_edge_degree, vec_from_current_point_to_last_point_degree)) | |
| # print(rotate_deltas_counterclockwise) | |
| max_rotate_index = rotate_deltas_counterclockwise.index(max(rotate_deltas_counterclockwise)) | |
| interior_angle_counterclockwise = interior_angles[max_rotate_index] | |
| current_point_semantic = [ | |
| current_point[3], | |
| current_point[2], | |
| current_point[5], | |
| current_point[4], | |
| ] | |
| interior_angle_counterclockwise_degree_smaller = min(interior_angle_counterclockwise) | |
| interior_angle_counterclockwise_degree_bigger = max(interior_angle_counterclockwise) | |
| quadrant_smaller_to_bigger_counterclockwise = get_quadrant( | |
| ( | |
| interior_angle_counterclockwise_degree_smaller, | |
| interior_angle_counterclockwise_degree_bigger, | |
| ) | |
| ) | |
| if interior_angle_counterclockwise.index(interior_angle_counterclockwise_degree_smaller) == 0: | |
| pass | |
| elif ( | |
| interior_angle_counterclockwise.index(interior_angle_counterclockwise_degree_smaller) == 1 | |
| ): | |
| quadrant_smaller_to_bigger_counterclockwise = ( | |
| 90 - quadrant_smaller_to_bigger_counterclockwise[0], | |
| 90 - quadrant_smaller_to_bigger_counterclockwise[1], | |
| 90 - quadrant_smaller_to_bigger_counterclockwise[2], | |
| 90 - quadrant_smaller_to_bigger_counterclockwise[3], | |
| ) | |
| else: | |
| assert 0 | |
| current_point_semantic_valid = [] | |
| for qd, seman in enumerate(current_point_semantic): | |
| if 1: | |
| current_point_semantic_valid.append(seman) | |
| else: | |
| current_point_semantic_valid.append(-1) | |
| simple_cycle_semantics.append(current_point_semantic_valid) | |
| max_rotate_edge = relevant_edges[max_rotate_index] | |
| if max_rotate_edge[0] == current_point: | |
| next_point = max_rotate_edge[1] | |
| next_point_number = d[next_point] | |
| elif max_rotate_edge[1] == current_point: | |
| next_point = max_rotate_edge[0] | |
| next_point_number = d[next_point] | |
| else: | |
| assert 0 | |
| last_point = current_point | |
| current_point = next_point | |
| current_point_number = next_point_number | |
| simple_cycle.append(current_point) | |
| simple_cycle_number.append(current_point_number) | |
| for point_number_ind, point_number in enumerate(simple_cycle_number): | |
| if point_number_ind < len(simple_cycle_number) - 1: | |
| edge_number = (point_number, simple_cycle_number[point_number_ind + 1]) | |
| if edge_number[0] < edge_number[1]: | |
| if ( | |
| d_rev[edge_number[0]], | |
| d_rev[edge_number[1]], | |
| ) in output_edges_c_copy_for_traversing: | |
| output_edges_c_copy_for_traversing.remove( | |
| (d_rev[edge_number[0]], d_rev[edge_number[1]]) | |
| ) | |
| elif ( | |
| d_rev[edge_number[1]], | |
| d_rev[edge_number[0]], | |
| ) in output_edges_c_copy_for_traversing: | |
| output_edges_c_copy_for_traversing.remove( | |
| (d_rev[edge_number[1]], d_rev[edge_number[0]]) | |
| ) | |
| simple_cycle.pop(-1) | |
| simple_cycle_number.pop(-1) | |
| polygon_counterclockwise = [(int(p[0]), -int(p[1])) for p in simple_cycle] | |
| polygon_counterclockwise.pop(-1) | |
| if poly_area(polygon_counterclockwise) > 0: | |
| simple_cycles_c.append(simple_cycle) | |
| simple_cycles_number_c.append(simple_cycle_number) | |
| semantic_result = {} | |
| for semantic_label in range(0, 13): | |
| semantic_result[semantic_label] = 0 | |
| for everypoint_semantic in simple_cycle_semantics: | |
| for _ in range(0, 13): | |
| if _ in everypoint_semantic: | |
| semantic_result[_] += 1 | |
| del semantic_result[11] | |
| del semantic_result[12] | |
| this_cycle_semantic = sorted(semantic_result.items(), key=lambda d: d[1], reverse=True) | |
| this_cycle_result = None | |
| if this_cycle_semantic[0][1] > this_cycle_semantic[1][1]: | |
| this_cycle_result = this_cycle_semantic[0][0] | |
| else: | |
| this_cycle_results = [ | |
| i[0] for i in this_cycle_semantic if i[1] == this_cycle_semantic[0][1] | |
| ] | |
| this_cycle_result = this_cycle_results[random.randint(0, len(this_cycle_results) - 1)] | |
| simple_cycle_semantics_c.append(this_cycle_result) | |
| simple_cycles.extend(simple_cycles_c) | |
| simple_cycles_number.extend(simple_cycles_number_c) | |
| simple_cycles_semantics.extend(simple_cycle_semantics_c) | |
| return d_rev, simple_cycles, simple_cycles_semantics | |
| def get_cycle_basis(best_result): | |
| output_points, output_edges = get_results(best_result) | |
| output_points = copy.deepcopy(output_points) | |
| output_edges = copy.deepcopy(output_edges) | |
| d = {} | |
| for output_point_index, output_point in enumerate(output_points): | |
| d[output_point] = output_point_index | |
| d_rev = {} | |
| for output_point_index, output_point in enumerate(output_points): | |
| d_rev[output_point_index] = output_point | |
| es = [] | |
| for output_edge in output_edges: | |
| es.append((d[output_edge[0]], d[output_edge[1]])) | |
| G = nx.Graph() | |
| for e in es: | |
| G.add_edge(e[0], e[1]) | |
| simple_cycles = [] | |
| simple_cycles_number = [] | |
| bridges = list(nx.bridges(G)) | |
| for b in bridges: | |
| if (d_rev[b[0]], d_rev[b[1]]) in output_edges: | |
| output_edges.remove((d_rev[b[0]], d_rev[b[1]])) | |
| es.remove((b[0], b[1])) | |
| G.remove_edge(b[0], b[1]) | |
| if (d_rev[b[1]], d_rev[b[0]]) in output_edges: | |
| output_edges.remove((d_rev[b[1]], d_rev[b[0]])) | |
| es.remove((b[1], b[0])) | |
| G.remove_edge(b[1], b[0]) | |
| connected_components = list(nx.connected_components(G)) | |
| for c in connected_components: | |
| if len(c) == 1: | |
| pass | |
| else: | |
| simple_cycles_c = [] | |
| simple_cycles_number_c = [] | |
| output_edges_c = [e for e in output_edges if d[e[0]] in c or d[e[1]] in c] | |
| output_edges_c_copy_for_traversing = copy.deepcopy(output_edges_c) | |
| for edge_c in output_edges_c: | |
| if edge_c not in output_edges_c_copy_for_traversing: | |
| pass | |
| else: | |
| simple_cycle = [] | |
| simple_cycle_number = [] | |
| point1 = edge_c[0] | |
| point2 = edge_c[1] | |
| point1_number = d[point1] | |
| point2_number = d[point2] | |
| if point1_number < point2_number: | |
| initial_point = point1 | |
| initial_point_number = point1_number | |
| current_point = point2 | |
| current_point_number = point2_number | |
| else: | |
| initial_point = point2 | |
| initial_point_number = point2_number | |
| current_point = point1 | |
| current_point_number = point1_number | |
| simple_cycle.append(initial_point) | |
| simple_cycle_number.append(initial_point_number) | |
| simple_cycle.append(current_point) | |
| simple_cycle_number.append(current_point_number) | |
| last_point = initial_point | |
| next_initial_point = copy.deepcopy(current_point) | |
| next_point = None | |
| while next_point != next_initial_point: | |
| relevant_edges = [] | |
| for edge in output_edges_c: | |
| if edge[0] == current_point or edge[1] == current_point: | |
| relevant_edges.append(edge) | |
| relevant_edges_degree = [] | |
| for relevant_edge in relevant_edges: | |
| vec = None | |
| if relevant_edge[0] == current_point: | |
| vec = ( | |
| relevant_edge[1][0] - relevant_edge[0][0], | |
| relevant_edge[1][1] - relevant_edge[0][1], | |
| ) | |
| elif relevant_edge[1] == current_point: | |
| vec = ( | |
| relevant_edge[0][0] - relevant_edge[1][0], | |
| relevant_edge[0][1] - relevant_edge[1][1], | |
| ) | |
| else: | |
| assert 0 | |
| vec_degree = x_axis_angle(vec) | |
| relevant_edges_degree.append(vec_degree) | |
| vec_from_current_point_to_last_point_degree = None | |
| for relevant_edge_ind, relevant_edge in enumerate(relevant_edges): | |
| if relevant_edge == (current_point, last_point): | |
| vec_from_current_point_to_last_point_degree = relevant_edges_degree[relevant_edge_ind] | |
| relevant_edges.remove(relevant_edge) | |
| relevant_edges_degree.remove(vec_from_current_point_to_last_point_degree) | |
| elif relevant_edge == (last_point, current_point): | |
| vec_from_current_point_to_last_point_degree = relevant_edges_degree[relevant_edge_ind] | |
| relevant_edges.remove(relevant_edge) | |
| relevant_edges_degree.remove(vec_from_current_point_to_last_point_degree) | |
| else: | |
| continue | |
| rotate_deltas_counterclockwise = [] | |
| for relevant_edge_degree in relevant_edges_degree: | |
| rotate_delta = rotate_degree_counterclockwise_from_counter_degree( | |
| vec_from_current_point_to_last_point_degree, relevant_edge_degree | |
| ) | |
| rotate_deltas_counterclockwise.append(rotate_delta) | |
| max_rotate_index = rotate_deltas_counterclockwise.index(max(rotate_deltas_counterclockwise)) | |
| max_rotate_edge = relevant_edges[max_rotate_index] | |
| if max_rotate_edge[0] == current_point: | |
| next_point = max_rotate_edge[1] | |
| next_point_number = d[next_point] | |
| elif max_rotate_edge[1] == current_point: | |
| next_point = max_rotate_edge[0] | |
| next_point_number = d[next_point] | |
| else: | |
| assert 0 | |
| last_point = current_point | |
| current_point = next_point | |
| current_point_number = next_point_number | |
| simple_cycle.append(current_point) | |
| simple_cycle_number.append(current_point_number) | |
| for point_number_ind, point_number in enumerate(simple_cycle_number): | |
| if point_number_ind < len(simple_cycle_number) - 1: | |
| edge_number = (point_number, simple_cycle_number[point_number_ind + 1]) | |
| if edge_number[0] < edge_number[1]: | |
| if ( | |
| d_rev[edge_number[0]], | |
| d_rev[edge_number[1]], | |
| ) in output_edges_c_copy_for_traversing: | |
| output_edges_c_copy_for_traversing.remove( | |
| (d_rev[edge_number[0]], d_rev[edge_number[1]]) | |
| ) | |
| elif ( | |
| d_rev[edge_number[1]], | |
| d_rev[edge_number[0]], | |
| ) in output_edges_c_copy_for_traversing: | |
| output_edges_c_copy_for_traversing.remove( | |
| (d_rev[edge_number[1]], d_rev[edge_number[0]]) | |
| ) | |
| simple_cycle.pop(-1) | |
| simple_cycle_number.pop(-1) | |
| polygon_counterclockwise = [(int(p[0]), -int(p[1])) for p in simple_cycle] | |
| polygon_counterclockwise.pop(-1) | |
| if poly_area(polygon_counterclockwise) > 0: | |
| simple_cycles_c.append(simple_cycle) | |
| simple_cycles_number_c.append(simple_cycle_number) | |
| simple_cycles.extend(simple_cycles_c) | |
| simple_cycles_number.extend(simple_cycles_number_c) | |
| return d_rev, simple_cycles, simple_cycles_number | |