Подходящая структура данных для изменяемой 2D карты.
Есть карта, пространство которой разбито на столбцы. Внутри каждого столбца могут быть несколько отрезков и точек внутри отрезка.
Выглядит это как-то так:
|
| 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), но чёт не нашёл. Может быть есть какая-то стандартная структура данных для таких вещей?
Киньте в меня книгой или статьёй, или хотя бы ключевыми словами по которым стоит погулить.