Построение правильных многоугольников, описанных около окружности. Создание сеток шестиугольников Как из круга сделать шестиугольник

Сетки из шестиугольников (гексагональные сетки) используются в некоторых играх, но они не так просты и распространены, как сетки прямоугольников. Я коллекционирую ресурсы о сетках шестиугольников уже почти 20 лет, и написал это руководство по самым элегантным подходам, реализуемым в простейшем коде. В статье часто используются руководства Чарльза Фу (Charles Fu) и Кларка Вербрюгге (Clark Verbrugge). Я опишу различные способы создания сеток шестиугольников, их взаимосвязь, а также самые общие алгоритмы. Многие части этой статьи интерактивны: выбор типа сетки изменяет соответствующие схемы, код и тексты. (Прим. пер.: это относится только к оригиналу, советую его изучить. В переводе вся информация оригинала сохранена, но без интерактивности.) .

Примеры кода в статье написаны псевдокодом, так их легче читать и понимать, чтобы написать свою реализацию.

Геометрия

Шестиугольники - это шестигранные многоугольники. У правильных шестиугольников все стороны (грани) имеют одинаковую длину. Мы будем работать только с правильными шестиугольниками. Обычно в сетках шестиугольников используются горизонтальная (с острым верхом) и вертикальная (с плоским верхом) ориентации.

Шестиугольники с плоским (слева) и острым (справа) верхом

У шестиугольников по 6 граней. Каждая грань общая для двух шестиугольников. У шестиугольников по 6 угловых точек. Каждая угловая точка общая для трёх шестиугольников. Подробнее о центрах, гранях и угловых точках можно прочитать в моей статье о частях сеток (квадратах, шестиугольниках и треугольниках).

Углы

В правильном шестиугольнике внутренние углы равны 120°. Есть шесть «клиньев», каждый из которых является равносторонним треугольником с внутренними углами 60°. Угловая точка i находится на расстоянии (60° * i) + 30° , на size единиц от центра center . В коде:

Function hex_corner(center, size, i): var angle_deg = 60 * i + 30 var angle_rad = PI / 180 * angle_deg return Point(center.x + size * cos(angle_rad), center.y + size * sin(angle_rad))
Для заполнения шестиугольника нужно получить вершины многоугольника с hex_corner(…, 0) по hex_corner(…, 5) . Для отрисовки контура шестиугольника нужно использовать эти вершины, а затем нарисовать линию снова в hex_corner(…, 0) .

Разница между двумя ориентациями в том, что x и y меняются местами, что приводит к изменению углов: углы шестиугольников с плоским верхом равны 0°, 60°, 120°, 180°, 240°, 300°, а с острым верхом - 30°, 90°, 150°, 210°, 270°, 330°.

Углы шестиугольников с плоским и острым верхом

Размер и расположение

Теперь мы хотим расположить несколько шестиугольников вместе. В горизонтальной ориентации высота шестиугольника height = size * 2 . Вертикальное расстояние между соседними шестиугольниками vert = height * 3/4 .

Ширина шестиугольника width = sqrt(3)/2 * height . Горизонтальное расстояние между соседними шестиугольниками horiz = width .

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

Системы координат

Давайте приступим к сборке шестиугольников в сетку. В случае сеток квадратов существует только один очевидный способ сборки. Для шестиугольников же есть множество подходов. Я рекомендую использовать в качестве первичного представления кубические координаты. Осевые координаты или координаты смещений следует использовать для хранения карт и отображения координат для пользователя.

Координаты смещений

Наиболее частый подход - смещение каждого последующего столбца или строки. Столбцы обозначаются col или q . Строки обозначаются row или r . Можно смещать нечётные или чётные столбцы/строки, поэтому у горизонтальных и вертикальных шестиугольников есть по два варианта.

Горизонтальное расположение «нечет-r»

Горизонтальное расположение «чёт-r»

Вертикальное расположение «нечет-q»

Вертикальное расположение «чёт-q»

Кубические координаты

Ещё один способ рассмотрения сеток шестиугольников - видеть в них три основные оси, а не две , как в сетках квадратов. В них проявляется элегантная симметрия.

Возьмём сетку кубов и вырежем диагональную плоскость в x + y + z = 0 . Это странная мысль, но она поможет нам упростить алгоритмы сеток шестиугольников. В частности, мы сможем воспользоваться стандартными операциями из декартовых координат: суммированием и вычитанием координат, умножением и делением на скалярную величину, а также расстояниями.

Заметьте три основные оси на сетке кубов и их соотношение с шестью диагональными направлениями сетки шестиугольников. Диагональные оси сетки соответствуют основному направлению сетки шестиугольников.

Шестиугольники

Кубы

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

Изучите, как кубические координаты работают для сетки шестиугольников. При выборе шестиугольников выделяются кубические координаты, соответствующие трём осям.

