Wiki › Thuật toán › Hình học tính toán › Bao lồi 3D

Bao lồi 3D

Dựng bao lồi của tập điểm trong không gian bằng thuật toán gia tăng O(n^2) với phép thử định hướng nguyên chính xác, tính diện tích, thể tích, xử lý suy biến và suy ra tam giác phân Delaunay qua phép nâng lên paraboloid.

huunguyen huunguyen Updated Tháng 11. 17, 2026 Đọc 23 phút 3 lượt xem

Bao lồi 3D (3D convex hull) của n điểm trong không gian là khối đa diện lồi nhỏ nhất chứa tất cả các điểm. Hình dung: bọc các điểm bằng một tấm màng co, khi màng co hết cỡ nó ôm sát các điểm ngoài cùng và tạo thành một đa diện có các mặt tam giác. Cách ngây thơ thử mọi bộ ba điểm làm mặt rồi kiểm tra n điểm còn lại mất O(n4); thuật toán gia tăng (incremental) trong bài này chỉ mất O(n2), đủ cho n vài nghìn, và phiên bản gia tăng ngẫu nhiên với đồ thị xung đột đạt O(nlogn) kỳ vọng. Từ bao lồi 3D ta tính được diện tích mặt, thể tích, và (qua phép nâng lên paraboloid) cả tam giác phân Delaunay trong mặt phẳng.

Nếu chưa quen bao lồi trên mặt phẳng, nên đọc trước Convex Hull (Bao lồi).

Ý tưởng / Trực giác

Tích có hướng và tích vô hướng trong 3D

Với hai vector u→=(ux,uy,uz) và v→=(vx,vy,vz):

u→·v→=uxvx+uyvy+uzvz

u→×v→=(uyvz−uzvy,  uzvx−uxvz,  uxvy−uyvx)

  • Tích vô hướng (dot product) bằng |u→||v→|cosθ: dương khi hai vector cùng phía, bằng 0 khi vuông góc.
  • Tích có hướng (cross product) là một vector vuông góc với cả u→ và v→, có độ dài bằng diện tích hình bình hành dựng trên u→,v→. Chiều của nó theo quy tắc bàn tay phải: nếu nhìn từ đầu mũi tên u→×v→ xuống thì u→ quay sang v→ ngược chiều kim đồng hồ.

Hệ quả: tam giác ABC có pháp tuyến n→=(B−A)×(C−A) và diện tích 12|n→|.

Định hướng của một điểm so với một mặt (thể tích có dấu)

Đây là phép thử duy nhất mà thuật toán cần, tương tự phép thử "rẽ trái / rẽ phải" trong 2D:

orient(A,B,C,D)=((B−A)×(C−A))·(D−A)=det(B−AC−AD−A)

  • orient>0: D nằm cùng phía với pháp tuyến n→ của mặt ABC.
  • orient<0: D nằm phía ngược lại.
  • orient=0: bốn điểm đồng phẳng.

Giá trị tuyệt đối của nó bằng 6 lần thể tích tứ diện ABCD. Với tọa độ nguyên, đây là phép tính nguyên chính xác, không có sai số làm tròn: mọi quyết định của thuật toán đều đúng tuyệt đối.

Quy ước trong bài: mỗi mặt (a,b,c) của bao được lưu sao cho pháp tuyến (b−a)×(c−a) hướng ra ngoài, tức là nhìn từ ngoài vào, ba đỉnh đi ngược chiều kim đồng hồ. Khi đó một điểm p nhìn thấy mặt f khi và chỉ khi orient(f,p)>0.

Thuật toán gia tăng: mặt nhìn thấy và đường chân trời

Dựng bao cho vài điểm đầu, rồi thêm lần lượt từng điểm p:

  1. Nếu p ở trong bao (không mặt nào thấy p): bao không đổi.
  2. Nếu p ở ngoài: tưởng tượng đứng tại p cầm đèn pin chiếu vào khối đa diện. Các mặt được chiếu sáng là mặt nhìn thấy (visible faces); chúng tạo thành một vùng liền trên bề mặt. Biên của vùng sáng là một chu trình cạnh gọi là đường chân trời (horizon). Ta xóa mọi mặt nhìn thấy và nối p với từng cạnh chân trời, tạo một "nón" các mặt tam giác mới.

Vì sao đúng? Bao mới conv(H∪{p}) gồm hai phần: những mặt cũ p không thấy (chúng vẫn là mặt tựa, p nằm phía trong của chúng) và những mặt mới đi qua p. Một mặt mới qua p phải tựa lên bao cũ dọc một cạnh mà một bên được chiếu sáng, một bên không: chính là cạnh chân trời. Mặt nhìn thấy bị loại vì p nằm ngoài mặt phẳng của chúng, chúng không còn là mặt tựa.

Cài đặt cạnh chân trời rất gọn nhờ cạnh có hướng: mỗi cạnh u→v thuộc đúng một mặt (mặt kề bên kia chứa cạnh ngược v→u). Cạnh u→v của một mặt nhìn thấy là cạnh chân trời khi và chỉ khi mặt chứa v→u không nhìn thấy. Mặt mới là (u,v,p), tự động đúng chiều hướng ra ngoài.

Ví dụ chạy tay

Bắt đầu từ tứ diện A(0,0,0), B(4,0,0), C(0,4,0), D(0,0,4) rồi thêm lần lượt P(3,3,3), Q(1,1,1), R(5,1,−2).

Bước 0: tứ diện ban đầu. Bốn mặt, định hướng ra ngoài (đỉnh thứ tư cho orient<0):

Mặt Pháp tuyến ra ngoài Mặt phẳng
ACB (0,0,−16) z=0
ABD (0,−16,0) y=0
ADC (−16,0,0) x=0
BCD (16,16,16) x+y+z=4

Thể tích =646=323.

Bước 1: thêm P(3,3,3). Tính orient với từng mặt:

Mặt orient(·,P) Nhìn thấy?
ACB −48 không
ABD −48 không
ADC −48 không
BCD +80 có

Chỉ BCD được chiếu sáng, nên chân trời là ba cạnh của nó: B→C, C→D, D→B. Xóa BCD, thêm ba mặt BCP, CDP, DBP.

graph
5 9
1 2
1 3
1 4
2 3
3 4
4 2
5 2
5 3
5 4
name 1 A
name 2 B
name 3 C
name 4 D
name 5 P
pos 1 100 200
pos 2 260 200
pos 3 40 150
pos 4 100 40
pos 5 230 70
step Tứ diện ABCD và điểm mới P
highlight gray 5-2 5-3 5-4
highlight orange 5
step Mặt BCD nhìn thấy P: ba cạnh của nó là đường chân trời
highlight red 2-3 3-4 4-2
step Xóa BCD, nối P với các cạnh chân trời: thêm BCP, CDP, DBP
highlight green 5-2 5-3 5-4

Thể tích tăng đúng bằng tổng orient dương chia 6: 806=403, tổng thành 323+403=24. Diện tích mặt =3·8+3·12352=24+622≈52,142495 (mỗi mặt mới có pháp tuyến độ dài 122+122+82=352).

Bước 2: thêm Q(1,1,1). Cả sáu mặt cho orient(·,Q)<0 (ba mặt trục cho −16, ba mặt mới cho −32). Không mặt nào nhìn thấy: Q ở trong, bỏ qua.

Bước 3: thêm R(5,1,−2). Lần này hai mặt sáng:

Mặt orient(·,R) Nhìn thấy?
ACB +32 có
ABD, ADC, CDP, DBP <0 không
BCP +40 có

Hai mặt sáng ACB (cạnh A→C, C→B, B→A) và BCP (cạnh B→C, C→P, P→B) chung cạnh BC nên cạnh này không thuộc chân trời (cạnh ngược của nó cũng sáng). Chân trời là chu trình A→C→P→B→A, bốn mặt mới: ACR, CPR, PBR, BAR.

Trước:   6 mặt, thể tích 24
Sáng:    ACB, BCP           (chung cạnh BC -> không phải chân trời)
Chân trời: A->C, C->P, P->B, B->A
Sau:     6 - 2 + 4 = 8 mặt, thể tích 24 + (32 + 40)/6 = 36

Kiểm tra: 6 đỉnh A,B,C,D,P,R, đa diện tam giác hóa có F=2V−4=8 mặt. Chương trình bên dưới in đúng faces 8, area 66.974691, volume 36.000000 cho input này.

Cài đặt

