Как определить в какой гекс попали по XY координатам?

Question

Есть гексагональная сетка. Нарисовать её не проблема, но с ней остаётся другая задача. Пользователь куда-то ткнул, требуется вычислить номера строки и столбца. С квадрато-гнездовой сеткой проблем нет: делим разность координат курсора и угла сетки на размер поля, целая часть частного – это и есть номер ряда. Но гексагональная сетка имеет две особенности.

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

Перебирать все поля ещё и в тесте попадания не хочется. Можете предложить что-то быстрей? Не лучший вариант, а просто быстрей перебора полей. Только заполнять индексами внеэкранные буфера? Или есть ещё варианты? А если сетка повёрнута на 45°?

Answer 1

Искать не нужно, можно рассчитать - посложнее, чем с прямоугольной сеткой, но непринципиально.

Сначала рассчитываете "строку", деля Y-координату (отсчитываем от верхней вершины) верхнего ряда на 3/2*a, где а - сторона шестиугольника. Получается, что полоска захватывает треугольник от верхнего ряда, а нижний треугольник текущего - нет.

Если строка получилась с чётным номером (считая с нуля), то сдвига по X нет, иначе он равен a*sqrt(3)/2.

Вычитаем сдвиг из реальной X-координаты, делим результат на a*sqrt(3), находим "столбец".

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

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

Вот пример для другого (flat-top) расположения

Код на Delphi , здесь базовая точка ячейки - центр, сначала считается столбец, потом строка, затем делаются поправки при выходе за границу ячейки (точка лежит правее прямой правого-верхнего ребра или правее прямой правого-нижнего ребра. Полный код с рисованием здесь

const
  Edge = 30;
  HalfEdge = Edge div 2;
  HalfHgt = Edge * 1732 div 2000; //Sqrt(3)/2
  Hgt = HalfHgt * 2;
  Wdt = 2 * Edge;
  CellWdt = 3 * HalfEdge;
  Shift = Edge;

function TForm6.FindHexCell(x, y: Integer): TPoint;
var
  nx, remx, ny, remy, tmp: Integer;
begin
  x := x - Shift + HalfEdge;
  y := y - Shift + HalfHgt;
  nx := x div CellWdt;
  remx := ((x mod CellWdt) - CellWdt) * HalfHgt;
  tmp := -1;
  if Odd(nx) then begin
    y := y - HalfHgt;
    Inc(tmp);
  end;
  ny := y div Hgt;
  remy := ((y mod Hgt) - HalfHgt) * HalfEdge;
  if remy < remx then begin
    Inc(nx);
    Inc(ny, tmp);
  end;
  if remy > -remx then begin
    Inc(nx);
    Inc(ny, tmp + 1);
  end;
  Result.X := nx;
  Result.Y := ny;
end;

Answer 2

Исходник на c++:

#include <stdint.h>
#include <cmath>
bool Test (const double &x0, const double &y0, const uint8_t &Width, const uint8_t &Height, const double &Radius, const double &x, const double &y, uint8_t &Row, uint8_t &Column)
{
 bool   Result=false;
 double FieldWidth;
 double FieldHeight;
 double xleft;
 double ytop;
 double dy;
 int    BottomRow;
 double Bottomy0;
 double Bottomx0;
 double BottomLeft;
 double Bottomdx;
 int    BottomColumn;
 double BottomCenterx;
 int    UpRow;
 double Upy0;
 double Upx0;
 double UpLeft;
 double Updx;
 int    UpColumn;
 double UpCenterx;
 double BottomdxFromCenter;
 double BottomdyFromCenter;
 double UpdxFromCenter;
 double UpdyFromCenter;
 double Bottomr;
 double Upr;
 int    FoundRow;
 int    FoundColumn;
 FieldWidth =(Radius*(sqrt(3.0)));
 FieldHeight=(Radius*1.5);
 xleft=(x0-(Radius*(sqrt(3.0))/2.0));
 ytop =(y0+Radius);
 dx=(x   -xleft);
 dy=(ytop-y    );
 BottomRow=(floor(dy/FieldHeight));
 Bottomy0=(y0-(((double)BottomRow)*FieldHeight));
 if ((BottomRow%2)==0)
 {
  Bottomx0=x0;
  BottomLeft=xleft;
 }
 else
 {
  Bottomx0=(x0+(Radius*((sqrt(3.0))/2.0)));
  BottomLeft=x0;
 }
 Bottomdx=(x-BottomLeft);
 BottomColumn=(floor(Bottomdx/FieldWidth));
 BottomCenterx=(Bottomx0+(((double)BottomColumn)*FieldWidth));
 UpRow=(BottomRow-1);
 Upy0=(y0-(((double)UpRow)*FieldHeight));
 if ((UpRow%2)==0)
 {
  Upx0=x0;
  UpLeft=xleft;
 }
 else
 {
  Upx0=(x0+(Radius*((sqrt(3.0))/2.0)));
  UpLeft=x0;
 }
 Updx=(x-UpLeft);
 UpColumn=(floor(Updx/FieldWidth));
 UpCenterx=(Upx0+(((double)UpColumn)*FieldWidth));
 BottomdxFromCenter=(x       -BottomCenterx);
 BottomdyFromCenter=(Bottomy0-y            );
 UpdxFromCenter    =(x       -UpCenterx    );
 UpdyFromCenter    =(Upy0    -y            );
 Bottomr=(sqrt((BottomdxFromCenter*BottomdxFromCenter)+(BottomdyFromCenter*BottomdyFromCenter)));
 Upr    =(sqrt((UpdxFromCenter    *UpdxFromCenter    )+(UpdyFromCenter    *UpdyFromCenter    )));
 if (Upr<Bottomr)
 {
  FoundRowRow   =UpRow;
  FoundRowColumn=UpColumn;
 }
 else
 {
  FoundRow   =BottomRow;
  FoundColumn=BottomColumn;
 }
 if ((FoundRow%2)==0)
 {
  if ((FoundRow>=0)&&(FoundRow<((int)Height))&&(FoundColumn>=0)&&(FoundColumn<((int)Width)))
  {
   Result=true;
   Row   =((uint8_t)(FoundRow   ));
   Column=((uint8_t)(FoundColumn));
  }
 }
 else
 {
  if ((FoundRow>=0)&&(FoundRow<((int)Height))&&(FoundColumn>=0)&&(FoundColumn<((int)(Width-1))))
  {
   Result=true;
   Row   =((uint8_t)(FoundRow   ));
   Column=((uint8_t)(FoundColumn));
  }
 }
 return Result;
}

БЛОГ НА HUSL

Как определить в какой гекс попали по XY координатам?

Ответы (2 шт):