Реализация вопросов брака до завоевания алгоритма выпуклой оболочки
Я заинтересован в реализации и изучении Алгоритм Киркпатрика – Зайделя.
Это подход «разделяй и властвуй» для нахождения выпуклой оболочки некоторого набора точек. Я забочусь только о двухмерном случае.
Я нашел интересный материал об этой проблеме Вот:
Основные шаги алгоритма следующие:
INPUT: A set P of points on the plane.
OUTPUT: The set of points that define the convex hull.
1. Calculate median x-coordinate M of P.
2. Find the bridge segment that crosses the line x = M using the
Prune and Search Technique.
3. Trim the set based on this segment
4. Split P to sets PL, PR and recursively apply the above steps to find
the remaining segments
5. The above steps must be run twice, once for the upper hall and once
for the lower hall. Once you find both, you have the convex hull.
(1) можно найти в O (N). Это очень тривиально, особенно в C ++, вы можете просто использовать nth_element с указанным компаратором
(3) также можно найти в O (N). Если найденный вами сегмент определяется точками p1 а также p2 тогда вам просто нужно игнорировать каждую точку p где p1.x <= p.x <= p2.x
(4) это просто прямой результат (3)
(5) два рекурсивных вызова на двух подмножествах, которые вы только что нашли
Для достижения O(nlogn) сложность от этого разделяй и властвуй алгоритм. Нам нужен шаг (2) также принять O(n),
Согласно раздаточному материалу, этот шаг можно решить с помощью линейного программирования, и, поскольку мы работаем над плоскостью, можно достичь линейного времени.
Теперь раздаточный материал идет, чтобы объяснить часть (2) более подробно, вот шаги.
Я понимаю каждый шаг, кроме (3) и (4).
(3). Что такое b? Я думаю, это не имеет значения. Так как вы нашли склон m и затем перейдите к поиску линии поддержки для набора P. B — это то, что вы ищете.
(4). что такое опорная линия для множества P и как ее найти эффективно?
Решение
Учитывая наклон и точку, существует уникальная линия с этим наклоном через эту точку. Пусть наклон будет m, а точка будет (px, py). Затем решите для b в уравнении py = m px + b (то есть b = py — m px); линия имеет уравнение y = m x + b. То, что вы должны сделать на шагах (3) и (4), это вычислить b для каждой точки и взять p_t как точку, имеющую максимум b (разрывая связи по максимальной x-координате). Эта линия является опорной прямой выпуклой оболочки, так как она содержит одну из вершин и имеет все вершины (ненадлежащий образом) к одной стороне (в данном случае, не выше этого).
Постскриптум Если вам интересно из-за времени выполнения O (n log h), не теряйте надежды; постоянный фактор выглядит довольно плохо.
Другие решения