![]() |
Здравствуйте, гость ( Вход | Регистрация )
![]() ![]() |
![]() |
wiz29 |
![]()
Сообщение
#1
|
![]() Старейший участник ![]() ![]() ![]() ![]() Группа: Участник Сообщений: 600 Регистрация: 7.7.2010 Из: Санкт-Петербург Пользователь №: 1866 Спасибо сказали: 94 раз(а) Репутация: ![]() ![]() ![]() |
Реализовывал ли кто нибудь данный алгоритм?(нужна консультация по производительности, моя реализация считает несколько секунд на картинке 1500+ х 1500+, тогда как продвинутые реализации справляются "мгновенно" с точки зрения пользователя, не беру в расчет время на вычисление весов ребер)
|
|
|
Алексей1153 |
![]()
Сообщение
#2
|
![]() фрилансер ![]() ![]() ![]() ![]() ![]() ![]() Группа: Участник Сообщений: 2939 Регистрация: 19.6.2010 Из: Обливион Пользователь №: 1822 Спасибо сказали: 215 раз(а) Репутация: ![]() ![]() ![]() |
Какой алгоритм ?
|
|
|
kibsoft |
![]()
Сообщение
#3
|
Участник ![]() ![]() Группа: Участник Сообщений: 180 Регистрация: 21.7.2009 Из: Самара Пользователь №: 928 Спасибо сказали: 14 раз(а) Репутация: ![]() ![]() ![]() |
|
|
|
Алексей1153 |
![]()
Сообщение
#4
|
![]() фрилансер ![]() ![]() ![]() ![]() ![]() ![]() Группа: Участник Сообщений: 2939 Регистрация: 19.6.2010 Из: Обливион Пользователь №: 1822 Спасибо сказали: 215 раз(а) Репутация: ![]() ![]() ![]() |
ааа, вона чего... То есть выбор произвольной замкнутой области на битмапе
wiz29, ну дык, словесный алгоритм и саму реализацию - в студию попросим ) Для оптимизации |
|
|
wiz29 |
![]()
Сообщение
#5
|
![]() Старейший участник ![]() ![]() ![]() ![]() Группа: Участник Сообщений: 600 Регистрация: 7.7.2010 Из: Санкт-Петербург Пользователь №: 1866 Спасибо сказали: 94 раз(а) Репутация: ![]() ![]() ![]() |
ааа, вона чего... То есть выбор произвольной замкнутой области на битмапе wiz29, ну дык, словесный алгоритм и саму реализацию - в студию попросим ) Для оптимизации нет, ты говоришь про так называемый Magic Wand алгоритм , здесь другой алгоритм, просто хотел проконсультироваться с человеком который вероятно сталкивался с ним. Материала слишком много , чтобы писать в посте, поэтому и написал ("Если кто то сталкивался"). Последнюю реализацию я смог ускорить в 5 раз, но время решения всеравно занимает порядка 1сек на моей не медленной машине, хотелось бы быстрее ![]() |
|
|
ufna |
![]()
Сообщение
#6
|
![]() Активный участник ![]() ![]() ![]() Группа: Участник Сообщений: 362 Регистрация: 24.5.2008 Из: Курган/СПб Пользователь №: 182 Спасибо сказали: 29 раз(а) Репутация: ![]() ![]() ![]() |
приведи код реализации, посмотрим.
|
|
|
wiz29 |
![]()
Сообщение
#7
|
![]() Старейший участник ![]() ![]() ![]() ![]() Группа: Участник Сообщений: 600 Регистрация: 7.7.2010 Из: Санкт-Петербург Пользователь №: 1866 Спасибо сказали: 94 раз(а) Репутация: ![]() ![]() ![]() |
Раскрывающийся текст
блин нелзя файлы почемуто прикрепить ![]() |
|
|
ufna |
![]()
Сообщение
#8
|
![]() Активный участник ![]() ![]() ![]() Группа: Участник Сообщений: 362 Регистрация: 24.5.2008 Из: Курган/СПб Пользователь №: 182 Спасибо сказали: 29 раз(а) Репутация: ![]() ![]() ![]() |
оберни плз в тег code, чтобы читабельность сохранилась, а то без indent'ов сложно воспринимать
|
|
|
Алексей1153 |
![]()
Сообщение
#9
|
![]() фрилансер ![]() ![]() ![]() ![]() ![]() ![]() Группа: Участник Сообщений: 2939 Регистрация: 19.6.2010 Из: Обливион Пользователь №: 1822 Спасибо сказали: 215 раз(а) Репутация: ![]() ![]() ![]() |
в zip-архиве можно )
|
|
|
wiz29 |
![]()
Сообщение
#10
|
![]() Старейший участник ![]() ![]() ![]() ![]() Группа: Участник Сообщений: 600 Регистрация: 7.7.2010 Из: Санкт-Петербург Пользователь №: 1866 Спасибо сказали: 94 раз(а) Репутация: ![]() ![]() ![]() |
CODE #ifndef LWSOLVE_H #define LWSOLVE_H #include "lwimagegraph.h" namespace liveware { //solve for seed point with coord (xSeed, ySeed) void Dijkstra(ImageGraph& graph, int xSeed, int ySeed); }//namespace liveware #endif //LWSOLVE_H #include "lwsolve.h" #include "lwpriorityqueue.h" #include <algorithm> #include <functional> #include <QDebug> namespace liveware { //--------------------------------------------------------------------------------------------------------- enum NodeSate { NONE = 0x00, //if node was not processed PROCESSED = 0x01, //node was processed ACTIVE = 0x02 //node in active queue }; //--------------------------------------------------------------------------------------------------------- //functor //reset all calc dijkstra data class cleanGraph { public: void operator()(GraphNode* pNode) { if (pNode) { pNode->SetState(NONE);//reset state pNode->SetPrevNode(NULL);//reset prev node pNode->SetWeight(1.0e+10);//set "infinite" weight } } }; //--------------------------------------------------------------------------------------------------------- //functor //calculate transit cost for neighborhood nodes class calcCost { public: calcCost(PriorityQueue<GraphNode*, std::vector<GraphNode*>, less>& pq, GraphNode* pCurrNode) : m_pq(pq) , m_pCurrNode(pCurrNode) { } ~calcCost() { } public: void operator()(std::pair<GraphNode*, double>& pDstNodeData) { GraphNode* pNode(pDstNodeData.first); if (!(pNode->state() & PROCESSED)) { double localCost(m_pCurrNode->Weight() + pDstNodeData.second); if (!(pNode->state() & ACTIVE)) {//node is not in queue pNode->SetWeight(localCost); pNode->SetPrevNode(m_pCurrNode); m_pq.push(pNode); pNode->SetState(ACTIVE); } else if (localCost < pNode->Weight()) {//node already in queue pNode->SetWeight(localCost); pNode->SetPrevNode(m_pCurrNode); m_pq.update(); } } } private: PriorityQueue<GraphNode*, std::vector<GraphNode*>, less>& m_pq; GraphNode* m_pCurrNode; }; //--------------------------------------------------------------------------------------------------------- //solve for seed point with coord (xSeed, ySeed) void Dijkstra(ImageGraph& graph, int xSeed, int ySeed) { std::for_each(graph.Begin(), graph.End(), cleanGraph());//clean all dijkstra data PriorityQueue<GraphNode*, std::vector<GraphNode*>, less> pq;//construct empty priority queue //of active nodes GraphNode* pCurr(graph.ElementAt(xSeed, ySeed));//take seed node pCurr->SetWeight(0.0); pq.push(pCurr);//push seed node into queue pCurr->SetState(ACTIVE);//set active node state while(!pq.empty()) { pCurr = pq.top(); pq.pop(); pCurr->SetState(PROCESSED); std::for_each(pCurr->NeighborhoodBegin(), pCurr->NeighborhoodEnd(), calcCost(pq, pCurr)); } } //--------------------------------------------------------------------------------------------------------- }//namespace liveware если кому интересна данная задача могуть дать литературу Сообщение отредактировал wiz29 - 27.8.2010, 13:31 |
|
|
![]() ![]() ![]() |
![]() |
Текстовая версия | Сейчас: 1.9.2024, 5:59 |