О прямоугольных координатах и гексагональных сетках

Думаю, никому не нужно объяснять, насколько широко в играх (и не только) используются гексагональные сетки. Как для заданной шестиугольной ячейки найти координаты ее центра и вершин — достаточно очевидно. Обратное же преобразование (т.е. поиск ячейки, в которую попала данная точка с координатами x и y) уже не столь тривиально. О нём и пойдет речь в данном топике.

Пролог


У меня есть давняя мечта: написать интересную игру. К результату я иду очень медленно и, быть может, не совсем верно, но здесь речь пойдет не об этом. В очередной период свободного времени я захотел проработать кое-какую концепцию будущей игры, основанную на гексагональной сетке. Будучи на даче и без какого-либо признака интернета, я вынужден был сам искать алгоритм преобразования между «шестиугольными» и прямоугольными координатами. Позже я сравнил то, что получилось с известными алгоритмами и оказался приятно удивлен: самые первые ссылки в гугле по запросу «pixel to hexagon» выдавали описания алгоритмов, гораздо более трудоемких и запутанных, чем мой. Способ, эквивалентный моему, я нашел здесь.

По теме


Описание сетки

Для начала, различим два способа ориентировать шестиугольную ячейку относительно прямоугольных координат:
image
Оси я назвал буквами «m», «l» и «r» от main, left и right. (Первоначально это все было проделано на листочке, где m совпадало с осью x, а ось y смотрела вверх — поэтому «лево» и «право» здесь довольно-таки условны.) Таким образом, ось m совпадает с одной из прямоугольных осей; ось l повернута на 60 градусов относительно этой прямоугольной оси и на 30 градусов относительно второй прямоугольной оси; ось r составляет 60 градусов с первой прямоугольной осью и 150 градусов со второй. Нумерация ячеек идет вдоль осей m и l.

Для реализации сетки я написал «полевой менеджер» — класс, объект которого хранит информацию об ориентации и периоде решетки.

// В данном примере я использовал Qt-шные классы, но,
// т.к. в будущем не планирую их использовать, сделал
// соответствующие typedef-ы.
typedef QPointF MyPointF;
typedef QPoint MyPointI;

// Объявляем наш менеджер
class FieldManager
  {
  public:
  // Прямоугольная ось, вдоль которой направлена ось m.
    enum Orientation
      {
      OX,
      OY
      };

    // Конструктор по умолчанию.
    FieldManager(double period = 1, Orientation orientation = OX);

    // Метод получения координаты центра данной ячейки (прямое преобразование).
    MyPointF CellCenter(int m, int l) const;
    // Метод поиска ячейки, в которую попала точка (x, y) (обратное преобразование).
    MyPointI CellInd(double x, double y) const;

  private:
    // Период решетки.
    double m_period;
    // Ориентация решетки.
    Orientation m_orientation;
  };



Прямое преобразование

// Для начала введем константы, чтобы
// миллион раз не считать проекции.
const double sin60 = sqrt(3.0) * 0.5;
const double cos60 = 0.5;
const double sin30 = cos60;
const double cos30 = sin60;

// Реализуем конструктор.
FieldManager::FieldManager(double period, Orientation orientation)
  : m_period(period), m_orientation(orientation)
  {
  }

// Прямое преобразование. Здесь никаких хитростей.
MyPointF FieldManager::CellCenter(int m, int l) const
  {
  double along_coord = m_period * (m + l * cos60);
  double other_coord = m_period * l * sin60;
  if (m_orientation == OX)
    return MyPointF(along_coord, other_coord);
  else
    return MyPointF(other_coord, along_coord);
  }



Обратное преобразование

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

// Обратное преобразование.
MyPointI FieldManager::CellInd(double x, double y) const
  {
  // Выбираем правильную ориентацию.
  double along_coord = (m_orientation == OX) ? x : y;
  double other_coord = (m_orientation == OX) ? y : x;
  
  // Считаем проекции на оси m, l и r (в половинах периода решетки).
  // Здесь можно было обойтись меньшим количеством операций,
  // засунув, например, двойку и период решетки под косинусы и синусы
  // в отдельные константы
  int m = floor(2 * along_coord / m_period);
  int l = floor(2 * (cos60 * along_coord + sin60 * other_coord) / m_period);
  int r = floor(2 * (cos60 * along_coord - sin60 * other_coord) / m_period);

  // И, собственно, сам финт ушами:
  return MyPointI( floor((m + r + 2) / 3.0), 
                   floor((l - r + 1) / 3.0));
  }



