Алгоритм Quickhull для нахождения выпуклой оболочки

Алгоритм Quickhull для нахождения выпуклой оболочки

968

Как гласит определение, выпуклая оболочка некого множества — это меньшее выпуклое множество , содержащее в для себя это множество. Выпуклой оболочкой конечного множества попарно разных точек является многогранник.
Для реализации одномерного варианта метода Quickhull годится функция std::minmax_element. Но, для варианта случайной размерности слету находится только одна тяжёловесная реализация с веб-сайта qhull.org. В сети можно отыскать множество реализаций метода Quickhull для плоского варианта.
В скобках рядом с определениями я буду давать перевод на британский (в стиле Туґбо, уж извините). Это может быть полезно для тех, кто ещё не знаком с определениями и будет читать англоязычные тексты по ссылкам, или решит разобраться с текстами начального кода.
Но раз вы решите изолировать код, относящийся лишь только к одному методу Quickhull, то столкнётесь со сложностями. Всего порядка 750 строк. Упомянутая выше «каноническая» реализация написана на C (есть C++ биндинги), употребляется издавна и обширно (в составе пакетов GNU Octave и MATLAB) и, следовательно, отлично проверена. Для простых применений хотелось бы иметь возможность обходится чем-то наиболее малогабаритным. Незначительно постаравшись, я написал свою реализацию (https://bitbucket.org/tomilov/quickhull/): это единственный класс, без зависимостей.

Геометрические понятия.
Нужно несколько упорядочить познания: ввести некие новейшие определения и прояснить дела меж ними. Начиная работать с многомерными сущностями, понимаешь, что справедливы какие-то аналогии с обычными двухмерными и трёхмерными объектами.
Для начала я дам геометрические определения (не чрезвычайно строгие). Далее по тексту будут приведены описания соответствующих структур данных, комфортных для того, чтоб хранить данные и оперировать с ними довольно отлично. Для программера геометрические объекты — это до этого всего структуры данных.
Обозначим размерность места как .

affinely independent) точкой. vertex, мн. vertices). О аффинной независимости объясню дальше. Симплекс (англ. simplex) задаётся аффинно независящей (англ. ед. Эти точки именуются вершинами (англ.
Многогранник (син. политоп, многогранник, полиэдр, англ. simplicial polytope) — простой вариант -мерного тела, многогранники с наименьшим числом вершин непременно будут иметь нулевой -мерный размер. polytope, polyhedron) определяется как минимум аффинно независящей точкой (вершиной); симплекс (англ.
Параллелотоп (англ. parallelotope) — обобщение плоского параллелограмма и большого параллелепипеда. Для симплекса можно выстроить соответствующих параллелотопов (все они будут иметь однообразный размер, равный размерам симплекса), взяв в качестве образующих (векторов) параллелотопа вектора, выходящие из одной фиксированной вершины в другие вершины.
Понятие выпуклого многогранника (англ. convex polytope, convex polyhedron) я тут приводить не буду, сгодится ваше интуитивное представление о нём. Симплекс, как личный вариант многогранника, постоянно является выпуклым.
Понятие плоскости я также приводить не буду. Лишь замечу, что она имеет на единицу наименьшую размерность, чем место, в которое вложена.
Симплициальная грань (англ. Почти все утверждения в предстоящем будут справедливы лишь для невырожденных (все точки попарно различны) случаев симплициальных геометрических объектов. simplicial facet) определяется аффинно независящими точками (вершинами). Дальше речь будет идти лишь о симплициальных объектах (не считая выпуклого многогранника), так что определение «симплициальный» я буду опускать.
ridge) определяется как пересечение 2-ух граней и имеет вершину. Две грани могут иметь лишь одно общее ребро. Одна грань, таковым образом, может иметь соседей через рёбра. Ребро (англ.
Грань может иметь хоть какое количество примыкающих граней через пик, отсюда можно сделать вывод, что хранить граф смежности граней через пики накладно и по памяти и по затратам на поддержку актуальности структур данных при каких-или преобразованиях. Пик (англ. Тут интуитивная аналогия с трёхмерным местом может поплыть, так как понятие пика и вершины не совпадают, но таковыми объектами мы не будем оперировать. peak) определяется точками.

Дам ссылку на неплохой ресурс, где логически обосновывается, что в -мерном пространстве видимыми либо наблюдаемыми объектами могут являться лишь только -мерные объекты, то есть границы (англ. straight line) — это постоянно одномерная суть. Точку (вершину) можно в данной градации считать нуль-мерной. Британский термин facet — это конкретно наблюдаемая грань. Ровная (англ. на британском называются face. Грань многогранника, её границы, границы её границ и т.д. boundaries) -мерных объектов.
Определение линейной независимости векторов для вас скорей всего уже знакомо. Аналогия справедлива для остальных размерностей. Раз все точки лежали в одной плоскости, то плоскость сдвигается таковым образом, что начинает проходить через начало координат. origin). Таковым образом мы как бы назначим эту точку началом координат (англ. Имея дело с неким набором из точек, мы можем перейти к рассмотрению соответствующего набора из векторов, вычтя одну из точек из всех остальных. Аффинная независимость точек выполняется, когда выполняется линейная независимость -го соответствующего вектора. Таковым образом в -мерном пространстве нельзя выбрать больше точки так, чтоб все они были аффинно независимы. Объясню это: в трёхмерном пространстве треугольник (грань трёхмерного симплекса — тетраэдра) задан 3-мя точками (не лежащими на одной прямой, естественно); через эти три точки проходит единственная плоскость; неважно какая точка данной плоскости, добавленная ко множеству из 3-х вершин треугольника превратит можнество 3-х аффинно независящих точек в множество 4 аффинно зависимых.
Не считая всего остального нужно ввести понятие гиперобъёма (англ. hypervolume).

Для симплекса, образованного попарно разными точками (порядок перечисления точек важен), гиперобъём вычислить можно так: ограничены в соответствующем подпространстве. Понятие можно обобщить, назвав D-мерным объёмом либо D-гиперобъёмом. «Количество места», которое таковой объект занимает, можно измерить/найти/задать. Для одномерной прямой мера именуется длиной; для двумерной плоскости, мера именуется площадью; для трёхмерного тела — размер. Гиперобъём.Хоть какой рассмотреный объект из ряда симплекс, грань, ребро, пик и т.д.

раз мы транспонируем все матрицы, то на итог и выводы это не воздействует). Подобные формулы и рассуждения можно привести и для векторов-столбцов (т.е. Тут мы выписали координаты векторов в строчки.
Интересующимся основаниями, лежащими в базе этого утверждения, рекомендую прочесть про определитель матрицы Грама и о его геометрической интерпретации. Соответственно сам детерминант — это гиперобъём параллелотопа. Делитель детерминанта в формуле выше — это количество симплексов (все они имеют однообразный размер), на который можно разбить параллелотоп , построенный на векторах.
Для тетраэдра символ будет зависеть от того, в каком порядке (по часовой стрелке либо против) 1-ые 3 точки будут перечисляться при взоре на их из крайней. Следует отметить, что данная мера для «объёмных» объектов будет иметь ненулевое значение, а также может быть как положительной, так и отрицательной величиной. Таковым образом, в предстоящем, при задании геометрических объектов, мы должны принять, что порядок перечисления точек должен быть фиксированным. Осознать смысл знака несложно из последующих суждений: при обмене местами 2-ух точек симплекса мы получаем смену знака детерминанта; порядок точек — это «лево- и право- ориентированность» симплекса. На плоскости это нетрудно для себя представить: раз стороны треугольника перечислены против часовой стрелки , то определитель положителен , по другому — отрицателен.
Множитель перед детерминантом мы можем опустить, так как в методе будет употребляться только информация о знаке величины нацеленного гиперобъёма.
Нетрудно проверить соответствие приведённых выше рассуждений о аффинно зависимых точках и линейно зависимых векторах, соответственных им. Детерминант равен нулю, раз хотя бы две строчки линейно зависимы (помним, что точки попарно различны, то есть ни одна строчка не нулевая).
На абсолютное значение детерминанта не будет влиять то, какую конкретно точку вычитаем при переходе к векторам, — лишь на символ. Следует вычитать постоянно последнюю точку из первых, по другому для идиентично нацеленных подобных объектов, используемых в предстоящем, символ меры будет различным в чётных и нечётных размерностях.
Раз мы сконструируем матрицу так же, как это показано выше, то она будет прямоугольная. Оказывается формулу можно обобщить (это обобщение соединено с формулой Бине-Коши), используя всё ту же матрицу составленную из векторов-строк: Что же делать с мерой для объектов, вложенных в место очень большой размерности, к примеру, с гранями? Детерминант от таковой матрицы взять не получится.

Для аффинно зависимых точек матрица получится сингулярной (т.е. Для аффинно независящих попарно разных точек матрица под детерминантом постоянно выходит квадратной положительно определённой, а сам детерминант таковой матрицы — число постоянно положительное. её определитель равен нулю). Ясно, что мера постоянно неотрицательная и инфы о ориентации мы не имеем.
модуля, который мы можем опустить, с целью получить доп информацию о относительной ориентации точек в пространстве. С одной стороны детерминант произведения квадратных матриц равен произведению детерминантов, с иной — детерминант транспонированной квадратной матрицы совпадает с детерминантом начальной, таковым образом крайняя формула сводится к формуле для точки, за исключением корня из квадрата, т.е.

Метод.
«Каноническая» реализация на C от создателей размещается на уже упомянутом веб-сайте http://qhull.org/, репозиторий с C++ интерфейсом https://gitorious.org/qhull/qhull. ACM Transactions on Mathematical Software 22 (4): 469–483. Bradford; Dobkin, David P.; Huhdanpaa, Hannu (1 December 1996). Процитирую метод из первоисточника: «The quickhull algorithm for convex hulls». Сам метод Quickhull для варианта случайной размерности был предложен в труде Barber, C.
create a simplex of d + 1 points
for each facet F
for each unassigned point p
if p is above F
assign p to F`s outside set
for each facet F with a non-empty outside set
select the furthest point p of F`s outside set
initialize the visible set V to F
for all unvisited neighbours N of facets in V
if p is above N
add N to V
the set of horizon ridges H is the boundary of V
for each ridge R in H
create a new facet from R and P
link the new facet to its neighbours
for each new facet F’
for each unassigned point q in an outside set of a facet in V
if q is above F’
assign q to F’`s outside set
delete the facets in V

Выпуклая оболочка представляет собой перечень граней.

Стартовый симплекс.
Я буду именовать его временный многогранник. Основное требование на этом шаге — чтоб наш симплекс по способности не вышел «узким» (англ. Как видно, мы должны начать с некого стартового симплекса. В уникальной реализации употребляются точки с наивысшими и минимальными значениями координат (разумеется они же войдут во множество вершин выпуклой оболочки). Начав со стартового симплекса, на каждом следующем шаге мы будем получать всё больший и больший многогранник, постоянным свойством которого постоянно будет его неровность. narrow). Это принципиально в случае, раз употребляется математика с плавающей точкой (англ. Для этого можно выбрать любые аффинно независящие точки, но лучше применять какую-нибудь дешевенькую эвристику. floating-point arithmetic).

«Дальше» — в неком определённом смысле, который проясню дальше. Эвристика поиска вершин для стартового симплекса.Моя эвристика базирована на поочередном выборе точек таковым образом, чтоб любая последующая находилась от всех прошлых как можно далее.
Сначала берём первую (либо всякую другую) точку из и перемещаем её в. не пустое), запомним её, потом проведём из неё вектора во все другие точки из (получив при этом , которое будет содержать меньше на один элемент, чем ) и во все точки из (получив ). Для этого ищем соответственный точке вектор из , модуль проекции которого на ортогональное дополнение векторного подпространства максимален. Первую же точку из перемещаем обратно в (она была выбрана без какого-или аспекта). Ведётся два перечня точек: начальный перечень (вначале в нём находятся все точки со входа метода) и перечень точек симплекса (вначале — пустой). Для этого мы на уровне мыслей на каждом шагу данного метода избираем всякую точку из множества (д.б. вектора в получаются линейно независящими (по построению), то — базис этого векторного места. На каждом из последующих шагов ищем точку из , которая очень далека от аффинного места с базисом и перемещаем её из в. Дальше ищем вектор из с самым огромным модулем и перемещаем соответственную точку из в. В соответствие множествам и можно поставить множества векторов и. Тут — линейная оболочка , то есть — векторное место, т.к.
Формула расстояния от до :

Так как вектор конкретно раскладывается в сумму проекций на хоть какое подпространство и на ортогональное дополнение этого подпространства, то:

Имея ортонормированный базис векторного подпространства , мы можем вычислить модуль проекции на это подпространство:

Координаты векторов мы можем получить, произведя QR-разложение прямоугольной матрицы (к примеру, способом Хаусхолдера), составленной из (координат) столбцов-векторов из множества. Столбцы Q — это координаты векторов , образующих ортонормированный базис векторного места . В итоге мы получим ортогональную (прямоугольную) матрицу Q () и верхнетреугольную R (не употребляется).
Опосля завершения метода в находится точка.

Неважно какая точка попадает лишь в один перечень наружных точек. Из этого характеристики следует тот факт, что раз точка не попала ни в один из списков наружных точек граней выпуклой оболочки, то она достоверно находится снутри неё. В предстоящем в методе пригодится информация о том, какая из точек, содержащихся в перечне наружных точек и более удалена от плоскости грани, потому, добавляя точки в перечень наружных точек, нужно сохранять информацию о том, которая из их самая дальняя. Дальше мы должны распределить оставшиеся точки в так именуемые списки наружных точек (англ. outside sets) граней — это такие списки точек, которые ведутся для каждой грани и в которые попадают ещё не рассмотренные (дальше — неназначенные, англ. unassigned) точки, находящиеся относительно плоскости грани по другую сторону, ежели внутренность симплекса (либо временного многогранника в предстоящем). Тут мы пользуемся тем свойством выпуклого многогранника (и симплекса в частности), что весь он лежит полностью лишь в одном из 2-ух полупространств, получаемых при разбиении всего места плоскостью каждой грани. На асимптотическую сложность не влияет то как конкретно распределяются точки по перечням.
На данном шаге мне нужно сделать отступление и поведать о том, как задать грань, как вычислять расстояние до неё, как найти ориентацию точки относительно грани.

К примеру, совершив два обмена в всех 2-ух не непременно разных парах попарно разных точек, мы получим точно так же направленную грань в том смысле, что в всех операциях в предстоящем (а это традиционно будет взятие детерминантов от матриц, сформированных из констант и координат вершин) такие парные перестановки не влияют на итог. При этом упорядоченность нам нужна не полностью строгая. Двум вероятным ориентациям соответствует два вероятных направления нормали к плоскости (грани). Грань. По приведённым выше суждениям хранить мы эти точки будем упорядоченным образом. Направленное расстояние от плоскости грани до точки.Для задания грани нам нужно иметь точек — вершин грани.
Тут мы можем вспомнить школьную формулу, допускающую обобщение на вариант случайной размерности, а конкретно: «площадь треугольника равна половине произведения основания, на высоту» либо «объём пирамиды равен одной третьей от произведения площади основания на высоту». Меру тела и грани мы высилять умеем, следовательно мы можем выразить высоту (одномерную длину): directed distance) до точки. Лишь только единожды — в самом начале — нам пригодится вычислить значение гиперобъёма стартового симплекса чтоб по знаку найти его ориентацию. Все дальнейшие операции касательно граней будут заключаться лишь только в вычислении нацеленного расстояния (англ.

Не берусь оценивать как сложность вычисления детерминанта влияет на конечную сложность всего метода, но экспериментируя я заключил, что в худшем случае (к примеру, вариант точек расположенных на сфере (англ. cospherical points)) даже при малых размерностях места () вычисление детерминантов для оценки расстояния очень вычислительно затратно. LUP-decomposition), то можно достигнуть трудности и солидной численной стойкости (англ. В методе нам пригодится вычислять направленное расстояние от фиксированной плоскости (грани) до точек, которых может быть много. numerical stability). — тоже константа. Таковым образом мы можем разглядывать лишь относительные величины гиперобъёмов симплексов (а поточнее, соответствующих параллелотопов) построенных из грани и точки. Раз определитель считать не самым медленным методом (по определению за ) и не самым скорым (), а методом через LUP-разложение (англ. В этом случае мы можем увидеть, что в знаменателе стоит положительная константа. От положения точки («над» либо «под») зависит только гиперобъём в числителе.
offset): Иной подход — это внедрение нормированного уравнения плоскости (англ. hyperplane equation). Это уравнение первой степени, которое связывает координаты точки плоскости, координаты нормированного вектора нормали ( — ненормированная нормаль) к плоскости (англ. normalized normal vector) и её смещения от начала координат (англ.

Координаты нормали :

Величина — смещение плоскости от начала координат:

Невязка , получаемая при подстановке случайной точки в нормированное уравнения плоскости, — это как раз направленное расстояние от плоскости до точки.

Раз точка лежит по ту же сторону от плоскости, куда ориентирована нормаль, то величина будет положительной, по другому — отрицательной.
Отличие матрицы под детерминантом в выражениях для и лишь только в подмене -ой координаты (столбца) на единицы.
Вычисление расстояния сводится к вызову функции std::inner_product, в которую передаются итераторы начала и конца массива координат нормированной нормали, начало массива координат точки, а крайним параметром — значение. Так как везде дальше в методе употребляются только относительные значения расстояний, то, вообщем говоря, можно и не нормировать, но это достаточно доступная операция, а правильное значение расстояния может пригодиться и при работе с выпуклой оболочкой опосля действий метода. Таковым образом для плоскости грани нужно вычислить и хранить число: координат нормированной нормали и смещение от начала координат.

В случае, раз расстояние отрицательное они меняют символ у координат нормали к гиперплоскости и у её смещения от начала координат. Внутренней точкой для выпуклого многогранника будет среднее арифметическое хотя бы его вершин (т.н. Сейчас обрисовывать плоскость грани мы умеем, но осталась одна неясность: как же выбрать порядок перечисления точек в перечнях вершин граней стартового симплекса? центр масс, раз взять все вершины). Или задают значение флага, сигнализирующее о том, что грань перевёрнута (англ. Создатели не хранят перечень вершин упорядоченным. Они поступают по другому. То есть вычисляют направленное расстояние. inner point) относительно данной плоскости. Задав уравнение плоскости для случайного, но фиксированного порядка вершин, они узнают ориентацию какой-или внутренней точки (англ. flipped).

Для стартового симплекса я вычисляю его гиперобъём, при этом строчки матрицы я формирую из координат векторов, проведённых из крайней вершины () в 1-ые (). Раз таковым образом вычесленный гиперобъём отрицателен, то точка находится «под» гранью с вершинами и порядок точек верный, по другому мы должны поменять любые две точки местами (к примеру первую и последнюю). Переориентация граней стартового симплекса.В моей реализации на любом шаге метода грани временного многогранника (а равно и стартового симплекса и финальной выпуклой оболочки) нацелены вовне. В этом случае необходимо поменять символ координат нормали и смещения. Так как нужно произвести обмен 2-ух непременно разных точек, то таковой приём не сработает для варианта (ограничение на как раз отсюда).
1-ая грань и последующая грань с вершинами имеют общее ребро. Следовательно решение о том, обменивать ли местами две вершины обязано быть противоположным аналогичному решению для первой грани. И так дальше (решение о смене знака/порядка каждый раз изменяется). Раз на уровне мыслей посмотреть на симплекс снаружи и обойти поначалу первую грань в порядке возрастания номеров точек, а потом так же вторую, то общее ребро при этом будет пройдено в противоположных направлениях.
Следует отметить, что в массиве точек, с целью сформировать наборы из вершин для граней симплекса, мы движемся из конца в начало, исключая еще одну точку и начиная конкретно с крайней точки. Это агрессивно соединено с тем, что мы решили вычитать конкретно последнюю точку из первых при вычислении гиперобъёма симплекса.

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

Основной цикл.
В главном цикле этот временный многоугольник достраивается, «захватывая» всё больше и больше места, а совместно с ним и точки начального множества, пока не настанет таковой момент, когда вовне многогранника не остается ни одной точки. А конкретно, то, как он устроен в моей реализации. Дальше обрисую этот процесс наиболее тщательно. Сейчас есть временный многоугольник с которым можно работать в главном цикле.
На каждой итерации посреди граней с непустыми перечнями наружных точек выбирается самая наилучшая грань (англ. best facet); наилучшая в том смысле, что самая дальняя точка из перечня наружных точек находится далее от грани, чем у остальных граней. Основной цикл — это цикл по граням. Цикл завершается, когда граней с непустыми перечнями наружных точек не осталось.
Другие точки передвигаются в отдельный временный перечень неназначенных точек. Любая граничная видимая грань «разбирается» (дальше пригодится её перечень примыкающих граней и перечень вершин) и удаляется. horizon ridge), кстати, является частью горизонта той части поверхности временного многогранника, которая видна из точки. Та единственная вершина граничной видимой грани, которая не пренадлежит этому ребру, заменяется на точку в перечне вершин новейшей грани, другие же вершины — те же что и в (упорядоченном) перечне вершин граничной видимой грани и стоят на тех же местах. При этом просматривается перечень её примыкающих граней и для каждой грани из этого перечня, являющейся невидимой, ищется общее ребро с данной граничной видимой гранью. Уравнения гиперплоскостей для этих граней может быть рассчитать сходу опосля того, как мы имеем списки вершин для их. Разумеется, что другие примыкающие грани нужно находить посреди других новейших граней. В перечень вершин новейшей грани выписываются вершины общие для невидимой и граничной видимой граней (т.е. Из перечня наружных точек извлекается самая дальняя точка (англ. Опосля того, как все граничные видимые грани обработаны мы имеем перечень новейших граней. В теле главенствующего цикла избранная грань удаляется как заранее не являющаяся гранью выпуклой оболочки. вершины общего ребра), при этом конкретно в том порядке, в котором они записаны в перечне вершин граничной видимой грани. visited) граней и тестируется на видимость (англ. furthest point) — она наверное является вершиной выпуклой оболочки. Сейчас удаляются все грани из перечня на удаление. Раз грань невидимая из точки , то её примыкающие грани дальше не обходятся, по другому обходятся. Дальше по перечням примыкающих граней, начиная со перечня грани , обходится граф смежности граней временного многогранника и любая грань добавляется в перечень уже посещённых (англ. visibility) из точки. Опосля обхода графа смежности граней перечень граничных видимых граней и перечень граней на удаление в сумме содержат все видимые из точки грани. Так делать безопасно, поэтому что даже в случае раз соседняя грань является граничной видимой гранью, из перечня её примыкающих граней в предстоящем употребляется лишь информация о соседстве с невидимыми из точки гранями. Но раз все примыкающие грани являются видимыми, то таковая грань добавляется в перечень граней на удаление. Ребро (англ. Но предварительно она «разбирается на составляющие». before-the-horizon как противоположность over-the-horizon — «загоризонтный»). Для каждой граничной видимой грани создаются новейшие грани (от одной до штук), которые добавляются в перечень новейших граней. Раз у очередной видимой грани посреди примыкающих граней есть невидимые из точки , то она попадает в перечень граничных видимых граней (англ. Следом за списокм граней на удаление просматривается перечень граничных видимых граней. Таковым образом построенный перечень вершин новейшей грани гарантирует её правильную ориентацию, то есть при расчёте её нормированного уравнения плоскости нормаль будет ориентирована вовне временного многогранника и значение смещения получит верный символ. При этом любая удаляемая грань не удаляется из списков примыкающих граней у собственных соседей. Так же, при разработке новейших граней, в их списки сосдених граней можно добавить по одной грани, а конкретно — соответственную невидимую грань, которая была примыкающей для граничной видимой грани при формировании перечня вершин новейшей грани.
Как оказалось (при семплировании профайлером из Google Performance Tools), больше всего времени в случае огромных размерностей и/либо нехороших входных данных (т.е. В моей реализации вначале метод был устроен максимально просто: перебирались все вероятные пары (два вложенных цикла) граней из перечня новейших граней и производились сопоставления упорядоченных (по номеру из входного перечня точек) списков вершин с одним несовпадением (измененный метод std::set_difference либо std::set_symmetric_difference). В ней для каждого ребра (2-ух граней) хранится отдельная структура данных (перечень вершин ребра и информация о гранях «над» и «под» ребром), любая грань содержит перечень собственных рёбер. В уникальной реализации qhull употребляются как раз хеши (не LHS). когда крупная часть точек является вершинами выпуклой оболочки) метод проводит в поиске примыкающих граней для новейших граней. Этот метод я не использую, так как ни в обычной библиотеке, ни в STL нет такового средства, как hash combiner. то есть савнений хешей. Но в предстоящем мне удалось выиграть пару (двоичных =) порядков в скорости поиска примыкающих использовав упорядоченные ассоциативные массивы (std::set) в этом узеньком месте. Для определения соседства граней (посреди граней из перечня новейших граней) для всех рёбер граней создаётся ассоциативный неупорядоченный массив хешей массивов их вершин (с одним пропуском (англ. Самому специализировать без теоретико-информационного обоснования правильности std::hash для std::vector< std::size_t > мне не хотелось. Конкретно потому я употреблял ассоциативный упорядоченный контейнер рёбер для поиска примыкающих граней. Вообщем, есть целая область познаний, которая связана с данной задачей (определения соседей) — это Locality-sensitive_hashing. skip) и одной отброшеной вершиной ()). В итоге (судя по всему) моя реализация метода проигрывает qhull в скорости асимптотически в от до раз (для различного рода входных данных). Раз происходит коллизия (и следующее полное совпадение списков) хешей, то (разумеется) такие две грани имеют общее ребро (хеш, кстати, при этом можно удалить для уменьшения хеш-таблицы) и каждую из их можно добавить в перечень примыкающих граней иной. То есть сравнений, где — количество новейших граней.

Сравнительное тестирование.
Команда rbox t n D10 30 s > /tmp/quickhull.txt делает файл с координатами 30 точек на десятимерной сфере. Прототипом служит «каноническая» реализация метода Quickhull qhull, установленная через менеджер пакетов (в Ubuntu 14.04 LTS). Команда rbox t n D4 30000 s > /tmp/qhuckhull.txt делает файл с координатами 30000 точек на четырёхмерной сфере. Количество памяти, которое затрачивает программа можно поглядеть в выводе утилиты /usr/bin/time с ключём -v. Для генерации входных данных из этого же пакета qhull-bin использовалась утилита rbox. Таковым образом в выводе /usr/bin/time -v bin/quickhull /tmp/quickhull.txt | head -7 можно выяснить потребление и памяти и процессорного времени (очищенного от времени на чтение файлов и вывод на терминал) для моей реализации, а в выводе /usr/bin/time -v qconvex s Qt Tv TI /tmp/quickhull.txt — для «канонической» реализации qhull.
Где-то в коммитах он есть. Но для отладки (в режимах 2-ух- и трёхмерном) на неком шаге я реализовывал пошагово (через команду pause) анимированный вывод в формате gnuplot. Вывод программы — это выпуклая оболочка и пронумерованное множество входных точек выставленные в формате gnuplot. Правильность собственной реализации я определяю по совпадению количества граней выпуклых оболочек.
unit cube), снутри параллелотопа, в пределах обычного единичного симплекса (англ. Для генерации координат, умеренно распределённых в пределах случайного сиплекса (вложимого в место), я отыскал численно стабильный метод в вебе (через распределение Дирихле), а такеже выдумал собственный метод, который не различается таковым свойством. ball), на поверхности единичного «ромбовидного» многогранника (англ. cone), или цилиндра (англ. В итоге избрал 1-ый. unit simplex), а так же проецирует множество точек в размер конуса (англ. randombox думала как утилита, которая генерирует умеренно распределённые в пространстве (англ. randombox может генерировать наборы точек, ограниченные симплексом (хоть какой размерности, которая может быть вложена в место с точками), на единичной сфере (англ. cylinder). unit diamond), снутри единичного куба (англ. unit sphere), в шаре (англ. Не считая того, как-то было начал писать (но не окончил) утилиту randombox — аналог rbox. uniform spatial distribution) точки, в отличие от rbox, которая генерирует точки распределённые не умеренно.
bounding box). Ключ t задаёт внедрение текущего времени (в секундах) в качестве исходного значения ГПСЧ. rbox n D3 40 t сгенерирует 40 точек снутри ограничивающего куба (англ. helix): rbox n D3 50 l. Прекрасно смотрится выпуклая оболочка спирали (англ. Чтоб получить точки на сфере, нужно добавить ключ s. В случае одновременного расположения огромного количества точек, компланарных граням, огромное значение для правильности результатов начинает играться константа eps, которая задаётся при конструировании объекта метода. Для того, чтоб «пощупать» выпуклые оболочки взором, используя gnuplot, из корня проекта введите команду rbox n D3 40 t | bin/quickhull > /tmp/quickhull.plt && gnuplot -p -e «load ‘/tmp/quickhull.plt’». К примеру, раз применять в качестве малого значения std::numeric_limits< value_type >::epsilon(), то в случае «повёрнутого» куба из 64 целых точек rbox n D3 64 M3,4 в итоге работы метода может получиться неправильный геометрический объект, не являющийся выпуклым многоугольником. Также любопытно поглядеть как разбиваются несимплициальные грани: rbox n D3 c — куб, rbox n D3 729 M1,0,1 — точек, расположенных в целых узлах.

Результат либо запоздалый TL;DR.
На выходе метод даст массив структур данных описывающих грани выпуклой оболочки входного множества, являющийся ответом. В случае неудачи мы имеем точечный базис некого подпространства наименьшей размерности, которое вмещает все точки. Метод получает на входе значение размерности места, значение малой константы eps и набор точек, представляемый как спектр, задаваемый парой итераторов, как это принято в STL. Используя метод Хаусхолдера можно неким образом повернуть входное множество, занулив при этом старшие координаты точек. На первом шаге create_simplex строится стартовый симплекс и ворачивается точечный базис аффинного (под)места, вмещающего входные точки. Итогом моих трудов явилась релизация метода Quickhull на C++, достаточно малогабаритная и не сильно медлительнее реализации с qhull.org. Раз количество точек в базисе больше, чем размерность Евклидова места, вмещающего точки, то дальше нужно запустить метод достройки выпуклой оболочки. Такие координаты можно откинуть и применить метод Quickhull уже в пространстве наименьшей размерности.
habrahabr.ru Данная реализация уже кое-кому понадобилась, и была оплачена благодарностью (в Acknowledgements), что чрезвычайно приятно.