Skip to content

🔷 Геометрия на Полигони

Полигонът е затворена верига от отсечки. В състезанията върховете обикновено се дават в ред (по или обратно на часовниковата стрелка).

Полигонът се нарича прост, ако неговите страни не се пресичат една с друга (освен в общите върхове). Полигонът се нарича изпъкнал, ако всички вътрешни ъгли са по-малки от 180° и всеки отрезък между две точки в полигона лежи изцяло вътре в него.

0. Основни Дефиниции и Структури

struct Point {
    long long x, y;
    Point(long long x = 0, long long y = 0) : x(x), y(y) {}
    Point operator-(const Point& p) const { return Point(x - p.x, y - p.y); }
    Point operator+(const Point& p) const { return Point(x + p.x, y + p.y); }
};

// Векторно произведение (Cross Product)
long long cross(const Point& a, const Point& b) {
    return (long long)a.x * b.y - (long long)a.y * b.x;
}

// Скаларно произведение (Dot Product)
long long dot(const Point& a, const Point& b) {
    return (long long)a.x * b.x + (long long)a.y * b.y;
}

// Дължина на вектор на квадрат
long long len2(const Point& a) {
    return a.x * a.x + a.y * a.y;
}

1. Лице на Полигон (Shoelace Formula)

Площта на произволен прост полигон с върхове \((x_1, y_1), \dots, (x_n, y_n)\) може да се пресметне чрез формулата на обущарския връзка (Shoelace Formula). Тя е базирана на ориентираните лица на трапеци (или триъгълници).

\(2 \cdot S = \left| \sum_{i=1}^{n} (x_i y_{i+1} - x_{i+1} y_i) \right|\)

където \((x_{n+1}, y_{n+1}) = (x_1, y_1)\).

Геометрична Интуиция

Формулата работи, като разглежда всяка страна на полигона и изчислява "ориентираното лице" на трапеца, образуван между тази страна и x-оста. Ако върховете са в обратен ред на часовниковата стрелка, сумата дава положителна площ; ако са по часовниковата стрелка – отрицателна.

Имплементация

// Връща удвоеното лице (2 * S)
long long polygonArea2(const vector<Point>& p) {
    long long area = 0;
    int n = p.size();
    for (int i = 0; i < n; i++) {
        area += cross(p[i], p[(i + 1) % n]);
    }
    return abs(area); // Абсолютна стойност за положително лице
}

// Връща действителното лице (може да е дробно)
double polygonArea(const vector<Point>& p) {
    return polygonArea2(p) / 2.0;
}

// Знаково лице (позитивно ако върховете са counter-clockwise)
long long signedArea2(const vector<Point>& p) {
    long long area = 0;
    int n = p.size();
    for (int i = 0; i < n; i++) {
        area += cross(p[i], p[(i + 1) % n]);
    }
    return area;
}

Пример

За квадрат с върхове \((0, 0), (2, 0), (2, 2), (0, 2)\): - \(2S = |0 \cdot 0 - 2 \cdot 0 + 2 \cdot 2 - 2 \cdot 0 + 2 \cdot 2 - 0 \cdot 2 + 0 \cdot 0 - 0 \cdot 2| = |0 + 4 + 4 + 0| = 8\) - \(S = 4\) (коректно за квадрат със страна 2)

2. Периметър на Полигон

Периметърът е сумата от дължините на всички страни на полигона.

// Периметър (дробно число)
double polygonPerimeter(const vector<Point>& p) {
    double perimeter = 0;
    int n = p.size();
    for (int i = 0; i < n; i++) {
        Point diff = p[(i + 1) % n] - p[i];
        perimeter += sqrt(len2(diff));
    }
    return perimeter;
}

// За целочислени координати - на квадрат
long long polygonPerimeter2(const vector<Point>& p) {
    long long perimeter2 = 0;
    int n = p.size();
    for (int i = 0; i < n; i++) {
        Point diff = p[(i + 1) % n] - p[i];
        perimeter2 += len2(diff);
    }
    return perimeter2;
}

