Hesaplamalı Geometri, Algoritma Tasarımı ve Analizi

def closest_pair_1d(points):
    def find_closest_pair(sorted_points):
        # Base case: If there are only two points, return them
        if len(sorted_points) == 2:
            return sorted_points[0], sorted_points[1]
        # Base case: If there are three points, return the closest pair
        if len(sorted_points) == 3:
            return min(
                ((sorted_points[0], sorted_points[1]),
                 (sorted_points[1], sorted_points[2]),
                 (sorted_points[0], sorted_points[2])),
                key=lambda pair: abs(pair[1] - pair[0])
            )
        # Divide the points into two halves
        mid = len(sorted_points) // 2
        left_half = sorted_points[:mid]
        right_half = sorted_points[mid:]
        # Find the closest pair in each half
        closest_pair_left = find_closest_pair(left_half)
        closest_pair_right = find_closest_pair(right_half)
        # Find the closest pair across the split
        closest_pair_split = (left_half[-1], right_half[0])
        # Return the overall closest pair
        return min(closest_pair_left, closest_pair_right, closest_pair_split, key=lambda pair: abs(pair[1] - pair[0]))

    if len(points) < 2:
        raise ValueError("At least two points are required")
    # Sort the points
    sorted_points = sorted(points)
    # Find the closest pair using divide and conquer
    return find_closest_pair(sorted_points)

# Example usage
points = [0, 1, 3, 5, 7, 9, 11]
closest_points = closest_pair_1d(points)
print(f"The closest pair of points is: {closest_points}")

import math

def distance(point1, point2):
    return math.sqrt((point1[0] - point2[0]) ** 2 + (point1[1] - point2[1]) ** 2)

def closest_pair_2d(points):
    def closest_pair_recursive(points_sorted_by_x, points_sorted_by_y):
        n = len(points_sorted_by_x)

        if n <= 3:
            return brute_force_closest_pair(points_sorted_by_x)

        mid = n // 2
        left_half_x = points_sorted_by_x[:mid]
        right_half_x = points_sorted_by_x[mid:]

        midpoint = points_sorted_by_x[mid][0]
        left_half_y = list(filter(lambda x: x[0] <= midpoint, points_sorted_by_y))
        right_half_y = list(filter(lambda x: x[0] > midpoint, points_sorted_by_y))

        (p1, q1, d1) = closest_pair_recursive(left_half_x, left_half_y)
        (p2, q2, d2) = closest_pair_recursive(right_half_x, right_half_y)

        if d1 < d2:
            d = d1
            min_pair = (p1, q1)
        else:
            d = d2
            min_pair = (p2, q2)

        (p3, q3, d3) = closest_split_pair(points_sorted_by_x, points_sorted_by_y, d, min_pair)

        if d3 < d:
            return (p3, q3, d3)
        else:
            return min_pair[0], min_pair[1], d

    def brute_force_closest_pair(points):
        min_dist = float('inf')
        p1 = None
        p2 = None
        for i in range(len(points)):
            for j in range(i + 1, len(points)):
                d = distance(points[i], points[j])
                if d < min_dist:
                    min_dist = d
                    p1, p2 = points[i], points[j]
        return p1, p2, min_dist

    def closest_split_pair(points_sorted_by_x, points_sorted_by_y, delta, best_pair):
        n = len(points_sorted_by_x)
        mid_x = points_sorted_by_x[n // 2][0]

        Sy = [point for point in points_sorted_by_y if mid_x - delta <= point[0] <= mid_x + delta]

        best = delta
        len_Sy = len(Sy)
        for i in range(len_Sy - 1):
            for j in range(i + 1, min(i + 7, len_Sy)):
                p, q = Sy[i], Sy[j]
                dst = distance(p, q)
                if dst < best:
                    best = dst
                    best_pair = (p, q)
        return best_pair[0], best_pair[1], best

    points_sorted_by_x = sorted(points, key=lambda x: x[0])
    points_sorted_by_y = sorted(points, key=lambda x: x[1])

    p1, p2, min_dist = closest_pair_recursive(points_sorted_by_x, points_sorted_by_y)
    return p1, p2, min_dist

# Example usage
points = [(2, 3), (2, 4), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]
closest_points = closest_pair_2d(points)
print(f"The closest pair of points is: {closest_points[0]} and {closest_points[1]} with a distance of {closest_points[2]}")

import math

def graham_scan(points):
    # Find the point with the lowest y-coordinate, break ties by x-coordinate
    pivot = min(points, key=lambda p: (p[1], p[0]))
    points.remove(pivot)

    # Sort the points based on polar angle with the pivot
    points.sort(key=lambda p: (math.atan2(p[1] - pivot[1], p[0] - pivot[0]), p[1], p[0]))

    # Add the pivot back to the beginning
    points.insert(0, pivot)

    # Initialize the hull with the first two points
    hull = [points[0], points[1]]

    for p in points[2:]:
        while len(hull) > 1 and orientation(hull[-2], hull[-1], p) != 2:
            hull.pop()
        hull.append(p)

    return hull

def orientation(p, q, r):
    # Function to find the orientation of the triplet (p, q, r)
    # 0 -> p, q, and r are collinear
    # 1 -> Clockwise
    # 2 -> Counterclockwise
    val = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])
    if val == 0:
        return 0
    elif val > 0:
        return 1
    else:
        return 2

# Sample points
points = [(0, 0), (1, 1), (2, 2), (2, 0), (0, 2), (0.5, 2.5), (2.5, 2)]

# Call the function
convex_hull = graham_scan(points)

# Print the result
print("Convex Hull:", convex_hull)

def gift_wrapping(points):
    hull = []
    start = min(points, key=lambda p: p[0])  # Find the leftmost point
    on_hull = start
    while True:
        hull.append(on_hull)
        next_point = points[0]
        for p in points:
            if (next_point == on_hull) or (orientation(on_hull, next_point, p) == 2):
                next_point = p
        on_hull = next_point
        if on_hull == start:
            break
    return hull

def orientation(p, q, r):
    # Function to find the orientation of the triplet (p, q, r)
    # 0 -> p

, q, and r are collinear
    # 1 -> Clockwise
    # 2 -> Counterclockwise
    val = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])
    if val == 0:
        return 0
    elif val > 0:
        return 1
    else:
        return 2

# Sample points
points = [(0, 0), (1, 1), (2, 2), (2, 0), (0, 2), (0.5, 2.5), (2.5, 2)]

# Call the function
convex_hull = gift_wrapping(points)

# Print the result
print("Convex Hull:", convex_hull)