Hexagonal Lattice

Я тут заинтересовался немного гексагональными решетками, и применением их в GD.
1) подскажите, что лучше почитать/поглядеть на данную тему
2) интересуют больше всего LOD и Spiral Honeycomb Mosaic
и более конкретные вопросы.
Большая часть ссылок в гугле о SHM так или иначе ведет на вот эту страницу
Spiral Honeycomb Mosaic
там в исходниках к статье в качестве основного метода для построения SHM приводится

void HexCoord(long b10,double *X,double *Y)
{
   long i;
   double radius,theta;


   *X = 0;
   *Y = 0;
   radius = sqrt(3);
   for (i=1;i<12;i++) {
      if (i > 1)
         radius *= sqrt(7);
      if (HexDigit(b10,i) != 0) {
         theta = M_PI
               + (i - 1) * atan(sqrt(3)/2)
               + (HexDigit(b10,i) - 1) * M_PI / 3;
         *X += (radius * sin(theta));
         *Y += (radius * cos(theta));
      }
   }
}

данная функция получает на вход индекс гексагона в мозаике
преобразует индекс в 7-ричную систему исчисления, и возвращает координаты гексагона в ортогональной системе координат,
минусом данной функции я считаю применение тригонометрических функций, которые вносят погрешность в вычисления и потом допустим
при преобразовании в гексагональную систему координат (u, v) в координатах присутствует ошибка.
так вот собственно мой вопрос может кто-нить знает подобную формулу в гексагональных координатах?
либо может быть кто-нить сможет вывести/упростить формулу...
вообще преобразование из ортогональных координат в гексагональные выполняется по следующей формуле

u = 2 * x / 3;
v = y / sqrt(3) - u * 0.5;

и пока я просто выполняю преобразования выходных значений

hex.SHM.face = function (b10) {
  var pos = { x: 0, y: 0 },
      radius = hex.height,
      theta,
      b7 = b10.toString(7).split("").reverse(),
      length = b7.length;
  for (var i = 0; i < length; i++) {
    if (i > 0)
      radius *= Math.sqrt(7);
    if ( b7[i] != 0 ) {
      theta = 2 * Math.PI / 3
            - i * Math.atan(Math.sqrt(3)/2)
            - b7[i] * Math.PI / 3;
      pos.x += radius * Math.sin(theta);
      pos.y += radius * Math.cos(theta);
    }
  }
  var u = pos.x / hex.narrow_width; // вот тут преобразование
  var v = pos.y / hex.height - u * 0.5; // вот тут преобразование
  return new hex.Face(u, v);
};

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

PS: вообще мои потуги можно посмотреть вот тут http://cnonim-web.appspot.com/SHM/SHM.html

cNoNim
> 2) интересуют больше всего LOD и

Хексы обожаю :)

> и применением их в GD.

применяются - сам видел и колбасил

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

следующая цель как нить по трем координатам вычислить индекс SHM...
в статье по SHM делается тупой перебор и находится кратчайшее расстояние... что естественно медленно

тут вопрос немного не по теме наверное, но необходимо для реализации...
вот допустим у ряда
\(1,3, 8, 19, 42 ...\)
следующая формула
\(f(0)=0\\ f(n) = 2f(n-1)+n\)
вопрос: можно ли эту формулу записать без рекурсии?
если нельзя, то как-то можно найти обратную формулу?
\(n(f)=?\)

без рекурсии, но с суммой, будет вроде такая формула
\(f(n)=2^n + \sum_{k=0}^n 2^k*(n-k)\)
(если я ее правильно записал)
вопрос в принципе прежний
как избавиться от суммы? или как вывести
\(n(f)=?\)

2*2^n - n - 2
Математическая дедукция )

GeniusIsme
тем что ты вывел задается ряд
\(0,1,4,11,26...\)
а нужен ряд
\(1,3,8,19,42\)

может я формулу в #4 не правильно записал, но помоему все правильно, значит ты где то обшибся
щас попробую сам дедукцию покурить

