Алгоритм разбиения произвольного полигона на выпуклые

Это алгоритм наименее эффективный, но самый простой для понимания. Он состоит в том, что из полигона последовательно удаляются все вогнутые углы путем разбиения полигона дополнительными ребрами (хордами). Если полигон находится справа от ребер, то одно ребро вогнутого угла должно находится слева от другого.

1. Полигон представляется, как набор контуров. Каждый контур – циклический список ребер. Может быть много внутренних и внешних контуров, в конце должны получиться только контуры выпуклых полигонов.

2. В двойном цикле обходятся все вершины полигона и находится пара вершин, наиболее подходящая для создания хорды. Хорда не должна пересекаться или совпадать ни с одним ребром из существующих контуров и убирать максимальное число вогнутых углов. Если две хорды убирают одинаковое число вогнутых углов, то предпочтение имеет смысл отдать наиболее короткой.

3. Если не найдено ни одного вогнутого угла – завершаем работу.

4. Создаем два противоположно направленных ребра и добавляем их к контурам. Нужно отметить, что если мы соединяем точки одного контура, то он разделяется на два контура, а если точки с разных контуров – два контура сливаются в один.

5. Продолжаем искать хорды.

В худшем случае алгоритм требует времени O(N³), где N – количество ребер в полигоне, но если алгоритм немного модифицировать (например, обходить не все вершины, а только вогнутые) то он становится достаточно эффективным.