Реализовал триангуляцию многоугольника на C++ за O(n log(n))

Правка ru3, от dmkz, 2023-10-20 17:36:22

Привет, codeforces!

Сегодня, ориентируясь на статью Триангуляция полигонов с сайта neerc.ifmo.ru, я реализовал триангуляцию любых многоугольников без самопересечений (в том числе не являющихся выпуклыми) на C++.

$$$\text{ }$$$ $$$\text{ }$$$

Зачем мне это понадобилось? На отбор на RuCode 7.0 в этом году дали задачу H. Территориальное размежевание. Задача ставится следующим образом: вам дана бесконечная плоскость, покрашенная зеброй (чёрная полоска высоты $$$1$$$, белая полоска высоты $$$1$$$, чёрная ..., белая ...). На плоскости дан многоугольник без самопересечений, состоящий из $$$n\text{ }\left(3\le n \le 100000\right)$$$ вершин с целочисленными координатами $$$x_i, y_i \left(-10^9 \le x_i, y_i \le 10^9\right)$$$. Вершины указаны в порядке какого-то обхода. Требуется посчитать чёрную площадь внутри многоугольника.

Сначала я решил для случая, когда фигура — треугольник, а потом подумал, почему бы не триангулировать исходный многоугольник и не вызвать решение для треугольника $$$\left(n-2\right)$$$ раза?

Итак, всё упёрлось в триангуляцию. К сожалению, в статье выше многие моменты опускаются, есть всякие ошибки (к примеру, автор говорит, что вершина типа merge соединяется только с вершиной типа merge, хотя в примере, который он приводит, это не так, а в псевдокоде заифано на merge...). Плюс псевдокод, если его реализовывать так, как там написано, не проходит стресс-тестирование.

Я всё исправил и предоставляю свою реализацию. Итак, чтобы посчитать триангуляцию, надо вызвать следующую функцию:

std::vector<Triangle> triangulate(vpii points) {
    makeCounterClockwise(points);
    return triangulateFast(points);
}

Она вернёт вам вектор из треугольников, с которыми вы можете делать всё, что хотите. Будьте внимательны с тем, что я вырезаю вершины, которые лежат на одной прямой с соседними вершинами, ибо они бесполезны (т.е., если $$$P_{i-1}$$$, $$$P_{i}$$$ и $$$P_{i+1}$$$ лежат на одной прямой, то $$$P_i$$$ вырезается.

Исходный код (полное решение задачи H. Территориальное размежевание)

Исходный код

Это решение работает от $$$280$$$ до $$$296$$$ мс в системе Яндекс.Контест при $$$n=10^5$$$.

UPD. Обновил исходный код, удалив все неиспользуемые функции и закомментированные строки.

UPD 2. В комментариях на русском языке orz предложил решение оригинальной задачи за $$$O(N)$$$. Давайте применим тот же трюк, который делается при вычислении обычной площади многоугольника. Зафиксируем точку $$$P=(0,0)$$$ и посчитаем ориентированные площади треугольников $$$P A_i A_{i+1}$$$ для каждой стороны: если при обходе точек в данном порядке был левый поворот, то прибавим к ответу чёрную площадь внутри этого треугольника, иначе вычтем её из ответа.

Linear solution of problem H

UPD 3. k1r1t0 предложил использовать вместо треугольников трапеции, основания которых параллельны осям Ox или Oy. Я пока не понял, как складывать и вычитать трапеции, поэтому исходника нет.

Теги rucode, геометрия, триангуляция, никогда не пригодится

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru4 Русский dmkz 2023-10-20 17:55:32 242
en3 Английский dmkz 2023-10-20 17:43:19 9324
ru3 Русский dmkz 2023-10-20 17:36:22 9315
ru2 Русский dmkz 2023-10-20 17:14:59 23481
en2 Английский dmkz 2023-10-20 17:11:06 22576
en1 Английский dmkz 2023-10-20 01:56:27 51360 Initial revision for English translation
ru1 Русский dmkz 2023-10-20 01:19:04 51473 Первая редакция (опубликовано)