Input: n, rồi n dòng tọa độ nguyên x y z (|x|,|y|,|z|≤106). Output: số mặt tam giác, diện tích mặt và thể tích của bao.

Các bước: bỏ điểm trùng; tìm 4 điểm không đồng phẳng làm tứ diện ban đầu; thêm từng điểm còn lại như trên. Mảng owner[u*n + v] lưu mặt đang chứa cạnh có hướng u→v. Thể tích tính bằng công thức phân rã từ gốc tọa độ: 6V=∑mặt (a,b,c)a·(b×c), một tổng nguyên chính xác.

C++
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;

struct P3 {
    ll x, y, z;
    P3 operator-(const P3& o) const { return {x - o.x, y - o.y, z - o.z}; }
    bool operator<(const P3& o) const { return tie(x, y, z) < tie(o.x, o.y, o.z); }
    bool operator==(const P3& o) const { return x == o.x && y == o.y && z == o.z; }
};
// Cross product (components fit in long long for |coord| <= 1e6).
P3 cross(const P3& a, const P3& b) {
    return {a.y * b.z - a.z * b.y, a.z * b.x - a.x * b.z, a.x * b.y - a.y * b.x};
}
// Dot product in __int128: each term can reach ~1e19.
lll dot(const P3& a, const P3& b) {
    return (lll)a.x * b.x + (lll)a.y * b.y + (lll)a.z * b.z;
}
// Signed volume x6 of tetrahedron (a,b,c,d): > 0 if d is on the side
// the normal (b-a)x(c-a) points to.
lll orient(const P3& a, const P3& b, const P3& c, const P3& d) {
    return dot(cross(b - a, c - a), d - a);
}

struct Face { int a, b, c; };

int main() {
    int n;
    scanf("%d", &n);
    vector<P3> p(n);
    for (auto& q : p) scanf("%lld %lld %lld", &q.x, &q.y, &q.z);
    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());
    n = p.size();

    // Find 4 points that are not coplanar.
    int i1 = -1, i2 = -1, i3 = -1;
    for (int i = 1; i < n && i1 < 0; i++) i1 = i;
    for (int i = 1; i < n && i1 >= 0 && i2 < 0; i++) {
        P3 c = cross(p[i1] - p[0], p[i] - p[0]);
        if (c.x || c.y || c.z) i2 = i;
    }
    for (int i = 1; i < n && i2 >= 0 && i3 < 0; i++)
        if (orient(p[0], p[i1], p[i2], p[i]) != 0) i3 = i;
    if (i3 < 0) { puts("degenerate (all points coplanar)"); return 0; }

    // owner[a*n+b] = index of the alive face containing directed edge a->b.
    vector<int> owner((size_t)n * n, -1);
    vector<Face> faces;
    auto addFace = [&](int a, int b, int c) {
        int id = faces.size();
        faces.push_back({a, b, c});
        owner[(size_t)a * n + b] = owner[(size_t)b * n + c] = owner[(size_t)c * n + a] = id;
    };
    // Initial tetrahedron, each face oriented so the 4th vertex is behind it.
    int t[4] = {0, i1, i2, i3};
    for (int k = 0; k < 4; k++) {
        int a = t[(k + 1) % 4], b = t[(k + 2) % 4], c = t[(k + 3) % 4], d = t[k];
        if (orient(p[a], p[b], p[c], p[d]) > 0) swap(b, c);
        addFace(a, b, c);
    }
    vector<int> alive = {0, 1, 2, 3};
    vector<char> vis;

    for (int i = 0; i < n; i++) {
        if (i == 0 || i == i1 || i == i2 || i == i3) continue;
        vis.assign(faces.size(), 0);
        bool any = false;
        for (int f : alive) {
            const Face& F = faces[f];
            if (orient(p[F.a], p[F.b], p[F.c], p[i]) > 0) vis[f] = 1, any = true;
        }
        if (!any) continue;  // inside or on the hull: nothing changes
        // Horizon: edge a->b of a visible face whose twin b->a is not visible.
        vector<pair<int, int>> horizon;
        vector<int> keep;
        for (int f : alive) {
            if (!vis[f]) { keep.push_back(f); continue; }
            int v[3] = {faces[f].a, faces[f].b, faces[f].c};
            for (int k = 0; k < 3; k++) {
                int a = v[k], b = v[(k + 1) % 3];
                if (!vis[owner[(size_t)b * n + a]]) horizon.push_back({a, b});
            }
        }
        for (auto [a, b] : horizon) {   // cone from p[i] over the horizon
            keep.push_back(faces.size());
            addFace(a, b, i);
        }
        alive = keep;
    }

    double area = 0;
    lll vol6 = 0;
    for (int f : alive) {
        const P3 &A = p[faces[f].a], &B = p[faces[f].b], &C = p[faces[f].c];
        P3 c = cross(B - A, C - A);
        area += sqrt((double)dot(c, c)) / 2;
        vol6 += dot(A, cross(B, C));  // signed volume of (O,A,B,C) x6
    }
    printf("faces %d\n", (int)alive.size());
    printf("area %.6f\n", area);
    printf("volume %.6f\n", (double)vol6 / 6);
}
Python
import sys
from math import sqrt


def sub(a, b):
    return (a[0] - b[0], a[1] - b[1], a[2] - b[2])


def cross(a, b):
    return (a[1] * b[2] - a[2] * b[1],
            a[2] * b[0] - a[0] * b[2],
            a[0] * b[1] - a[1] * b[0])


def dot(a, b):
    return a[0] * b[0] + a[1] * b[1] + a[2] * b[2]


def orient(a, b, c, d):
    # Signed volume x6: > 0 if d is on the side the normal of (a,b,c) points to.
    return dot(cross(sub(b, a), sub(c, a)), sub(d, a))


def hull3d(pts):
    p = sorted(set(pts))
    n = len(p)
    i1 = 1 if n > 1 else None
    i2 = next((i for i in range(1, n) if i1 is not None
               and cross(sub(p[i1], p[0]), sub(p[i], p[0])) != (0, 0, 0)), None)
    i3 = next((i for i in range(1, n) if i2 is not None
               and orient(p[0], p[i1], p[i2], p[i]) != 0), None)
    if i3 is None:
        return None, p
    owner = {}          # directed edge (a, b) -> face id
    faces = []

    def add_face(a, b, c):
        faces.append((a, b, c))
        fid = len(faces) - 1
        owner[(a, b)] = owner[(b, c)] = owner[(c, a)] = fid
        return fid

    t = [0, i1, i2, i3]
    alive = []
    for k in range(4):
        a, b, c, d = t[(k + 1) % 4], t[(k + 2) % 4], t[(k + 3) % 4], t[k]
        if orient(p[a], p[b], p[c], p[d]) > 0:
            b, c = c, b
        alive.append(add_face(a, b, c))

    for i in range(n):
        if i in t:
            continue
        vis = {f for f in alive
               if orient(p[faces[f][0]], p[faces[f][1]], p[faces[f][2]], p[i]) > 0}
        if not vis:
            continue
        keep = [f for f in alive if f not in vis]
        for f in vis:
            a, b, c = faces[f]
            for u, v in ((a, b), (b, c), (c, a)):
                if owner[(v, u)] not in vis:      # horizon edge
                    keep.append(add_face(u, v, i))
        alive = keep
    return [faces[f] for f in alive], p


def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    pts = [tuple(map(int, data[1 + 3 * i: 4 + 3 * i])) for i in range(n)]
    faces, p = hull3d(pts)
    if faces is None:
        print("degenerate (all points coplanar)")
        return
    area = 0.0
    vol6 = 0
    for a, b, c in faces:
        cr = cross(sub(p[b], p[a]), sub(p[c], p[a]))
        area += sqrt(dot(cr, cr)) / 2
        vol6 += dot(p[a], cross(p[b], p[c]))
    print("faces", len(faces))
    print("area %.6f" % area)
    print("volume %.6f" % (vol6 / 6))


main()

Input của ví dụ chạy tay và output:

7
0 0 0
4 0 0
0 4 0
0 0 4
3 3 3
1 1 1
5 1 -2
faces 8
area 66.974691
volume 36.000000