1. Каждое направление сетки кубов соответствует линии на сетке шестиугольников. Попробуйте выделить шестиугольник с z , равным 0, 1, 2, 3, чтобы увидеть связь. Строка отмечена синим. Попробуйте то же самое для x (зелёный) и y (сиреневый).
2. Каждое направление сетки шестиугольника - это сочетание двух направлений сетки кубов. Например, «север» сетки шестиугольников лежит между +y и -z , поэтому каждый шаг на «север» увеличивает y на 1 и уменьшает z на 1.

Кубические координаты - разумный выбор для системы координат сетки шестиугольников. Условием является x + y + z = 0 , поэтому в алгоритмах оно должно сохраняться. Условие также гарантирует, что для каждого шестиугольника всегда будет каноническая координата.

Существует множество различных систем координат для кубов и шестиугольников. В некоторых из них условие отличается от x + y + z = 0 . Я показал только одну из множества систем. Можно также создать кубические координаты с x-y , y-z , z-x , у которых будет свой набор интересных свойств, но я не буду их здесь рассматривать.

Но вы можете возразить, что не хотите хранить 3 числа для координат, потому что не знаете, как хранить карту в таком виде.

Осевые координаты

Осевая система координат, иногда называемая «трапецеидальной», строится на основе двух или трёх координат из кубической системы координат. Поскольку у нас есть условие x + y + z = 0 , третья координата не нужна. Осевые координаты полезны для хранения карт и отображения координат пользователю. Как и в случае с кубическими координатами, с ними можно использовать стандартные операции суммирования, вычитания, умножения и деления декартовых координат.

Существует множество кубических систем координат и множество осевых. В этом руководстве я не буду рассматривать все сочетания. Я выберу две переменные, q (столбец) и r (строка). В схемах этой статьи q соответствует x , а r соответствует z , но такое соответствие произвольно, потому что можно вращать и поворачивать схемы, получая различные соответствия.

Преимущество этой системы перед сетками смещений в большей понятности алгоритмов. Недостатком системы является то, что хранение прямоугольной карты выполняется немного странно; см. раздел о сохранении карт. Некоторые алгоритмы ещё понятнее в кубических координатах, но поскольку у нас есть условие x + y + z = 0 , мы можем вычислить третью подразумеваемую координату и использовать её в этих алгоритмах. В своих проектах я называю оси q , r , s , поэтому условие выглядит как q + r + s = 0 , и я, когда нужно, могу вычислить s = -q - r .

Оси

Координаты смещения - это первое, о чём думает большинство людей, потому что они совпадают со стандартными декартовыми координатами, используемыми для сеток квадратов. К сожалению, одна из двух осей должна проходить «против шерсти», и это в результате всё усложняет. Кубическая и осевая система идут «по шерсти» и у них более простые алгоритмы, но хранение карт немного более сложное. Существует ещё одна система, называемая «чередуемой» или «двойной», но здесь мы не будем её рассматривать; некоторые считают, что с ней проще работать, чем с кубической или осевой.

Координаты смещения, кубические и осевые

Ось - это направление, в котором соответствующая координата увеличивается. Перпендикуляр к оси - это линия, на которой координата остаётся постоянной. На схемах сеток выше показаны линии перпендикуляров.

Преобразование координат

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

Осевые координаты близко связаны с кубическими, поэтому преобразование делается просто:

# преобразование кубических в осевые координаты q = x r = z # преобразование осевых в кубические координаты x = q z = r y = -x-z
В коде эти две функции могут быть записаны следующим образом:

Function cube_to_hex(h): # осевая var q = h.x var r = h.z return Hex(q, r) function hex_to_cube(h): # кубическая var x = h.q var z = h.r var y = -x-z return Cube(x, y, z)
Координаты смещения совсем немного сложнее:

Соседние шестиугольники

Дан один шестиугольник, с какими шестью шестиугольниками он находится рядом? Как и можно ожидать, легче всего дать ответ в кубических координатах, довольно просто в осевых координатах, и немного сложнее в координатах смещения. Также может потребоваться рассчитать шесть «диагональных» шестиугольников.

Кубические координаты

Перемещение на одно пространство в координатах шестиугольников приводит к изменению одной из трёх кубических координат на +1 и другой на -1 (сумма должна оставаться равной 0). На +1 могут изменяться три возможных координаты, а на -1 - оставшиеся две. Это даёт нам шесть возможных изменений. Каждое соответствует одному из направлений шестиугольника. Простейший и быстрейший способ - предварительно вычислить изменения и поместить их в таблицу кубических координат Cube(dx, dy, dz) во время компиляции:

Var directions = [ Cube(+1, -1, 0), Cube(+1, 0, -1), Cube(0, +1, -1), Cube(-1, +1, 0), Cube(-1, 0, +1), Cube(0, -1, +1) ] function cube_direction(direction): return directions function cube_neighbor(hex, direction): return cube_add(hex, cube_direction(direction))

Осевые координаты

Как и раньше, мы используем для начала кубическую систему. Возьмём таблицу Cube(dx, dy, dz) и преобразуем в таблицу Hex(dq, dr) :

Var directions = [ Hex(+1, 0), Hex(+1, -1), Hex(0, -1), Hex(-1, 0), Hex(-1, +1), Hex(0, +1) ] function hex_direction(direction): return directions function hex_neighbor(hex, direction): var dir = hex_direction(direction) return Hex(hex.q + dir.q, hex.r + dir.r)

Координаты смещения

В осевых координатах мы вносим изменения в зависимости от того, в каком месте сетки находимся. Если мы в столбце/строке смещения, то правило отличается от случая столбца/строки без смещения.

Как и раньше, мы создаём таблицу чисел, которые нужно прибавить к col and row . Однако на этот раз у нас будет два массива, один для нечётных столбцов/строк, а другой - для чётных. Посмотрите на (1,1) на рисунке карты сетки выше и заметьте, как меняются col и row меняются при перемещении в каждом из шести направлений. Теперь повторим процесс для (2,2) . Таблицы и код будут разными для каждого из четырёх типов сеток смещений, приводим соответствующий код для каждого типа сетки.

Нечет-r
var directions = [ [ Hex(+1, 0), Hex(0, -1), Hex(-1, -1), Hex(-1, 0), Hex(-1, +1), Hex(0, +1) ], [ Hex(+1, 0), Hex(+1, -1), Hex(0, -1), Hex(-1, 0), Hex(0, +1), Hex(+1, +1) ] ] function offset_neighbor(hex, direction): var parity = hex.row & 1 var dir = directions return Hex(hex.col + dir.col, hex.row + dir.row)

Чёт-r
var directions = [ [ Hex(+1, 0), Hex(+1, -1), Hex(0, -1), Hex(-1, 0), Hex(0, +1), Hex(+1, +1) ], [ Hex(+1, 0), Hex(0, -1), Hex(-1, -1), Hex(-1, 0), Hex(-1, +1), Hex(0, +1) ] ] function offset_neighbor(hex, direction): var parity = hex.row & 1 var dir = directions return Hex(hex.col + dir.col, hex.row + dir.row)


Сетка для чётной (EVEN) и нечётной (ODD) строк

Нечет-q
var directions = [ [ Hex(+1, 0), Hex(+1, -1), Hex(0, -1), Hex(-1, -1), Hex(-1, 0), Hex(0, +1) ], [ Hex(+1, +1), Hex(+1, 0), Hex(0, -1), Hex(-1, 0), Hex(-1, +1), Hex(0, +1) ] ] function offset_neighbor(hex, direction): var parity = hex.col & 1 var dir = directions return Hex(hex.col + dir.col, hex.row + dir.row)

Чёт-q
var directions = [ [ Hex(+1, +1), Hex(+1, 0), Hex(0, -1), Hex(-1, 0), Hex(-1, +1), Hex(0, +1) ], [ Hex(+1, 0), Hex(+1, -1), Hex(0, -1), Hex(-1, -1), Hex(-1, 0), Hex(0, +1) ] ] function offset_neighbor(hex, direction): var parity = hex.col & 1 var dir = directions return Hex(hex.col + dir.col, hex.row + dir.row)


Сетка для чётного (EVEN) и нечётного (ODD) столбцов

Диагонали

Перемещение в «диагональном» пространстве в координатах шестиугольников изменяет одну из трёх кубических координат на ±2 и две другие на ∓1 (сумма должна оставаться равной 0).

Var diagonals = [ Cube(+2, -1, -1), Cube(+1, +1, -2), Cube(-1, +2, -1), Cube(-2, +1, +1), Cube(-1, -1, +2), Cube(+1, -2, +1) ] function cube_diagonal_neighbor(hex, direction): return cube_add(hex, diagonals)
Как и раньше, мы можем преобразовать эти координаты в осевые, откинув одну из трёх координат, или преобразовать в координаты смещения, предварительно вычислив результаты.

Расстояния

Кубические координаты

В кубической системе координат каждый шестиугольник является кубом в трёхмерном пространстве. Соседние шестиугольники находятся в сетке шестиугольников на расстоянии 1 друг от друга, но на расстоянии 2 в сетке кубов. Это делает расчёт расстояний простым. В сетке квадратов манхэттенские расстояния равны abs(dx) + abs(dy) . В сетке кубов манхэттенские расстояния равны abs(dx) + abs(dy) + abs(dz) . Расстояние в сетке шестиугольников равно их половине:

Function cube_distance(a, b): return (abs(a.x - b.x) + abs(a.y - b.y) + abs(a.z - b.z)) / 2
Эквивалентом этой записи будет выражение того, что одна из трёх координат должна быть суммой двух других, а затем получение её в качестве расстояния. Можно выбрать форму деления пополам или форму максимального значения, приведённую ниже, но они дают одинаковый результат:

Function cube_distance(a, b): return max(abs(a.x - b.x), abs(a.y - b.y), abs(a.z - b.z))
На рисунке максимальные значения выделены цветом. Заметьте также, что каждый цвет обозначает одно из шести «диагональных» направлений.

GIF

Осевые координаты

В осевой системе третья координата выражена неявно. Давайте преобразуем из осевой в кубическую систему для расчёта расстояния:

Function hex_distance(a, b): var ac = hex_to_cube(a) var bc = hex_to_cube(b) return cube_distance(ac, bc)
Если компилятор в вашем случае встраивает (inline) hex_to_cube и cube_distance , то он сгенерирует такой код:

