Created
April 3, 2024 07:14
-
-
Save MrPanch/8f614cf0793ccfaefecc2e41aea3790d to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import matplotlib.pyplot as plt | |
| import numpy as np | |
| import time | |
| norm = np.linalg.norm | |
| def calculate_baricenter(points): | |
| mid_result = 0 | |
| points.append(points[0]) | |
| for i in range(len(points)-1): | |
| mid_result += points[i][0]*points[i+1][1] - points[i+1][0]*points[i][1] | |
| A = 0.5 * mid_result | |
| G_x = 0 | |
| for i in range(len(points)-1): | |
| G_x += (points[i][0] + points[i+1][0]) * (points[i][0] * points[i+1][1] - points[i+1][0] * points[i][1]) | |
| G_x *= 1/(6 * A) | |
| G_y = 0 | |
| for i in range(len(points)-1): | |
| G_y += (points[i][1] + points[i+1][1]) * (points[i][0] * points[i+1][1] - points[i+1][0] * points[i][1]) | |
| G_y *= 1/(6 * A) | |
| return (G_x, G_y) | |
| def line_intersection(line1, line2): | |
| xdiff = (line1[0][0] - line1[1][0], line2[0][0] - line2[1][0]) | |
| ydiff = (line1[0][1] - line1[1][1], line2[0][1] - line2[1][1]) | |
| def det(a, b): | |
| return a[0] * b[1] - a[1] * b[0] | |
| div = det(xdiff, ydiff) | |
| if div == 0: | |
| return None | |
| d = (det(*line1), det(*line2)) | |
| x = det(d, xdiff) / div | |
| y = det(d, ydiff) / div | |
| return x, y | |
| def sample_all_edges(points): | |
| result = [] | |
| for i in range(len(points)-1): | |
| result.append((points[i],points[i+1])) | |
| return result | |
| def plot_lines(lines, color, legend=""): | |
| x_s = [item[0] for item in lines] | |
| y_s = [item[1] for item in lines] | |
| plt.plot(x_s, y_s, linestyle="-", marker="o", color=color, label=legend) | |
| def distance(a,b): | |
| return ((a[0] - b[0])**2 + (a[1] - b[1])**2)**0.5 | |
| def is_between(a,c,b): | |
| return abs(distance(a, c) + distance(c, b) - distance(a, b)) < 0.01 | |
| def check_intersection(edges, correcponding_points): | |
| result = [] | |
| for edge, point in zip(edges, correcponding_points): | |
| if point is None: | |
| result.append(False) | |
| else: | |
| result.append(is_between(edge[0], point, edge[1])) | |
| return result | |
| def find_closest_v1(current_figure, external_point): | |
| current_figure = current_figure.copy() | |
| st = time.time() | |
| center = calculate_baricenter(current_figure) | |
| centroid_line = (center, external_point) | |
| all_edges = sample_all_edges(current_figure) | |
| intersection_points = [line_intersection(current_line, centroid_line) for current_line in all_edges] | |
| on_edge = check_intersection(all_edges, intersection_points) | |
| distaces = [] | |
| for intersec_point, intersection_flag in zip(intersection_points, on_edge): | |
| if not intersection_flag: | |
| distaces.append(None) | |
| continue | |
| distaces.append(distance(intersec_point, external_point)) | |
| output = min((v,i) for i,v in enumerate(distaces) if v is not None)[1] | |
| elapsed = time.time() - st | |
| plot_lines(current_figure, "b", legend="polygon") | |
| plot_lines(centroid_line, "r", legend="centroid line") | |
| plot_lines(all_edges[output], "g", legend="the closest to the point edge") | |
| return elapsed | |
| def find_closest_v2(current_figure, external_point): | |
| current_figure = current_figure.copy() | |
| st = time.time() | |
| all_edges = sample_all_edges(current_figure) | |
| result = [] | |
| for edge in all_edges: | |
| p1 = np.array(edge[0]) | |
| p2 = np.array(edge[1]) | |
| p3 = np.array(external_point) | |
| d_1 = np.abs(norm(np.cross(p2-p1, p1-p3)))/norm(p2-p1) | |
| d_2 = distance(edge[0],external_point) | |
| d_3 = distance(edge[1],external_point) | |
| result.append(min(d_1,d_2,d_3)) | |
| index_min = np.argmin(result) | |
| elapsed = time.time() - st | |
| plot_lines(current_figure, "b", legend="polygon") | |
| plt.scatter(external_point[0], external_point[1], color="r", label="external_point") | |
| plot_lines(all_edges[index_min], "g", legend="the closest to the point edge") | |
| return elapsed | |
| if __name__ == "__main__": | |
| rect = [(0,0),(0,6),(10,6),(10,0)] | |
| tri = [(1,0),(3,5),(4,1)] | |
| parallelogram = [(2.5, 3.5), (10, -4), (2.5, -2.5), (-5, 5)] | |
| non_convex = [(0,0),(0,10),(8,10),(3,3),(6,0)] | |
| current_figure = parallelogram | |
| external_point = (6,4) | |
| times = [] | |
| for idx in range(10): | |
| elapsed = find_closest_v1(current_figure, external_point) | |
| if idx > 4: | |
| times.append(elapsed) | |
| print("centroid approach: ", np.mean(times) * 1000, " ms") | |
| times = [] | |
| for idx in range(10): | |
| elapsed = find_closest_v2(current_figure, external_point) | |
| if idx > 4: | |
| times.append(elapsed) | |
| print("classic: ", np.mean(times) * 1000, " ms") | |
| # plt.legend(loc="upper left") | |
| # plt.show() | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment