Chuyển tới nội dung chính
Z

Trình trực quan hóa Bao lồi (Convex Hull)

Bao lồi (convex hull) hoạt hình dựng bằng thuật toán monotone chain của Andrew trên một mặt phẳng điểm — quá trình push/pop kèm điều khiển từng bước. Chạy ngay trong trình duyệt của bạn.

Miễn phí Không cần đăng ký Chạy trên trình duyệt Tôn trọng riêng tư Updated

/

Mã giả

Press Run to animate the algorithm.

Cách dùng

  1. 1 Nhấn Run để dựng bao lồi của các điểm rải rác.
  2. 2 Theo dõi thuật toán monotone chain đẩy (push) các điểm vào và loại bỏ (pop) chúng khi khúc rẽ không phải rẽ trái.
  3. 3 Dùng Shuffle để tạo bộ điểm ngẫu nhiên mới, hoặc chạy từng thao tác một.
  4. 4 Đường viền màu xanh lá chính là bao lồi cuối cùng.

Vì sao dùng công cụ này

  • Xem thuật toán monotone chain của Andrew dựng bao dưới và bao trên.
  • Hiểu vì sao các điểm gây ra khúc rẽ phải sẽ bị loại khỏi chuỗi.
  • Quan sát quá trình dựng với độ phức tạp O(n log n) — chi phí chủ yếu nằm ở bước sắp xếp.
  • Chạy hoàn toàn trong trình duyệt của bạn. Không cần đăng ký, không tải lên.

Câu hỏi thường gặp

Bao lồi là gì?

Là đa giác lồi nhỏ nhất chứa trọn một tập điểm — hãy hình dung như kéo căng một sợi dây thun bao quanh tất cả các điểm rồi để nó siết chặt lại.

Công cụ này sử dụng thuật toán nào?

Thuật toán monotone chain của Andrew: sắp xếp các điểm, sau đó dựng bao dưới và bao trên bằng cách đẩy (push) từng điểm vào và loại bỏ (pop) bất kỳ điểm nào tạo ra khúc rẽ không phải rẽ trái (rẽ phải/theo chiều kim đồng hồ).

Độ phức tạp thời gian của bao lồi là gì?

O(n log n), chủ yếu do bước sắp xếp ban đầu quyết định; còn việc dựng chuỗi (chain construction) tự nó có độ phức tạp tuyến tính. Graham scan và QuickHull cũng có cùng chặn trung bình này.

Bao lồi được dùng để làm gì?

Phát hiện va chạm (collision detection), phân tích hình dạng, tìm đường (pathfinding), GIS, và như một bước tiền xử lý cho nhiều thuật toán hình học khác.

Trình trực quan hóa Bao lồi (Convex Hull) là gì?

Trình trực quan hóa Bao lồi minh họa cách tìm đa giác lồi nhỏ nhất bao quanh một tập điểm. Sử dụng thuật toán monotone chain của Andrew, công cụ sắp xếp các điểm rồi dựng bao dưới (lower hull) và bao trên (upper hull), loại bỏ (pop) bất kỳ điểm nào tạo ra một khúc rẽ không phải rẽ trái (non-left turn).

Tính năng

Hoạt ảnh từng bước

Xem bao lồi được xây dựng khi các điểm được sắp xếp và các phép kiểm tra góc rẽ được thực hiện.

Độ phức tạp

Thời gian: O(n log n) (chi phối bởi bước sắp xếp). Không gian: O(n).

Riêng tư 100%

Chạy hoàn toàn trong trình duyệt của bạn — không có gì được tải lên.

Ví dụ

Input

points incl. one interior point

Output

hull = outer points only; interior point excluded

Trường hợp sử dụng

  1. 1

    Hình học tính toán

    Xem bao lồi nền tảng được sử dụng bởi nhiều thuật toán hình học.

  2. 2

    Va chạm & giới hạn

    Tính toán ranh giới lồi khít quanh một đám mây điểm.

  3. 3

    Học các phép kiểm tra hướng

    Hiểu các phép kiểm tra rẽ trái/phải dùng để xây dựng bao lồi.

Tóm tắt

Trình trực quan hóa bao lồi (convex hull) của Zerethon minh họa động quá trình tìm đa giác lồi nhỏ nhất bao quanh một tập hợp điểm ngay trong trình duyệt của bạn, sử dụng thuật toán O(n log n) (chẳng hạn như Graham scan hoặc Andrew's monotone chain — bị chi phối bởi bước sắp xếp ban đầu). Các điểm nằm bên trong bị loại khỏi bao lồi; không gian sử dụng là O(n).

Danh mục
Thuật toán
Giá
Miễn phí
Quyền riêng tư
Chạy trên trình duyệt
Đăng ký
Không cần

Tài liệu tham khảo

Quyền riêng tư

Dữ liệu của bạn không bao giờ rời khỏi trình duyệt trừ khi được nêu rõ. Trình trực quan hóa Bao lồi (Convex Hull) chạy hoàn toàn phía client — không tải lên máy chủ, không ghi log, không theo dõi dữ liệu bạn nhập.

Công cụ liên quan

Trình mô phỏng Bubble Sort

Mô phỏng bubble sort có hoạt ảnh với các nút điều khiển từng bước, tốc độ, dữ liệu đầu vào tùy chỉnh, bộ đếm so sánh/hoán đổi trực tiếp và pseudocode. Chạy hoàn toàn trong trình duyệt của bạn.

Mở công cụ

Trình trực quan hóa Insertion Sort

Insertion Sort hoạt hình với các nút điều khiển từng bước, tốc độ, dữ liệu đầu vào tùy chỉnh, bộ đếm so sánh/ghi trực tiếp và mã giả (pseudocode). Chạy hoàn toàn trên trình duyệt của bạn.

Mở công cụ

Trình trực quan hóa Selection Sort

Selection Sort hoạt hình với các nút điều khiển từng bước, tốc độ, dữ liệu đầu vào tùy chỉnh, bộ đếm so sánh/hoán đổi trực tiếp và mã giả (pseudocode). Chạy hoàn toàn trên trình duyệt của bạn.

Mở công cụ

Trình trực quan hóa Merge Sort

Mô phỏng merge sort có hoạt ảnh với điều khiển từng bước, tốc độ, dữ liệu đầu vào tùy chỉnh, bộ đếm so sánh/ghi trực tiếp và mã giả (pseudocode). Chạy hoàn toàn trên trình duyệt.

Mở công cụ

Xây dựng, chia sẻ và phát triển trên Zerethon Social

Đăng ký miễn phí. Kiếm điểm, sưu tầm thành tựu và kết nối với nhà sáng tạo khắp thế giới.

Đăng ký miễn phí