Function hex_distance(a, b): return (abs(a.q - b.q) + abs(a.q + a.r - b.q - b.r) + abs(a.r - b.r)) / 2
Существует множество различных способов записи расстояний между шестиугольниками в осевых координатах, но вне зависимости от способа записи расстояние между шестиугольниками в осевой системе извлекается из манхэттенского расстояния в кубической системе . Например, описанная «разность разностей» получается из записи a.q + a.r - b.q - b.r как a.q - b.q + a.r - b.r и с использованием формы максимального значения вместо формы деления пополам cube_distance . Все они аналогичны, если увидеть связь с кубическими координатами.

Координаты смещения

Как и в случае с осевыми координатами, мы преобразуем координаты смещения в кубические координаты, а затем используем расстояние кубической системы.

Function offset_distance(a, b): var ac = offset_to_cube(a) var bc = offset_to_cube(b) return cube_distance(ac, bc)
Мы будем использовать тот же шаблон для многих алгоритмов: преобразуем из шестиугольников в кубы, выполняем кубическую версию алгоритма и преобразуем кубические результаты в координаты шестиугольников (осевые или координаты смещения).

Отрисовка линий

Как нарисовать линию от одного шестиугольника до другого? Я использую линейную интерполяцию для рисования линий . Линия равномерно сэмплируется в N+1 точках и вычисляется, в каких шестиугольниках находятся эти сэмплы.

GIF

1. Сначала мы вычисляем N , которое будет расстоянием в шестиугольниках между конечными точками.
2. Затем равномерно сэмплируем N+1 точек между точками A и B. С помощью линейной интерполяции определяем, что для значений i от 0 до N , включая их, каждая точка будет A + (B - A) * 1.0/N * i . На рисунке эти контрольные точки показаны синим. В результате получаются координаты с плавающей запятой.
3. Преобразуем каждую контрольную точку (float) обратно в шестиугольники (int). Алгоритм называется cube_round (см. ниже).

Соединяем всё вместе для отрисовки линии от A до B:

Function lerp(a, b, t): // для float return a + (b - a) * t function cube_lerp(a, b, t): // для шестиугольников return Cube(lerp(a.x, b.x, t), lerp(a.y, b.y, t), lerp(a.z, b.z, t)) function cube_linedraw(a, b): var N = cube_distance(a, b) var results = for each 0 ≤ i ≤ N: results.append(cube_round(cube_lerp(a, b, 1.0/N * i))) return results
Примечания:

• Бывают случаи, когда cube_lerp возвращает точку, находящуюся точно на грани между двумя шестиугольниками. Затем cube_round сдвигает её в ту или иную сторону. Линии выглядят лучше, если их сдвигают в одном направлении. Это можно сделать, добавив «эпсилон»-шестиугольный Cube(1e-6, 1e-6, -2e-6) к одной или обеим конечным точкам перед началом цикла. Это «подтолкнёт» линию в одном направлении, чтобы она не попадала на границы граней.
• Алгоритм DDA-линии в сетках квадратов приравнивает N к максимуму расстояния по каждой из осей. Мы делаем то же самое в кубическом пространстве, что аналогично расстоянию в сетке шестиугольников.
• Функция cube_lerp должна возвращать куб с координатами в float. Если вы программируете на языке со статической типизацией, то не сможете использовать тип Cube . Вместо него можно определить тип FloatCube или встроить (inline) функцию в код отрисовки линий, если вы не хотите определять ещё один тип.
• Можно оптимизировать код, встроив (inline) cube_lerp , а затем рассчитав B.x-A.x , B.x-A.y и 1.0/N за пределами цикла. Умножение можно преобразовать в повторяющееся суммирование. В результате получится что-то вроде алгоритма DDA-линии.
• Для отрисовки линий я использую осевые или кубические координаты, но если вы хотите работать с координатами смещения, то изучите .
• Существует много вариантов отрисовки линий. Иногда требуется «сверхпокрытие» . Мне прислали код отрисовки линий с сверхпокрытием в шестиугольниках, но я пока не изучал его.

Диапазон перемещения

Диапазон координат

Для заданного центра шестиугольника и диапазона N какие шестиугольники находятся в пределах N шагов от него?

Мы можем произвести обратную работу из формулы расстояния между шестиугольниками distance = max(abs(dx), abs(dy), abs(dz)) . Чтобы найти все шестиугольники в пределах N , нам нужны max(abs(dx), abs(dy), abs(dz)) ≤ N . Это значит, что нужны все три значения: abs(dx) ≤ N и abs(dy) ≤ N и abs(dz) ≤ N . Убрав абсолютное значение, мы получим -N ≤ dx ≤ N и -N ≤ dy ≤ N и -N ≤ dz ≤ N . В коде это будет вложенный цикл:

