2

我正在寻找一种有效的算法来处理 2D 动态直线凸包。

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

任何帮助将不胜感激，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
4

1 回答 1

0

为了实现正确的算法，您可能想看看这个。对于Rectilinear Convex hull的动态维护，最好寻找动态数据结构来维护Maxima of a Set，这是一个研究较多的课题。点集的最大元素集是 Rectilinear Convex Hull 的顶点集，所以这两个问题是等价的。

您可以在本文中找到每次操作花费 $O(\log n)$ 时间的算法。

于 2020-01-06T23:08:09.463 回答