Поиск наибольшего подмножества точек, образующих выпуклый многоугольник

Ответ 1

Эта проблема уже опубликована в этих соревнованиях:

• Проблема SPOJ BOYSCOUT
• Проблема USACO DEC08 "Самый большой забор" (последняя проблема на странице)

И его решение (O (N ³)) можно найти на этой странице: "Забота о безопасности USACO DEC08" "Анализ" Брюса Мерри и Якова Штайнхардта.

Ниже приведена попытка объяснить этот алгоритм. Также вот моя реализация этого алгоритма в С++ 11. Этот код работает для N <= 250 и целочисленных координат в диапазоне 0.. 1023. Три точки не должны находиться в одной строке. Вот Python script, который генерирует тестовые данные, удовлетворяющие этим требованиям.

O (N ²) алгоритм для упрощенной задачи

Упрощенная задача: найдите наибольшее подмножество точек, которые образуют выпуклый многоугольник и содержат самую левую точку данного множества (или если есть несколько левых точек, этот многоугольник должен содержать самые верхние из них).

Чтобы решить эту проблему, мы могли бы подключить каждую пару точек по направленному отрезку линии, затем (неявно) рассматривать каждый сегмент как график node, как показано на диаграмме:

Здесь родительский node и соответствующий сегмент имеют синий цвет. Линейный сегмент, соответствующий его левому дочернему элементу (красный цвет), начинается в конце "родительского" сегмента, и это сегмент линии делает наименьший возможный левый поворот относительно направления "родительского" сегмента. Сегмент линии, соответствующий его правому дочернему элементу (зеленый цвет), начинается с начала "родительского" сегмента, а также является сегментом линии, который делает наименьший возможный левый поворот относительно направления "родительского" сегмента.

Любой сегмент, заканчивающийся в самой левой точке, соответствует "листу" node, то есть он не имеет дочерних узлов. Такая конструкция графика гарантирует отсутствие циклов, другими словами, этот граф является DAG.

Теперь, чтобы найти наибольшее выпуклое подмножество точек, достаточно найти самый длинный путь на этом графе. И самый длинный путь в DAG можно найти с помощью алгоритма динамического программирования во времени O (E), где E - количество ребер на графике. Поскольку каждый node имеет только 2 исходящих ребра, каждый из которых соответствует паре точек, эта проблема может быть решена в O (N ²) времени.

Все это можно реализовать, если мы предварительно обрабатываем входные данные, сортируя направленные сегменты линии, начиная с одной и той же точки по углу. Это позволяет выполнить обход глубины в графе. Мы должны запомнить самый длинный путь, начиная с каждого обработанного node, так что каждый край графика посещается не более одного раза, и мы имеем алгоритм времени O (E) = O (N ²) (игнорируя предварительную обработку время на данный момент). Требования к пространству также O (N ²), потому что нам нужно сохранять отсортированные направления для каждой пары точек, а запоминание использует одно значение за node (которое также является парой точек).

Вот реализация этого алгоритма динамического программирования на С++:

unsigned dpStep(ind_t i_left, ind_t from, ind_t to_ind)
{
    ind_t child = sorted[from][to_ind];

    while (child < i_left)
        child = sorted[from][++to_ind];

    if (child == i_left)
        return 1;

    if (auto v = memorize[from][child])
        return v;

    const auto x = max(dpStep(i_left, child, lefts[from][child]) + 1,
                       dpStep(i_left, from, static_cast<ind_t>(to_ind + 1)));

    memorize[from][child] = static_cast<ind_t>(x);
    return x;
}

Входные параметры - самая левая точка и пара точек, образующих текущий сегмент линии (где начальная точка сегмента задана непосредственно, а конечная точка задается как индекс в отсортированном по угловому массиву точек). Слово "левый" в этом фрагменте кода немного злоупотребляется: это означает как самую левую точку (i_left), так и предварительно обработанный массив, содержащий левые дочерние элементы для графика (lefts[][]).

O (N ³) алгоритм

Общая проблема (где крайняя левая точка не фиксирована) может быть решена следующим образом:

• Сортировка точек в левом и правом направлениях
• Предварительно обработать точки, чтобы получить два массива: (a) каждая точка, отсортированная по направлению относительно друг друга, и (b) позиция в первом массиве конца сегмента линии, делая наименьший возможный левый поворот относительно направления "родительский" "сегмент.
• Используйте каждую точку как самую левую точку и найдите самый длинный выпуклый многоугольник с "упрощенным" алгоритмом.
• Периодически обрезать все точки слева от "самой левой" точки из предварительно обработанных массивов.
• Возьмите самый длинный путь, найденный на шаге 3.

Этап 4 не является обязательным. Это не улучшает сложность времени O (N ³). Но это немного улучшает скорость алгоритма DP, исключая ненужные точки. В моих тестах это дает 33% ускорение скорости.

Существует несколько альтернатив для предварительной обработки. Мы могли вычислять каждый угол (с помощью atan2) и сортировать их, как это делается в примере кода Брюса Мерри и Якова Штайнхардта. Это самый простой способ, но atan2 может быть слишком дорогим, особенно для небольших наборов точек.

Или мы могли бы исключить atan2 и отсортировать тангенсы вместо углов, как это сделано в моей реализации. Это немного сложнее, но быстрее.