Var results = for each -N ≤ dx ≤ N: for each -N ≤ dy ≤ N: for each -N ≤ dz ≤ N: if dx + dy + dz = 0: results.append(cube_add(center, Cube(dx, dy, dz)))
Этот цикл сработает, но будет довольно неэффективным. Из всех значений dz , которые мы перебираем в цикле, только одно действительно удовлетворяет условию кубов dx + dy + dz = 0 . Вместо этого мы напрямую вычислим значение dz , удовлетворяющее условию:

Var results = for each -N ≤ dx ≤ N: for each max(-N, -dx-N) ≤ dy ≤ min(N, -dx+N): var dz = -dx-dy results.append(cube_add(center, Cube(dx, dy, dz)))
Этот цикл проходит только по нужным координатам. На рисунке каждый диапазон является парой линий. Каждая линия - это неравенство. Мы берём все шестиугольники, удовлетворяющие шести неравенствам.

GIF

Пересекающиеся диапазоны

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

Можно подойти к этой проблеме с точки зрения алгебры или геометрии. Алгебраически каждая область выражается как условия неравенств в форме -N ≤ dx ≤ N , и нам нужно найти пересечение этих условий. Геометрически каждая область является кубом в трёхмерном пространстве, и мы пересечём два куба в трёхмерном пространстве для получения прямоугольного параллелепипеда в трёхмерном пространстве. Затем мы проецируем его обратно на плоскость x + y + z = 0 , чтобы получить шестиугольники. Я буду решать эту задачу алгебраически.

Во-первых, мы перепишем условие -N ≤ dx ≤ N в более общей форме x min ≤ x ≤ x max , и примем x min = center.x - N и x max = center.x + N . Сделаем то же самое для y и z , в результате получив общий вид кода из предыдущего раздела:

Var results = for each xmin ≤ x ≤ xmax: for each max(ymin, -x-zmax) ≤ y ≤ min(ymax, -x-zmin): var z = -x-y results.append(Cube(x, y, z))
Пересечением двух диапазонов a ≤ x ≤ b и c ≤ x ≤ d является max(a, c) ≤ x ≤ min(b, d) . Поскольку область шестиугольников выражена как диапазоны над x , y , z , мы можем отдельно пересечь каждый из диапазонов x , y , z , а затем использовать вложенный цикл для генерирования списка шестиугольников в пересечении. Для одной области шестиугольников мы принимаем x min = H.x - N and x max = H.x + N , аналогично для y и z . Для пересечения двух областей шестиугольников мы принимаем x min = max(H1.x - N, H2.x - N) и x max = min(H1.x + N, H2.x + N), аналогично для y и z . Тот же шаблон работает для пересечения трёх или более областей.

GIF

Препятствия

При наличии препятствий проще всего выполнить заливку с ограничением по расстоянию (поиск в ширину). На рисунке ниже мы ограничиваемся четырьмя ходами. В коде fringes[k] - это массив всех шестиугольников, которых можно достичь за k шагов. При каждом проходе по основному циклу мы расширяем уровень k-1 на уровень k .

Function cube_reachable(start, movement): var visited = set() add start to visited var fringes = fringes.append() for each 1 < k ≤ movement: fringes.append() for each cube in fringes: for each 0 ≤ dir < 6: var neighbor = cube_neighbor(cube, dir) if neighbor not in visited, not blocked: add neighbor to visited fringes[k].append(neighbor) return visited

Повороты

Для заданного вектора шестиугольника (разницу между двумя шестиугольниками) нам может понадобиться повернуть его, чтобы он указывал на другой шестиугольник. Это просто сделать, имея кубические координаты, если придерживаться поворота на 1/6 окружности.

Поворот на 60° вправо сдвигает каждую координату на одну позицию вправо:

[ x, y, z] to [-z, -x, -y]
Поворот на 60° влево сдвигает каждую координату на одну позицию влево:

[ x, y, z] to [-y, -z, -x]

«Поиграв» [в оригинале статьи] со схемой, можно заметить, что каждый поворот на 60° меняет знаки и физически «поворачивает» координаты. После поворота на 120° знаки снова становятся теми же. Поворот на 180° меняет знаки, но координаты поворачиваются в своё изначальное положение.

Вот полная последовательность поворота положения P вокруг центрального положения C, приводящего к новому положению R:

1. Преобразование положений P и C в кубические координаты.
2. Вычисление вектора вычитанием центра: P_from_C = P - C = Cube(P.x - C.x, P.y - C.y, P.z - C.z) .
3. Поворот вектора P_from_C как описано выше и присваивание итоговому вектору обозначения R_from_C .
4. Преобразование вектора обратно в положение прибавлением центра: R = R_from_C + C = Cube(R_from_C.x + C.x, R_from_C.y + C.y, R_from_C.z + C.z) .
5. Преобразование кубического положения R обратно в нужную систему координат.

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

Кольца

Простое кольцо

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

Function cube_ring(center, radius): var results = # этот код не работает для radius == 0; вы понимаете, почему? var cube = cube_add(center, cube_scale(cube_direction(4), radius)) for each 0 ≤ i < 6: for each 0 ≤ j < radius: results.append(cube) cube = cube_neighbor(cube, i) return results
В этом коде cube начинается на кольце, показанном большой стрелкой от центра к углу схемы. Я выбрал для начала угол 4, потому что он соответствует пути, в котором двигаются мои числа направлений. Вам может понадобиться другой начальный угол. На каждом этапе внутреннего цикла cube двигается на один шестиугольник по кольцу. Через 6 * radius шагов он завершает там, где начал.