3. Теорема на Пик (Pick's Theorem)

За полигон, чиито върхове са целочислени координати (lattice polygon): \(S = I + \frac{B}{2} - 1\)

  • \(S\): Лице на полигона.
  • \(I\): Брой целочислени точки вътре в полигона.
  • \(B\): Брой целочислени точки по границата (boundary).

Намиране на B (Boundary Points)

\(B\) може да се намери, като се сумират НОД на разликите в координатите за всяка страна: \(B = \sum_{i=1}^{n} \gcd(|x_i - x_{i+1}|, |y_i - y_{i+1}|)\)

long long gcd(long long a, long long b) {
    return b ? gcd(b, a % b) : a;
}

// Брой целочислени точки по границата
long long boundaryPoints(const vector<Point>& p) {
    long long B = 0;
    int n = p.size();
    for (int i = 0; i < n; i++) {
        Point diff = p[(i + 1) % n] - p[i];
        B += gcd(abs(diff.x), abs(diff.y));
    }
    return B;
}

// Брой целочислени точки вътре (използвайки Pick's Theorem)
long long interiorPoints(const vector<Point>& p) {
    long long area2 = polygonArea2(p);
    long long B = boundaryPoints(p);
    // S = I + B/2 - 1  =>  I = S - B/2 + 1
    // 2S = 2I + B - 2  =>  I = (2S - B + 2) / 2
    return (area2 - B + 2) / 2;
}

Пример

За триъгълник с върхове \((0, 0), (3, 0), (0, 4)\): - Лице: \(S = \frac{3 \cdot 4}{2} = 6\) - \(B = \gcd(3, 0) + \gcd(3, 4) + \gcd(0, 4) = 3 + 1 + 4 = 8\) - \(I = S - \frac{B}{2} + 1 = 6 - 4 + 1 = 3\)

4. Точка в Полигон (Point in Polygon)

4.1. Изпъкнал полигон

За изпъкнал полигон може да се реши за \(O(\log N)\) с двоично търсене по ъглите.

// Проверка дали точка е в изпъкнал полигон (O(log n))
bool inConvexPolygon(const vector<Point>& p, Point pt) {
    int n = p.size();
    // Проверка дали точката е от правилната страна на всички страни
    bool pos = false, neg = false;
    for (int i = 0; i < n; i++) {
        long long cp = cross(p[(i + 1) % n] - p[i], pt - p[i]);
        if (cp > 0) pos = true;
        if (cp < 0) neg = true;
    }
    return !(pos && neg); // Вътре, ако всички cross products са с един знак
}

4.2. Произволен полигон (Ray Casting)

За произволен (не непременно изпъкнал) полигон използваме алгоритъма Ray Casting.

Идея: Пускаме лъч от точката \(P\) надясно (към \(+\infty\)). Броим колко пъти лъчът пресича страните на полигона. * Нечетен брой пресичания \(\implies\) Точката е вътре. * Четен брой (включително 0) \(\implies\) Точката е вън.

Гранични случаи: - Точката лежи точно на ръб - Лъчът минава през връх на полигона - Лъчът е успореден на някоя страна

// Ray Casting алгоритъм - произволен полигон
bool isInside(const vector<Point>& p, Point pt) {
    int n = p.size();
    bool inside = false;
    for (int i = 0, j = n - 1; i < n; j = i++) {
        // Проверяваме дали лъчът пресича ръба (j, i)
        if (((p[i].y > pt.y) != (p[j].y > pt.y)) &&
            (pt.x < (p[j].x - p[i].x) * (pt.y - p[i].y) / (double)(p[j].y - p[i].y) + p[i].x)) {
            inside = !inside;
        }
    }
    return inside;
}

// Проверка дали точка лежи на границата на полигона
bool onBoundary(const vector<Point>& p, Point pt) {
    int n = p.size();
    for (int i = 0; i < n; i++) {
        Point a = p[i], b = p[(i + 1) % n];
        // Проверка дали pt лежи на отсечката [a, b]
        if (cross(pt - a, b - a) == 0 &&
            min(a.x, b.x) <= pt.x && pt.x <= max(a.x, b.x) &&
            min(a.y, b.y) <= pt.y && pt.y <= max(a.y, b.y)) {
            return true;
        }
    }
    return false;
}

// Пълна проверка: вътре, вън или на границата
// Връща: 0 = вън, 1 = на границата, 2 = вътре
int pointInPolygon(const vector<Point>& p, Point pt) {
    if (onBoundary(p, pt)) return 1;
    return isInside(p, pt) ? 2 : 0;
}

4.3. Winding Number Algorithm

Алтернативен метод, който брои колко пъти полигонът "обвива" точката.

// Winding number - по-робустен за деликатни случаи
int windingNumber(const vector<Point>& p, Point pt) {
    int wn = 0;
    int n = p.size();
    for (int i = 0; i < n; i++) {
        Point a = p[i], b = p[(i + 1) % n];
        if (a.y <= pt.y) {
            if (b.y > pt.y && cross(b - a, pt - a) > 0)
                wn++;
        } else {
            if (b.y <= pt.y && cross(b - a, pt - a) < 0)
                wn--;
        }
    }
    return wn; // != 0 означава вътре
}

5. Изпъкналост (Convexity Check)

Полигон е изпъкнал, ако всички завои са в една и съща посока (само наляво или само надясно). Това означава, че всички вътрешни ъгли са по-малки от 180°.

Полигон е вдлъбнат (concave), ако има поне един вътрешен ъгъл по-голям от 180°.

Проверка за Изпъкналост

Използваме векторно произведение (cross product) за всеки три последователни върха. Ако всички имат един и същи знак, полигонът е изпъкнал.

// Проверка дали полигон е изпъкнал
bool isConvex(const vector<Point>& p) {
    int n = p.size();
    if (n < 3) return false;

    bool hasPos = false, hasNeg = false;
    for (int i = 0; i < n; i++) {
        Point a = p[i];
        Point b = p[(i + 1) % n];
        Point c = p[(i + 2) % n];

        long long cp = cross(b - a, c - b);
        if (cp > 0) hasPos = true;
        if (cp < 0) hasNeg = true;
    }

    return !(hasPos && hasNeg); // Изпъкнал, ако всички са с един знак
}

// Определяне на ориентацията (по или обратно на часовниковата стрелка)
// Връща: 1 = counter-clockwise, -1 = clockwise, 0 = дегенериран
int orientation(const vector<Point>& p) {
    long long area = signedArea2(p);
    if (area > 0) return 1;  // CCW
    if (area < 0) return -1; // CW
    return 0; // Дегенериран
}

// Обръщане на ориентацията на полигон
void reversePolygon(vector<Point>& p) {
    reverse(p.begin(), p.end());
}

Детекция на Изпъкли и Вдлъбнати Върхове

// Класификация на всеки връх: изпъкнал (convex) или вдлъбнат (reflex)
// Връща вектор: true = изпъкнал връх, false = вдлъбнат връх
vector<bool> classifyVertices(const vector<Point>& p) {
    int n = p.size();
    vector<bool> isConvexVertex(n);

    for (int i = 0; i < n; i++) {
        Point a = p[(i - 1 + n) % n];
        Point b = p[i];
        Point c = p[(i + 1) % n];

        long long cp = cross(b - a, c - b);
        // За CCW полигон: cp > 0 => изпъкнал връх
        isConvexVertex[i] = (cp >= 0);
    }

    return isConvexVertex;
}

6. Триангулация на Полигон

Всеки прост полигон може да бъде разделен на триъгълници. Това е полезно за много алгоритми и визуализации.

6.1. Ear Clipping Method

Метод "отрязване на уши" - намира "ухо" (триъгълник, чиито диагонал е вътре в полигона) и го премахва.

// Проверка дали триъгълник (a, b, c) съдържа точка p
bool triangleContains(Point a, Point b, Point c, Point p) {
    long long cp1 = cross(b - a, p - a);
    long long cp2 = cross(c - b, p - b);
    long long cp3 = cross(a - c, p - c);

    return (cp1 >= 0 && cp2 >= 0 && cp3 >= 0) ||
           (cp1 <= 0 && cp2 <= 0 && cp3 <= 0);
}

// Проверка дали диагоналът от i до k е валиден (не пресича полигона)
bool isValidDiagonal(const vector<Point>& p, int i, int k) {
    int n = p.size();

    // Проверка дали диагоналът е вътре в полигона
    Point mid = Point((p[i].x + p[k].x) / 2, (p[i].y + p[k].y) / 2);
    if (!isInside(p, mid)) return false;

    // Проверка дали някой връх е вътре в триъгълника
    for (int j = 0; j < n; j++) {
        if (j == i || j == k || j == (i + 1) % n) continue;
        if (triangleContains(p[i], p[(i + 1) % n], p[k], p[j]))
            return false;
    }

    return true;
}

// Ear Clipping триангулация (O(n^2) за прости полигони)
vector<array<int, 3>> triangulate(vector<Point> p) {
    vector<array<int, 3>> triangles;
    int n = p.size();
    vector<int> indices(n);
    for (int i = 0; i < n; i++) indices[i] = i;

    while (indices.size() > 3) {
        bool found = false;
        for (int i = 0; i < indices.size(); i++) {
            int prev = (i - 1 + indices.size()) % indices.size();
            int next = (i + 1) % indices.size();

            Point a = p[indices[prev]];
            Point b = p[indices[i]];
            Point c = p[indices[next]];

            // Проверка дали това е "ухо"
            if (cross(b - a, c - b) > 0) {
                bool isEar = true;
                for (int j = 0; j < indices.size(); j++) {
                    if (j == prev || j == i || j == next) continue;
                    if (triangleContains(a, b, c, p[indices[j]])) {
                        isEar = false;
                        break;
                    }
                }

                if (isEar) {
                    triangles.push_back({indices[prev], indices[i], indices[next]});
                    indices.erase(indices.begin() + i);
                    found = true;
                    break;
                }
            }
        }
        if (!found) break; // Не може да се триангулира
    }

    if (indices.size() == 3) {
        triangles.push_back({indices[0], indices[1], indices[2]});
    }

    return triangles;
}

6.2. Монотонна Триангулация (за напреднали)

За изпъкнали полигони триангулацията е тривиална - всички диагонали от един връх.

// Триангулация на изпъкнал полигон от връх 0
vector<array<int, 3>> triangulateConvex(int n) {
    vector<array<int, 3>> triangles;
    for (int i = 1; i < n - 1; i++) {
        triangles.push_back({0, i, i + 1});
    }
    return triangles;
}

7. Разлагане на Полигон (Decomposition)

7.1. Разлагане на Изпъкнали Части

Вдлъбнат полигон може да се раздели на изпъкнали части.

// Намиране на всички вдлъбнати върхове (reflex vertices)
vector<int> findReflexVertices(const vector<Point>& p) {
    vector<int> reflex;
    int n = p.size();

    for (int i = 0; i < n; i++) {
        Point a = p[(i - 1 + n) % n];
        Point b = p[i];
        Point c = p[(i + 1) % n];

        if (cross(b - a, c - b) < 0) { // За CCW полигон
            reflex.push_back(i);
        }
    }

    return reflex;
}

8. Практически Приложения и Специални Случаи

8.1. Център на Тежест (Centroid)

// Център на тежест на полигон
Point centroid(const vector<Point>& p) {
    long long cx = 0, cy = 0, area = 0;
    int n = p.size();

    for (int i = 0; i < n; i++) {
        long long cp = cross(p[i], p[(i + 1) % n]);
        cx += (p[i].x + p[(i + 1) % n].x) * cp;
        cy += (p[i].y + p[(i + 1) % n].y) * cp;
        area += cp;
    }

    // Делим на 3 * площта (за да избегнем деление по време на натрупване)
    return Point(cx / (3 * area), cy / (3 * area));
}

8.2. Най-далечна Двойка Точки (Rotating Calipers)

За изпъкнал полигон можем да намерим най-далечната двойка точки за O(n).

8.3. Минковски Сума

Сумата на два полигона \(P + Q = \{p + q : p \in P, q \in Q\}\).

8.4. Пресичане на Полигони

Проверка дали два полигона се пресичат или един съдържа друг.

// Проверка дали два изпъкнали полигона се пресичат
bool convexPolygonsIntersect(const vector<Point>& p1, const vector<Point>& p2) {
    // Проверка дали някой връх на p1 е в p2
    for (const Point& pt : p1) {
        if (inConvexPolygon(p2, pt)) return true;
    }

    // Проверка дали някой връх на p2 е в p1
    for (const Point& pt : p2) {
        if (inConvexPolygon(p1, pt)) return true;
    }

    // Проверка дали някои страни се пресичат
    for (int i = 0; i < p1.size(); i++) {
        for (int j = 0; j < p2.size(); j++) {
            // Проверка за пресичане на отсечки [p1[i], p1[i+1]] и [p2[j], p2[j+1]]
            // (изисква функция за пресичане на отсечки)
        }
    }

    return false;
}

9. Специални Случаи и Грешки

Често Срещани Грешки:

  1. Деление с нула при проверка за пресичане
  2. Overflow - винаги използвайте long long за координати
  3. Грешки при закръгляне - работете с удвоено лице (2*S) докато е възможно
  4. Дегенерирани случаи - колинеарни точки, полигон с площ 0
  5. Гранични случаи при Point-in-Polygon - точка на ръб или връх

Проверки за Валидност:

// Проверка дали полигон е валиден (не се самопересича)
bool isSimplePolygon(const vector<Point>& p) {
    int n = p.size();
    // Проверка за самопресичане на страни
    for (int i = 0; i < n; i++) {
        for (int j = i + 2; j < n; j++) {
            if (j == (i + n - 1) % n) continue; // Съседни страни
            // Проверка дали отсечки [i, i+1] и [j, j+1] се пресичат
            // (изисква функция за пресичане на отсечки)
        }
    }
    return true;
}

// Проверка за дегенериран полигон (с площ 0)
bool isDegenerate(const vector<Point>& p) {
    return polygonArea2(p) == 0;
}

10. Задачи

  1. Codeforces 166B: Polygon (Point inside convex polygon).
  2. POJ 1265: Area (Pick's theorem).
  3. SPOJ GSSQ: General queries.

11. Сложност и Оптимизации

Времева Сложност:

  • Лице на полигон: O(n)
  • Периметър: O(n)
  • Point in Polygon (Ray Casting): O(n)
  • Point in Polygon (изпъкнал, двоично търсене): O(log n)
  • Проверка за изпъкналост: O(n)
  • Триангулация (Ear Clipping): O(n²)
  • Триангулация (оптимална): O(n log n)

Съвети за Оптимизация:

  1. Използвайте long long за координати, за да избегнете overflow
  2. Работете с удвоено лице (2*S) докато е възможно
  3. Кеширайте резултати като лице и периметър, ако се използват многократно
  4. За изпъкнали полигони използвайте специализирани алгоритми
  5. Избягвайте операции с плаваща запетая, когато е възможно

🏁 Заключение

Геометрията на полигони е фундаментална тема в състезателното програмиране. Основните концепции включват:

✅ Винаги работете с \(2 \cdot S\) (удвоено лице), за да останете в целите числа (long long) до последния момент.

✅ Внимавайте за overflow - използвайте long long за всички междинни изчисления.

✅ Тествайте гранични случаи - дегенерирани полигони, колинеарни точки, точки на границата.

✅ Използвайте векторно произведение - то е основен инструмент за повечето операции с полигони.

✅ Разбирайте разликата между изпъкнали и вдлъбнати полигони - различни алгоритми имат различна ефективност.

Практикувайте с реални задачи, за да затвърдите познанията си!