Hai chương trình đã được đối chiếu với một lời giải vét cạn O(n4) (với mỗi bộ ba điểm, kiểm tra mọi điểm nằm cùng một phía; gom các mặt phẳng tựa, tính diện tích đa giác phẳng trên từng mặt phẳng) trên 1800 bộ test ngẫu nhiên, gồm cả tọa độ trong {−1,0,1}3 (rất nhiều điểm đồng phẳng, thẳng hàng), toàn bộ đồng phẳng và toàn bộ thẳng hàng. Với 3000 điểm trên mặt cầu bán kính 106 (mọi điểm đều nằm trên bao, trường hợp nặng nhất), bản C++ chạy khoảng 0,06 giây.

Độ phức tạp

  • Thời gian O(n2): mỗi lần thêm điểm, ta duyệt mọi mặt đang sống để tìm mặt nhìn thấy. Theo công thức Euler, đa diện tam giác hóa có V đỉnh thì có F=2V−4≤2n mặt, nên mỗi bước O(n), cả thuật toán O(n2). Số mặt mới tạo ra mỗi bước bằng số cạnh chân trời, tổng cộng cũng O(n2) trong trường hợp xấu.
  • Bộ nhớ: bảng owner kích thước n2 số nguyên (với n=3000 khoảng 36 MB). Nếu giới hạn bộ nhớ chặt, thay bằng unordered_map theo khóa u·n+v, hoặc lưu cho mỗi mặt chỉ số ba mặt kề, khi đó bộ nhớ O(n) cộng với danh sách mặt đã tạo.
  • Bản Python cùng thuật toán nhưng chậm hơn trên 100 lần (3000 điểm trên mặt cầu mất khoảng 9 giây), dùng để hiểu và kiểm tra với n vài trăm.
Gia tăng ngẫu nhiên: O(nlogn) kỳ vọng

Chỗ tốn kém của bản O(n2) là tìm mặt nhìn thấy bằng cách duyệt hết mọi mặt. Bản nhanh (Clarkson và Shor) làm như sau:

  1. Trộn ngẫu nhiên thứ tự các điểm.
  2. Duy trì đồ thị xung đột (conflict graph): với mỗi điểm chưa thêm q, lưu một mặt hiện tại mà q nhìn thấy (hoặc "ở trong"); với mỗi mặt, lưu danh sách điểm chưa thêm đang nhìn thấy nó.
  3. Khi thêm p: mặt xung đột của p cho ngay một mặt sáng, từ đó loang (BFS/DFS qua mặt kề) để lấy cả vùng sáng và chân trời, chỉ tốn thời gian tỉ lệ với số mặt bị xóa.
  4. Với mỗi mặt mới (u,v,p) dựng trên cạnh chân trời u→v, các điểm có thể thấy nó chỉ nằm trong danh sách xung đột của hai mặt cũ kề cạnh uv (mặt sáng bị xóa và mặt tối còn lại). Ta chỉ kiểm tra lại những điểm đó.

Phân tích ngược (backward analysis), giống thuật toán đường tròn bao nhỏ nhất trong Thuật toán ngẫu nhiên: với thứ tự ngẫu nhiên, số mặt mới tạo ở bước i có kỳ vọng O(1) (bằng bậc trung bình của một đỉnh ngẫu nhiên, ≤6), và tổng công việc cập nhật xung đột có kỳ vọng O(nlogn). Trong thi đấu, bản O(n2) thường đủ; bản này cần khi n≥105.

