Правильный шестиугольник по 3 точкам в гексагональной системе координат
работаю с гексагональной системой координат и появилась такая задача:
Дано три точки. Построить правильный шестиугольник, проходящий через них (все три точки должны лежать НА ГРАНИЦЕ, а не ВНУТРИ, шестиугольника). Если шестиугольников существует более одного, выбрать имеющий минимальный радиус. Если шестиугольника не существует - вернуть null.
Моих знаний в области геометрии недостаточно, чтоб понять, как определить, где находится центр такого шестиугольника, единственная идея, которая у меня возникла, это взять область вокруг каждой точки, равную максимальному расстоянию между ними и перебрать каждую точку в области, однако это очень долго и явно существует более быстрый метод это сделать.
Пример гексагональной системы координат: (Первая цифра - y, вторая - x)
60 61 62 63 64 65
50 51 52 53 54 55 56
40 41 42 43 44 45 46 47
30 31 32 33 34 35 36 37 38
21 22 23 24 25 26 27 28
12 13 14 15 16 17 18
03 04 05 06 07 08
Пример шестиугольников:
- Через точки 13, 32 и 44 проходит правильный шестиугольник с центром в 24 и радиусом 2.
- Для точек 13, 32 и 45 такого шестиугольника не существует.
- Для точек 32, 33 и 35 следует вернуть шестиугольник радиусом 3 (с центром в 62 или 05).
Надеюсь у вас будут какие-то идеи или предложения
Ответы (1 шт):
Собственно решить как-то с помощью одного уравнения я не смог, пришлось изобретать велосипед.
Алгоритм:
Моя идея состоит в том, чтоб каждую итерацию рисовать окружность радиуса R (R+1, R+2...).
Каждую такую итерацию брать все точки на границе каждой из окружностей и искать точки, которые находятся в каждой из границ.
Если несколько раз нарисовать это задание, то становится очевидно, что именно такие точки и являются центрами наших гексагональных окружностей.
Но возникает вопрос: Когда можно остановиться, перестать увеличивать радиус и вернуть null?"
Тут все просто: Увеличиваем до тех пор, пока не достигнем максимальной дистанции (т.е. пока все центры окружностей не будут находится в каждой из окружностей). Опять же, это становится очевидно после нескольких часов рисований гексов на листике.
Оптимизации:
С алгоритмом худо-бедно разобрались, теперь нужно оптимизировать, чтоб не ждать результата 20 лет.
К сожалению чего-то очень умного придумать не вышло, единственное - за начальное значение R явно имеет смысл брать максимальное расстояние между гексами, деленное на 2 (потому что только с этого значения все три окружности начинают пересекаться)
На данный момент это все оптимизации, которые были придуманы.
Код:
Используется язык kotlin т.к. именно для этого языка мне давали задачу. Весь код можно увидеть по ссылке (функция hexagonByThreePoints)
Из-за особенности структуры кода задания будет сложно перенести все сюда.