下凸包

Question

目前我正在Python中实现一种算法来计算[牛顿多边形]。(https://en.wikipedia.org/wiki/Newton_polygon)

在Scipy中已经有一个函数来计算给定点集的凸包，但我不明白如何取其下边界，有人有想法吗？

我已经应用了 Scipy 中的凸包函数，并尝试只获取前几个条目，直到右侧的点，但有时会导致上凸包。

Answer 1

我会通过找到极值 x 并获取两者之间的点来解决这个问题。 SciPy 保证按逆时针顺序发出一组 2D 点的凸包的坐标，因此您可以从最小 x 值的位置读取到最大 x 值的位置，并获得下凸包。

代码：

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

如何使用此示例：

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])