Быстрый переход Новости Основы файлового ввода вывода Структуры данных Теория графов Геометрия - основы планиметрии Математические алгоритмы Геометрия - основы стереометрии

• Новости
• Алгоритмы
  • Структуры данных
  • Теория графов
  • Геометрия
  • Стереометрия
  • Математика

Разрез многоугольника диагональю

Дан многоугольник и индексы вершин, образующих диагональ
Необходимо разделить многоугольник на две части, лежащие с разных сторон относительно диагонали

    Создадим два списка. Пройдём по вершинам от первой исходной ко второй и добавим все рассматриваемые вершины в первый список. Пройдём от второй к первой и добавим все рассматриваемые вершины во второй список.

Асимптотика O(n).

Листинг C++

void cut_polygon_for_edge (vector < point > p, int i1, int i2, 
            vector < point > &p1, vector < point > &p2)
{
    int i;    
    int n = p.size();

    for (i = i1; i != (i2 + 1) % n; i = (i + 1) % n)
        p1.push_back (p[i]);

    for (i = i2; i != (i1 + 1) % n; i = (i + 1) % n)
        p2.push_back (p[i]);
}

22.06.2007, 15:41