Комментарии 12
Однако, для случая произвольной размерности сходу находится лишь одна тяжёловесная реализация с сайта qhull.org.
Есть такая библиотека CGAL, там есть очень многое для вычислительной геометрии, в том числе и dD Triangulations.
Спасибо за ссылку. Полезным будет реализовать проверку выпуклости результата как у них (Mehlhorn algorithm).
Добавил проверку выпуклости. В CGAL не Quickhull, так что противоречия нет.
А в каком контексте, если не секрет, понадобилась новая реализация? Какую проблему вы решаете?
Как-то году в 2011 решал задачку и никак не мог взять в толк, как её решить. Со второй попытки (прошлым летом) всё же решил в общем виде, будучи в отпуске.
Уважаемый, коллега.
Я прошу прощения, что не смог дочитать статью до конца, завис после слов
Дам ссылку на хороший ресурс, где логически обосновывается, что в D-мерном пространстве видимыми или наблюдаемыми объектами могут являться только лишь (D-1)-мерные объекты, то есть границы (англ. boundaries) D-мерных объектов.

Может я ошибаюсь? Давайте обсудим. Что значит видеть? Это значит уметь считывать информацию с помощью измерительных приборов из материального пространства. Два глаза человеку позволяют считывать-видеть 3D. Один глаз позволяет считывать-видеть 2D. Закройте глаз полностью, оставив только одну одномерную полоску видимости — глаз сможет видеть только 1D.
Восприятие размерности пространства — свойство используемых измерительных приборов, но никак не объективная данность. В размерности D мы можем видеть размерность D или меньше, в зависимости от имеющихся в нашем распоряжении измерительных приборов.
В задаче выпуклой оболочки, в программировании у нас абстрактное пространство, позволяющее видеть весь объект целиком. Если дана матрица определяющая D-мерный объект (симплекс), то мы видим весь этот объект целиком и сразу.
В большинстве случаев мы не видим 3D. Мы видим только поверхности (например, грани) объектов, а они является двумерными.
Ситуация, когда мы можем видеть 3D в целом — это наблюдение какой-нибудь полупрозрачной сцены, в которой видны все внутренние точки всех объектов. Но она встречается довольно редко, и для неё нужны другие подходы.
Одним глазом мы видим ширину и высоту и не можем оценить = увидеть = измерить дальность. Если глаза, т.е. два глаза, считать одним органом зрения то каждый день, регулярно, этим органом мы видим 3D.
Перископ позволяет измерять расстояния, ширину и высоту — вот вам 3 измерения.
Всё равно, то, что мы видим — это двумерная поверхность, вложенная в трёхмерное пространство. Увидеть трёхмерный объект целиком, не используя рентгеновский аппарат, томограф или бензопилу, не так то просто.
Да, кажется понял идею. Если есть множество точек в D-мерии и выпуклая непрозрачная оболочка, то мы никогда не увидим точки попавшие внутрь оболочки и не сможем узнать их координаты.
Но всё-таки на ЭВМ, в рамках поставленной задачи, мы знаем все координаты, в том числе и внутренних точек.
Грани выпуклой оболочки, конечно имеют на одну размерность ниже, но сама оболочка (многогранник) остаётся D-мерной в D-мерном пространстве. И всю фигуру (многогранник, с неизвестной внутренностью) можно увидеть целиком, все координаты известны, значит мы всё видим.
Утрирую: если мы не видим что внутри многогранника, то не значит, что он стал на одну размерность ниже.
Надо подумать. :)
Вопрос, безусловно, философский. По ссылке, насколько я помню, автор придерживается несколько другого подхода, а именно: он рассуждает в терминах луча зрения, который должен иметь возможность падать на сетчатку без помех (have an unobstructed path). Автор делает вывод:
A 2D retina works, because there is a 3rd dimension in which the light can travel unobstructed from the object onto the retina.

Т.о. сетчатка должна иметь размерность (D — 1) и меньше.
Сетчатка — это 2D измерительный прибор, т.е. на одну размерность ниже 3D. Утрирую, но смысл статьи на которую дана ссылка: в D-мерном пространстве возьмём измерительный прибор размерности (D-1), тогда мы сможем видеть не более (D-1) измерений.
Вероятно это не принципиально для данной статьи на хабре, это больше принципиально для меня лично.
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.