Спиральные кольца

Проходя по кольцам по спиральному паттерну, мы можем заполнить внутренние части колец:

Function cube_spiral(center, radius): var results = for each 1 ≤ k ≤ radius: results = results + cube_ring(center, k) return results

Площадь большого шестиугольника равна сумме всех окружностей плюс 1 для центра. Для вычисления площади используйте эту формулу .

Обход шестиугольников таким способом можно также использовать для вычисления диапазона перемещения (см. выше).

Область видимости

Что видимо из заданного положения с заданным расстоянием, и не перекрывается препятствиями? Простейший способ определить это - нарисовать линию к каждому шестиугольнику в заданном диапазоне. Если линия не встречается со стенами, то вы видите шестиугольник. Перемещайте мышь по шестиугольникам [на схеме в оригинале статьи], чтобы увидеть отрисовку линий к этим шестиугольникам и стены, с которыми линии встречаются.

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

GIF

Существует много разных определений видимости. Хотите ли вы видеть центр другого шестиугольника из центра начального? Хотите ли вы видеть любую часть другого шестиугольника из центра начального? Может быть, любую часть другого шестиугольника из любой точки начального? Мешающие взгляду препятствия меньше полного шестиугольника? Область видимости - это более хитрое и разнообразное понятие, чем кажется на первый взгляд. Начнём с простейшего алгоритма, но ждите, что он обязательно правильно вычислит ответ в вашем проекте. Бывают даже случаи, когда простой алгоритм даёт нелогичные результаты.

Я хочу в дальнейшем расширять это руководство. У меня есть

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

Правильный шестиугольник можно построить, пользуясь рейсшиной и угольником 30X60°. Для выполнения этого построения принимаем горизонтальный диаметр окружности за биссектрису углов 1 и 4 (фиг. 60, б), строим стороны 1 -6, 4-3, 4-5 и 7-2, после чего прово­дим стороны 5-6 и 3-2.

Построение вписанного в окружность равностороннего треуголь­ника . Вершины такого треугольника можно построить с помощью циркуля и угольника с углами в 30 и 60° или только одного цир­куля.

Рассмотрим два способа построения вписанного в окружность рав­ностороннего треугольника.

Первый способ (фиг. 61,a) основан на том, что все три угла треугольника 7, 2, 3 содержат по 60°, а вертикальная прямая, прове­дённая через точку 7, является одновременно высотой и биссектрисой угла 1. Так как угол 0-1-2 равен 30°, то для нахождения стороны

1-2 достаточно построить по точке 1 и стороне 0-1 угол в 30°. Для этого устанавливаем рейсшину и угольник так, как это показано на фигуре, проводим линию 1-2, которая будет одной из сторон искомого треугольника. Чтобы построить сторону 2-3, устанавливаем рейсшину в положение, показанное штриховыми линиями, и через точку 2 прово­дим прямую, которая определит третью вершину треугольника.

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

Для построения треугольника (фиг. 61, б) намечаем на диаметре вершину-точку 1 и проводим диаметральную линию 1-4. Далее из точки 4 радиусом, равным D/2, описываем дугу до пересечения с окруж­ностью в точках 3 и 2. Полученные точки будут двумя другими вер­шинами искомого треугольника.

Построение квадрата, вписанного в окружность . Это построение можно выполнить при помощи угольника и циркуля.

Первый способ основан на том, что диагонали квадрата пере­секаются в центре описанного круга и наклонены к его осям под углом 45°. Исходя из этого, устанавливаем рейсшину и угольник с углами 45° так, как это показано на фиг. 62, а, и отмечаем точки 1 и 3. Далее через эти точки проводим при помощи рейсшины горизонтальные сто­роны квадрата 4-1 и 3-2. Затем с помощью рейсшины по катету угольника проводим вертикальные стороны квадрата 1-2 и 4-3.

Второй способ основан на том, что вершины квадрата делят пополам дуги окружности, заключённые между концами диаметра (фиг. 62, б). Намечаем на концах двух взаимно перпендикулярных диа­метров точки А, В и С и из них радиусом у описываем дуги до вза­имного их пересечения.

Далее через точки пересечения дуг проводим вспомогательные пря­мые, отмеченные на фигуре сплошными линиями. Точки их пересече­ния с окружностью определят вершины 1 и 3; 4 и 2. Полученные таким образом вершины искомого квадрата соединяем последовательно между собою.

Построение вписанного в окружность правильного пятиугольника.

Чтобы вписать в окружность правильный пятиугольник (фиг. 63), про­изводим следующие построения.

