алгоритм генерации блоков из узлов и связей
У меня есть список узлов и линий между ними, это выглядит так:
Что мне нужно, это генерировать блоки, в этом случае это будет так:
block1: 1,2,14,11
block2: 2,13,12,14
block3: 2,3,4,5,6,12,13
block4: 6,7,12
так далее…
У кого-нибудь есть идеи, как создать алгоритм для этого? Спасибо
Решение
Сначала вы можете отсортировать ребра для каждого узла по часовой стрелке. (например, сортировка по ключу atan2 (dy, dx), где dx, dy — вектор вдоль ребра.)
Затем, используя каждое ребро (и оба направления вдоль ребра) в качестве отправной точки, следуйте ребрам против часовой стрелки вокруг блоков.
Чтобы следовать против часовой стрелки, вы найдете входящее ребро в отсортированном списке для узла назначения и выйдете по следующему ребру в списке.
Например, если вы начали с ребра 11-> 14, то, когда вы дойдете до узла 14, вы будете знать, что следующим будет ребро 14-> 2 (потому что ребра для узла 14 будут иметь порядок по часовой стрелке 14-> 12 , 14-> 11, 14-> 2). Когда вы достигнете начального узла, вы определили блок.
Вы можете пометить края как используемые, когда будете следовать за ними, чтобы избежать создания одного и того же блока дважды. (Пропустите начальные ребра, если они уже отмечены как используемые в этом направлении.)
Это также сгенерирует блок 0, состоящий из фоновой области.
Другие решения
Мне кажется, что вы пытаетесь сгенерировать двойственный планарный граф.
http://en.wikipedia.org/wiki/Dual_graph
Может быть, это хорошее место для начала.