Comments 12
Однако, для случая произвольной размерности сходу находится лишь одна тяжёловесная реализация с сайта qhull.org.Есть такая библиотека CGAL, там есть очень многое для вычислительной геометрии, в том числе и dD Triangulations.
А в каком контексте, если не секрет, понадобилась новая реализация? Какую проблему вы решаете?
Как-то году в 2011 решал задачку и никак не мог взять в толк, как её решить. Со второй попытки (прошлым летом) всё же решил в общем виде, будучи в отпуске.
Уважаемый, коллега.
Я прошу прощения, что не смог дочитать статью до конца, завис после слов
Может я ошибаюсь? Давайте обсудим. Что значит видеть? Это значит уметь считывать информацию с помощью измерительных приборов из материального пространства. Два глаза человеку позволяют считывать-видеть 3D. Один глаз позволяет считывать-видеть 2D. Закройте глаз полностью, оставив только одну одномерную полоску видимости — глаз сможет видеть только 1D.
Восприятие размерности пространства — свойство используемых измерительных приборов, но никак не объективная данность. В размерности D мы можем видеть размерность D или меньше, в зависимости от имеющихся в нашем распоряжении измерительных приборов.
В задаче выпуклой оболочки, в программировании у нас абстрактное пространство, позволяющее видеть весь объект целиком. Если дана матрица определяющая D-мерный объект (симплекс), то мы видим весь этот объект целиком и сразу.
Я прошу прощения, что не смог дочитать статью до конца, завис после слов
Дам ссылку на хороший ресурс, где логически обосновывается, что в D-мерном пространстве видимыми или наблюдаемыми объектами могут являться только лишь (D-1)-мерные объекты, то есть границы (англ. boundaries) D-мерных объектов.
Может я ошибаюсь? Давайте обсудим. Что значит видеть? Это значит уметь считывать информацию с помощью измерительных приборов из материального пространства. Два глаза человеку позволяют считывать-видеть 3D. Один глаз позволяет считывать-видеть 2D. Закройте глаз полностью, оставив только одну одномерную полоску видимости — глаз сможет видеть только 1D.
Восприятие размерности пространства — свойство используемых измерительных приборов, но никак не объективная данность. В размерности D мы можем видеть размерность D или меньше, в зависимости от имеющихся в нашем распоряжении измерительных приборов.
В задаче выпуклой оболочки, в программировании у нас абстрактное пространство, позволяющее видеть весь объект целиком. Если дана матрица определяющая D-мерный объект (симплекс), то мы видим весь этот объект целиком и сразу.
В большинстве случаев мы не видим 3D. Мы видим только поверхности (например, грани) объектов, а они является двумерными.
Ситуация, когда мы можем видеть 3D в целом — это наблюдение какой-нибудь полупрозрачной сцены, в которой видны все внутренние точки всех объектов. Но она встречается довольно редко, и для неё нужны другие подходы.
Ситуация, когда мы можем видеть 3D в целом — это наблюдение какой-нибудь полупрозрачной сцены, в которой видны все внутренние точки всех объектов. Но она встречается довольно редко, и для неё нужны другие подходы.
Одним глазом мы видим ширину и высоту и не можем оценить = увидеть = измерить дальность. Если глаза, т.е. два глаза, считать одним органом зрения то каждый день, регулярно, этим органом мы видим 3D.
Перископ позволяет измерять расстояния, ширину и высоту — вот вам 3 измерения.
Перископ позволяет измерять расстояния, ширину и высоту — вот вам 3 измерения.
Всё равно, то, что мы видим — это двумерная поверхность, вложенная в трёхмерное пространство. Увидеть трёхмерный объект целиком, не используя рентгеновский аппарат, томограф или бензопилу, не так то просто.
Да, кажется понял идею. Если есть множество точек в D-мерии и выпуклая непрозрачная оболочка, то мы никогда не увидим точки попавшие внутрь оболочки и не сможем узнать их координаты.
Но всё-таки на ЭВМ, в рамках поставленной задачи, мы знаем все координаты, в том числе и внутренних точек.
Грани выпуклой оболочки, конечно имеют на одну размерность ниже, но сама оболочка (многогранник) остаётся D-мерной в D-мерном пространстве. И всю фигуру (многогранник, с неизвестной внутренностью) можно увидеть целиком, все координаты известны, значит мы всё видим.
Утрирую: если мы не видим что внутри многогранника, то не значит, что он стал на одну размерность ниже.
Надо подумать. :)
Но всё-таки на ЭВМ, в рамках поставленной задачи, мы знаем все координаты, в том числе и внутренних точек.
Грани выпуклой оболочки, конечно имеют на одну размерность ниже, но сама оболочка (многогранник) остаётся D-мерной в D-мерном пространстве. И всю фигуру (многогранник, с неизвестной внутренностью) можно увидеть целиком, все координаты известны, значит мы всё видим.
Утрирую: если мы не видим что внутри многогранника, то не значит, что он стал на одну размерность ниже.
Надо подумать. :)
Вопрос, безусловно, философский. По ссылке, насколько я помню, автор придерживается несколько другого подхода, а именно: он рассуждает в терминах луча зрения, который должен иметь возможность падать на сетчатку без помех (have an unobstructed path). Автор делает вывод:
Т.о. сетчатка должна иметь размерность (D — 1) и меньше.
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) измерений.
Вероятно это не принципиально для данной статьи на хабре, это больше принципиально для меня лично.
Вероятно это не принципиально для данной статьи на хабре, это больше принципиально для меня лично.
Sign up to leave a comment.
Алгоритм Quickhull для нахождения выпуклой оболочки