LINUX.ORG.RU

Подходящая структура данных для изменяемой 2D карты.

 , ,


2

3

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

Выглядит это как-то так:

       
     | 
 |   o 
 | | o 
 | o | 
 o | | 
 |   o 
 | | | 
 o |   
 | o   
   |   

Начало и старт отрезка изначально заданы в микросекундах, положение точки также задаётся в микросекундах.

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

Проблема в том, что мне нужно уметь вставить новые отрезки и точки в уже существующую карту и оставить всё отсортированным. Кроме того хочется уметь быстро менять местами столбцы.

Подумав я наговнякал такую структуру:

map = {
  columnsOrder: [colId1, colId2, ...],
  columns: {
    colId1: {
      segments: [
        // yOffset -- отступ относительно конца предыдущего отрезка в столбце
        //
        // points содержит набор точек внутри этого отрезка,
        // с Y координатами относительно начала отрезка
        {id, at, yOffset, yLength, points},
        ...
      ]
    }
  }
}

Отрезки имеют длину, но не имеют абсолютных координат. То же самое для точек, нет абсолютный координат, есть лишь относительные. Для того чтобы вставить новую точку нужно

  • последовательно пройтись по всем столбцам, вычислить их абсолютные координаты.
  • найти подходящие координату после которой можно вставить точку
  • сдвинуть вниз все точки внутри отрезков внутри которых находится эта координата
  • увеличить длину отрезка на 1
  • вставить точку в отрезок

Вроде должно работать, но выглядит как-то криво и переусложнённо. Я пробовал поискать что-то похожее на gamedev форумах (всё-таки 2D), но чёт не нашёл. Может быть есть какая-то стандартная структура данных для таких вещей?

Киньте в меня книгой или статьёй, или хотя бы ключевыми словами по которым стоит погулить.

Отдельно в бинарном дереве храни координаты точек и границ отрезков. Вставить точку — добавить элемент в дерево. Обойти точки и отрезки по порядку — обход дерева в глубину.

NeXTSTEP ★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.