Skip to content
TheChatArchiveThe Chat Archive
gpt-4o-2024-05-13· OpenAIAi2 WildChat-4.8M (AI2)

import random import math import matplotlib.pyplot as plt def orientation(p, q, r):…

  1. User

    import random import math import matplotlib.pyplot as plt

    def orientation(p, q, r): vector1 = (q[0] - p[0], q[1] - p[1]) vector2 = (r[0] - p[0], r[1] - p[1]) cross_product = vector1[0] * vector2[1] - vector1[1] * vector2[0] if cross_product == 0: return "collinear" elif cross_product > 0: return "CCW" else: return "CW"

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

    def gift_wrapping(points): r0 = min(points, key = lambda point: (point[0], point[1])) r = r0 hull = [r]

    while 1:
        next = points[0]
        for point in points:
            if point == r:
                continue
            direction = orientation(r, next, point)
            if direction == "CW" or next == r or (direction == "collinear" and distance(r, next) < distance(r, point)):
                next = point
    
        if next != r0:
            hull.append(next)
            r = next
        else:
            return hull
    

    Main function

    points = [(0, 0), (1, 1), (2, 2), (0, 2), (2, 0), (0.9, -0.1)]

    for i in range(1,100):

    x = random.uniform(0, 100) # Random coordinates in [0, 10]

    y = random.uniform(0, 100) # Random coordinates in [0, 10]

    points.append((x, y))

    convex_hull = gift_wrapping(points) print(convex_hull)

    Visualization

    plt.figure(figsize=(8, 8)) plt.scatter(points[:, 0], points[:, 1], label='points') plt.plot(convex_hull[:, 0], convex_hull[:, 1], 'r-', lw=2, label='Convex Hull') plt.scatter(convex_hull[:, 0], convex_hull[:, 1], c='r') plt.fill(convex_hull[:, 0], convex_hull[:, 1], 'b', alpha=0.1) plt.legend() plt.show() Traceback (most recent call last): File "gift_wrapping.py", line 54, in plt.scatter(points[:, 0], points[:, 1], label='points') TypeError: list indices must be integers or slices, not tuple

  2. Assistant

    The error you're encountering is because you're trying to index a list (which holds tuples) as if it were a NumPy array. Lists of tuples are not indexed like 2D NumPy arrays. To fix this, you need to convert your list of points to a NumPy array before plotting. Here's the updated code:

    import random
    import math
    import numpy as np
    import matplotlib.pyplot as plt
    
    
    def orientation(p, q, r):
        vector1 = (q[0] - p[0], q[1] - p[1])
        vector2 = (r[0] - p[0], r[1] - p[1])
        cross_product = vector1[0] * vector2[1] - vector1[1] * vector2[0]
        if cross_product == 0:
            return "collinear"
        elif cross_product > 0:
            return "CCW"
        else:
            return "CW"
    
    
    def distance(p1, p2):
        return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)
    
    
    def gift_wrapping(points):
        r0 = min(points, key=lambda point: (point[0], point[1]))
        r = r0
        hull = [r]
    
        while 1:
            next_point = points[0]
            for point in points:
                if point == r:
                    continue
                direction = orientation(r, next_point, point)
                if direction == "CW" or next_point == r or (direction == "collinear" and distance(r, next_point) < distance(r, point)):
                    next_point = point
    
            if next_point != r0:
                hull.append(next_point)
                r = next_point
            else:
                return hull
    
    
    # Main function
    points = [(0, 0), (1, 1), (2, 2), (0, 2), (2, 0), (0.9, -0.1)]
    # for i in range(1, 100):
    #    x = random.uniform(0, 100)  # Random coordinates in [0, 100]
    #    y = random.uniform(0, 100)  # Random coordinates in [0, 100]
    #    points.append((x, y))
    convex_hull = gift_wrapping(points)
    print(convex_hull)
    
    # Convert to numpy arrays for easy indexing
    points = np.array(points)
    convex_hull = np.array(convex_hull)
    
    # Visualization
    plt.figure(figsize=(8, 8))
    plt.scatter(points[:, 0], points[:, 1], label='points')
    plt.plot(convex_hull[:, 0], convex_hull[:, 1], 'r-', lw=2, label='Convex Hull')
    plt.scatter(convex_hull[:, 0], convex_hull[:, 1], c='r')
    plt.fill(convex_hull[:, 0], convex_hull[:, 1], 'b', alpha=0.1)
    plt.legend()
    plt.show()
    

    In the gift_wrapping function, I replaced next with next_point to avoid conflict with the built-in next function. Additionally, I converted the points and convex_hull lists to NumPy arrays before plotting. Now, the indexing will work correctly for plotting.