Выпуклая оболочка, состоящая из макс.n баллов - PullRequest
Новая
       96

Выпуклая оболочка, состоящая из макс.n баллов

0 голосов
/ 08 февраля 2019

Учитывая набор двумерных точек X, я хотел бы найти выпуклую оболочку, состоящую из максимум n точек.Конечно, это не всегда возможно.Поэтому я ищу приблизительный выпуклый корпус, состоящий из макс.n точек, максимально покрывающих множество точек X.

Если сформулировать более формально, если F (H, X) возвращает количество точек X, покрытых выпуклой оболочкой H, где | H |это количество точек, из которых построен корпус, тогда я ищу следующее количество:

H_hat = argmax_H F (H, X), st | H | <= n </p>

ДругоеСпособом решения проблемы является задача нахождения многоугольника, состоящего из макс.n углов множества X так, чтобы оно максимально покрывало указанное множество X.

Я придумал следующий способ: 

X = getSet() \\ Get the set of 2D points
H = convexHull(X) \\ Compute the convex hull
while |H| > n do
    n_max = 0
    for h in H:
        H_ = remove(h,H) \\ Remove one point of the convex hull
        n_c = computeCoverage(X,H_) \\ Compute the coverage of the modified convex hull.
        \\ Save which point can be removed such that the coverage is reduced minimally.
        if n_c > n_max:
            n_max = n_c
            h_toremove = h
    \\ Remove the point and recompute the convex hull.
    X = remove(h,X)
    H = convexHull(X)

Однако это очень медленный способ.делать это.У меня большой набор точек и n (ограничение) мало.Это означает, что исходная выпуклая оболочка содержит много точек, поэтому цикл while повторяется в течение очень долгого времени.Есть ли более эффективный способ сделать это?Или есть еще какие-нибудь предложения для приблизительных решений?

Ответы [ 3 ]

0 голосов
/ 08 февраля 2019

Пара идей.

  1. Точки, которые мы исключаем при удалении вершины, лежат в треугольнике, образованном этой вершиной и двумя смежными с ней вершинами на выпуклой оболочке.Удаление любой другой вершины не влияет на набор потенциально исключаемых точек.Поэтому нам нужно только дважды пересчитать покрытие для каждой удаленной вершины.

  2. Говоря о пересчете покрытия, нам не обязательно смотреть на каждую точку.Эта идея не улучшает худший случай, но я думаю, что это должно стать большим улучшением на практике.Поддерживать индекс очков следующим образом.Выберите случайную вершину в качестве «корня» и сгруппируйте точки, по которым их содержит треугольник, образованный корнем и двумя другими вершинами (O (m log m) с хорошим алгоритмом).Всякий раз, когда мы удаляем некорневую вершину, мы объединяем и фильтруем два набора точек для треугольников, в которые входит удаленная вершина.Всякий раз, когда мы пересчитываем покрытие, мы можем сканировать только точки в двух соответствующих треугольниках.Если мы когда-либо удалим этот корень, выберите новый и переделайте индекс.Общая стоимость этого обслуживания будет O (m log ^ 2 m) в ожидании, где m - количество баллов.Однако сложнее оценить стоимость вычислительного покрытия.

  3. Если точки достаточно равномерно распределены внутри корпуса, возможно, используйте область в качестве прокси для покрытия.Храните вершины в приоритетной очереди, упорядоченной по области их треугольника, образованного их соседями (ухом).Всякий раз, когда мы удаляем точку, обновите область уха двух ее соседей.Это алгоритм O (m log m).

0 голосов
/ 22 февраля 2019

Следующее не решает вопрос так, как я его сформулировал, но оно решило проблему, которая породила вопрос.Поэтому я хотел добавить его на случай, если кто-нибудь еще столкнется с чем-то похожим.

Я исследовал два подхода:

1) Рассматривает выпуклую оболочку как многоугольник и применяю к ней алгоритм упрощения многоугольника.Конкретным алгоритмом, который я исследовал, был алгоритм Рамера-Дугласа-Пекера .

2). Примените алгоритм, описанный в вопросе, без пересчета выпуклой оболочки.

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

0 голосов
/ 08 февраля 2019

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

Это, похоже, немного связано с RANSAC, но для этой задачи у нас на самом деле нет понятия о том, чтовыбросы есть, поэтому мы не можем реально оценить соотношение выбросов.Следовательно, я не знаю, насколько хорошим будет приближение или сколько итераций вам нужно, чтобы получить разумный результат.Может быть, вы можете добавить некоторые эвристики вместо того, чтобы выбирать n точек чисто случайным образом, или у вас может быть порог того, сколько точек должно содержаться хотя бы в Q, и затем останавливаться, когда вы достигаете этого порога.

Редактировать

На самом деле, подумав об этом, вы можете использовать подход RANSAC: 

max_inliers = 0
best_Q = None
while(true):
    points = sample_n_points(X)
    Q = construct_convex_hull(points)
    n_inliers = count_inliers(Q, X)
    if n_inliers > max_inliers:
        max_inliers = n_inliers
        best_Q = Q
    if some_condition:
        break

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

...