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.
Mã giả
Press Run to animate the algorithm.
Time · Space
Cách dùng
- 1 Nhấn Run để dựng bao lồi của các điểm rải rác.
- 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 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 Đườ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).
Trình trực quan hóa Bao lồi (Convex Hull) là công cụ thuật toán miễn phí của Zerethon Tools. 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. Chạy hoàn toàn trong trình duyệt — không đăng ký, không tải lê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
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.