2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Алгоритм поиска изолиний
Сообщение07.10.2011, 11:39 
Заслуженный участник


26/07/09
1559
Алматы
2Ed_Em
Цитата:
Если сетка неперекрываемая, то только треугольная, как у вас. С квадратной такой "финт" не пройдет.

Ничего подобного. Кстати, где вы про шагающие квадраты читали? Даже на wiki/Marching_squares неплохо написано...

 Профиль  
                  
 
 Re: Алгоритм поиска изолиний
Сообщение08.10.2011, 13:11 
Заслуженный участник


26/07/09
1559
Алматы
При попытке написать код на C и протестировать этот изотрейсер, наткнулся таки на проблемы с распараллеливанием. Как и ожидалось, этап выделения элементарных отрезков параллелится на ура, ведь все ячейки абсолютно независимы. Полученные отрезки сразу же можно рисовать.

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

А идея-то проста. Мне кажется, что ячейки можно упорядочить так, чтобы среди двух ячеек меньшей считалась ячейка, являющаяся одновременно самой левой и самой верхней; пока не знаю как такой критерий записать, но суть заключается в предположении о существовании наименьшей (i.e. минимальной по такому порядку и единственной) ячейки.

Допустим, для определенности, что у нас только одна замкнутая изолиния. Также предположим, что каждая ячейка обрабатывается в отдельном потоке. С пустыми ячейками понятно -- их потоки сразу же завершаются. В каждой же ячейке интереса после определения направления элементарного отрезка её поток вычисляет номер ячейки в смысле намеченного выше упорядочивания и посылает сообщение с этим номером потоку следующей ячейки контура в порядке его обхода, ну скажем, по часовой стрелке.

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

Воть. Фактически мы параллельно (правда с пересылкой сообщений) генерируем список ведущих ячеек каждой изолии. Когда нам нужно получить конкретную изолинию, например чтобы её нарисовать, нам придется пройти по соответсвующий ссылке, нарисовать соответствующий элементарный отрезок, пройти по следущей ссылке, нарисовать второй отрезок, etc. То есть можно считать, что изолинии уже хранятся в виде связных списков, полченных чисто параллельно. Но для испольщования этих связных списков их ве-равно придется обходить в последовательном режиме.

Что вы думаете об этой (концептуальной) схеме?

 Профиль  
                  
 
 Re: Алгоритм поиска изолиний
Сообщение09.10.2011, 01:51 


04/02/08
325
Буково
Circiter в сообщении #490323 писал(а):
Кстати, где вы про шагающие квадраты читали? Даже на wiki/Marching_squares неплохо написано...

На википедии и читал. И не только там. Но готовых библиотек не нашел.
Circiter в сообщении #490603 писал(а):
Что вы думаете об этой (концептуальной) схеме?

Сдается мне, ее реализация будет довольно сложной.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 18 ]  На страницу Пред.  1, 2

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group