Намечаем на окружности точку 1 и принимаем её за одну из вер­шин пятиугольника. Делим отрезок АО пополам. Для этого радиусом АО из точки А описываем дугу до пересечения с окружностью в точ­ках M и В. Соединив эти точки прямой, получим точку К, которую соединяем затем с точкой 1. Радиусом, равным отрезку A7, описываем из точки К дугу до пересечения с диаметральной линией АО в точке H. Соединив точку 1 с точкой H, получим сторону пятиугольника. Затем раствором циркуля, равным отрезку 1H, описав дугу из вершины 1 до пересечения с окружностью, найдём вершины 2 и 5. Сделав тем же раствором циркуля засечки из вершин 2 и 5, получим остальные вер­шины 3 и 4. Найденные точки последовательно соединяем между собой.

Построение правильного пятиугольника по данной его стороне.

Для построения правильного пятиугольника по данной его стороне (фиг. 64) делим отрезок AB на шесть равных частей. Из точек А и В радиусом AB описываем дуги, пересечение которых даст точку К. Через эту точку и деление 3 на прямой AB проводим вертикальную прямую.

Получим точку 1-вершину пятиугольника. Затем радиусом, равным АВ, из точки 1 описываем дугу до пересечения с дугами, ранее проведён­ными из точек А и В. Точки пересечения дуг определяют вершины пятиугольника 2 и 5. Найденные вершины соединяем последовательно между собой.

Построение вписанного в окружность правильного семиугольника.

Пусть дана окружность диаметра D; нужно вписать в неё правильный семиугольник (фиг. 65). Делим вертикальный диаметр окружности на семь равных частей. Из точки 7 радиу­сом, равным диаметру окружности D, описываем дугу до пересечения с про­должением горизонтального диаметра в точке F. Точку F назовём полюсом многоугольника. Приняв точку VII за одну из вершин семиугольника, прово­дим из полюса F через чётные деления вертикального диаметра лучи, пересече­ние которых с окружностью определят вершины VI, V и IV семиугольника. Для получения вершин / - // - /// из точек IV, V и VI проводим до пересечения с окружностью горизонтальные прямые. Найденные вершины соединяем после­довательно между собой. Семиугольник может быть построен путём проведе­ния лучей из полюса F и через нечётные деления вертикального диаметра.

Приведённый способ годен для построения правильных многоуголь­ников с любым числом сторон.

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

Есть ли поблизости от Вас карандаш? Взгляните-ка на его сечение - оно представляет собой правильный шестиугольник или, как его еще называют, гексагон. Такую форму имеет также сечение гайки, поле гексагональных шахмат, некоторых сложных молекул углерода (к примеру, графит), снежинка, пчелиные соты и другие объекты. Гигантский правильный шестиугольник был недавно обнаружен в Не кажется ли странным столь частое использование природой для своих творений конструкций именно этой формы? Давайте рассмотрим поподробнее.

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

• Длина его сторон соответствует радиусу описанной окружности. Из всех это свойство имеет лишь правильный шестиугольник.
• Углы равны между собой, и величина каждого составляет 120°.
• Периметр гексагона можно найти по формуле Р=6*R, если известен радиус описанной вокруг него окружности, или Р=4*√(3)*r, если окружность в него вписана. R и r - радиусы описанной и вписанной окружности.
• Площадь, которую занимает правильный шестиугольник, определяется следующим образом: S=(3*√(3)*R 2)/2. Если радиус неизвестен, вместо него подставляем длину одной из сторон - как известно, она соответствует длине радиуса описанной окружности.

У правильного шестиугольника есть одна интересная особенность, благодаря которой он получил в природе такое широкое распространение, - он способен заполнить любую поверхность плоскости без наложений и пробелов. Существует даже так называемая лемма Пала, согласно которой правильный гексагон, сторона которого равна 1/√(3), представляет собой универсальную покрышку, то есть может покрыть любое множество с диаметром в одну единицу.

Теперь рассмотрим построение правильного шестиугольника. Есть несколько способов, самый простой из которых предполагает использование циркуля, карандаша и линейки. Вначале рисуем циркулем произвольную окружность, затем в произвольном месте на этой окружности делаем точку. Не меняя раствора циркуля, ставим острие в эту точку, отмечаем на окружности следующую насечку, продолжаем так до тех пор, пока не получим все 6 точек. Теперь остается лишь соединить их между собой прямыми отрезками, и получится искомая фигура.

На практике бывают случаи, когда требуется нарисовать шестиугольник большого размера. Например, на двухуровневом гипсокартонном потолке, вокруг места крепления центральной люстры, нужно установить на нижнем уровне шесть небольших светильников. Циркуль таких размеров найти будет очень и очень сложно. Как поступить в этом случае? Как вообще нарисовать большую окружность? Очень просто. Нужно взять крепкую нить нужной длины и обвязать один из ее концов напротив карандаша. Теперь осталось лишь найти помощника, который бы прижал к потолку в нужной точке второй конец нити. Конечно, в этом случае возможны незначительные погрешности, но вряд ли они вообще будут заметны постороннему человеку.

Правильный описанный треугольник строят следующим образом (рисунок 38). Из центра заданной окружности радиуса R 1 проводят окружность радиусом R 2 = 2R 1 и делят ее на три равные части. Точки деления А, В, С являются вершинами правильного треугольника, описанного около окружности радиуса R 1 .

