Bao lồi

Bao lồi hai chiều

Định nghĩa

Đa giác lồi

Đa giác lồi là đa giác đơn giản mà tất cả các góc trong đều nằm trong khoảng \([0,\pi]\).

Bao lồi

Trên mặt phẳng, bao lồi của một tập hợp điểm là đa giác lồi nhỏ nhất chứa tất cả các điểm đó.

Định nghĩa chính xác: Với tập hợp \(X\) cho trước, giao của tất cả các tập lồi chứa \(X\) được gọi là bao lồi của \(X\).

Có thể hình dung như dùng một sợi dây chun bao quanh tất cả các điểm đã cho.

Bao lồi là đa giác có chu vi nhỏ nhất bao quanh tất cả các điểm đã cho. Nếu một đa giác lõm bao quanh tất cả các điểm, chu vi của nó chắc chắn không nhỏ nhất, như hình dưới. Theo bất đẳng thức tam giác, đa giác lồi luôn tối ưu về chu vi.

Thuật toán Andrew tìm bao lồi

Có hai phương pháp phổ biến là Graham scan và Andrew, ở đây chủ yếu giới thiệu thuật toán Andrew.

Tính chất

Độ phức tạp thời gian của thuật toán này là \(O(n\log n)\), với \(n\) là số lượng điểm, chủ yếu do bước sắp xếp các điểm theo hai khóa.

Quy trình

Đầu tiên, sắp xếp tất cả các điểm theo hoành độ tăng dần, nếu hoành độ bằng nhau thì so sánh tung độ.

Rõ ràng, điểm nhỏ nhất và lớn nhất sau khi sắp xếp chắc chắn nằm trên bao lồi. Vì là đa giác lồi, nếu đi ngược chiều kim đồng hồ từ một điểm, đường đi luôn "rẽ trái", nếu xuất hiện "rẽ phải" thì đoạn đó không thuộc bao lồi. Do đó, ta có thể dùng một ngăn xếp đơn điệu để duyệt vỏ trên và vỏ dưới.

Vì hướng quay của vỏ trên và vỏ dưới khác nhau, để ngăn xếp đơn điệu hoạt động đúng, ta duyệt tăng để tìm vỏ dưới, sau đó duyệt giảm để tìm vỏ trên.

Khi tìm vỏ, nếu phát hiện điểm sắp vào ngăn xếp (\(P\)) và hai điểm trên đỉnh ngăn xếp (\(S_1, S_2\), \(S_1\) là đỉnh) tạo thành hướng quay phải, tức là tích có hướng nhỏ hơn \(0\): \(\overrightarrow{S_2S_1}\times \overrightarrow{S_1P}<0\), thì loại bỏ đỉnh ngăn xếp, lặp lại kiểm tra cho đến khi \(\overrightarrow{S_2S_1}\times \overrightarrow{S_1P}\ge 0\) hoặc ngăn xếp chỉ còn một phần tử.

Thông thường không cần giữ các điểm nằm trên cạnh bao lồi, nên điều kiện "\(<\)" ở trên có thể thay bằng "\(\le\)", đồng thời điều kiện sau đổi thành "\(>\)".

Andrew

Cài đặt

Cài đặt mã nguồn

C++Python

// stk[] là mảng chỉ số nguyên, lưu chỉ số điểm
// p[] lưu vector hoặc điểm
tp = 0;                       // Khởi tạo ngăn xếp
std::sort(p + 1, p + 1 + n);  // Sắp xếp các điểm
stk[++tp] = 1;
// Thêm phần tử đầu tiên vào ngăn xếp, không cập nhật used để 1 vẫn được xử lý khi đóng bao lồi
for (int i = 2; i <= n; ++i) {
  while (tp >= 2  // Dòng dưới: * được nạp chồng thành tích có hướng
         && (p[stk[tp]] - p[stk[tp - 1]]) * (p[i] - p[stk[tp]]) <= 0)
    used[stk[tp--]] = 0;
  used[i] = 1;  // used đánh dấu điểm nằm trên vỏ
  stk[++tp] = i;
}
int tmp = tp;  // tmp lưu kích thước vỏ dưới
for (int i = n - 1; i > 0; --i)
  if (!used[i]) {
    // ↓ Khi tìm vỏ trên không ảnh hưởng vỏ dưới
    while (tp > tmp && (p[stk[tp]] - p[stk[tp - 1]]) * (p[i] - p[stk[tp]]) <= 0)
      used[stk[tp--]] = 0;
    used[i] = 1;
    stk[++tp] = i;
  }
