Russian Qt Forum
Август 21, 2017, 20:28 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало Форум WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  
  Просмотр сообщений
Страниц: [1] 2 3 ... 117
1  Программирование / Алгоритмы / Re: Сетка на сфере : Сегодня в 10:24
Цитировать
Какие-то там kd-tree и.т.п.
Можно организовать таблицу, с поиском ближайших узлов за O(ln(N)). Смотри схему ниже..

2  Программирование / Алгоритмы / Re: Сетка на сфере : Август 19, 2017, 14:30
Цитировать
Какие-то там kd-tree и.т.п. - это ж все "велики"
Да пожалуйста.. Но о каком kd-tree и.т.п. сейчас может идти речь, если мы ещё до сих пор не знаем/не представляем (ну лично я) как Вы хотите параметризовывать, строить сетку на сфере? Когда это будет понято, тогда уже можно будет говорить о модели представления этих узлов. Т.е. где то отображение, которое переводит какие-либо 2 обобщённые координаты (например в случае ССК это углы theta и phi) в координаты конкретного узла сетки?

Цитировать
перебор - вот наш метод!
Я себе сейчас представляю следующую ситуацию: предположим у меня есть массив из N векторов узлов на сфере. Т.е. мне его предоставляют по моему требованию. Я могу запросить скажем: хочу сетку из 1000 узлов - мне вернули массив из этих 1000 векторов. Всё.. Я имею random access к нему, могу этот массив сортировать и т.д. Но я не знаю по какому принципу он строится, я имею дело только по факту..
Какова потановка вопроса в таком случае? Для любой точки на сфере найти все ближайшие к ней узлы, нах. внутри заданного телесного угла (из центра сферы).
Я правильно понимаю?


Цитировать
Если мы умеем строить сферу из куба (а мы умеем),
   
Я не совсем понимаю, что Вы имеете в виду под "мы умеем строить сферу из куба"..
   
3  Программирование / Алгоритмы / Re: Сетка на сфере : Август 18, 2017, 16:17
Цитировать
Нет, координаты узлов "априорно" неизвестны, они тоже должны получаться из построения.
Которое ещё тоже не понятно какое?

Цитировать
Общий алгоритм:
У меня такой алгоритм:
1) У меня есть метод/алгоритм который на сфере (для определённости единичного радиуса) строит сетку в зависимости от числа N узлов (вершин) этой сетки. Чем больше узлов, тем меньше растояние между ними и тем меньше ячейки. Т.е. на выходе я имею N единичных векторов, определяющих положение узлов.

2) Для любой точки на поверхности сферы, простым перебором (самое простое) находим ближайшие к этой точке узлы (просто оценивая скалярное произведение вектора узла на вектор точки - что для единичной сферы сведётся к косинусу угла между ними).

Всё) 
4  Программирование / Алгоритмы / Re: Сетка на сфере : Август 18, 2017, 10:24
Цитировать
Мне нужно определить в какую ячейку попал заданный вектор (он же точка на поверхности сферы) чтобы использовать значения в углах для интерполяции.
А координаты узлов сетки в принципе известны (их можно получить, перебрать, сортировать и т.д.)?  Т.е. фактически тогда нужно построить такую модель данных (для узлов), чтоб по заданному направлению получить координаты 4-ёх вершин?   
5  Программирование / Алгоритмы / Re: Сетка на сфере : Август 17, 2017, 16:35
Цитировать
Обычная "меридианная" сетка не годится, клеточки в ней разного размера
Какие две координаты (криволинейные) вы предлагаете использовать? Меридианная - это я полагаю сферическая СК с углами theta, phi?
Цитировать
Индекс ячейки нам не очень нужен. но цель та же - найти значения в 4-х углах, а возможно и в соседних ячейках.
 
А с чего вы взяли, что возможно замостить 3D сферу одинаковыми четырёхугольниками? Почему не треугольниками или шестиугольниками? И что такое step в этом контексте - расстояние между двумя ближайшими узлами рещётки?

