Sowmya15/Identifying_Commercial_Centers_Using_Machine_Learning

1# Convex Hull2# point class with x, y as point3class Point:4    def __init__(self, x, y):5        self.x = x6        self.y = y7 8 9def Left_index(points):10    """Finding the left most point"""11    minn = 012    for i in range(1, len(points)):13        if points[i].x < points[minn].x:14            minn = i15        elif points[i].x == points[minn].x:16            if points[i].y > points[minn].y:17                minn = i18    return minn19 20 21def orientation(p, q, r):22    """23    To find orientation of ordered triplet (p, q, r).24    The function returns following values25    0 --> p, q and r are colinear26    1 --> Clockwise27    2 --> Counterclockwise28    """29    val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y)30 31    if val == 0:32        return 033    elif val > 0:34        return 135    else:36        return 237 38 39def convexHull(points, n):40    # There must be at least 3 points41    if n < 3:42        return43 44    # Find the leftmost point45    l = Left_index(points)46 47    hull = []48 49    """ 50    Start from leftmost point, keep moving counterclockwise 51    until reach the start point again. This loop runs O(h) 52    times where h is number of points in result or output. 53    """54    p = l55    q = 056    while True:57        # Add current point to result58        hull.append(p)59 60        """ 61        Search for a point 'q' such that orientation(p, x, 62        q) is counterclockwise for all points 'x'. The idea 63        is to keep track of last visited most counterclock- 64        wise point in q. If any point 'i' is more counterclock- 65        wise than q, then update q. 66        """67        q = (p + 1) % n68 69        for i in range(n):70 71            # If i is more counterclockwise than current q, then update q72            if orientation(points[p], points[i], points[q]) == 2:73                q = i74 75        """ 76        Now q is the most counterclockwise with respect to p 77        Set p as q for next iteration, so that q is added to 78        result 'hull' 79        """80        p = q81 82        # While we don't come to first point83        if p == l:84            break85 86    # Print Result87    result = []88    for each in hull:89        result.append([points[each].x, points[each].y])90    return result91 92 93def apply_convex_hull(coordinates):94    points = []95    for coordinate in coordinates:96        x, y = coordinate[0], coordinate[1]97        points.append(Point(x, y))98 99    return convexHull(points, len(points))100