for (int i = 1; i <= tp; ++i)  // Sao chép sang mảng mới
  h[i] = p[stk[i]];
int ans = tp - 1;

stk = []  # Mảng chỉ số nguyên, lưu chỉ số điểm
p = []  # Lưu vector hoặc điểm
tp = 0  # Khởi tạo ngăn xếp
p.sort()  # Sắp xếp các điểm
tp = tp + 1
stk[tp] = 1
# Thêm phần tử đầu tiên vào ngăn xếp, không cập nhật used để 1 vẫn được xử lý khi đóng bao lồi
for i in range(2, n + 1):
    while tp >= 2 and (p[stk[tp]] - p[stk[tp - 1]]) * (p[i] - p[stk[tp]]) <= 0:
        # Dòng dưới: * được nạp chồng thành tích có hướng
        used[stk[tp]] = 0
        tp = tp - 1
    used[i] = 1  # used đánh dấu điểm nằm trên vỏ
    tp = tp + 1
    stk[tp] = i
tmp = tp  # tmp lưu kích thước vỏ dưới
for i in range(n - 1, 0, -1):
    if used[i] == False:
        #      ↓ Khi tìm vỏ trên không ảnh hưởng vỏ dưới
        while tp > tmp and (p[stk[tp]] - p[stk[tp - 1]]) * (p[i] - p[stk[tp]]) <= 0:
            used[stk[tp]] = 0
            tp = tp - 1
        used[i] = 1
        tp = tp + 1
        stk[tp] = i
for i in range(1, tp + 1):
    h[i] = p[stk[i]]
ans = tp - 1

Theo đoạn mã trên, cuối cùng bao lồi có \(\textit{ans}\) điểm (mảng \(h\) có \(\textit{ans}+1\) phần tử, do lưu thêm điểm đầu), các điểm được sắp xếp ngược chiều kim đồng hồ. Chu vi là:

\[ \sum_{i=1}^{\textit{ans}}\left|\overrightarrow{h_ih_{i+1}}\right| \]

Thuật toán Graham scan

Tính chất

Tương tự Andrew, Graham scan cũng có độ phức tạp \(O(n\log n)\), chủ yếu do bước sắp xếp.

Quy trình

Đầu tiên, tìm điểm có tung độ nhỏ nhất (nếu bằng nhau thì lấy hoành độ nhỏ nhất), gọi là \(P\). Theo định nghĩa bao lồi, điểm này chắc chắn nằm trên bao lồi. Sau đó, sắp xếp tất cả các điểm còn lại theo thứ tự tăng dần của góc cực so với \(P\).

Tương tự Andrew, nếu đi ngược chiều kim đồng hồ trên bao lồi, mỗi bước đều là "rẽ trái". Cụ thể, với ba điểm liên tiếp \(P_1, P_2, P_3\) trên bao lồi, luôn có \(\overrightarrow{P_1 P_2} \times \overrightarrow{P_2 P_3} \ge 0\).

Dùng một ngăn xếp để lưu các điểm trên bao lồi, đầu tiên đẩy \(P\) vào ngăn xếp, sau đó lần lượt thử thêm từng điểm theo thứ tự góc cực. Nếu điểm mới vào ngăn xếp cùng hai điểm trên đỉnh tạo thành "rẽ phải", thì loại bỏ đỉnh ngăn xếp, lặp lại cho đến khi điều kiện thỏa mãn hoặc ngăn xếp chỉ còn một phần tử, rồi đẩy điểm mới vào.

Cài đặt mã nguồn

struct Point {
  double x, y, ang;

  Point operator-(const Point& p) const { return {x - p.x, y - p.y, 0}; }
} p[MAXN];

double dis(Point p1, Point p2) {
  return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}

bool cmp(Point p1, Point p2) {
  if (p1.ang == p2.ang) {
    return dis(p1, p[1]) < dis(p2, p[1]);
  }
  return p1.ang < p2.ang;
}

