Python实现Newton多边形：如何提取Scipy凸包的下边界？

核心逻辑 #

Scipy的ConvexHull返回的顶点是逆时针顺序排列的，Newton多边形需要的是从最左点到最右点的下凸包部分，可通过以下步骤精准分离：

• 定位凸包顶点中的最左点（x坐标最小）和最右点（x坐标最大）
• 基于这两个端点，提取凸包的两条候选路径（逆时针方向的两个分支）
• 通过斜率变化判断哪条路径是下凸包（下凸包的相邻点斜率单调非递减）

具体实现代码 #

import numpy as np
from scipy.spatial import ConvexHull

# 示例点集（模拟Newton多边形的输入点）
points = np.array([[0, 5], [1, 3], [2, 2], [3, 4], [4, 1], [5, 6]])
hull = ConvexHull(points)
hull_vertices = points[hull.vertices]

# 找到最左、最右点在凸包顶点中的索引
left_idx = np.argmin(hull_vertices[:, 0])
right_idx = np.argmax(hull_vertices[:, 0])

# 生成两条从左到右的候选路径
# 路径1：顺着逆时针顺序从左到右
if left_idx < right_idx:
    path1 = hull_vertices[left_idx:right_idx+1]
else:
    path1 = np.vstack([hull_vertices[left_idx:], hull_vertices[:right_idx+1]])

# 路径2：逆着逆时针顺序从左到右（即另一条分支）
if right_idx < left_idx:
    path2 = hull_vertices[right_idx:left_idx+1]
else:
    path2 = np.vstack([hull_vertices[right_idx:], hull_vertices[:left_idx+1]])
path2 = path2[::-1]  # 反转后变成从左到右的顺序

# 判断下凸包：下凸包的相邻点斜率单调非递减（允许浮点误差）
def is_lower_hull(path):
    x_diffs = np.diff(path[:, 0])
    y_diffs = np.diff(path[:, 1])
    slopes = y_diffs / x_diffs
    # 检查斜率的差分是否非负（下凸的特征）
    return np.all(np.diff(slopes) >= -1e-9)

# 确定最终的下凸包
lower_hull = path1 if is_lower_hull(path1) else path2

print("Newton多边形下边界点集：")
print(lower_hull)

原方法失效原因 #

直接截取到最右侧点前的条目不可靠，因为ConvexHull的顶点是逆时针排列的：当最左点不在顶点列表起始位置时，截取的路径可能是上凸包分支，而非需要的下凸包。必须通过定位左右端点+路径判断的方式，才能准确分离出下边界。

内容的提问来源于stack exchange，提问作者Ragon