Bao lồi
Bao lồi của một tập điểm
Giới thiệu về máy tính này
Máy tính Bao lồi tìm đa giác lồi nhỏ nhất bao quanh một tập điểm 2D bằng thuật toán chuỗi đơn điệu của Andrew. Công cụ liệt kê các đỉnh góc của bao theo thứ tự ngược chiều kim đồng hồ, đếm số điểm nằm trên bao và bên trong bao, cho biết diện tích và chu vi chính xác, kèm biểu đồ phân tán vẽ viền kết quả. Các điểm trùng và thẳng hàng đều được xử lý đúng.
Cách tìm bao lồi
- Nhập các điểm dưới dạng cặp x,y phân cách bằng dấu phẩy — thứ tự không quan trọng.
- Máy tính gộp các điểm trùng và sắp xếp các điểm từ trái sang phải.
- Nó quét các điểm đã sắp xếp để dựng biên dưới và biên trên, chỉ giữ lại các đỉnh góc nơi đường viền rẽ trái.
- Đọc các đỉnh của bao, diện tích và chu vi, và xem đường viền được vẽ trên các điểm của bạn.
Ví dụ thường gặp
- Bốn góc hình vuông 0,0 6,0 6,4 0,4 với các điểm bên trong 3,2 và 2,1 → 4 đỉnh bao, diện tích 24, chu vi 20
- Tam giác 0,0 4,0 0,3 → 3 đỉnh bao, diện tích 6, chu vi 12
- Các điểm thẳng hàng 0,0 1,1 2,2 3,3 → bao suy biến (một đoạn thẳng), diện tích 0
- Hình vuông 0,0 4,0 4,4 0,4 cùng đỉnh nhọn 2,5 → 5 đỉnh bao vì đỉnh nhọn kéo dài cạnh trên
Câu hỏi thường gặp
Bao lồi là gì?
Bao lồi của một tập điểm là đa giác lồi nhỏ nhất chứa tất cả các điểm đó — giống như căng một sợi dây thun quanh các điểm ngoài cùng rồi thả cho nó co lại sát.
Những điểm nào trở thành đỉnh của bao?
Chỉ các điểm góc ở ngoài cùng mới nằm trên bao. Các điểm nằm hẳn bên trong hình, và các điểm nằm đúng trên một cạnh của bao, không được liệt kê là đỉnh.
Các điểm trùng hoặc thẳng hàng được xử lý thế nào?
Các điểm giống hệt nhau được gộp lại trước. Nếu mọi điểm nằm trên một đường thẳng, bao suy biến thành một đoạn thẳng có diện tích bằng 0, và máy tính báo đó là bao suy biến.
Tôi cần bao nhiêu điểm?
Cần ít nhất ba điểm phân biệt, không thẳng hàng để tạo được một bao có diện tích dương.