动态和/或静态直线/正交/XY凸形Hu

Question

我在寻找一个处理2D动态rectilinear convex hulls的有效算法。在

我已经编写了一个静态算法，但虽然它在大多数情况下都能工作，但根本不起作用，所以我也在寻找关于静态直线凸壳的资源。维基百科有一些关于算法的研究论文，但我无法访问它们。因此，寻找其他来源或帮助编写代码。在

任何帮助都将不胜感激，一个Python算法，非常感谢。在

当前静态代码：

def stepped_hull(points, is_sorted=False, return_sections=False):
    # May be equivalent to the orthogonal convex hull

    if not is_sorted:
        points = sorted(set(points))

    if len(points) <= 1:
        return points

    # Get extreme y points
    min_y = min(points, lambda p:p[1])
    max_y = max(points, lambda p:p[1])

    points_reversed = list(reversed(points))

    # Create upper section
    upper_left = build_stepped_upper(points, max_y)
    upper_right = build_stepped_upper(points_reversed, max_y)

    # Create lower section
    lower_left = build_stepped_lower(points, min_y)
    lower_right = build_stepped_lower(points_reversed, min_y)

    # Correct the ordering
    lower_right.reverse()
    upper_left.reverse()

    if return_sections:
        return lower_left, lower_right, upper_right, upper_left

    # Remove duplicate points
    hull = OrderedSet(lower_left + lower_right + upper_right + upper_left)
    return list(hull)

def build_stepped_upper(points, max_y):
    # Steps towards the highest y point

    section = [points[0]]

    if max_y != points[0]:
        for point in points:
            if point[1] >= section[-1][1]:
                section.append(point)

            if max_y == point:
                break
    return section

def build_stepped_lower(points, min_y):
    # Steps towards the lowest y point

    section = [points[0]]

    if min_y != points[0]:
        for point in points:
            if point[1] <= section[-1][1]:
                section.append(point)

            if min_y == point:
                break
    return section

Answer 1

为了实现正确的算法，您可能需要看看this。对于直线凸壳的动态维护，最好寻找动态数据结构来保持集合的最大值，这是一个研究较多的课题。点集的最大元素集是直线凸壳的顶点集，因此这两个问题是等价的。在

您可以在this paper中找到一种算法，该算法每次操作花费$O（\logn）$时间。在