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

[Xaositect]

Sonic86 в сообщении #1131879 писал(а):

Я так пробовал. Время обработки сразу увеличивается в несколько порядков.

Разумеется, это очевидно. Но раз уж самому писать на диск нельзя...
С другой стороны, если увеличить своп и все-таки вызвать стандартный std::sort на std::vector, то еще медленнее получится.

[Sonic86]

Я, честно говоря, не знаю, до std::sort я еще не доучил.
Может там у него все уже отсортировано. Может у него там извратная структура данных.
И вообще - вот написано, что даны данные. В каком виде они даны? Он же это должен знать. М.б. там уже изначально БД стоит или файлик или массив в оперативе суперкомпа, а мы тут голову зря ломаем. Начальный вид сильно влияет на скорость.
Т.е. предлагаю ждать ТС.
Я ничего умного написать все равно не смогу.

[Geen]

Подождите, давайте ещё с задачей разберёмся - вот есть две пересекающиеся сферы, и у одной из них выброшен сегмент лежащий внутри/снаружи другой - "дырка" есть или нет?
Если дырка всё же есть, то нужна только чётность ребра, а тогда, если из них сделать хэш, то его размер будет порядка миллиона (всего лишь)....

[DLL]

Про данные чуть позже отвечу... По поводу двух сфер - вообще как бы это дырой считать не следует.
Но если все-таки считать полагаю, решение простое:
1) Найти все ребра принадлежащие только одному патчу.
2) Разбить их по компонентам связности
3) Те компоненты связности которые замкнуты - кандидаты на дыры.

[Geen]

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

Найти все ребра принадлежащие только одному патчу.

Нет - нечётному количеству патчей - это даст сильный выигрыш и по памяти, и по скорости.