Блог пользователя dmkz

Автор dmkz, история, 13 месяцев назад, По-русски

Привет, 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. Здесь описана идея метода трапеций.

  • Проголосовать: нравится
  • +114
  • Проголосовать: не нравится

»
13 месяцев назад, # |
  Проголосовать: нравится +41 Проголосовать: не нравится

Молодец, что разобрался со сложным алгоритмом.

Отмечу, что, если ты выкладываешь вот так решение на публичное обозрение, лучше постараться причесать код. Базовое причёсывание — убрать все дефайны, инклюды, функции и переменные, которыми ты не пользуешься, а также убрать все комментарии, которые не комментируют код, а являются результатом того, что ты закомментировал какую-то строчку.

Задача выглядит так, будто в ней не нужна триангуляция. Скажи, если бы задача звучала как «найдите площадь многоугольника», ты бы тоже сводил эту задачу к задаче «найдите площадь треугольника» при помощи триангуляции? Неужели не нашлось бы чего-то менее хардкорного?

  • »
    »
    13 месяцев назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Да в том-то и дело, что я не придумал, как решать это без триангуляции. Конечно, мы можем складывать треугольники и, что может быть полезно, вычитать треугольники из какой-то объемлющей фигуры, но это ни к чему не привело.

    В дополнение скажу, что там есть подгруппы. Общий случай — это 4-я подгруппа. Третья подгруппа: выпуклый многоугольник на 100000 вершин. Вторая подгруппа: произвольный многоугольник на 1000 вершин. Первая подгруппа: дан прямоугольник. За первые 3 подгруппы дают 59 баллов.

    • »
      »
      »
      13 месяцев назад, # ^ |
        Проголосовать: нравится +16 Проголосовать: не нравится

      А искать площадь многоугольника без триангуляции как?

      • »
        »
        »
        »
        13 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Складывать определители второго порядка в процессе обхода многоугольника. Полученная площадь будет удвоенной. Знак плюс, если против часовой, знак минус, если по часовой, и ноль, если есть пересечение причём это пересечение является одной из заданных точек.

        • »
          »
          »
          »
          »
          13 месяцев назад, # ^ |
            Проголосовать: нравится +22 Проголосовать: не нравится

          Ну точно так же можно и чёрную площадь посчитать. Перебираешь треугольники, пусть очередной треугольник $$$A_1 A_i A_{i + 1}$$$. Считаешь в нём чёрную площадь $$$S_i$$$. Если $$$A_1 A_i A_{i + 1}$$$ — обход треугольника против часовой стрелки, то $$$S_i$$$ добавляется к ответу, а если по часовой стрелке — вычитается из ответа.

          • »
            »
            »
            »
            »
            »
            13 месяцев назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Понял, спасибо, днём попробую. Я думал, что никто не сдал эту задачу за две недели отбора из-за того, что там триангуляция, а не из-за того, что никто не знает, откуда формула площади многоугольника берётся, какая идея там заложена и как можно её применить здесь.

            • »
              »
              »
              »
              »
              »
              »
              13 месяцев назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

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

              • »
                »
                »
                »
                »
                »
                »
                »
                13 месяцев назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                А разве нельзя вместо треугольников считать площадь трапециями? Там тогда всё совсем просто должно быть

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  13 месяцев назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  Можно. Да, должно быть ещё проще, если брать не треугольники, а трапеции с горизонтальными или вертикальными основаниями.

              • »
                »
                »
                »
                »
                »
                »
                »
                13 месяцев назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                Да, я долго смотрел на треугольник чтобы увидеть, что это прямоугольник, из которого вырезали три прямоугольных треугольника, и то не всегда три и не всегда из одного

          • »
            »
            »
            »
            »
            »
            13 месяцев назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            Сдал, выбрав в качестве $$$A_1$$$ точку $$$(0,0)$$$ и перебрав все стороны $$$A_i A_{i+1}$$$.

            O(n) solution

            С трапециями пока не понял как делать.

            UPD. Похоже, понял, вот статья

»
13 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Wow I got chills, literally about 10 hours ago I was looking for a valid Subquadratic Polygon Triangulation after seeing the lecture 2 days ago.

But I found this code by Takanori Maehara which does the same thing in $$$O(N)$$$

real triangulate(vector<point> ps) {
  int n = ps.size();
  vector<int> next(n);
  for (int i = 0; i < n-1; ++i) next[i] = i+1;
  auto is_ear = [&](int i, int j, int k) {
    if (sign(cross(ps[j]-ps[i], ps[k]-ps[i])) <= 0) return false;
    for (int l = next[k]; l != i; l = next[l])
      if (sign(cross(ps[i]-ps[l], ps[j]-ps[l])) >= 0
       && sign(cross(ps[j]-ps[l], ps[k]-ps[l])) >= 0
       && sign(cross(ps[k]-ps[l], ps[i]-ps[l])) >= 0) return false;
    return true;
  };
  real area = 0;
  for (int i = 0; next[next[i]] != i; ) {
    if (is_ear(i, next[i], next[next[i]])) {
      area  += abs(cross(ps[next[i]]-ps[i], ps[next[next[i]]] - ps[i])) / 2;
      next[i] = next[next[i]];
    } else i = next[i];
  }
  return area;
}