Suy biến: đồng phẳng, thẳng hàng, nhiễu loạn

  • Ít hơn 4 điểm không đồng phẳng. Nếu mọi điểm thẳng hàng hoặc đồng phẳng thì bao là đoạn thẳng hoặc đa giác phẳng, thể tích 0. Code trên báo degenerate; nếu đề cần diện tích của "đa giác phẳng" đó, chiếu các điểm xuống mặt phẳng tọa độ ứng với thành phần pháp tuyến lớn nhất rồi dùng bao lồi 2D (diện tích chia cho |nk|/|n→| để bù phép chiếu).
  • Điểm nằm trên một mặt hoặc trên phần kéo dài của mặt. Dùng điều kiện chặt orient>0 cho "nhìn thấy". Điểm nằm đúng trên một mặt (orient =0) không làm mặt sáng, nên bị bỏ qua khi nó nằm trong mặt đó; khi nằm ngoài biên mặt, một mặt kề sẽ thấy nó chặt và thuật toán vẫn đúng. Hệ quả: một mặt phẳng của đa diện thật (ví dụ mặt vuông của khối lập phương) có thể bị chia thành nhiều tam giác đồng phẳng. Diện tích và thể tích vẫn đúng, nhưng số mặt tam giác không phải số mặt thật của đa diện.
  • Đếm mặt thật. Gộp các tam giác kề nhau có pháp tuyến cùng phương (tích có hướng hai pháp tuyến bằng 0→ và tích vô hướng dương), ví dụ bằng DSU trên các cạnh có hai mặt đồng phẳng.
  • Nhiễu loạn (perturbation). Một cách xử lý suy biến là dịch mỗi điểm một lượng rất nhỏ để không còn bốn điểm đồng phẳng. Làm bằng số thực ngẫu nhiên (cỡ 10−9) thì dễ cài nhưng mất tính chính xác và có thể sinh mặt "mảnh" sai. Cách đúng là nhiễu loạn ký hiệu (symbolic perturbation, ví dụ Simulation of Simplicity): coi tọa độ điểm i là pi+ε(i) với ε vô cùng bé, khi orient=0 thì quyết định dấu theo hệ số của lũy thừa ε nhỏ nhất. Với tọa độ nguyên và điều kiện chặt như trên, thường không cần nhiễu loạn để tính diện tích, thể tích.

Ứng dụng: diện tích, thể tích, Delaunay qua paraboloid

Diện tích và thể tích. Diện tích mặt =12∑|(b−a)×(c−a)|. Thể tích =16∑a·(b×c), tổng các tứ diện có dấu từ gốc O tới từng mặt: phần tứ diện nằm ngoài khối bị trừ đi đúng nhờ dấu, nên công thức đúng cho mọi vị trí của O. Trọng tâm khối cũng tính được tương tự (trọng tâm từng tứ diện, trọng số là thể tích có dấu).

Tam giác phân Delaunay bằng phép nâng (lifting). Nâng mỗi điểm (x,y) trên mặt phẳng lên paraboloid: (x,y)↦(x,y,x2+y2). Khi đó:

Điểm d nằm trong đường tròn ngoại tiếp tam giác abc (định hướng ngược chiều kim đồng hồ) khi và chỉ khi điểm nâng d′ nằm dưới mặt phẳng qua a′,b′,c′.

Lý do: giao của một mặt phẳng z=αx+βy+γ với paraboloid chiếu xuống mặt phẳng là đường tròn x2+y2=αx+βy+γ; phần paraboloid nằm dưới mặt phẳng chiếu xuống đúng phần trong đường tròn. Do đó các mặt của bao dưới (mặt có pháp tuyến ra ngoài với thành phần z<0) chiếu xuống chính là các tam giác Delaunay: không điểm nào nằm trong đường tròn ngoại tiếp của chúng. Phép thử "in-circle" quen thuộc thực chất là orient của bốn điểm đã nâng.

Ví dụ: 5 điểm (0,0),(2,0),(0,2),(2,2),(1,1) nâng thành độ cao 0,4,4,8,2. Chạy hull3d trên các điểm nâng được 6 mặt: 4 mặt dưới chính là 4 tam giác Delaunay chung đỉnh (1,1), 2 mặt trên là hai nửa của hình vuông (bốn góc đồng phẳng sau khi nâng, đúng vì chúng cùng nằm trên một đường tròn). Bao trên cho tam giác phân "Delaunay xa nhất" (farthest-point Delaunay). Chi tiết về Delaunay, Voronoi và cách dùng xem Delaunay và Voronoi.

Phiên bản 1D của cùng ý tưởng: nâng x↦(x,x2) biến bài toán về parabol thành bài toán bao lồi 2D (xem bài uparab ở dưới).

