Title: Find multiple convex hulls for a set of points in Python

[Convex hulls for a set of points]

The post Find the convex hull of a set of points in Python finds the convex hull for a set of points. After writing it, I wondered what it would be like to find the convex hull, remove it, and then repeat, sort of like peeling an onion.

The following find_convex_hulls method does that.

def find_convex_hulls(points): '''Extract convex hulls from the points until there's nothing left.''' # Make a copy so we don't messs up the points list. points = points.copy() hulls = [] while len(points) > 0: # Find the convex hull. _, _, _, _, hull = find_convex_hull(points) # Save the hull. hulls.append(hull) # Remove this hull's points from the points list. for point in hull: points.remove(point) return hulls

The method first copies the points list so it doesn't mess up the original list. It then enters a loop that runs as long as the list isn't empty.

Within the loop, the program uses the find_convex_hull method created by the previous example to find the points' convex hull. It adds the convex hull to the hulls list, removes the hull's points from the points list, and repeats.

When you click the Find Hulls button, the program executes the following code.

def find_hulls_click(self): '''Solve by using random orderings of the points.''' self.hulls = find_convex_hulls(self.points) # Disable the Find Hull button. self.find_hull_button.configure(state=tk.DISABLED) # Draw the results. self.draw()

This code calls find_convex_hulls to build the self.hulls list. It then calls the following draw method.

def draw(self): '''Draw the points, hull, etc.''' # Delete any previous drawing objects. self.canvas.delete(tk.ALL) # Draw the points. for point in self.points: self.draw_point(point, 'blue') # Draw the hulls. for hull in self.hulls: self.canvas.create_polygon(hull, outline='red', fill='')

This code clears the drawing canvas. It then loops through all of the points and calls the draw_point method to draw the points. Finally the code loops through the hulls and uses create_polygon to draw them.

The following code shows the draw_point method.

def draw_point(self, point, color): RADIUS = 5 self.canvas.create_oval( point[0] - RADIUS, point[1] - RADIUS, point[0] + RADIUS, point[1] + RADIUS, fill=color)

This code just wraps the create_oval method to make it a little easier to draw a circle centered at a point.

Download the example to experiment with it and to see additional details.