7

Задан многоугольник координатами своих вершин вдоль обхода его контура. Требуется указать множество непересекающихся во внутренних точках диагоналей, разбивающих многоугольник на треугольники.

Вход: файл input.txt, , в первой строке которого записано число N – количество вершин многоугольника, потом в N строках пары целых чисел – координат вершин многоугольника в порядке обхода контура.

Ограничения: 4 ≤ N ≤ 200; каждая координата от -10000 до 10000.

Выход: файл output.txt, в первой строке которого должно быть число k, указывающее необходимое число диагоналей. В последующих k строках должно быть по два натуральных числа – номер начальной и конечной вершины соответствующей диагонали.

Дополнительные ограничения: диагонали должны лежать строго внутри многоугольника (все точки диагонали, за исключением концов, являются внутренними точками многоугольника).


Пример:

input.txt 
5
1 1
2 5
5 5
5 1
2 2

output.txt
2
2 5
3 5

Мое решение:

  1. Количество диагоналей равно (количество вершин - 3)

  2. Соединяем все точки от (2) до (количество вершин - 2) с последней точкой; если прямая между соединяемой и последней точкой лежит вне многоугольника (многоугольник невыпуклый), то берем следующую точку и соединяем ее с некоторыми (какими?) точками.

Помогите, пожалуйста, все это реализовать или подскажите, как проверить принадлежность прямой (или точки) многоугольнику и какие точки соединять, если многоугольник является невыпуклым.

2
  • Вроде число триангуляций выпуклого n-угольника, это n+2ое "Число Каталана". Они считаются довольно просто, погуглите. 4 дек 2012 в 15:09
  • @Андрей Жигунов: нужно не число, а множество, тем более, многоугольник не обязательно выпуклый.
    – VladD
    4 дек 2012 в 22:49

2 ответа 2

10
  1. Если число вершин <= 3 разбиение закончено
  2. Выбраем первую вершину как текущую (N)
  3. Если из неё нельзя провести диагональ внутри многоугольника к точке N+2, то теущей становится следующая и т.д. по кольцу. Думаю можно доказать, что этот цикл не бесконечен.
  4. "Отрезаем" треугольник от многоугольника, вершин становится на одну меньше за счёт исключения вершины N+1.
  5. Переходим к пункту 1

Наверно удобно использовать связный список.

Определение проходит ли диагональ внутри многоугольника.

Заранее определим в каком направлении задан многоугольник - по или против часовой стрелки. Далее если треугольник N N+1 N+2 обходится в противоположном направлении, значит наша диагональ снаружи - не подходит. В противном случае возможен ещё вариант когда диагональ оказывается снаружи полностью или частично по вине других внутренних углов, это проверяется далее.

Для точек N+3 и N-1 нужно проверить, чтобы эти углы при этих вершинах были больше чем соответствующие углы отрезаемого треугольника. Т.е. вершина лежит по другую сторону от диагонали относительно вершины N+1, либо угол при вершине больше развёрнутого. (См. на картинке для вершины 2 угол 2-3-1 больше чем 2-3-4, или 4 и 2 находятся по одну сторону от диагонали 3-1, поэтому диагональ 3-1 не подходит. Для вершины 8 она с вершиной 6 по одну сторону диагонали 7-1, но угол 7 больше развёрнутого, поэтому это не мешает, вершина подходит.)

Для оставшихся сторон нужно проверить не пересекают ли они данную диагональ. (Например на рисунке сторона 6-7 пересекает диагональ 4-2. Точка пересечения прямых принадлежит отрезку.) Тут четыре стороны проверять не нужно: это стороны при вершине и соседние к ним.

Определение направления обхода многоугольника

Проводим из одной вершины A1 вектора ко всем остальным A1->A2, A1->A3, ... A1->AN. Считаем сумму N-1 векторных произведений соседних векторов по порядку, нас интереует только координата z. Эта сумма по модулю равна удвоенной площади фигуры, а знак указывает направление обхода.

Оптимизация от @AnT: Для того, чтобы определить направление обхода многоугольника достаточно вычислить векторное произведение сторон инцидентных с нижней-левой вершиной (минимальный x среди минимальных y). Делать это во всех вершинах (т.е. считать полную площадь) нет никакой необходимости.

Иллюстрация к случаям рассмотренным в алгоритме. введите сюда описание изображения

9
  • +1. Но пункт "можно или нельзя провести диагональ" достаточно сложен.
    – VladD
    4 дек 2012 в 15:17
  • @VladD Да, не просто. Добавил как определить подходящая ли диагональ. Может быть есть способ выбрать отрезаемую вершину, чтобы это условие было легче проверить?
    – sercxjo
    4 дек 2012 в 18:37
  • @sercxjo: надо выбрать входящую вершину (ту, около которой угол > 180). Если такой нет, то многоугольник выпуклый, и подойдёт любая диагональ.
    – VladD
    4 дек 2012 в 19:07
  • @VladD вы наверно имеете в виду N - входящая вершина, т.е отрезается соседняя. всё рано можно придумать такую картинку, что требуется вся эта сложная проверка.
    – sercxjo
    4 дек 2012 в 19:12
  • 1
    Для того, чтобы определить направление обхода многоугольника достаточно вычислить векторное произведение сторон инцидентных с нижней-левой вершиной (минимальный x среди минимальных y). Делать это во всех вершинах (т.е. считать полную площадь) нет никакой необходимости. 8 фев 2018 в 0:04
2

Классический алгоритм решения этой задачи заключается в выполнении двух этапов

  1. Декомпозиция исходного многоугольника на монотонные многоугольники. Эта задача аккуратно решается алгоритмом сканирующей прямой.
  2. Триангуляция каждого монотонного многоугольника. Это делается несложным алгоритмом триангуляции.

В конечном итоге результирующий алгоритм получится намного проще и эффективнее, чем алгоритм "отрезания ушей" с проверкой попадания диагонали внутрь многоугольника.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.