[more nearest neighbors] Animating the algorithm to find your way through a cloud of points. #manim #isolated_point #distance #nearest

20240308_pathfinder.py

from manim import *

class PathFinder(MovingCameraScene):
    def construct(self):
        # thanks ChatGPT
        def closest_neighbor(given_point, points):
            # Convert points to numpy array for efficient calculations
            points_array = np.array(points)

            # Calculate Euclidean distance between given_point and all points
            distances = np.linalg.norm(points_array - given_point, axis=1)

            # Find index of closest point
            closest_index = np.argmin(distances)

            return closest_index

        npl = NumberPlane(
            x_range=[-30,30,1],
            y_range=[-30,30,1]
        )
        self.add(npl)

        pts = [(np.random.uniform(-6,6), np.random.uniform(-3,3), 0) for _ in range(50)]
        # find starting point
        pt2 = np.array(pts)
        start = None
        maxsum = 0
        isodist = 0
        for pt in pts[0:100]:
            dists = np.sort(np.linalg.norm(pt2 - pt, axis=1))
            sum = np.sum(dists[0:3])
            if sum > maxsum:
                maxsum = sum
                isodist = dists[1]
                start = pt
        print(start)
        sorted = [start]
        pts.remove(start)
        while (len(pts)>0):
            idx = closest_neighbor(sorted[-1], pts)
            sorted.append(pts[idx])
            pts.remove(pts[idx])

        circs = VGroup(
            *[Circle(radius = isodist, stroke_width=0, color=BLUE, fill_opacity=0.25).set_z_index(-2).move_to(pt) for pt in sorted]
        )

        path = VMobject()
        path.set_points_smoothly(sorted).set_stroke(width=.05)

        for pt in sorted:
            self.add(Dot(point=pt,radius=.05,color=RED))
        self.wait()

        self.play(
            *[GrowFromPoint(circ, circ.get_center()) for circ in circs],
            run_time = 4,
            rate_func=rate_functions.linear,
        )
        self.wait()
        self.play(circs[0].animate.set_fill(color=YELLOW))
        self.wait()

        d = Dot(radius=0.05, color=YELLOW, fill_opacity=1, stroke_width=0).move_to(path.get_start())

        self.play(
            self.camera.frame.animate.scale(0.25).move_to(path.get_start()),
            *[FadeOut(circ) for circ in circs],
            run_time=3
        )

        trace = TracedPath(d.get_center, stroke_width=1, stroke_color=YELLOW)
        self.add(d,trace)

        for pt in sorted[1:]:
            startprop = path.proportion_from_point(d.get_center())
            endprop = path.proportion_from_point(pt)
            radius = np.linalg.norm(d.get_center()-pt)
            circ = Circle(radius=radius, color=YELLOW, fill_opacity=0.4, stroke_width=0).move_to(d.get_center())
            self.play(
                self.camera.frame.animate.scale_to_fit_height(2*radius)
            )
            self.play(
                GrowFromPoint(circ, d.get_center()),
            )
            self.play(
                MoveAlongPath(d, path, rate_func=lambda t: startprop+t*(endprop-startprop)),
                MoveAlongPath(self.camera.frame, path, rate_func=lambda t: startprop+t*(endprop-startprop)),
                FadeOut(circ)
            )
        self.wait()
        self.play(self.camera.frame.animate.scale_to_fit_height(8).move_to(ORIGIN), run_time=3)
        self.wait()

readme.md