РЕДАКТИРОВАТЬ: этот вопрос сложнее, чем я думал вначале, я перепишу свой ответ с некоторыми рабочими, однако я не уверен, что путь решения какой-либо улучшения по другим ответам.
вопрос можно перефразировать: при любом x, y найдите шестиугольник, центр которого ближе всего к x, y
, то есть минимизируйте dist_squared (Hex [n] .center, (x, y)) над n (квадрат означает, что выне нужно беспокоиться о квадратных корнях, которые экономят некоторый процессор)
Однако сначала мы должны сузить число шестиугольников для проверки - мы можем сузить их максимум до 5 следующим способом:
Итак, первый шаг - это выразить вашу точку (x, y) в УФ-пространстве, т.е. (x, y) = лямбда U + mu V, то есть = (лямбда, мю) в УФ-пространстве
Это просто двумерное матричное преобразование (http://playtechs.blogspot.co.uk/2007/04/hex-grids.html может быть полезно, если вы не понимаете линейные преобразования).
Теперь с учетом точки (лямбда, мю), если мы округляем оба до ближайшего целого числа, то имеем:
Везде в пределах Зеленого квадрата отображается обратно в (2,1)
Таким образом, большинство точек в этом Зеленом квадрате будут правильными, т.е. они находятся в шестиугольнике (2,1).
Но некоторые точки должны возвращать шестиугольник # (2,2), то есть:
Точно так же некоторые должны возвращать шестиугольник # (3,1).И затем в противоположном углу этого зеленого параллелограмма будут еще 2 области.
Итак, подведем итог: если int (lambda, mu) = (p, q), то мы, вероятно, находимся внутри шестиугольника (p,q) но мы также можем быть внутри шестиугольников (p + 1, q), (p, q + 1), (p-1, q) или (p, q-1)
Несколько способов определениякакой из них имеет место.Проще всего было бы преобразовать центры всех этих пяти шестиугольников обратно в исходную систему координат и найти ближайшую к нашей точке точку.
Но оказывается, что вы можете сузить это до ~ 50%время без проверки расстояния, ~ 25% времени - одна проверка расстояния, а оставшиеся ~ 25% времени - 2 проверки расстояния (я угадываю цифры, глядя на области, на которых работает каждая проверка):
p,q = int(lambda,mu)
if lambda * mu < 0.0:
// opposite signs, so we are guaranteed to be inside hexagon (p,q)
// look at the picture to understand why; we will be in the green regions
outPQ = p,q
else:
// circle check
distSquared = dist2( Hex2Rect(p,q), Hex2Rect(lambda, mu) )
if distSquared < .5^2:
// inside circle, so guaranteed inside hexagon (p,q)
outPQ = p,q
else:
if lambda > 0.0:
candHex = (lambda>mu) ? (p+1,q): (p,q+1)
else:
candHex = (lambda<mu) ? (p-1,q) : (p,q-1)
И этот последний тест можно привести в порядок:
else:
// same sign, but which end of the parallelogram are we?
sign = (lambda<0) ? -1 : +1
candHex = ( abs(lambda) > abs(mu) ) ? (p+sign,q) : (p,q+sign)
Теперь мы сузили его до еще одного возможного шестиугольника, нам просто нужно найти, который ближе:
dist2_cand = dist2( Hex2Rect(lambda, mu), Hex2Rect(candHex) )
outPQ = ( distSquared < dist2_cand ) ? (p,q) : candHex
Функция Dist2_hexSpace (A, B) привела бы в порядок вещи.