Комментарии 14
Есть несколько вопросов и замечаний.
«Алгоритм работает только если на вход подается множество точек, в котором никакие 4 не лежат в одной плоскости. То есть каждые 3 точки задают свою плоскость.»
А почему в этом случае алгоритм не будет работать? Кажется, что будет небольшая неопределенность в том, какая точка будет добавлена (как именно будет триангулирован конкретный четырехугольник/полигон), зависящая от ошибок в округлении. Но в целом задача будет решена. Или есть какие то критические случаи?
Алгоритм использует стек. Это обязательно? Можно ли использовать очередь?
Я представляю его работу, как некий «жадный» алгоритм в глубину — получается ребра будут нарастать с одной стороны, наматываясь в сторону первого ребра по часовой стрелке, получится нечто похожее на кожуру апельсина, который рвали одной стороной. При этом когда до первых ребер дойдет очередь, они уже будут закрыты. Кажется, что использование очереди просто сделает заворачивание похожим на апельсин, заворачиваемый дольками — больше похоже на оборачивание подарка)) Единственный плюс стека — отсутствие фрагментации.
По поводу замечаний — после нахождения первых трех точек нигде не вводится определение «ребра». Стоило бы уточнить, что речь о ребрах, уже входящих в оболочку (прежде всего — идущих по ее краю — остальные ребра закрыты), и первые три точки образуют начальную грань, добавляющую первые 3 ребра.
Второе — фраза «Мы храним ребра в стеке, поочередно достаем их и рассматриваем: нужно ли добавить это ребро в нашу оболочку.» Эта фраза кажется построенной не правильно — мы храним список ребер, входящих в нашу оболочку (являющиеся краями уже найденных граней). Мы поочередно достаем их и проверяем — можем ли мы добавить к ним грань? (Не является ли ребро уже закрытым гранями с обеих сторон?)
Возможно, Я неправильно понял алгоритм, и тогда оба замечания не верные)
Здравствуйте! Спасибо за Ваш комментарий. Мне как раз этим и понравился алгоритм, ведь он кажется довольно сложным со стороны, но если разобраться в нем, думаешь, почему же я раньше считал, что он сложноват?
В случае четырех точек в одной плоскости алгоритм сработает в зависимости от случая. Но в общем, правильная оболочка не будет гарантироваться. Дело в том, что мы смотрим на нормаль к плоскости, и если точки 4, будет как минимум еще одна плоскость с нормалью, коллинеарной изначальной. Угол между ними нулевой, и все зависит от порядка точек, которые подаются на вход. Иначе мы можем взять не ту плоскость, а за эти последует неправильное добавление ребер и тд...
Да, Вы правы, никакой разницы, используем мы стек или очередь, нет. Что кому больше нравится. Очень интересное замечание насчет апельсина, я так не размышлял, но вроде Вы правы, получается будет как будто мы чистили апельсин овощечисткой :)
Насчет замечаний. Да, все верно, Вы правильно поняли. Спасибо, учту, добавлю описание, что массив ребер — это массив ребер, входящих в оболочку. Я просто, наверное, записался, не подумал, что это может быть по-другому.
Второе замечание тоже верно. Только там мы смотрим и на то, является ли ребро закрытым (то есть пока мы дошли в стеке до текущего ребра, возможно, обе его грани уже добавили в оболочку), и на то, какую грань, и, соответственно, какие ее ребра мы добавляем.
Спасибо за замечания.
Нельзя ли её заменить охватывающей сферой?
Здравствуйте!
Вопрос хороший: лично я сам не сталкивался именно с использованием выпуклой оболочки, но могу предположить, где ее можно использовать. Если у Вас есть конкретные примеры, я бы с удовольствием их узнал.
Как я писал в статье, основная задача — уменьшить число рассматриваемых точек: то есть если Вам надо посчитать корреляцию каких-то величин, найти максимальные отклонения — оболочка Вам в помощь. Или если надо найти поверхность какой-то фигуры, зная некоторые точки. Я читал, что это используется в геологии для сканирования поверхностей, наверное, для определения форм тела с помощью локаторов. Но опять же, сам так не делал, так что только предполагаю, ссылаюсь на тех, кто использовал. Также читал об использовании в астрономии, для объединения некоторых тел в группы — еще одно применение. Возможно, оболочку можно использовать для 3D рисовалок.
Как по мне, алгоритм служит в основном для этих целей, но, наверняка, его можно использовать и по-другому.
Замена охватывающей сферой… ну возможно, в каких-то задачах и можно, но ведь в оболочке лежат именно точки из множества, то есть ничего лишнего. Так что если Вам важно максимальное отклонение — то, наверное, да. В случае, если Вам важно, чтобы точки были из Вашего множества, то лучше использовать именно выпуклую оболочку.
Обычно, правда, для подобных вещей (где точки в сетке с определенным разрешением) используют Marching Cubes
Хороший случай именно для такого алгоритма — построение выпуклой оболочки 3д объекта для использования в физическом движке (для игр и симуляций). Часто в физ движках выпуклые многогранники проще проверяются, кроме того, он будет состоять из значительно меньшего количества треугольников, чем исходная модель.
Благодарю! Интересненько… Ну да, звучит очень логично. Вы не будете против, если я дополню статью Вашими данными, а то мне кажется, что именно практического применения очень не хватает в статье?
Вот вам пример из Unity 3D — там есть коллайдер на основе шариков, кубиков (простые формы), а есть — на основе меша.
В нем можно использовать произвольный меш, но по умолчанию Unity умеет строить конвексы прямо из модели.
На картинке кораблик из моего проекта, можете использовать иллюстрацию.
drive.google.com/file/d/1by6wbx8YMIB6h6x8omtN43bTWi0-SRTe/view?usp=sharing
drive.google.com/file/d/1UNAuOjxsJsVQlCvJjSGXn47DSJMfHSJh/view?usp=sharing
Спасибо, очень приятно! Да, Вы абсолютно правы — это именно Джарвис в 3D.
На всякий случай, вот ссылка на реализацию алгоритма Джарвиса в 2D. Я пробовал провести параллель между двумерным случаем и 3D, но потерпел крах, даже сам немного запутался, поэтому не стал его упоминать.
Нет, QuickHull я не писал, а Вы рекомендуете попробовать, что-то интересное? (вот ссылка на QuickHull)
Не думаю, что в QuickHull вы найдете что-то для себя интересное :) По крайней мере для 2D он в чем-то похож на алгоритм Джарвиса, но начинается с поиска наиболее удаленных точек по X и Y (и, видимо, Z для 3D). В конечном итоге все оборачивается таким же перебором оставшихся точек с такой же сложностью.
Спрашиваю, потому что сам недавно экспериментировал с параллелизацией построений выпуклых оболочек в 2D. Смотрел как раз на алгоритм Джарвиса и QuickHull, и последний мне показался чуть проще.
По вашей ссылке на QuickHull удивительная статья, где геометрическая задача разбирается без единой картинки, это, по-моему, за гранью добра и зла. Если же нормально рассказывать идею алгоритма, используя только термины известные шестикласснику (без симплекса и детерминанта), то, как по мне, в 3D-случае QuickHull гораздо интуитивнее Джарвиса.
Здравствуйте!
Нашел англоязычную статью, выглядит она достойно.
Не знаю почему, но в русскоязычной литературе мало упоминаются выпуклые 3D оболочки, так что вложил чуть ли не единственную ссылку на русскоязычное описание алгоритма. (теперь помимо этой статьи :) )
Но если Вас не затрудняет чтение на английском, советую тогда лучше изучить алгоритм Чана с лучшей асимптотикой.
Мне кажется, идею 3D-QuickHull можно изложить еще проще.
- Выбираем из исходного мн-ва 3 точки принадлежащие выпуклой оболочке. Результат — объединение выпуклых оболочек для подмножества точек лежащих выше и подмножества точек лежащих ниже плоскости, определяемой нашими 3-мя точками.
- Мы свели задачу к следующей. Есть 3 точки A, B, C не лежащие на одной прямой и мн-во точек S лежащих над плоскостью P проходящей через A, B, C. Построить оболочку для мн-ва
S u {A, B, C}. Решение: выбираем из S наиболее удаленную от P точку D, она в ответ точно входит, разбиваем мн-воS\{D}на 4 подмн-ва:
- (0) точки лежащие в тетраэдре (A, B, C, D) (они точно в ответ не попадут),
- (1) точки над плоскостью (A, B, D),
- (2) точки над плоскостью (B, C, D),
- (3) точки над плоскостью (C, A, D).
Для мн-в (1), (2), (3) и соотвественно плоскостей (A, B, D), (B, C, D), (C, A, D) запускаемся рекурсивно.
Построение выпуклой 3D оболочки