Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Поиск поверхности  (Прочитано 3657 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« : 11-01-2014 00:45 » 

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

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

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

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

Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #1 : 11-01-2014 10:57 » 

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

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.

Хз, я не очень просто не очень во всё это верю, во всякие там сатурны и прочую поебень.
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #2 : 11-01-2014 13:34 » 

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

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

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #3 : 11-01-2014 13:55 » 

Dimka, даже в дискретном пространстве возможны варианты: либо есть единое связное тело, и тогда есть некая монолитная "поверхность", что каждая точка "поверхности" обязательно граничит с другими точками "поверхности" - и тогда задача - только нащупать тело, выйти на границу и дальше просто специальный вариант floodfill, который окрашивает только граничные точки. Либо единой поверхности, которую можно одним проходом закрасить, нет, и получается, есть какие-то разрозненные области, и сколько их - может быть неизвестно.
« Последнее редактирование: 11-01-2014 13:57 от Вад » Записан
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #4 : 11-01-2014 15:02 » 

Цитата: Вад
возможны варианты: либо есть единое связное тело
Именно об этом я и сказал.

Цитата: Вад
и тогда задача - только нащупать тело, выйти на границу и дальше просто специальный вариант floodfill, который окрашивает только граничные точки.
В точности с этим подходом я и экспериментирую - он первый очевидный. Но пока производительность не устраивает.
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #5 : 11-01-2014 21:41 » 

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

upd. Кстати, пришла в голову такая мысль по оптимизации floodfill (которая применяется и к самому floodfill, в принципе): можно красить не всё пространство разом, а делать срезы гиперплоскостями (наверное, это можно делать даже рекурсивно, но тут не поручусь). Тонкость в том, что нужно учесть "вертикальную" и, если нужно, "диагональную" связность при поиске граничных точек - то есть, случаи, когда точка лежит на одной гиперплоскости, и в окрестности этой точки на соседнем срезе нет принадлежащих телу точек. То есть, нужно брать значения из двух соседних срезов (если нужны диагонали - предварительно свернув эти срезы с нужным ядром). То есть, граничные точки получаются, условно, из двух источников: то, что мы нашли на срезе, + то, что обнаружилось при "склейке" срезов. Эта мысль как раз и может дальше в глубину разворачиваться, понижая разрядность пространства - и при правильной организации памяти, можно из кэша почти не вылазить, наверное.
« Последнее редактирование: 11-01-2014 22:09 от Вад » Записан
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #6 : 11-01-2014 22:26 » 

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

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

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines