Сетка на сфере (решено)

[m_ax]

Какие-то там kd-tree и.т.п. - это ж все "велики"

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

перебор - вот наш метод!

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

Если мы умеем строить сферу из куба (а мы умеем),

   
Я не совсем понимаю, что Вы имеете в виду под "мы умеем строить сферу из куба"..
   

[Igors]

Я не совсем понимаю, что Вы имеете в виду под "мы умеем строить сферу из куба"..

Дан куб с центром в (0, 0, 0) и стороной 2 / sqrt(3) (чтобы половинка диагонали =  радиуc, удобнее считать ) Для каждой из его 6 граней берем 4 новых вертекса на середине каждого ребра + центр грани, итого 5. Нормируем эти вертексы (теперь они лежат на поверхности сферы). Теперь каждая грань разбита на 4 новых 4-угольника, повторяем все для них. См картинку выше.

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

Рассмотрим требуемый алгоритм на плоскости (это случай параллельного источника). Есть квадрат напр QRectF(-1, -1, 2, 2). Никаких узлов еще нет. Приходит запрос - посчитать данные напр в точке QPointF(0.27, 0.33) с точностью напр 0.1. Наши действия

- находим шаг сетки < требуемого, step = 0.0625

- находим индексы
  index_x = int((0.27 + 1) / step) 
  index_y = int((0.33 + 1) / step)

- тогда координаты 4 близлежащих узлов
  left_top_x = index_x * step - 1 
  left_top_y = index_y * step - 1
  и.т.д

- смотрим есть ли они в хеше (считались ли уже эти узлы). Ключ = пара индексов. Если нет, то считаем и пополняем хеш.

- интерполируем значение в заданной точке используя значения в узлах

Да, с квадратом-то все хорошо, но что делать для сферы? 

[deMax]

deMax, сетка что "равномерна на кубе" не будет "равномерна на сфере" и наоборот (см. вттвч). Др словами медиана не равна биссектрисе

Это я знаю, но если вам принципиально нужны равные углы(мне с нормализованным квадратом проще работать было, а то что в центре квадратик чуть больше мне было неважно), то алгоритм нужно слегка изменить:
floor( xyz / step)*step или ceil ( xyz / step )*step нужно заменить, на что то типа atg( floor ( tg(xyz) / step2 ) * step2 ) это если в лоб (step2 = step*90).
Если не в лоб, то для каждого step создать массив( for(float a=-90; a<90; a+=180/step) array << atg(a)  ) и потом округлять xyz используя полученный массив std::lower_bound и предыдущий элемент.

p.s. писал из головы, возможно много где опечатался, но смысл думаю понятен. Должно работать.

p.s.s. А зачем вам это выравнивание? Кубик из равномерной сетки проще получить и работать с ним проще, а выигрыша в детализации с гулькин нос.

[m_ax]

Какие-то там kd-tree и.т.п.

Можно организовать таблицу, с поиском ближайших узлов за O(ln(N)). Смотри схему ниже..

[Igors]

то алгоритм нужно слегка изменить:
floor( xyz / step)*step или ceil ( xyz / step )*step нужно заменить, на что то типа atg( floor ( tg(xyz) / step2 ) * step2 )

Как у Вас все легко и просто Но это не дает клеточек равного размера. По существу Вы предложили обычную полярную систему координат. Смотрим на глобус с нарисованными меридианами и параллелями - клетки там ну никак не равны

p.s.s. А зачем вам это выравнивание? Кубик из равномерной сетки проще получить и работать с ним проще, а выигрыша в детализации с гулькин нос.

"Сетка" предполагает клеточки равного размера (ну хотя бы примерно). А если использовать сетку куба, то на сфере площадь "угловой" клетки будет в 4 раза меньше площади "центральной". Ничего себе гулькин "нос" Хуже того, клетки перестают быть квадратными, из пропорции теперь до 2:1. И что это за сетка такая?

Можно организовать таблицу, с поиском ближайших узлов за O(ln(N)). Смотри схему ниже..

Хранить саму сетку (в любом виде) = немедленная гибель по памяти. Хранятся только обсчитанные узлы, их обычно доли %

[deMax]

Как у Вас все легко и просто Но это не дает клеточек равного размера. По существу Вы предложили обычную полярную систему координат. Смотрим на глобус с нарисованными меридианами и параллелями - клетки там ну никак не равны

Нет у меня не полярная система, у меня куб в котором сетка не равномерная, а полученная через atg(формируется углом с одинаковым шагом). Потом нормализация этого куба до сферы. имхо площади будут одинаковые для всех кусочков.

Опишите алгоритм и формулу как вы получаете сферу? От этой формулы и будем плясать. мне кажеться через atg ресурсоемко слишком.
есть еще формулы https://math.stackexchange.com/questions/118760/can-someone-please-explain-the-cube-to-sphere-mapping-formula-to-me может в них можно получить сферу с равными углами из куба с равномерной сеткой. ( у меня нормализация координат кусочков, это разделить на длину )

т.е. еще раз мой алгоритм:
есть куб с сеткой из которого получается сфера нормализацией, я беру вектор и превращаю его в вектор на куб, через std::lower_bound нахожу в массиве по 2 точки для двух координат(третья игнориться, это грань), 4 точки на кубе через нормализацию превращаю в 4 точки на сфере.

[deMax]

Давайте определимся как нарисовать сферу для заданного step, а потом и точки ближайшие найдем без перебора.

есть еще формулы https://math.stackexchange.com/questions/118760/can-someone-please-explain-the-cube-to-sphere-mapping-formula-to-me может в них можно получить сферу с равными углами из куба с равномерной сеткой. ( у меня нормализация координат кусочков, это разделить на длину )

если найти обратную формулу(думаю не сложно) мы сможем ваш вектор на сферу превратить в вектор на куб с равномерной сеткой

[deMax]

думаю не сложно

https://stackoverflow.com/questions/2656899/mapping-a-sphere-to-a-cube
походу не совсем просто, ждем от вас работающую сборку этого ужаса... мне это тоже пригодиться чуть позже, наверное.

p.s. Есть ли исходники аналогов google earth? (детализация минимум до домов и ландшафт)

[deMax]

тут статейка появилась https://habrahabr.ru/post/335588/, может пригодиться

[Igors]

Так, ну вроде все есть, вот примерная ссылка где вся нужная математика. Итого

- мапим исходный вектор на одну из граней куба
- находим вмещающую ячейку в координатах куба (так же как на плоскости)
- переводим координаты узлов ячейки в сферу

Ну с 6 гранями все-таки возиться придется. Ладно, не умрем, распишем свитчем. Конечно все это надо отладить и убедиться что формулы верные

deMax, спасибо за энтузиазм и толчок в нужном направлении