Оба этих варианта требуют O (N ² log N) времени (если мы не используем некоторую сортировку распределения). Третья альтернатива - использовать известные методы вычислительной геометрии (механизмы и двойственность) для получения предварительной обработки O (N ²). Но я не думаю, что он полезен для нашей проблемы: он, вероятно, слишком медленный для небольших наборов точек из-за большого постоянного коэффициента, так как для больших точечных множеств он может дать некоторое улучшение скорости, но слишком незначительный, поскольку шаг 3 значительно перевешивает шаг 2. Также его гораздо сложнее реализовать.

Некоторые другие результаты: я попытался реализовать итеративный DP вместо рекурсии; это заметно не изменило скорость. Также я попытался выполнить сразу два поиска DP, чередуя шаги каждого поиска (что-то похожее на волокна или HyperThreading, реализованное в программном обеспечении); это может помочь, поскольку DP состоит в основном из доступа к памяти с высокой задержкой и предотвращения полного использования пропускной способности процессора; результаты не очень впечатляют, только около 11% ускорения скорости, скорее всего, с реальной HyperThreading было бы намного быстрее.

Ответ 2

Я думаю, что придумал алгоритм для этого, расширив алгоритм Andrew для выпуклых оболочек.

def maximal_convex_hull(points):
    # Expects a list of 2D points in the format (x,y)


    points = sorted(set(points)) # Remove duplicates and sort
    if len(points) <= 1: # End early
        return points

    def cross(o, a, b): # Cross product
        return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])


    # Use a queue to extend Andrew algorithm in the following ways:
    # 1. Start a new convex hull for each successive point
    # 2. Keep track of the largest convex hull along the way
    Q = []
    size = 0
    maximal_hull = None
    for i,p in enumerate(points):
        remaining = len(points) - i + 1
        new_Q = []
        for lower, upper in Q: # Go through the queue
            # Build upper and lower hull similtanously, slightly less efficent
            while len(lower) >= 2 and cross(lower[-2], lower[-1], p) < 0:
                lower.pop()
            lower.append(p)
            while len(upper) >= 2 and cross(upper[-2], upper[-1], p) > 0:
                upper.pop()
            upper.append(p)

            new_size = len(lower) + len(upper)
            if new_size > size: # Check for a new highest maximal convex hull
                size = new_size
                maximal_hull = (lower, upper)


        # There is an odd bug? that when one or both if statements are removed
        #  xqg237.tsp (TSPLIB) gives slightly different solutions and is
        #   missing a number of points it should have.
        #  Seems like if the opposite should be true if anything since they
        #   were intended to be easy optimizations not required code.
            if remaining + new_size >= size: # Don't bother if not enough
                new_Q.append((lower, upper)) # Add an updated convex hulls
        if remaining > size: # Don't bother if not enough
            new_Q.append(([p], [p])) # Add a new convex hull
        Q = new_Q # Update to the new queue

    # Extract and merge the lower and upper to a maximium convex hull
    # Only one of the last points is ommited because it is repeated
    #    Asserts and related variables used for testing
    #    Could just have "return lower[:-1] + list(reversed(upper[:-1]))[:-1]"
    lower, upper = maximal_hull
    max_hull_set = set(lower) | set(lower) | set(upper)
    lower = lower
    upper = list(reversed(upper[:-1]))[:-1]
    max_convex_hull = lower + upper
    assert len(lower) + len(upper) == len(max_hull_set)
    assert max_hull_set == set(max_convex_hull)
    return max_convex_hull

Изменить: этот алгоритм неверен, но он послужил источником вдохновения для правильного алгоритма, и поэтому я оставляю его здесь.

Ответ 3

Это мой алгоритм динамического программирования O (N ^ 4) с идеей из Andrew Algorithm, опубликованной Nuclearman, я все еще ищу алгоритм O (N ^ 3)

upper_hull(most left point, previous point, current point)
{
    ret = 0
    if (current point != most left point)   /* at anytime we can decide to end the upper hull and build lower_hull from current point ending at most left point */
        ret = min(ret,lower_hull(most left point, -1, current point)) 
    for all point on the right of current point /* here we try all possible next point that still satisfy the condition of convex polygon */
        if (cross(previous point,current point,next point) >= 0) max(ret,1+upper_hull(most left point, current point, next point))
    return ret;
}

lower_hull(most left point, previous point, current point)
{
    if (current point == most left point) return 0;
    ret = -INF /* it might be impossible to build a convex hull here, so if it does it will return -infinity */
    for all point on the left of current point and not on the left of most left point
        if (cross(previous point,current point,next point) >= 0) max(ret,1+lower_hull(most left point, current point, next point))
    return ret;
}

Сначала отсортируйте точку, основанную на оси x, затем для привязки сортировки по оси y, затем попробуйте все точки как большинство левых точек для запуска upper_hull (p, -1, p), пожалуйста, скажите мне, есть ли какой-либо недостаток в этом алгоритме

Ответ 4

Вы можете использовать триангуляцию delaunay и удалить самый длинный ребро, а также вершину. Я использую аналогичный алгоритм для поиска вогнутого корпуса. Вы можете найти пример jan на основе данных о населении @http://www.phpdevpad.de/geofence. Я также написал php-класс concave-hull @phpclasses.org.