grahamScan.py

from random import randint

import matplotlib.pyplot as plt


def orientation(m, n, o):
    val = ((n[1] - m[1]) * (o[0] - n[0])) - ((o[1] - n[1]) * (n[0] - m[0]))
    if val > 0:
        return 1
    elif val < 0:
        return -1
    return 0


def distance(m, n):
    return (n[0] - m[0]) ** 2 + (n[1] - m[1]) ** 2


def Sorting_with_bubble(coordinates, b):
    for coord_ith in range(len(coordinates)):
        for j in range(len(coordinates) - coord_ith - 1):
            if (orientation(b, coordinates[j], coordinates[j + 1]) > 0) or (
                orientation(b, coordinates[j], coordinates[j + 1]) == 0
                and (distance(b, coordinates[j]) > distance(b, coordinates[j + 1]))
            ):
                temp = coordinates[j + 1]
                coordinates[j + 1] = coordinates[j]
                coordinates[j] = temp

    return coordinates


def Convex_hull_through_graham(coordinates):
    b = min(coordinates, key=lambda coord: (coord[1], coord[0]))
    coord_ith = coordinates.index(b)
    coordinates[coord_ith] = coordinates[0]
    coordinates[0] = b
    coordinates = [b] + Sorting_with_bubble(coordinates[1:], b)
    size_triplet = [coordinates[0], coordinates[1], coordinates[2]]
    for coord_ith in range(3, len(coordinates)):
        while (
            len(size_triplet) >= 3
            and orientation(size_triplet[-2], size_triplet[-1], coordinates[coord_ith])
            >= 0
        ):
            size_triplet.pop()
        size_triplet.append(coordinates[coord_ith])
    return size_triplet + [size_triplet[0]]


def random_points(n=30):
    coordinates = [(randint(0, n), randint(0, n)) for _ in range(n)]
    print(coordinates)
    return coordinates


if __name__ == "__main__":
    coordinates = random_points(120)

    X = [coord[0] for coord in coordinates]
    Y = [coord[1] for coord in coordinates]
    plt.plot(X, Y, ".b")

    boundary_poly = Convex_hull_through_graham(coordinates)

    X = [coord[0] for coord in boundary_poly]
    Y = [coord[1] for coord in boundary_poly]
    plt.plot(X, Y, "-og")

    plt.show()