у меня есть список узлов и линий между ними, это выглядит следующим образом:алгоритм для генерации блока из узлов и связей
Что мне нужно, чтобы генерировать блоки, в этом случае было бы, это: блок1: 1,2,14,11 блок2: 2,13,12,14 блок3: 2,3,4,5,6,12,13 блок4: 6,7,12 и т.д .. .
Doeas Кто-нибудь есть идеи, как создать алгоритм для этого? thx
Вы можете сначала отсортировать ребра для каждого узла в порядке по часовой стрелке. (например, сортировка на основе ключа atan2 (dy, dx), где dx, dy - вектор вдоль края.)
Затем с каждым ребром (и в обоих направлениях по краю) в качестве отправной точки, по часовой стрелке вокруг блоков.
Чтобы следить за против часовой стрелки, вы найдете входящий край в отсортированном списке для узла назначения и выходите по следующему краю в списке.
Например, если вы начали с края 11-> 14, то, когда вы достигнете узла 14, вы знаете, что взять край 14-> 2 следующий (поскольку ребра для узла 14 будут по часовой стрелке 14-> 12, 14-> 11, 14-> 2). Когда вы достигнете начального узла, вы определили блок.
Вы можете пометить грани, используемые при их последующем использовании, чтобы не генерировать один и тот же блок дважды. (Пропустите стартовые края, если они уже отмечены как используемые в этом направлении.)
Это также сгенерирует блок 0, состоящий из области фона.
. Я думал об одном и том же, но я не мог решить проблему с несколькими блоками. Но, поскольку вы пишете, каждое ребро является частью одного блока в одном направлении и одного блока в другом направлении. Огромное спасибо! – user1602687
Мне кажется, что вы пытаетесь сгенерировать дуал планарного графа.
http://en.wikipedia.org/wiki/Dual_graph
Может быть хорошим местом для начала.
Если вы можете показать образец кода или как вы планируете его настройку, это может послужить хорошей отправной точкой для помощи вам. –
Мне просто нужна идея, и я могу описать ее на любом языке. Предпочитаю – user1602687