⚠️ Lỗi thường gặp

  • Tràn số trong orient. Hiệu tọa độ tới 2·106, mỗi số hạng của định thức tới ≈8·1018, tổng có thể vượt 9,2·1018 của long long. Triệu chứng: bao sai lặt vặt trên test tọa độ lớn. Cách tránh: tích vô hướng cuối cùng dùng __int128 (như code), hoặc đảm bảo |tọa độ|≤105.
  • Dùng số thực và epsilon cho phép thử định hướng. Sai số làm một điểm "vừa thấy vừa không thấy" mặt kề, vùng sáng không liền, chân trời không khép kín, bao bị thủng (số mặt lệch khỏi 2V−4, thể tích âm). Với input nguyên, luôn tính định hướng bằng số nguyên chính xác; chỉ đổi sang double ở bước cuối (căn bậc hai cho diện tích).
  • Tứ diện ban đầu suy biến. Lấy đại 4 điểm đầu tiên mà chúng đồng phẳng thì mọi mặt có "pháp tuyến ra ngoài" sai chiều. Phải tìm lần lượt: điểm khác p0, điểm không thẳng hàng, điểm không đồng phẳng; và nhớ bỏ điểm trùng trước.
  • Định hướng mặt không nhất quán. Mặt mới phải là (u,v,p) với u→v là cạnh của mặt sáng (không phải (v,u,p)). Đảo chiều làm pháp tuyến hướng vào trong, ở bước sau mặt đó "thấy" gần như mọi điểm. Kiểm tra nhanh: tổng thể tích có dấu phải dương và F=2V−4.
  • Dùng ≥0 thay cho >0 khi xét nhìn thấy. Với điều kiện không chặt, một điểm đồng phẳng với một mặt làm mặt đó sáng, có thể tạo mặt suy biến diện tích 0 (ba điểm thẳng hàng) và phá cấu trúc cạnh kề. Dùng điều kiện chặt.
  • Đếm số mặt tam giác rồi coi là số mặt đa diện. Khi có điểm đồng phẳng, một mặt thật bị chia thành nhiều tam giác (khối lập phương 2×2×2 thêm tâm mặt trên ra 14 tam giác thay vì 6 mặt vuông). Nếu đề hỏi số mặt, phải gộp các tam giác đồng phẳng kề nhau.
  • Quên trộn ở bản O(nlogn). Thuật toán gia tăng ngẫu nhiên với input theo thứ tự xấu (ví dụ điểm trên mặt cầu sắp theo độ cao) thoái hóa về O(n2).

Biến thể / Mở rộng

  • Bao lồi 2D: cùng tư tưởng nhưng đơn giản hơn nhiều nhờ sắp xếp, xem Convex Hull (Bao lồi).
  • Delaunay và Voronoi: tam giác phân Delaunay là bao dưới của các điểm nâng, sơ đồ Voronoi là đối ngẫu của nó, xem Delaunay và Voronoi.
  • Giao các nửa không gian: theo đối ngẫu điểm và mặt phẳng, giao của n nửa không gian chứa một điểm trong biết trước tương ứng với bao lồi 3D của các điểm đối ngẫu.
  • Khoảng cách, va chạm giữa hai khối lồi: sau khi có bao, khoảng cách nhỏ nhất giữa hai đa diện lồi tính bằng các thuật toán như GJK; khoảng cách từ điểm trong tới bề mặt là min khoảng cách tới các mặt phẳng mặt.
  • Các kỹ thuật hình học khác trong mục Hình học.

Bài tập luyện

Kho bài CTOJ hiện chưa có bài yêu cầu dựng bao lồi 3D trực tiếp. Các bài dưới đây luyện những mảnh ghép của trang này: phép tính vector 3D chính xác trên số nguyên, chiếu điểm trong không gian bằng tích có hướng và tích vô hướng, và phép nâng lên parabol.

  • Khôi phục khối lập phương (rstcube) (Rất khó) Duyệt hoán vị tọa độ của 8 đỉnh rồi kiểm tra có tạo khối lập phương; cần ba vector cạnh từ một đỉnh có độ dài bằng nhau và tích vô hướng đôi một bằng 0, tính hoàn toàn trên số nguyên.
  • Tia laser trong thực tại song song (laserray) (Chuyên gia) Chiếu các điểm 3D lên mặt phẳng vuông góc với một vector pháp tuyến, dựng cơ sở của mặt phẳng bằng tích có hướng, rồi tìm đường tròn bao nhỏ nhất của hình chiếu.
  • Parabol chữ U (uparab) (Chuyên gia) Đổi biến z=y−x2 biến parabol y=x2+bx+c thành đường thẳng; đếm parabol "rỗng" chính là đếm cạnh của bao lồi trên, phiên bản một chiều thấp hơn của phép nâng Delaunay.
Trang này có hữu ích không? Đăng nhập để trả lời

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0