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

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Поиск поверхности  (Прочитано 9703 раз)
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