Преобразование структуры данных двумерного сетчатого графа в дерево
У меня есть сетка:
Сетка состоит из ячеек, рекурсивно разделенных на более мелкие ячейки. Каждая дочерняя ячейка в сетке ограничена своим родителем.
Ячейки сетки хранятся в виде графа -, похожего на структуру. Каждая ячейка имеет четыре соединения, по одному в каждом углу. Каждый угол соединяется с другой ячейкой так, что края ячеек, параллельные соединению и ближайшие к нему, находятся на одном уровне. Эта сетка может быть представлена следующим JSON:
{
"grid1":
{
"topLeft": null,
"topRight": "grid2",
"bottomLeft": "grid3",
"bottomRight": "grid2",
"topLeftDirection": null,
"topRightDirection": "horizontal",
"bottomLeftDirection": "vertical",
"bottomRightDirection": "horizontal"
},
"grid2":
{
"topLeft": "grid1",
"topRight": "grid4",
"bottomLeft": "grid1",
"bottomRight": "grid5",
"topLeftDirection": "horizontal",
"topRightDirection": "horizontal",
"bottomLeftDirection": "horizontal",
"bottomRightDirection": "vertical"
},
"grid3":
{
"topLeft": "grid1",
"topRight": "grid2",
"bottomLeft": null,
"bottomRight": "grid10",
"topLeftDirection": "vertical",
"topRightDirection": "vertical",
"bottomLeftDirection": null,
"bottomRightDirection": "horizontal"
},
"grid4":
{
"topLeft": "grid2",
"topRight": "grid7",
"bottomLeft": "grid5",
"bottomRight": "grid5",
"topLeftDirection": "horizontal",
"topRightDirection": "horizontal",
"bottomLeftDirection": "vertical",
"bottomRightDirection": "vertical"
},
"grid5":
{
"topLeft": "grid4",
"topRight": "grid4",
"bottomLeft": "grid6",
"bottomRight": "grid6",
"topLeftDirection": "vertical",
"topRightDirection": "vertical",
"bottomLeftDirection": "vertical",
"bottomRightDirection": "vertical"
},
"grid6":
{
"topLeft": "grid5",
"topRight": "grid5",
"bottomLeft": "grid9",
"bottomRight": "grid8",
"topLeftDirection": "vertical",
"topRightDirection": "vertical",
"bottomLeftDirection": "vertical",
"bottomRightDirection": "horizontal"
},
"grid7":
{
"topLeft": "grid4",
"topRight": "grid11",
"bottomLeft": "grid8",
"bottomRight": "grid8",
"topLeftDirection": "horizontal",
"topRightDirection": "horizontal",
"bottomLeftDirection": "vertical",
"bottomRightDirection": "vertical"
},
"grid8":
{
"topLeft": "grid7",
"topRight": "grid7",
"bottomLeft": "grid6",
"bottomRight": "grid9",
"topLeftDirection": "vertical",
"topRightDirection": "vertical",
"bottomLeftDirection": "horizontal",
"bottomRightDirection": "vertical"
},
"grid9":
{
"topLeft": "grid6",
"topRight": "grid8",
"bottomLeft": "grid10",
"bottomRight": "grid10",
"topLeftDirection": "vertical",
"topRightDirection": "vertical",
"bottomLeftDirection": "vertical",
"bottomRightDirection": "vertical"
},
"grid10":
{
"topLeft": "grid9",
"topRight": "grid9",
"bottomLeft": "grid3",
"bottomRight": "grid12",
"topLeftDirection": "vertical",
"topRightDirection": "vertical",
"bottomLeftDirection": "horizontal",
"bottomRightDirection": "horizontal"
},
"grid11":
{
"topLeft": "grid7",
"topRight": null,
"bottomLeft": "grid12",
"bottomRight": "grid12",
"topLeftDirection": "horizontal",
"topRightDirection": null,
"bottomLeftDirection": "vertical",
"bottomRightDirection": "vertical"
},
"grid12":
{
"topLeft": "grid11",
"topRight": "grid11",
"bottomLeft": "grid10",
"bottomRight": null,
"topLeftDirection": "vertical",
"topRightDirection": "vertical",
"bottomLeftDirection": "horizontal",
"bottomRightDirection": null
}
}
Вот изображение структуры:
Глядя на график, человек может увидеть большие группы клеток, которые содержат меньшие группы клеток. Я пытаюсь разработать алгоритм, который может взять структуру данных сетки и преобразовать ее в дерево . Каждый элемент дерева является либо листом (, представляющим ячейку в сетке ), либо контейнером, содержащим более мелкие контейнеры или ячейки в сетке. Вот как выглядит сетка в виде дерева:
Пока мне не очень везло. Вот что я пробовал до сих пор:
- Я пытался работать снаружи, определяя большие части сетки, а затем разбивая их на части, чтобы найти меньшие части. Проблема в том, что трудно определить, что представляет собой контейнер, и как выбрать самый большой контейнер в сетке помимо самой сетки.
- Я попытался взять отдельные ячейки и проследить цепочку до их наибольшего родителя, а затем объединить цепочки, чтобы сформировать сетку. Проблема с этим подходом заключается в том, что родительский контейнер не всегда очевиден.
- Я попытался взять сетку, разбить ее на более мелкие сетки и разбить ее вдоль ее самого большого края. Однако при встрече с концом ребратрудно сказать, является ли конец на самом деле краем сетки или это локальный край.
- Я попытался определить, какие ячейки в сетке имеют прямых братьев и сестер (, отметив, какие соединения находятся на одной стороне ячейки, соединяющейся с той же ячейкой. Затем я помещаю их в контейнер, заменяю ячейки в структуре контейнером и повторяю процесс. Я считаю, что этот подход действительно может работать, но он кажется очень громоздким и неэффективным.
- Наконец, я рассмотрел несколько различных структур данных, включая древовидные карты. Я считаю, что древовидная карта — очень хорошая структура данных для использования в этом случае, но в моей сетке уже есть встроенная структура. Все алгоритмы, которые я смог найти и которые строили kd-деревья, не предполагали какой-либо ранее существовавшей структуры в сетке.
Я действительно застрял на этом, и я был бы признателен за любые комментарии, предложения или идеи.
Обновление
Посмотрев на ответ Йохая Тиммера, я хочу подчеркнуть, насколько важна структура сетки. Вот пример двух блоков, которые выглядят одинаково, но имеют разную структуру и, как следствие, имеют очень разные древовидные представления:
