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

正しいアルゴリズムを実装するには、これを参照してください。直線凸包の動的維持については、セットの最大値を維持するための動的データ構造を探す方がよいでしょう。これは、より研究されたトピックです。点集合の最大要素の集合は、直凸包の頂点の集合であるため、両方の問題は互いに同等です。

この論文では、操作ごとに $O(\log n)$ 時間かかるアルゴリズムを見つけることができます。

于 2020-01-06T23:08:09.463 に答える