Вообщем как всегда - постановка никакая(   
6  Qt / Вопросы новичков / Re: Быстрый поиск ближайшего значения : Август 11, 2017, 20:01
Как быстро найти число в массиве больше заданного? Допусти {1,10,100,150} на 15 вывести 100.
Есть QMap::lowerBound(const Key &key) вроде то что нужно, но придется хранить значения для ключей.
Если предполагается, что последовательность отсортирована, то стандартный std::lower_bound, а если нет.. То да, фактически остаётся перебор
Код
C++ (Qt)
template <class InputIt>
InputIt greater_than(InputIt first, InputIt last, int val)
{
   auto it_res = std::find_if(first, last, [&](int x){ return x >= val; });
   if (it_res == last)
       return last;
 
   first = it_res;
 
   while ((first = std::find_if(++first, last, [&](int x){ return x >= val; })) != last)
   {
       if (*first <= *it_res)
           it_res = first;
   }
 
   return it_res;
}
 
7  Разное / Говорилка / Re: Qt стал онли платным? : Август 03, 2017, 14:48
m_ax, а разве в бусте есть GUI?
Да я уж так, пошутил про буст)
8  Разное / Говорилка / Re: Qt стал онли платным? : Август 02, 2017, 21:44
Да форконут Qt, на крайней случай, если уж его свободе будет кто то угрожать..) Не надо трагедий (с)
Ну или буст -  наше всё) (но не для всех)
9  Разное / Говорилка / Re: Qt стал онли платным? : Август 02, 2017, 21:41
Ну, онлайн инсталлеры теперь полностью только платные. Если нет лицензии на аккаунте Qt инсталлер шлёт лесом Веселый

Ой, какая трагедия, особенно из уст поклонника форточек.. А может оно и к лучшему? Ммм?
Не Вам ли, адептом всех благ коммерческого софта, возмущаться личным решением digia?  
10  Программирование / Алгоритмы / Re: Вычислить кадр мувика : Июнь 01, 2017, 12:43
Цитировать
И если поступило указание "на 100 собак вперед" - то мы 100 раз зовем ++it, расписываясь в том что "просто посчитать" не умеем. Ну как-то неудобно
И в чём проблема?
Код
C++ (Qt)
it += 100;
 
Это random access итератор.
11  Программирование / Алгоритмы / Re: Вычислить кадр мувика : Май 25, 2017, 19:12
Цитировать
У меня другие результаты - противоположные..
Сделал вашу функцию инлайн и результаты примерно выровнялись:
Код
Bash
m_ax, total time: 296
deMax, total time: 305
 
m_ax, total time: 296
deMax, total time: 304
 
m_ax, total time: 297
deMax, total time: 303
 
(результаты после 3-х запусков), что говорит о том, что компилятор не видит особой разницы между
Код
C++ (Qt)
posCurrentFrame -= (posCurrentFrame / sizeWithBack) * sizeWithBack;
if(posCurrentFrame<0) posCurrentFrame += sizeWithBack;
 
и этим
Код
C++ (Qt)
return toFrame((x + step % T) % T);
 


 
12  Программирование / Алгоритмы / Re: Вычислить кадр мувика : Май 25, 2017, 16:00
Цитировать
Моя функция 20млн.раз выполняется за 301мс(с поддержкой отрицательного шага 324), а ваша 640.
У меня другие результаты - противоположные..
Может вы её в холостую запускали?

Мой тест приаттачен.
компилятор: gcc 4.9.2
13  Программирование / Алгоритмы / Re: Вычислить кадр мувика : Май 25, 2017, 15:35
Цитировать
нет ерунда, да еще за диапазон вышла.
Я вот на таком тесте
Код
C++ (Qt)
#include <iostream>
#include <random>
#include <cmath>
#include <stdexcept>
 
 
inline int NextFrame_m_ax(int currentFrame, int step, int x0, int x1) throw (std::logic_error)
{
   if ((currentFrame < std::min(x0, x1)) || (currentFrame > std::max(x0, x1)))
       throw std::logic_error("out of range");
 
   if (x0 == x1) return x0;
 
   const int sign = (x1 > x0) ? 1 : -1;
 
   const int T = 2*sign*(x1 - x0);
 
   auto toFrame = [&](int x)->int
   {
       return (x <= T/2) ? (x0 + sign*x) : (sign*(T - x) + x0);
   };
 
   int x = sign*(currentFrame - x0);
 
   return toFrame((x + step % T) % T);
}
 
 
int NextFrame_deMax(int currentFrame, int step, int x0, int x1) {
   int dPosFirst = x1>x0? 1: -1; // направление в первой последовательности
   int size = abs(x1-x0)+1;
 
   int posCurrentFrame = (currentFrame - x0) * dPosFirst;
   if(posCurrentFrame >= size || posCurrentFrame<0) return 0; //TODO error: число не принадлежит последовательности
 
   posCurrentFrame += step; // new Frame;
 
   if(x0 == x1)return x0; // если один кадр
   int sizeWithBack = size*2 - 2; // размер последовательности включая обратную(не правильно считает для одного кадра x0==x1, но этот случай отсекли)
   posCurrentFrame -= (posCurrentFrame / sizeWithBack) * sizeWithBack; // теперь новый кадр будет лежать в диапазоне [0, sizeWithBack), так как данная последовательность повторяется
 
   return posCurrentFrame < size? x0 + posCurrentFrame * dPosFirst:
                                  x0 + (sizeWithBack - posCurrentFrame) * dPosFirst;
}
 
 
int main()
{
   int f0 = 5;
   int f1 = 10;
   int frame = 9;
 
   std::cout << "m_ax \t deMax" << std::endl;
 
   for(int i=-20; i<20; ++i)
   {
       std::cout <<  NextFrame_m_ax(frame, i, f0, f1) << "\t" << NextFrame_deMax(frame, i, f0, f1) << std::endl;
   }
 
   return 0;
}
 
получил следующее:
Код
Bash
m_ax    deMax
9 -1
0 0
1 1
2 2
3 3
4 4
5 5
6 -4
7 -3
8 -2
9 -1
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
9 9
8 8
7 7
6 6
5 5
6 6
7 7
8 8
9 9
10 10
9 9
8 8
7 7
6 6
5 5
6 6
7 7
8 8
 
т.е. у вас она уходит в отрицательные значения..

Если изменить порядок диапазона:
Код
C++ (Qt)
   int f0 = 10;
   int f1 = 5;
 
то обе реализации выдают ерунду (
Код
Bash
m_ax deMax
9 19
18 18
17 17
16 16
15 15
14 14
13 13
12 12
11 11
10 10
9 19
18 18
17 17
16 16
15 15
14 14
13 13
12 12
11 11
10 10
9 9
8 8
7 7
6 6
5 5
6 6
7 7
8 8
9 9
10 10
9 9
8 8
7 7
6 6
5 5
6 6
7 7
8 8
9 9
10 10
 
14  Программирование / Алгоритмы / Re: Вычислить кадр мувика : Май 25, 2017, 14:43
Цитировать
1. uint step - для отрицательных чисел у вас алгоритм вычисляет неправильно(автору не нужно)
Да вроде и с отрицательными работает нормально)

Цитировать
2. при x0 == x1 у вас T == 0 -> %T сгенерирует ошибку и программа упадет без обработчика
Да, согласен)

Цитировать
4. имхо, через деление выражение ((x + step % T) % T) быстрее будет
Не знаю.. думаю сейчас, это больше от компилятора зависит..

Цитировать
5. std::min и max тоже можно убрать повысив производительность, if((sign>0 && currentFrame<x0 ?&& currentFrame>x1) || (sign<0 && currentFrame<x1 ?&& currentFrame>x0)) throw std::logic_error("out of range");
Здесь, думаю, тож спорно в плане производительности.. Я за читабельность в данном случае)
15  Программирование / Алгоритмы / Re: Вычислить кадр мувика : Май 25, 2017, 13:15
Цитировать
остальные программы работают неправильно
Всё работает как надо) Слегка подправил для для обратного порядка и на проверку на диапазон.
Код
C++ (Qt)
inline int NextFrame(int currentFrame, int step, int x0, int x1) throw (std::logic_error)
{
   if ((currentFrame < std::min(x0, x1)) || (currentFrame > std::max(x0, x1)))
       throw std::logic_error("out of range");
 
   int sign = (x1 > x0) ? 1 : -1;
 
   const int T = 2*sign*(x1 - x0);
 
   auto toFrame = [&](int x)->int
   {
       return (x <= T/2) ? (x0 + sign*x) : (sign*(T - x) + x0);
   };
 
   int x = sign*(currentFrame - x0);
 
   return toFrame((x + step % T) % T);
}
 
По моему это гораздо проще и нагляднее)
Страниц: [1] 2 3 ... 117
Страница сгенерирована за 0.216 секунд. Запросов: 23.