Чтобы найти это преобразование, мне помогли следующие действия: я расчертил на бумажке сетку из этих треугольников, затем выделил на ней «линии» из шестиугольников с постоянным (с учетом округления) значением m и посмотрел, что объединяет получившиеся треугольники. Затем сделал то же самое для оси l. Видно было, что для полосы шестиугольников, направленной вдоль оси l, оси m и r разбивают пространство на ромбики, не пересекающие данную полосу (т.е. лежащие целиком внутри или снаружи от нее). Причем при фиксированном m данной полосе соответствуют три ромбика с различными l и наоборот. Отсюда и взялось округление от деления на 3. Аналогично для другого набора полос.

Заключение


На этой ноте данное повествование заканчивается. Благодарю всех, кто не обделил вниманием. Надеюсь, смог кому-нибудь помочь.

P. S.
Также надеюсь, что игра когда-нибудь увидит свет и здесь про нее также появится статья.
Поделиться публикацией
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама
Комментарии 51
  • 0
    Казалось бы всё просто, но так приятно читать! Спасибо за доставленное удовольствие!
    • +1
      Красиво. У меня с первой попытки получилось заметно сложнее.
      • +1
        А главное все сложности инкапсулировать в библиотеке))

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

        Так что интересующиеся могут почитать статью по ссылке — там тоже можно что-то почерпнуть.

        Исходник
        atom.declare( 'LibCanvas.Engines.Hex.Projection', {
        	multipliers: {
        		height: Math.cos( Math.PI / 6 ) * 2,
        		chord : 1/2 // Math.sin( Math.PI / 6 )
        	},
        
        	initialize: function (settings) {
        		settings = this.settings = new Settings({
        			baseLength : 0,
        			chordLength: null,
        			hexHeight  : null,
        			start      : new Point(0, 0)
        		}).set(settings);
        
        		if (settings.get('chordLength') == null) {
        			settings.set({
        				chordLength: settings.get('baseLength') * this.multipliers.chord,
        				hexHeight  : settings.get('hexHeight' ) * this.multipliers.height
        			});
        		}
        	},
        
        	isZero: function (c) {
        		return c[0] === 0 && c[1] === 0 && c[2] === 0;
        	},
        
        	rgbToPoint: function (coordinates) {
        		var
        			red      = coordinates[0],
        			green    = coordinates[1],
        			blue     = coordinates[2],
        			settings = this.settings,
        			base     = settings.get('baseLength'),
        			chord    = settings.get('chordLength'),
        			height   = settings.get('hexHeight'),
        			start    = settings.get('start');
        		if (red + green + blue !== 0) {
        			throw new Error( 'Wrong coordinates: ' + red + ' ' + green + ' ' + blue);
        		}
        
        		return new Point(
        			start.x + (base + chord) * red,
        			start.y + (blue - green) * height / 2
        		);
        	},
        
        	pointToRgb: function (point) {
        		var
        			settings = this.settings,
        			base     = settings.get('baseLength'),
        			chord    = settings.get('chordLength'),
        			height   = settings.get('hexHeight'),
        			start    = settings.get('start'),
        			// counting coords
        			red   = (point.x - start.x) / (base + chord),
        			blue  = (point.y - start.y - red * height / 2) / height,
        			green = 0 - red - blue;
        
        		var dist = function (c) {
        			return Math.abs(c[0] - red) + Math.abs(c[1] - green) + Math.abs(c[2] - blue);
        		};
        
        		var
        			rF = Math.floor(red  ), rC = Math.ceil(red  ),
        			gF = Math.floor(green), gC = Math.ceil(green),
        			bF = Math.floor(blue ), bC = Math.ceil(blue );
        
        		return [
        			// we need to find closest integer coordinates
        			[rF, gF, bF],
        			[rF, gC, bF],
        			[rF, gF, bC],
        			[rF, gC, bC],
        			[rC, gF, bF],
        			[rC, gC, bF],
        			[rC, gF, bC],
        			[rC, gC, bC]
        		].filter(function (v) {
        			// only correct variants - sum must be equals to zero
        			return atom.array.sum(v) == 0;
        		})
        		.sort(function (left, right) {
        			// we need coordinates with the smallest distance
        			return dist(left) < dist(right) ? -1 : 1;
        		})[0];
        	},
        
        	createPolygon: function (center) {
        		var
        			settings   = this.settings,
        			halfBase   = settings.get('baseLength') / 2,
        			halfHeight = settings.get('hexHeight')  / 2,
        			radius     = halfBase + settings.get('chordLength'),
        
        			right  = center.x + halfBase,
        			left   = center.x - halfBase,
        			top    = center.y - halfHeight,
        			bottom = center.y + halfHeight;
        
        		return new Polygon([
        			new Point(left , top),                  // top-left
        			new Point(right, top),                  // top-right
        			new Point(center.x + radius, center.y), // right
        			new Point(right, bottom),               // bottom-right
        			new Point(left , bottom),               // bottom-left
        			new Point(center.x - radius, center.y)  // left
        		]);
        	}
        });
      • 0
        А можете объяснить в чем выигрыш гексагональной сетки перед сеткой разбитой на квадраты? Для квадратных ячеек можно обходиться побитовыми сдвигами и исключить операцию деления совсем, здесь же на одно преобразивание уходит целых 5 операций деления, что невыгодно сказывается на производительности.
        • +4
          Прежде всего — у нее меньше разброс расстояний до центра (при той же площади): для квадрата максимальное расстояние 0.7071, для шестиугольника — 0.6204. Во вторых, при разбивке поля на связные области не возникает проблемы с тем, что две ячейки соприкасаются по вершине. Если уж соприкоснулись — то по углу. В третьих, кратчайший путь по клеткам между двумя точками короче. Четвертое относится к компьютерной графике — при триангуляции нам лучше брать вершины на треугольной сетке (= центры 6-угольной), и если мы хотим, чтобы вершина была усреднением точек области — усреднять как раз по шестиугольникам.
          Возможно, есть и другие преимущества.
          • +1
            поправка: не «по углу», а «по стороне» :(
          • +2
            При переходе в любую соседнюю клетку расстояние всегда одинаковое. В то время, как для квадратных клеток переход по диагонали в SQRT(2) раз длиннее, чем в стороны.
            • 0
              Ну, это если клетку по диагонали считать соседней. Тут уж каждый выбирает сам.
            • +1
              Прежде всего в игровой механике, я не могу представить себе HoMM на квадратной сетке.
              • +3
                Зачем представлять, просто поиграйте в 5 и 6 части.
              • –2
                Спросите у пчел за соты. Апологеты численных методов, основанных на гексагональных сетках, рвут волосы на груди, утверждая, что шестиугольные сетки выбрала сама природа.
                • 0
                  Еще можно спросить у игроков в бильярд, почему они не пользуются квадратной укладкой шаров.
                  Я, вообще, предпочитаю укладку усеченных октаэдров (хоть они и не равногранные). Или 24-гранников…
                • 0
                  Про выигрыш уже довольно много комментариев, мне добавить нечего.

                  А вот насчет
                  здесь же на одно преобразивание уходит целых 5 операций деления

                  не соглашусь. Как я написал в комментарии в коде, операции деления на полупериод решетки можно засунуть внутрь констант (cos и sin). Итого будет 4 сложения, 2 вычитания, 5 умножений, 2 деления и 5 округлений.
                  • 0
                    Для сетки с квадратами, например, приходится искать / рисовать спрайт в 8 положениях (4 стороны + 4 диагонали), а для гексагональной сетки, соответственно, только в 6.
                    • 0
                      Добавлю к вышесказанному, что пчелы используют шестиугольные соты из-за того, что шестиугольник с одной стороны по форме больше приближен к кругу, чем квадрат, а значит имеет большее соотношение площадь / периметр (экономия материала), а с другой — шестиугольники упаковываются без промежутков, в отличие от кругов.

                      Возможно большее количество вещей в нашей жизни могло бы / будет иметь форму шестиугольника, а не квадрата/прямоугольника (разбивка города на кварталы или форма разреза зданий например), просто форма квадрата используется в силу исторических и некоторых других причин (из-за простоты вычислений).
                      • 0
                        Разбивка города на 6-угольные кварталы неудобна для лошадей — улицы будут состоять из сплошных поворотов, с ветерком не прокатишься. Для зданий шестиугольник вообще ни к чему: там главный приоритет — не затраты материала на стены, а площадь окон в пересчете на объем, чем больше — тем лучше. Кроме того, вдоль стены прямоугольного склада/фургона можно уложить без щелей прямоугольные контейнеры любого размера. Шестиугольные так не уложишь. Далее, прямоугольник можно двигать по проходу, ширина которого равна ширине прямоугольника (проделанному прямо в решетке их укладки), а для 6-угольника придется освобождать гораздо больше места. И в жизни мы этим пользуемся очень часто. В общем, прямоугольники лучше, и в первую очередь — из-за того, что 90+90=180.
                        • 0
                          Разбивка города на 6-угольные кварталы неудобна для лошадей — улицы будут состоять из сплошных поворотов, с ветерком не прокатишься.


                          Вполне прокатишься — не обязательно же на каждом повороте куда-то заворачивать. Для перемещения из точки A в точку B нужен всего один поворот максимум, как в случае и с прямоугольниками. Ну и тем более на лошадях сейчас почти никто не катается.

                          Для зданий шестиугольник вообще ни к чему: там главный приоритет — не затраты материала на стены, а площадь окон в пересчете на объем, чем больше — тем лучше.


                          Спорный вопрос — спрошу также у свои родственников-архитекторов.

                          Кроме того, вдоль стены прямоугольного склада/фургона можно уложить без щелей прямоугольные контейнеры любого размера. Шестиугольные так не уложишь.


                          Ну а прямоугольные можно так уложить :)

                          Далее, прямоугольник можно двигать по проходу, ширина которого равна ширине прямоугольника (проделанному прямо в решетке их укладки), а для 6-угольника придется освобождать гораздо больше места. И в жизни мы этим пользуемся очень часто. В общем, прямоугольники лучше, и в первую очередь — из-за того, что 90+90=180.


                          Но у шестиугольников есть другие преимущества, а везде пользуются прямоугольниками, потому что так привычно, так же как и 10-значной системой счисления. Это мое мнение.
                          • 0
                            Вполне прокатишься — не обязательно же на каждом повороте куда-то заворачивать. Для перемещения из точки A в точку B нужен всего один поворот максимум, как в случае и с прямоугольниками. Ну и тем более на лошадях сейчас почти никто не катается.

                            Если я не поверну, то на первом же перекрестке (там сходятся три улицы под углом 120 гр, как и на любом другом) врежусь в угол квартала, находящегося передо мной. И не важно, на лошади я буду, на автомобиле или на гексацикле.
                            Ну а прямоугольные можно так уложить :)

                            Да, и все так делают. Особенно если контейнеры одинакового размера. Шестиугольники как не укладывай, а у стен останутся щели — треугольные или трапецевидные.
                            Но у шестиугольников есть другие преимущества

                            Еще одно преимущество прямоугольника или квадрата — что его можно разрезать на прямоугольники меньших размеров. И этим мы тоже часто пользуемся — и при застройке прямоугольного квартала, и при разработке карты с непостоянным разрешением, и при проектировании шкафа для одежды. Шестиугольник на меньшие 6-угольники не разрежешь.
                            • 0
                              Если я не поверну, то на первом же перекрестке (там сходятся три улицы под углом 120 гр, как и на любом другом) врежусь в угол квартала, находящегося передо мной. И не важно, на лошади я буду, на автомобиле или на гексацикле.
                              Ну а прямоугольные можно так уложить :)


                              Да, действительно не подумал и написал глупость.
                    • +3
                      Два умножения можно сэкономить:

                      double fm = along_coord * ( 2.0 / m_period);
                      double fl= (cos60 * along_coord + sin60 * other_coord) * ( 2.0 / m_period)
                      int m = floor(fm);
                      int l = floor(fl);
                      int r = floor(fm-fl);
                      • НЛО прилетело и опубликовало эту надпись здесь
                        • 0
                          Тогда уж

                          double m_period_inv2 = 2.0 / m_period;
                          double m_cos60_per=m_period_inv2/2;
                          double m_sin60_per=m_period_inv2*sqrt(3)/2;

                          double fm = along_coord * m_period_inv2;
                          double fl= (m_cos60_per * along_coord + m_sin60_per * other_coord);

                          — как и говорил автор.
                          В итоге: 3 вещественных умножения, два вещественных сложения, 3 (округления + преобразования к int), 4 целочисленных сложения и два целочисленных деления на константу (правда, там надо унести подальше начало координат — чтобы результат получился неотрицательным).
                          • 0
                            Вообще стоит приучать себя никогда не делить на 2, а умножать на 0.5, тем более если с double работаем.
                            • 0
                              С double это все равно (компилятор соптимизирует), а с целыми — конечно, надо вместо DIV писать SAR :)
                              • 0
                                Это смотря на чем писать, в Lua все числа double, и компилятор ничего оптимизировать не будет, т.к. язык интерпретируемый. Так, что приучить себя к такому подходу стоит, хуже уж точно не будет.
                                • 0
                                  Да. И вместо sqrt(3)/2 надо было написать sqrt(0.75). Можно было бы сразу вычислить в калькуляторе и выписать 20 знаков (на всякий случай) в виде константы, но мне это не очень нравится. Хотя с «пи» я так делаю, когда не помню, в каком include-файле ее искать.
                              • 0
                                Но надо не перестараться и не заменить деление на 3 умножением на 0.33…
                                Но целые числа на 0.5 умножать категорически нельзя, если не хотите получить вещественный результат. Впрочем, это все очевидно.
                                • 0
                                  Не вижу рядом корабля :)
                                  А вот насчет оптимизаций компилятора вы неправы — большую часть времени я работаю в Debug режиме и там нет оптимизаций.
                                  • 0
                                    Вы правы — компилятор действительно пишет fdiv для деления на два. Теряется на этом примерно 1 такт процессора (0.3 нс)
                                    • 0
                                      Дайте ссылку на деление за пару тактов. По моей информации на этом теряется от 10 и более тактов.
                                      • 0
                                        Я сравнивал циклы

                                        double u,s;
                                        scanf("%lf",&u);
                                        int N=1000000000;

                                        s=0;
                                        for(int i=0;i<N;i++) s+=(u+i)*0.5;

                                        и
                                        s=0;
                                        for(int i=0;i<N;i++) s+=(u+i)/2;

                                        Разница в коде была только в команде fmul для первого цикла против fdiv для второго. Время выполнения первого — 6.07 сек, второго — 6.38 сек (проверял несколько раз, ставя их в программе в разном порядке, потом усреднил). Разница — 0.3 сек, что в пересчете на один шаг цикла даст 1 такт.
                                        • 0
                                          Рекомендую больше так никогда не делать, а смотреть в даташитах процессоров, ну или хотя бы по профильным ресурсам полазить.
                                          Дело в том, что кол-во тактов зависит не только от производителя процессора, и даже не только от модели, но еще и от чисел, участвующих в делении, и от того есть ли данные в кэше процессора. В результате кол-во тактов на деление на одном AMD процессоре скачет от 15 до 70 с мелочью, у интела та же ситуация, только цифры другие. И так для всякой тригонометрии и прочего.
                                          • 0
                                            В таком случае мне придется еще и изучить алгоритм распределения команд по логическим устройствам, а данных — по конвееру, разобраться, какие команды в каждом конкретном случае будут выполняться параллельно, а какие будут ждать и сколько — и даже при этом я буду ошибаться, пытаясь определить скорость выполнения кода. Мне кажется, что эксперимент даст более надежный результат (пусть даже этот результат только для конкретных условий).
                                            И, кстати, после того, как я убрал сложение, время выполнения кода с делением уменьшилось до 2.7 сек, т.е. 10 тактов на шаг цикла. Немного не соответсятвует Вашей информации про 15-70 тактов на одно только деление. Проверил по коду — он ничего не оптимизирует.
                                            Процессор AMD FX-8120, 3.9 GHz.
                                            • 0
                                              Попробовал делить на разные числа (например, на 2.01) — получается проигрыш около 30 тактов на одно деление. Но конкретно деление на 2 проигрывает умножению на 0.5 ровно 1 такт — в нескольких разных экспериментах. Так что «доверяй, но проверяй».
                                              • 0
                                                Думаю имеет место быть оптимизация в процессоре. В любом случае тесты годятся в основном для реального кода — когда важна фактическая производительность, когда цикл большой, когда не все данные попали в кэш.
                                                • 0
                                                  В реальном коде может быть уже поздно: выбор последовательности обработки влияет на архитектуру программы. Например, мне надо решить, как эффективнее обработать массив данных (последовательно несколькими функциями, список их заранее неизвестен): завести массив функций, обрабатывающих по одному элементу (и прогонять каждый элемент по этому массиву без задержки в памяти), или заставить каждую функцию обрабатывать весь массив, и сохранять результаты тоже в массиве. При этом я уже знаю, что эта обработка является узким местом программы (так что оптимизация не будет «преждевременной»). Интуиция вообще ничего не подсказывает — и то и другое плохо. Как тут обойтись без игрушечных тестов?
                                                  • 0
                                                    Так игрушечный тест даст игрушечный результат. Когда будете тестировать на живом коде — результаты могут быть совсем другими. Потому как зависит от того — все ли данные в кеше, помещается ли цикл целиком в кеш или нет. Если же вы все это учтете в игрушечном тесте, то тест по факту уже перестанет быть игрушечным и станет кодом, который уже написан и его можно вставлять в приложение.
                                                    • 0
                                                      Да, примерно по этому пути я и иду. В результате получается два кода :(
                          • 0
                            посмотрите тут исходники. хоть там и AS3, но разберётесь. там много интересного.
                            • –3
                              Обратное преобразование нужно, чтоб узнать куда ткнул мышкой(или пальцем) игрок, угадал?
                              Для 3D такой фокус не пройдет — нужно использовать хит-тест.

                              В WPF-3D это делается вот так
                              private void viewport_MouseDown(object sender, MouseButtonEventArgs e)
                              {
                              int increment = 0;
                              RayMeshGeometry3DHitTestResult result = (RayMeshGeometry3DHitTestResult)VisualTreeHelper.HitTest(viewport, e.GetPosition(viewport));
                              Сell cl = gMap.getCell(result.MeshHit);

                              тут предполагается, что все поверхности (Mesh) запомнены в словаре, например, и getCell оборачивает к ней доступ.
                            • +1
                              Есть такая убер-статья, почитайте, мне она сильно помогла в своё время: www-cs-students.stanford.edu/~amitp/game-programming/grids/
                              • +2
                                • 0
                                  У меня как раз курсовая второго курса была на них основана. Тогда я тоже пытался сам придумать алгоритм. Придумать смог, но его вычислительная сложность оказалась что-то вроде O(n^4) :)

                                  Кстати, в первом варианте программы был занимательный баг с ее рисованием, получалось вот что:
                                  image
                                  • –2
                                    Респект)
                                    Давно был второй курс?
                                    • –2
                                      Спасибо :)
                                      В 2008-2009.
                                      Сейчас вот закончил пятый. Впереди полгода на диплом. Правда, направление уже совсеееем другое: физика высоких энергий :)
                                      • –3
                                        МФТИ или МИФИ?
                                        • –3
                                          Отнюдь. МГУ.
                                          • –3
                                            Забыл я об alma mater нашей ))
                                            позор мне
                              • 0
                                Немного переделал под свои нужды, чтобы поле рисовалось не параллелограммом, а прямоугольником:
                                В прямом преобразовании:
                                double along_coord = m_period * m + (l&1 ? m_period/2. : 0.);
                                


                                В обратном преобразовании:
                                // Считаем проекции на оси m, l и r (в половинах периода решетки).
                                // Здесь можно было обойтись меньшим количеством операций,
                                // засунув, например, двойку и период решетки под косинусы и синусы
                                // в отдельные константы
                                // int m = floor(2 * along_coord / m_period); // это уже не нужно
                                int l = floor(2 * (cos60 * along_coord + sin60 * other_coord) / m_period);
                                int r = floor(2 * (cos60 * along_coord - sin60 * other_coord) / m_period);
                                
                                // И, собственно, сам финт ушами:
                                int rc = floor((l - r + 1) / 3.0);
                                int cc = floor((along_coord + (!(rc&1) ? m_period/2. : 0.)) / m_period);
                                
                                return MyPointI(cc, rc);
                                


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