[SOLVED] Lower convex hull

Lower convex hull

At the moment I am implementing an algorithm to compute the Newton-Polygon in Python.

In Scipy there is already a function to compute the convex hull of a given set of points, but I am not understanding how to take its lower boundary, does someone have an idea?

I already applied the ConvexHull function from Scipy and tried only taking the first few entries up until the point on the right, but it sometimes it resulted in the upper convex hull.

Solution

I would solve this by finding the extreme x values, and getting the points between the two. SciPy is guaranteed to emit coordinates for the convex hull of a set of 2D points in counter-clockwise order, so you can read from the position of the minimum x value to the position of the maximum x value, and get the lower convex hull.

Code:

def get_lower(polygon):
    minx = np.argmin(polygon[:, 0])
    maxx = np.argmax(polygon[:, 0]) + 1
    if minx >= maxx:
        lower_curve = np.concatenate([polygon[minx:], polygon[:maxx]])
    else:
        lower_curve = polygon[minx:maxx]
    return lower_curve

Example of how to use this:

import scipy.spatial
import matplotlib.pyplot as plt
import numpy as np

rng = np.random.default_rng()
points = rng.random((10, 2))
hull = scipy.spatial.ConvexHull(points)

plt.plot(points[:,0], points[:,1], 'o')
for simplex in hull.simplices:
    plt.plot(points[simplex, 0], points[simplex, 1], 'k-')

lower_curve = get_lower(points[hull.vertices])
plt.plot(lower_curve[:, 0], lower_curve[:, 1])