Для твоего ряда нулевой член должен быть равен 1, а не 0, как ты написал.
В этом случае получаем:
3*2^2 - n - 2

GeniusIsme
я что то запутался :)
в общем мне нужен был ряд
\(0,1,3,8,19,42\)
оказывается )
и он задается вот так
\(f(0) = 0 \\ f(n) = 3 * 2 ^ {n - 1} - n - 1\)
в общем ты правильно вывел )))
а не покажешь как выводится, а то я что то толкового ни чего не нашел по дедукции...
читал вроде бы что-то когда-то, а вспомнить где не могу.

и да... из этой формулы ведь нельзя вывести
\(n(f)\)
?

cNoNim
> и да... из этой формулы ведь нельзя вывести
> n(f)
> ?
    Ну это не по дедукции вопрос. Но, думаю, нельзя. Возможно, можно разложить в ряд)

cNoNim
> а не покажешь как выводится
    Выводится - сильно сказано, но обо всем по порядку.
    Во-первых, я не математик, поэтому где то могу не до конца формально излагать, не обессудь )

    Дедукция на самом деле позволяет всего лишь проверить, подходит ли данная формула для получения нного члена ряда. О том, как все же получить эту формулу - чуть позже.
    Итак, формула подходит, если:
    - в общем виде разница между f(n) - f(n-1) равна разнице между соседними членами ряда по рекурсивной формуле в общем виде.
    - Формула верна хотя бы для одного члена ряда.

    Теперь - осталось всего навсего подобрать формулу! )
    Как это сделать? Начинаем пляски с бубном. Из рекурсивной формулы мы можем получить разницу между соседними членами ряда. Что дальше? Используем аналогию с непрерывными функциями - мы получили производную (разность) - надо ее проинтегрировать! Естественно, аналогия неполная, поэтому нюансы:
    - аналогию первообразной будем называть суммой
    - суммой n^k будет многочлен a0*n^(k+1) + a1*n^(k) + ... + ak+1*n^0
    - суммой m*f(n-1) будет что? Экспонента! Но с другим основанием :  a*(m+1)^n
    - остальное в том же духе, но тривиальней. Вспоминай дифференцирование, если понадобится
    Как ты, должно быть, уже заметил, у нас появилась куча коэффициентов. Где их взять? Очень просто. Находишь несколько членов ряда (по количеству коэффициентов), получаешь слау, решаешь
    При получении формулы мы использовали инженерный подход, а не математический, не мешало бы убедиться в его корректности. Применяем дедукцию. На самом деле 2 условие уже выполнено, надо проверить только первое.

    Для закрепления пример (на основе твоих данных):
    У нас есть рекурсивная формула:
    f(n) = 2 * f(n -1) + n
    Выведем разность:
    2 * f(n -1) + n - f(n-1) = f(n-1) + n
    Ищем "первообразную" - "сумму"
    f(n) = a*2^n + b * n^2 + c * n + d
    Отлично. Теперь берем последовательность членов ряда(должно хватить 4, по числу коэффициентов:
    0,1,3,8,19
    Получаем слау:
    a + d = 0
    2 * a + b + c + d = 3
    4 * a + 4 * b + 2 * c + d = 8
    8 * a + 9 * b + 3 * c + d = 19
    Решать такое, я думаю, ты умеешь ). Получаем a = 2, b = 0, c = -1, d = -2. Тут хочу отметить, что последовательность членов ряда была бы другая, если бы нулевой элемент был бы другой, или это был бы не нулевой элемент а, скажем, первый. Соответственно поменялись бы уравнения их решения, хотя рекурсивная формула не менялась. Именно этот эффект привел к недоразумению в 5 ом посте.
    Осталось проверить первое условие дедукции:
    f(n) - f(n-1) = 2*2^n - n - 2  - (2*2^(n-1) - (n-1) - 2) = 4*2^(n-1) - 2*2^(n-1) + 1 = 2*2^(n-1) + 1 + n - n =
  = 2*2^(n-1) - (n -1) - n = f(n-1) - n
  Все сошлось, мои поздравления!