double cross(Point p1, Point p2) { return p1.x * p2.y - p1.y * p2.x; }

int main() {
  for (int i = 2; i <= n; ++i) {
    if (p[i].y < p[1].y || (p[i].y == p[1].y && p[i].x < p[1].x)) {
      std::swap(p[1], p[i]);
    }
  }
  for (int i = 2; i <= n; ++i) {
    p[i].ang = atan2(p[i].y - p[1].y, p[i].x - p[1].x);
  }
  std::sort(p + 2, p + n + 1, cmp);
  sta[++top] = 1;
  for (int i = 2; i <= n; ++i) {
    while (top >= 2 &&
           cross(p[sta[top]] - p[sta[top - 1]], p[i] - p[sta[top]]) < 0) {
      top--;
    }
    sta[++top] = i;
  }
  return 0;
}

Tổng Minkowski

Định nghĩa

Tổng Minkowski của hai tập điểm \(P\) và \(Q\) được định nghĩa là \(P+Q=\{a+b|a\in P,b\in Q\}\), tức là dịch chuyển mỗi điểm của \(P\) theo từng vector của \(Q\), tập hợp kết quả là \(P+Q\). Ở đây chỉ xét tổng Minkowski của bao lồi.

Ví dụ: Với \(P=\{(0,0),(-3,3),(2,1)\}\) và \(Q=\{(0,0),(-1,3),(1,4),(2,2)\}\),

Dịch \(P\) theo từng vector của \(Q\):

Dễ thấy hình mới cũng là một bao lồi:

Tính chất

Nếu \(P\), \(Q\) là tập lồi, thì \(P+Q\) cũng là tập lồi.

Chứng minh

Giả sử \(e,f\in P+Q\), tồn tại \(a,b \in P\), \(c,d\in Q\) sao cho \(e=a+c,f=b+d\), với mọi \(t\in[0,1]\):

\[ \begin{aligned} te + (1-t)f &= t(a+c)+(1-t)(b+d)\\ &=(ta+(1-t)b)+(tc+(1-t)d)\\ &\in P+Q. \end{aligned} \]

Q.E.D.
1. Nếu \(P\), \(Q\) là tập lồi, thì các cạnh của \(P+Q\) là kết quả nối các cạnh của \(P\), \(Q\) sau khi sắp xếp theo góc cực.
Chứng minh

Giả sử các cạnh của \(P\) và \(Q\) không có cạnh nào cùng độ dốc. Xoay hệ trục tọa độ sao cho một cạnh \(XY\) của \(P\) song song với trục \(x\) và nằm thấp nhất.

Khi đó, điểm thấp nhất của \(Q\) là \(U\), điểm thấp nhất và trái nhất của \(P+Q\) là \(A\).

Ta có \(\vec{A} = \vec{X} + \vec{U}\), nên \(A\) nằm trên biên \(P+Q\).

Tương tự, điểm thấp nhất và phải nhất của \(P+Q\) là \(B\) với \(\vec{B} = \vec{Y} + \vec{U}\), cũng nằm trên biên.

Do đó, \(\vec{AB} = \vec{XY} + \vec{U}\).

Nếu tiếp tục xoay, ta sẽ nhận được liên tiếp các cạnh của \(P+Q\).

Q.E.D.

Cài đặt

Dựa vào tính chất 2, ta sắp xếp các cạnh của \(P,Q\) theo góc cực, lấy \(P_1+Q_1\) làm điểm bắt đầu, sau đó dùng kỹ thuật trộn (merge) để lần lượt thêm các cạnh.

Độ phức tạp: \(O(n+m)\)

Cài đặt

template <class T>
struct Point {
  T x, y;

  Point(T x = 0, T y = 0) : x(x), y(y) {}

  friend Point operator+(const Point &a, const Point &b) {
    return {a.x + b.x, a.y + b.y};
  }

  friend Point operator-(const Point &a, const Point &b) {
    return {a.x - b.x, a.y - b.y};
  }

  // Tích vô hướng
  friend T operator*(const Point &a, const Point &b) {
    return a.x * b.x + a.y * b.y;
  }

  // Tích có hướng
  friend T operator^(const Point &a, const Point &b) {
    return a.x * b.y - a.y * b.x;
  }
};

