Поиск поверхности

[Dimka]

Дано дискретное N-мерное пространство, на котором определена функция f(x1 : int, x2 : int, ..., xn : int) : bool

Нужно получить все точки пространства, где функция true, но хотя бы в одной соседней точке false. Т.е. окрестность поверхности.

И, разумеется, быстрее, чем полным сканированием пространства (оно большое - 2К^3, а функция не самая быстрая - запрашивает оборудование). И даже быстрее, чем сканированием всей true или всей false области - это тоже долго.

Кто какие алгоритмы знает?

[RXL]

1. Саму функцию, если я правильно понял, ты не знаешь?
2. Характеристики функции известны? Она непрерывная?

[Dimka]

Ну раз я завёл речь про поверхность, то можно сказать, что функция определяет в пространстве некий кусок, у которого есть то, что можно назвать поверхностью. Такой кусок один. И из общих соображений скорее всего он прижат к углу с максимальными координатами. Ближайшим аналогом будет поверхность гиперболоида, но "неровная". Т.е. не аналог эллипсоида в середине, правильного многогранника, простого многогранника (пирамида, призма и т.п.) и т.д.

Говорить о непрерывности, о гладкости и т.п. в дискретном пространстве - это как-то странно.

[Вад]

Dimka, даже в дискретном пространстве возможны варианты: либо есть единое связное тело, и тогда есть некая монолитная "поверхность", что каждая точка "поверхности" обязательно граничит с другими точками "поверхности" - и тогда задача - только нащупать тело, выйти на границу и дальше просто специальный вариант floodfill, который окрашивает только граничные точки. Либо единой поверхности, которую можно одним проходом закрасить, нет, и получается, есть какие-то разрозненные области, и сколько их - может быть неизвестно.

[Dimka]

возможны варианты: либо есть единое связное тело

Именно об этом я и сказал.

и тогда задача - только нащупать тело, выйти на границу и дальше просто специальный вариант floodfill, который окрашивает только граничные точки.

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

[Вад]

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

upd. Кстати, пришла в голову такая мысль по оптимизации floodfill (которая применяется и к самому floodfill, в принципе): можно красить не всё пространство разом, а делать срезы гиперплоскостями (наверное, это можно делать даже рекурсивно, но тут не поручусь). Тонкость в том, что нужно учесть "вертикальную" и, если нужно, "диагональную" связность при поиске граничных точек - то есть, случаи, когда точка лежит на одной гиперплоскости, и в окрестности этой точки на соседнем срезе нет принадлежащих телу точек. То есть, нужно брать значения из двух соседних срезов (если нужны диагонали - предварительно свернув эти срезы с нужным ядром). То есть, граничные точки получаются, условно, из двух источников: то, что мы нашли на срезе, + то, что обнаружилось при "склейке" срезов. Эта мысль как раз и может дальше в глубину разворачиваться, понижая разрядность пространства - и при правильной организации памяти, можно из кэша почти не вылазить, наверное.

[Dimka]

Вад, точки поверхности - это одна задача. Разумеется, сами по себе они не очень интересны - над ними решаются другие задачи.

Мне кажется, гиперплоскости - это перебор бОльшего количества точек, чем просто floodfill по такому правилу, чтобы в окрестностях обязательно было сочетание true и false. К тому же поверхность там не очень-то ровная, т.е. гладкой поверхностью не аппроксимируется - там "ступеньки" случаются. К тому же, поскольку мне нужны все точки, а их количество не запредельно большое, это не floodfill в смысле правильным образом определённой рекурсии (для исключения повторов), а вариант с памятью - он же используется для отсекания обратного хода алгоритма.