Эффективный алгоритм определения того, к какому шестиугольнику относится точка

Question

Я пытаюсь найти более эффективный способ определить, к какому шестиугольнику принадлежит точка, из следующего:

1. массив точек - ради аргумента, 10000 баллов.
2. массив центральных точек шестиугольников, приблизительно 1000 шестиугольников.
3. каждая точка будет принадлежать ровно одному шестиугольнику, некоторые (большинство) шестиугольников будут пустыми.
4. Шестиугольники образуют идеальную сетку с точкой одного шестиугольника, начинающейся в верхнем левом углу (она будет перекрывать край общей площади).

Мое текущее решение работает, но довольно медленно n * (m log m) Я думаю, где n=length(points) и m=length(hexagons).

Я подозреваю, что я могу сделать намного лучше, чем это, одно решение, которое приходит на ум, состоит в том, чтобы отсортировать (только один раз) обе точки и шестиугольники по их расстоянию до некоторой произвольной точки (возможно, середина, возможно, угол), затем выполнить итерацию по точкам и по подмножеству шестиугольников, начиная с первого шестиугольника, расстояние до которого равно> = до последнего соответствующего шестиугольника. Точно так же мы могли бы перестать смотреть на шестиугольники, как только разница расстояний между (точка -> точка отсчета) и (центр шестиугольника -> точка отсчета) больше, чем «радиус» шестиугольника. Теоретически, поскольку мы знаем, что каждая точка будет принадлежать шестиугольнику, мне даже не нужно рассматривать эту возможность.

Мой вопрос: есть ли Намного лучший способ сделать это, чем этот? С точки зрения сложности, я думаю, что наихудший случай становится немного лучше n * m, но средний случай должен быть очень хорошим, вероятно, в районе n * 20 (например, нам нужно посмотреть только на 20 шестиугольников на точку). Ниже мое текущее неэффективное решение для справки.

points.forEach((p) => {
  p.hex = _.sortBy(hexes, (hex) => {
    const xDist = Math.abs(hex.middle.x - p.x);
    const yDist = Math.abs(hex.middle.y - p.y);
    return Math.sqrt((xDist * xDist) + (yDist * yDist));
  })[0];
});

Answer 1

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

• разделите абсциссу на горизонтальное расстояние междуцентрирует и округляет до ближайшего целого числа.

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

• рассмотрите этот центр и шесть вокруг него и держитесь ближе к целевой точке.

Это дает вам индексы плитки, в постоянное время.

Answer 2

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

         -----
       /       \
           -     -----        -----------> x - axis
       \       /       \
         -----     -    
       /       \       /
           -     -----
       \       /       \
         -----     -    
           |   \       /
           |     ----- 
           |  
           |          
           V
        y - axis

Вы можете думать, что ваша система координат начинается с центра шестиугольника в верхнем левом углу, а ось координат y идет вертикально вниз, а ось x идет слева направо.по горизонтали.Центры шестиугольников из вашей правильной гексагональной сетки образуют правильную квадратную сетку, где целочисленные вершины квадратной сетки преобразуются в центры многоугольников, просто умножая координаты точек в квадратной сетке на 2 x2 квадратная матрица (явная метрика)

A = a*[ sqrt(3)/2    0;

          1/2        1 ]

, где a - параметр гексагональной сетки, расстояние между центрами двух смежных с ребром шестиугольников.Это позволяет назначать целочисленные индексы [m n] для сетки, образованной гексагональными центрами.После этого, если вам задана точка с координатами [x y] в гексагональной сетке, вы можете применить обратную матрицу A

 [u; v] = A^(-1)*[x; y] 

where 

A^(-1) = (2/(a*sqrt(3)))*[  1           0   ;

                           -1/2   sqrt(3)/2 ]

([x; y] и [u; v] столбецвекторы), а затем возьмите m = floor(u) и n = floor(v), чтобы определить целочисленные координаты (также индексы) [m = floor(u), n = floor(v)] верхнего левого угла квадратной ячейки из квадратной сетки (обратите внимание, что мы выбрали координаты для обеих сеток, чтобыначать с верхнего левого угла).Таким образом, ваша точка [u, v] находится в квадрате с вершинами [m,n] [m+1, n] [m, n+1] [m+1, n+1], что означает, что исходная точка [x y] находится в одном из четырех шестиугольников, центры которых имеют индексы [m,n] [m+1, n] [m, n+1] [m+1, n+1].Таким образом, вы можете использовать это, чтобы проверить, в каком из четырех шестиугольников находится точка [x y].

Надеюсь, это поможет.

Answer 3

Обновление: оставив комментарий ниже для потомков

Я сейчас использую код, представленный здесь: https://www.redblobgames.com/grids/hexagons/

Действительно важным примечанием является то, что ваш шестиугольникСетка ДОЛЖНА начинаться с середины первых шестиугольников в (0, 0) - если этого не произойдет, вы получите чрезвычайно странные результаты, которые на первый взгляд выглядят как ошибки округления (даже после учета ожидаемого смещения).Для меня не имело значения, где был расположен первый шестиугольник, поэтому я просто установил его на (0, 0), и он отлично работал.

Старое решение

Я все еще надеюсь на оптимальное решение, но в итоге я выбрал свой собственный, который должен проверять только 6 шестиугольников на точку, с дополнительными затратами (приблизительно sqrt(m)), необходимыми дополнительно.

При приблизительно 3000 точках и 768 шестиугольниках (из которых 310 были заполнены), он правильно назначил точку шестиугольнику в 100% случаев (при проверке методом грубой силы) и занял 29 миллисекунд по сравнениюдо ~ 840 с грубой силой.

Для начала я храню шестиугольники на карте, где ключом является "${column},${row}".Столбцы технически перекрываются, поэтому для 0-й строки 0-й столбец начинается с -0.5 * hexWidth, а для строки 1 0-й столбец начинается с 0px.

Далее я начинаю с позиции верхнего левого шестиугольника, позиция "0,0", которая также должна быть в позиции 0, и увеличиваю y либо на высоту шестиугольника, либо на длину краяшестиугольник соответственно.Когда y это> точки y, я нашел вероятную строку, затем я проверяю строку выше и ниже.

Для столбца в строке я беру оба значения Math.floor и Math.ceil из x / hexWidth.

В результате получается 6 шестиугольников для проверки, с этого момента решениеидентично решению в вопросе.

Теоретически, это можно использовать, чтобы просто найти правильный шестиугольник, используя позицию x / y.Однако на практике это не сработало для меня примерно в 5% случаев с ошибками off на 1, вероятно, это проблема округления.

Некоторые другие вещи, на которые я смотрел:

1. Как подсказывает @ jason-aller, https://www.redblobgames.com/grids/hexagons/#rounding. К сожалению, это, кажется, предполагает некоторую форму преобразования нашестнадцатеричная сетка (повороты), и за ней нелегко следить - постоянно ссылаясь на функции, которые еще предстоит определить.

2. QuadTree (различные реализации), к сожалению, это вернуло примерно 100 «потенциальных совпадений» для каждой точки - поэтому улучшение производительности было не очень хорошим.Я знаю, что порядок вставки меняет полезность QuadTree, я пробовал естественный порядок, отсортированный по расстоянию сверху, слева и в случайном порядке, все они одинаково плохо работали.Вполне вероятно, что оптимальное решение с QuadTree предполагает заполнение дерева элементом, ближайшим к средней точке, а затем элементами 1/2 от средней точки до каждого угла, рекурсивно.Слишком похоже на тяжелую работу для меня!