import random import math import matplotlib.pyplot as plt def orientation(p, q, r):…
- 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 hullMain 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
- 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_wrappingfunction, I replacednextwithnext_pointto avoid conflict with the built-innextfunction. Additionally, I converted thepointsandconvex_hulllists to NumPy arrays before plotting. Now, the indexing will work correctly for plotting.