Вычислительная геометрия: обнаружение дыр

[DLL]

Пусть поверхность $F$ задана как конечный набор треугольников в пространстве, при чем пересечение любых двух треугольников есть либо ребро, либо пустое множество.
Интересует вопрос - всегда ли легко определить является поверхность замкнутой или нет?

С первого взгляда, кажется что на языке ребер (а именно скольким треугольникам принадлежит ребро) этот вопрос можно будет несложно исчерпать. Так ли это всегда будет?

[arseniiv]

Можно попробовать теорему Эйлера $F-E+V=\chi(\text{многогранник})$, где для замкнутых многогранников $\chi\in\{2,0,-2,\ldots\}$. Если удалить одну грань и сделать многогранник дырявым, получится $1,-1,-3,\ldots$, но если удалить ещё нечётное число граней, мы придём к ситуации, в которой не можем отличить замкнутый от незамкнутого по характеристике.* Пичаль. Но можно уже хотя бы нечётное число дыр отделить от чётного.

* Наглядный пример. Пускай есть две треугольные дыры. Можно вклеить в них треугольную призму без оснований, что добавит столько же рёбер, сколько и граней, так что характеристика останется той же, а поверхность замкнётся.

F, E, V — faces, edges, vertices, если вдруг.

-- Сб июн 11, 2016 21:45:20 --

Что, конечно, не отменяет возможность существования каких-то других несложных алгоритмов (в том числе применимых только при чётном числе дыр, т. к. нечётное, считай, отброшено).

-- Сб июн 11, 2016 21:47:32 --

Плюс, если все замкнутые поверхности предполагаются быть гомеоморфными сфере, вопрос тоже, понятно, решён — даже если характеристика получится 0, она будет вызвана дырками, а не тем, что перед нами что-то гомеоморфное тору.

[Munin]

arseniiv
Очень сложно.

Достаточно перебрать все рёбра, и убедиться, что каждое принадлежит двум и только двум треугольникам. (Или чётному числу, если допускается самопересечение по рёбрам.)

[Sonic86]

Munin в сообщении #1130877 писал(а):

Достаточно перебрать все рёбра, и убедиться, что каждое принадлежит двум и только двум треугольникам. (Или чётному числу, если допускается самопересечение по рёбрам.)

Добавлю, что чтобы это доказать, достаточно индукции по ребрам.
А для обнаружения дыр (краев (края - это окрестности, гомеоморфные $\mathbb{R}\times [0;+\infty)}$ (правильно хоть сказал?))) процесс надо немного модифицировать: найти все ребра, принадлежащие только одному треугольнику и потом уже искать инцидентность у них.
Или Вам нужны не такие дыры? (и вообще написано непонятно: в заголовке слово "дыры" есть, а в тексте - нету)

(Оффтоп)

И замкнутая поверхность - это та, которая не содержит краев, правильно? Ну хотя да, триангуляция же.

[Munin]

В общем, "дыры" как у бублика, или как у дырявого мячика?

[arseniiv]

FTR, я тоже подумал, что под дырами понимаются края.

[DLL]

Типичный пример дыры. Возьмем поверхность куба.
В соответствии с постановкой она представлена конечным набором треугольников.
Выкинем один из треугольников - получается дыра.

[ИСН]

Тогда всё просто, и делается так, как сказал Munin. Ну, если поверхность без самопересечений. Если с ними, то вещи становятся волосатыми.

-- менее минуты назад --

Upd. Или не становятся, смотря как Вы определяете, что такое дыра в этом случае.

[DLL]

Да, самопересечения могут быть. Например, можно "пристыковать" к кубу кусочек плоскости.
Таким образом, появятся ребра которые принадлежат как 3 треугольникам, так и 1.

[svv]

DLL в сообщении #1131702 писал(а):

Да, самопересечения могут быть. Например, можно "пристыковать" к кубу кусочек плоскости.

Уточните, пожалуйста. Такое, как на левой картинке, не страшно. А вот нет ли такого, как на правой?

[DLL]

Если речь идет о поверхностях , то оба случая возможны.
Если про патчи-треугольники (из которых состоят поверхности), то второй случай не реализиуется, потому что пересечение любых двух треугольников есть либо ребро, либо пустое множество.

[grizzly]

DLL в сообщении #1131738 писал(а):

пересечение любых двух треугольников есть либо ребро

И наверняка имеется в виду, что пересечение даёт общее ребро, а не ребро одного из них.

[svv]

Наверное, поверхность линейно связна? Причем связна даже после удаления вершин треугольников (через рёбра).

Если бы я писал программу. Поверхность делит пространство на $n$ областей, задача — узнать $n$. Каждой из двух сторон каждого треугольника отводится ячейка, в которую алгоритм должен вписать номер области, на которую эта сторона «смотрит». Вначале выбираем произвольный треугольник и одной из сторон присваиваем номер области $1$, а дальше переносим (копируем) этот номер на все стороны треугольников, которые смотрят на ту же область, пользуясь некоторыми правилами переноса (они, вроде, очевидны; нужно ли их пояснять?). Если ещё остались стороны без номера, выбираем одну из них и присваиваем ей номер области $2$, далее распространяем его насколько возможно. И т.д.

[DLL]

Честно скажу, ничего не понял в последней мысли.
Единственное, что когда мы работаем на практике - может оказаться что у нас 10 миллиардов патчей (треугольников).
В этом случае даже сортировка уже может быть проблемой - поскольку std::vector столько элементов иногда не хочет в себя помещать...
P.S: да поверхность можно считать линейно связной - задача практическая, по сути когда она не линейна связная - можем считать что имеем дело с независимыми поверхностями...

[Munin]

(Оффтоп)

DLL в сообщении #1131812 писал(а):

Единственное, что когда мы работаем на практике - может оказаться что у нас 10 миллиардов патчей (треугольников).
В этом случае даже сортировка уже может быть проблемой - поскольку std::vector столько элементов иногда не хочет в себя помещать...

Кто вас учил такие объёмы данных пихать в std::vector?