MrPanch · April 3, 2024 07:14 · Apr 3, 2024
diff --git a/Solution b/Solution
@@ -0,0 +1,151 @@
+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()
+
+