Рисунок 38

Правильный описанный четырехугольник (квадрат) можно построить с помощью циркуля и линейки (рисунок 39). В заданной окружности проводят два взаимно перпендикулярных диаметра. Приняв точки пересечения диаметров с окружностью за центры, радиусом окружности R описывают дуги до взаимного их пересечения в точках А, В, С,D . Точки A , B , C , D и являются вершинами квадрата, описанного около данной окружности.

Рисунок 39

Для построения правильного описанного шестиугольника необходимо вначале построить вершины описанного квадрата указанным выше способом (рисунок 40, а). Одновременно с определением вершин квадрата заданную окружность радиуса R делят на шесть равных частей в точках 1, 2, 3, 4, 5, 6 и проводят вертикальные стороны квадрата. Проведя через точки деления окружности 2–5 и 3–6 прямые до пересечения их с вертикальными сторонами квадрата (рисунок 40, б), получают вершины А, В, D, Е описанного правильного шестиугольника.

Рисунок 40

Остальные вершины C и F определяют с помощью дуги окружности радиуса OA , которая проводится до пересечения ее с продолжением вертикального диаметра заданной окружности.
3 СОПРЯЖЕНИЯ

Построение вписанного в окружность правильного шестиуголь­ника. Построение правильного пятиугольника по данной его стороне. Переставьте иглу циркуля в точку пересечения только что начерченной дуги с окружностью. Это построение можно выполнить при помощи угольника и циркуля. Правильный шестиугольник можно построить, пользуясь рейсшиной и угольником 30X60°. Постройте точки вершин углов правильного шестиугольника.

Построение вписанного в окружность равностороннего треуголь­ника. Вершины такого треугольника можно построить с помощью циркуля и угольника с углами в 30 и 60° или только одного цир­куля. Чтобы построить сторону 2-3, устанавливаем рейсшину в положение, показанное штриховыми линиями, и через точку 2 прово­дим прямую, которая определит третью вершину треугольника.

Метод 1 из 3: Рисуем идеальный шестиугольник при помощи циркуля

Намечаем на окружности точку 1 и принимаем её за одну из вер­шин пятиугольника. Пусть дана окружность диаметра D; нужно вписать в неё правильный семиугольник (фиг. 65). Делим вертикальный диаметр окружности на семь равных частей. Из точки 7 радиу­сом, равным диаметру окружности D, описываем дугу до пересечения с про­должением горизонтального диаметра в точке F. Точку F назовём полюсом многоугольника.

Именно на умении строить биссектрисы углов и серединные перпендикуляры отрезков и основывается методика построения правильных многоугольников

В первой колонке этой таблицы указаны числа сторон правильного вписанного многоугольника, а во второй-коэффициенты. Длина стороны заданного многоугольника получится от умножения радиуса данной окружности на коэффициент, соответствующий числу сторон этого многоугольника.

Тема этого видеоурока – «Построение правильных многоугольников». Также еще раз дадим определение правильному многоугольнику, изобразим его графически, после чего еще раз убедимся, что центры вписанной и описанной окружностей вокруг такой фигуры будут совпадать. В этот многоугольник всегда можно вписать окружность и около него всегда можно описать окружность. В ходе предыдущих уроков мы выяснили, что базовую роль для описания свойств многоугольников играют биссектрисы его углов и серединные перпендикуляры к его сторонам.

4. Получили искомый правильный треугольник АВС. Задача решена. 3. Поместив одну ножку циркуля в произвольную точки А1 на окружности, при помощи второй ножки отметим на той же окружности точку А2 и соединим ее с точкой А1. Получим первую сторону шестиугольника. 3. При помощи серединных перпендикуляров к сторонам многоугольника, опущенным из точки О, разделим все его стороны и все дуги окружности, заключенные между его соседними вершинами, пополам.

Геометрические построения являются одной из важных частей обучения. Игла должна проткнуть начерченную линию. Чем точнее будет установлен циркуль, тем точнее будет построение. Начертите еще одну дугу, пересекающую окружность. Последовательно соедините все шесть точек пересечения дуг с первоначально начерченной окружностью. В этом случае шестиугольник может получиться неправильным.

Для получения вершин / - // - /// из точек IV, V и VI проводим до пересечения с окружностью горизонтальные прямые

Найденные вершины соединяем после­довательно между собой. Семиугольник может быть построен путём проведе­ния лучей из полюса F и через нечётные деления вертикального диаметра. Центры обеих окружностей совпадают (точка О на Рис. 1). Также на рисунке приведены радиусы описанной (R) и вписанной (r) окружностей.

Построение шестиугольника основано на том, что сторона его равна радиусу описанной окружности. На данном занятии мы рассмотрим способы построения правильных многоугольников с помощью циркуля и линейки. Второй способ основан на том, что,если построить правильный шестиугольник, вписанный в окружность, и затем соединить его вер­шины через одну, то получится равносторонний треугольник. Приведённый способ годен для построения правильных многоуголь­ников с любым числом сторон.