Ближайшая точка в треугольной сетке

Question

Я хотел бы написать функцию, которая возвращает ближайший узел сетки (в виде точки) треугольной сетки (выполненной из равносторонних треугольников с шириной основания w, параллельной оси OX), ближайшей к некоторой точке p , Сетка начинается в точке s. Функция подписи должна выглядеть следующим образом:

def snapToGrid(p,w,s): 
    ... 

для exapmle SnapToGrid ([0.49,0], 0,5 [0,0]) == [0.5,0]

какие-либо идеи, как начать?

Answer 1

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

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

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

Это, в свою очередь, позволит вам знать, следует ли использовать triangle width как Y координат нескольких или triangle width+1/2 triangle width для Y мультипликатора.

Используя эти два значения, вы должны легко найти ближайшую комбинацию n*height и n*width, которая наиболее близка к вашей точке.

К сожалению о стене текста, если вы рисуете вашу сетку на бумаге, вы увидите, что треугольники образуют ряды узлов вдоль оси X и столбцов (для even rows) и полуколонны (для odd rows).

---

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

Кажется, что это было бы наиболее легко найти, используя K-D Tree, где точки разделения - это координаты сетки X и Y. Простой двоичный поиск затем покажет ближайшую точку сетки к координате, которую вы вводите.

Связанная статья содержит псевдокод для операций дерева K-D.

---

Вы также могли бы иметь словарь сопоставлен X координат, с каждым значением, содержащим словарь y:name пар, которые соответствуют тому, что X координат.

Это позволит вам искать узел следующим образом:

coordinate_x[<xvale>][<yvalue>] 

, который будет возвращать узел, который вы ищете, чтобы получить xvalue и yvalue просто сделать ближайший поиск по ключам словаря например:

for x in coordinate_x.keys(): 
    if x-point_x < min: 
     make x-point the closest