template <class T>
vector<Point<T>> minkowski_sum(vector<Point<T>> a, vector<Point<T>> b) {
  vector<Point<T>> c{a[0] + b[0]};
  for (usz i = 0; i + 1 < a.size(); ++i) a[i] = a[i + 1] - a[i];
  for (usz i = 0; i + 1 < b.size(); ++i) b[i] = b[i + 1] - b[i];
  a.pop_back(), b.pop_back();
  c.resize(a.size() + b.size() + 1);
  merge(a.begin(), a.end(), b.begin(), b.end(), c.begin() + 1,
        [](const Point<i64> &a, const Point<i64> &b) { return (a ^ b) < 0; });
  for (usz i = 1; i < c.size(); ++i) c[i] = c[i] + c[i - 1];
  return c;
}

Bài tập ví dụ

Bài tập ví dụ [JSOI2018] Chiến tranh

Cho hai bao lồi \(P,Q\), dịch chuyển \(Q\) \(q\) lần, hỏi sau mỗi lần dịch chuyển có giao điểm với \(P\) không. \(1\le n,m\le 10^5,1\le q\le 10^5\).

Cài đặt

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;
using i64 = int64_t;
using isz = ptrdiff_t;
using usz = size_t;

template <class T>
struct Point {
  T x, y;

  Point(T x = 0, T y = 0) : x(x), y(y) {}

  friend Point operator+(const Point &a, const Point &b) {
    return {a.x + b.x, a.y + b.y};
  }

  friend Point operator-(const Point &a, const Point &b) {
    return {a.x - b.x, a.y - b.y};
  }

  // 点乘
  friend T operator*(const Point &a, const Point &b) {
    return a.x * b.x + a.y * b.y;
  }

  // 叉乘
  friend T operator^(const Point &a, const Point &b) {
    return a.x * b.y - a.y * b.x;
  }

  friend istream &operator>>(istream &is, Point &p) { return is >> p.x >> p.y; }
};

template <class T>
vector<Point<T>> convex_hull(vector<Point<T>> p) {
  assert(!p.empty());
  sort(p.begin(), p.end(),
       [](const Point<i64> &a, const Point<i64> &b) { return a.x < b.x; });
  vector<Point<T>> u{p[0]}, d{p.back()};
  for (usz i = 1; i < p.size(); ++i) {
    while (u.size() >= 2 &&
           ((u.back() - u[u.size() - 2]) ^ (p[i] - u.back())) > 0)
      u.pop_back();
    u.push_back(p[i]);
  }
  for (usz i = p.size() - 2; (isz)i >= 0; --i) {
    while (d.size() >= 2 &&
           ((d.back() - d[d.size() - 2]) ^ (p[i] - d.back())) > 0)
      d.pop_back();
    d.push_back(p[i]);
  }
  u.insert(u.end(), d.begin() + 1, d.end());
  return u;
}

template <class T>
vector<Point<T>> minkowski_sum(vector<Point<T>> a, vector<Point<T>> b) {
  vector<Point<T>> c{a[0] + b[0]};
  for (usz i = 0; i + 1 < a.size(); ++i) a[i] = a[i + 1] - a[i];
  for (usz i = 0; i + 1 < b.size(); ++i) b[i] = b[i + 1] - b[i];
  a.pop_back(), b.pop_back();
  c.resize(a.size() + b.size() + 1);
  merge(a.begin(), a.end(), b.begin(), b.end(), c.begin() + 1,
        [](const Point<i64> &a, const Point<i64> &b) { return (a ^ b) < 0; });
  for (usz i = 1; i < c.size(); ++i) c[i] = c[i] + c[i - 1];
  return c;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  uint32_t n, m, q;
  vector<Point<i64>> a, b;
  cin >> n >> m >> q;
  a.resize(n), b.resize(m);
  for (auto &p : a) cin >> p;
  for (auto &p : b) cin >> p, p = 0 - p;
  a = convex_hull(a), b = convex_hull(b);
  a = minkowski_sum(a, b);
  a.pop_back();
  for (usz i = 1; i < a.size(); ++i) a[i] = a[i] - a[0];
  while (q--) {
    Point<i64> v;
    cin >> v;
    v = v - a[0];
    if (v.x < 0) {
      cout << "0\n";
      continue;
    }
    auto it = upper_bound(
        a.begin() + 1, a.end(), v,
        [](const Point<i64> &a, const Point<i64> &b) { return (a ^ b) < 0; });
    if (it == a.begin() + 1 || it == a.end()) {
      cout << "0\n";
      continue;
    }
    i64 s0 = *it ^ *prev(it), s1 = v ^ *prev(it), s2 = *it ^ v;
    cout << (s1 >= 0 && s2 >= 0 && s1 + s2 <= s0) << '\n';
  }
  return 0;
}

