Thu nhỏ các đỉnh đa giác

Question

Thuật toán tốt để giảm số lượng đỉnh trong đa giác mà không làm thay đổi cách hiển thị của các đa giác là gì?

Đầu vào: Một đa giác, được biểu diễn dưới dạng danh sách các điểm, với chiều dài quá nhiều: đầu vào thô từ chuột chẳng hạn.

Kết quả: Một đa giác với nhiều đỉnh ít hơn trông vẫn giống như bản gốc: một thứ có thể sử dụng để phát hiện va chạm, ví dụ (không nhất thiết lồi).

Chỉnh sửa: Giải pháp cho điều này sẽ tương tự như việc tìm một dòng có nhiều phân đoạn phù hợp nhất trên biểu đồ. Nó được gọi là Phân đoạn Tối thiểu Hình vuông trong sách thuật toán của tôi.

Chỉnh sửa2: Thuật toán Douglas Peucker là những gì tôi thực sự muốn.

Answer 1

Edit: Oh nhìn, Simplifying Polygons

Bạn nói phát hiện va chạm. Bạn có thể đi thực sự đơn giản và tính toán một vỏ lồi bao quanh nó.

Nếu bạn quan tâm đến các khu vực lõm, bạn có thể tính toán thân lõm bằng cách lấy trọng tâm của đa giác và chọn một điểm để bắt đầu. Từ điểm bắt đầu xoay quanh tâm, tìm từng đỉnh bạn muốn giữ, và gán nó làm đỉnh kế tiếp trong thân tàu. Sự phức tạp của thuật toán sẽ đi vào cách bạn xác định các đỉnh để giữ, nhưng tôi chắc chắn bạn đã nghĩ về điều đó rồi. Bạn có thể ném tất cả các đỉnh của bạn vào xô dựa trên vị trí của họ so với centroid. Khi một xô được nhiều hơn một số tùy ý của các đỉnh đầy đủ, bạn có thể chia nó. Sau đó lấy giá trị trung bình của các đỉnh trong xô đó làm đỉnh để sử dụng trong thân tàu của bạn. Hoặc, quên các thùng, và khi bạn đang di chuyển xung quanh centroid, chỉ chọn một điểm nếu nó nhiều hơn một khoảng cách nhất định từ điểm cuối cùng.

Thực ra, bạn có thể chỉ sử dụng tất cả các đỉnh trong đa giác của mình làm "đám mây điểm" và tính toán thân lõm xung quanh đó. Tôi sẽ tìm một liên kết thuật toán. Trường hợp xấu nhất trên đây sẽ là một đa giác lồi hoàn toàn.

Một giải pháp thay thế khác là bắt đầu bằng hình chữ nhật có giới hạn. Đối với mỗi đỉnh trên hình chữ nhật, hãy tìm khoảng cách từ điểm đến đa giác. Đối với các đỉnh xa nhất, chia nó thành hai đỉnh khác và di chuyển chúng trong một số. Lặp lại cho đến khi một số tỷ lệ của một trong hai đỉnh hoặc khu vực được đáp ứng. Tôi phải suy nghĩ về chi tiết của cái này nhiều hơn một chút.

Nếu bạn quan tâm đến đa giác thực sự trông giống nhau, ngay cả trong trường hợp đa giác tự giao nhau, thì cách tiếp cận khác sẽ được yêu cầu, nhưng nó không có vẻ như cần thiết kể từ khi bạn hỏi về phát hiện va chạm.

Điều này post có một số chi tiết về phần thân lồi.

Answer 2

Có rất nhiều tài liệu ngoài kia. Chỉ cần google cho những thứ như "giảm lưới", "lưới đơn giản hóa", "lưới tối ưu hóa", vv