Группа делит многоугольник на N смежных фигур

Question

Учитывая следующий многоугольник, который разделен на подполигоны, как показано ниже [слева], я хотел бы создать n количество смежных групп подполигонов одинакового размера [справа, где n=6]. Подполигоны не имеют регулярного рисунка, хотя они гарантированно будут смежными и без дырок.

This is not splitting a polygon into equal shapes, it is grouping its sub-polygons into equal, contiguous groups. The initial polygon may not have a number of sub-polygons divisible by n, and in these cases non-equally sized groups are ok. The only data I have is n, the number of groups to create, and the coordinates of the sub-polygons and their outer shell (generated through a clipping library).

My current algorithm is as follows:

list sub_polygons[] # list of polygon objects

for i in range(n - 1):
    # start a new grouping
    pick random sub_polygon from list as a starting point
    remove this sub_polygon from the list
    add this sub_polygon to the current group

    while (number of shapes in group < number needed to be added):
        add a sub_polygon that the group borders to the group
        remove this sub-polygon from the sub-polygons list

add all remaining sub-shapes to the final group

This runs into problems with contiguity, however. The below illustrates the problem - if the red polygon is added to the blue group, it cuts off the green polygon such that it cannot be added to anything else to create a contiguous group.

It's simple to add a check for this when adding a sub-polygon to a group, such as

if removing sub-polygon from list will create non-contiguous union
   pass;

but this runs into edge conditions where every possible shape that can be added creates a non-contiguous union of the available sub-polygons. In the below, my current algorithm is trying to add a sub-polygon to the red group, and with the check for contiguity is unable to add any:

Есть ли лучший алгоритм для группировки подполигонов?

Answer 1

Я думаю, что сложнее быть решенным за один проход. Несмотря на критерии, используемые для выбора следующего многоугольника, он может располагаться где-то посередине. Итак, вам нужен алгоритм, который возвращается и изменяет предыдущее решение в таких случаях. Классифицирующим алгоритмом c является BackTracking .

Но перед тем, как начать, давайте изменим представление проблемы. Эти многоугольники образуют график следующим образом:

Это псевдокод алгоритма:

function [ selected, stop ] = BackTrack(G, G2, selected, lastGroupLen, groupSize)
    if (length(selected) == length(G.Node))
        stop = true;
        return;
    end
    stop = false;
    if (lastGroupLen==groupSize)
        // start a new group
        lastGroupLen=0;
    end;
    // check continuity of remaining part of graph
    if (discomp(G2) > length(selected))
        return;
    end

    if (lastGroupLen==0)
        available = G.Nodes-selected;
    else
        available = []
        // find all nodes connected to current group
        for each node in last lastGroupLen selected nodes
            available = union(available, neighbors(G, node));
        end
        available = available-selected;
    end
    if (length(available)==0)
        return;
    end
    lastSelected = selected;
    for each node in available
        [selected, stop] =  BackTrack(G, removeEdgesTo(G2, node), 
            Union(lastSelected, node), lastGroupLen+1, groupSize);
        if (stop)
            break;
        end
    end
end

где:
selected: упорядоченный набор узлов, который можно разделить на n последовательных групп
stop: становится истинным, когда найдено решение
G: начальный граф
G2: что остатки графика после удаления всех ребер до последнего выбранного узла
lastGroupLen: количество узлов, выбранных для последней группы
groupSize: максимально допустимый размер каждой группы
discomp(): возвращает количество разрывов компоненты графика
removeEdgesTo(): удаляет все ребра, связанные с узлом

Это должно называться следующим образом:

[ selected, stop ] = BackTrack( G, G, [], 0, groupSize);

Надеюсь, это достаточно ясно. Это выглядит так:

Просто имейте в виду, что на производительность этого алгоритма может сильно влиять порядок узлов. Одним из способов ускорить его является упорядочение полигонов по центроидам:

Но есть и другое решение, если вы не удовлетворены таким результатом, как себя. Вы можете упорядочить набор available узлов по их степеням в G2, поэтому на каждом шаге сначала будут посещаться узлы, у которых меньше шансов отключить график:

И в качестве более сложной проблемы я проверил карту Ирана, в которой 262 округа. Я установил groupSize на 20:

Answer 2

Я думаю, что вы можете просто выполнить процедуру:

1. Возьмите некоторую непрерывную группу подполигонов, лежащих по периметру текущего многоугольника (если число многоугольников по периметру меньше, чем Целевой размер группы, просто возьмите их все и возьмите все, что вам нужно от следующего периметра, и повторяйте, пока не достигнете размера целевой группы).
2. Удалите эту группу и рассмотрите новый многоугольник, который состоит из остальные подполигоны.
3. Повторяйте, пока оставшийся полигон не станет пустым.

Реализация зависит от вас, но этот метод должен гарантировать, что все сформированные группы являются смежными, а оставшийся полигон сформирован на шаге 2 смежный.

РЕДАКТИРОВАТЬ:

Неважно, user58697 поднимает хорошую точку, контрпример к алгоритму выше будет многоугольник в форме 8, где один подполигон соединяет два других многоугольника.