Untitled

import numpy as np
from scipy.spatial import ConvexHull, distance

def epsilon_approximate_hull(points, epsilon):
    # Step 1: Compute the original convex hull
    hull = ConvexHull(points)
    
    # Step 2: Find the centroid of the original hull (for expanding outward)
    centroid = np.mean(points[hull.vertices], axis=0)
    
    # Step 3: Calculate new points on expanded facets to include epsilon margin
    expanded_points = []
    for simplex in hull.simplices:
        # Get the points of the simplex (facet)
        facet_points = points[simplex]
        # Calculate the direction vectors from the centroid to each facet point
        directions = facet_points - centroid
        # Normalize directions and expand each point by (1 + epsilon)
        expanded_facet = centroid + (1 + epsilon) * directions
        expanded_points.extend(expanded_facet)
    
    # Combine original points with expanded points
    all_points = np.vstack([points, expanded_points])
    
    # Step 4: Compute the convex hull on the expanded point set
    approx_hull = ConvexHull(all_points)
    
    return approx_hull

# Example usage
np.random.seed(0)
# Create a 3D dataset of 30 random points
points = np.random.rand(30, 3)

# Set epsilon (0.1 corresponds to a 10% increase)
epsilon = 0.1

# Compute the epsilon-approximate convex hull
approx_hull = epsilon_approximate_hull(points, epsilon)

# Output: Vertices of the approximate convex hull
print("Vertices of the approximate convex hull:")
print(approx_hull.vertices)