Bao lồi ba chiều

Kiến thức cơ bản

Phép nghịch đảo tròn: Với tâm \(O\), bán kính \(R\), nếu đường thẳng qua \(O\) đi qua \(P,P'\), và \(OP\times OP'=R^{2}\), thì \(P\) và \(P'\) gọi là nghịch đảo nhau qua \(O\).

Quy trình

Các bước tìm bao lồi ba chiều:

Đầu tiên, thực hiện nhiễu nhỏ để tránh trường hợp bốn điểm đồng phẳng.
Với bao lồi đã biết, thêm một điểm \(P\), coi \(P\) là nguồn sáng, chiếu tia tới bao lồi, các mặt nhìn thấy và không nhìn thấy được phân tách bởi các cạnh.
Xóa các mặt nhìn thấy, thêm các mặt mới tạo bởi các cạnh phân tách và \(P\). Lặp lại quá trình này. Theo Định lý Pick, công thức Euler (\(V−E+F=2\) với đa diện lồi), và phép nghịch đảo tròn, độ phức tạp \(O(n^2)\).¹

Bài mẫu

P4724【Mẫu】Bao lồi ba chiều

Lặp lại quy trình trên để có đáp án.

Cài đặt mã nguồn

#include <cmath>
#include <cstdlib>
#include <iomanip>
#include <iostream>
using namespace std;
constexpr int N = 2010;
constexpr double eps = 1e-9;
int n, cnt, vis[N][N];
double ans;

double Rand() { return rand() / (double)RAND_MAX; }

double reps() { return (Rand() - 0.5) * eps; }

struct Node {
  double x, y, z;

  void shake() {
    x += reps();
    y += reps();
    z += reps();
  }

  double len() { return sqrt(x * x + y * y + z * z); }

  Node operator-(Node A) const { return {x - A.x, y - A.y, z - A.z}; }

  Node operator*(Node A) const {
    return {y * A.z - z * A.y, z * A.x - x * A.z, x * A.y - y * A.x};
  }

  double operator&(Node A) const { return x * A.x + y * A.y + z * A.z; }
} A[N];

struct Face {
  int v[3];

  Node Normal() { return (A[v[1]] - A[v[0]]) * (A[v[2]] - A[v[0]]); }

  double area() { return Normal().len() / 2.0; }
} f[N], C[N];

int see(Face a, Node b) { return ((b - A[a.v[0]]) & a.Normal()) > 0; }

void Convex_3D() {
  f[++cnt] = {1, 2, 3};
  f[++cnt] = {3, 2, 1};

  for (int i = 4, cc = 0; i <= n; i++) {
    for (int j = 1, v; j <= cnt; j++) {
      if (!(v = see(f[j], A[i]))) C[++cc] = f[j];

      for (int k = 0; k < 3; k++) vis[f[j].v[k]][f[j].v[(k + 1) % 3]] = v;
    }

    for (int j = 1; j <= cnt; j++)
      for (int k = 0; k < 3; k++) {
        int x = f[j].v[k], y = f[j].v[(k + 1) % 3];

        if (vis[x][y] && !vis[y][x]) C[++cc] = {x, y, i};
      }

    for (int j = 1; j <= cc; j++) f[j] = C[j];

    cnt = cc;
    cc = 0;
  }
}

int main() {
  cin >> n;

  for (int i = 1; i <= n; i++) cin >> A[i].x >> A[i].y >> A[i].z, A[i].shake();

  Convex_3D();

  for (int i = 1; i <= cnt; i++) ans += f[i].area();

  cout << fixed << setprecision(3) << ans << '\n';
  return 0;
}

Bài tập luyện tập

Tài liệu tham khảo & chú thích

Ghi chú học tập về bao lồi 3D ↩

Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:OI-wiki
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply