Phát hiện các hình dạng tùy ý

Question

Lời chào,

Chúng tôi có một tập hợp các điểm đại diện cho giao điểm của cơ thể 3d và mặt phẳng nằm ngang. Chúng tôi muốn phát hiện các hình dạng 2D đại diện cho các mặt cắt ngang của cơ thể. Có thể có một hoặc nhiều hình dạng như vậy. Chúng tôi đã tìm thấy các bài viết thảo luận cách hoạt động trên hình ảnh bằng cách sử dụng Biến đổi Hough, nhưng chúng tôi có thể có hàng nghìn điểm như vậy, vì vậy việc chuyển đổi sang một hình ảnh rất lãng phí. Có cách nào đơn giản hơn để thực hiện việc này không?

Cảm ơn bạn

Answer 1

Khi chuyển đổi mô hình 3D thành tập hợp các điểm, bạn đã vứt bỏ thông tin cần thiết để tìm hình dạng giao lộ. Đi theo biểu đồ kết nối cạnh khuôn mặt của mô hình 3D của bạn để tìm các điểm giao nhau trên mặt phẳng theo thứ tự.

Giả sử bạn có, hoặc có thể xây dựng, mô hình địa hình 3d (một số số đỉnh, gờ giữa đỉnh, khuôn mặt bị ràng buộc bởi các cạnh):

1. Duyệt qua danh sách cạnh cho đến khi bạn tìm thấy một giao với máy bay kiểm tra, thêm nó vào danh sách
2. Chọn một trong những gương mặt mà chia sẻ cạnh này
3. Duyệt qua các cạnh khác của khuôn mặt đó để tìm ngã tư tiếp theo, thêm nó vào danh sách
4. Lặp lại cho khuôn mặt khác chia sẻ cạnh đó cho đến khi bạn quay lại t cạnh bắt đầu

Bạn đã xây dựng một danh sách thứ tự các cạnh giao cắt mặt phẳng - nó không tầm thường để nội suy tuyến tính từng cạnh để tìm các điểm giao nhau, để tạo thành hình dạng giao lộ. Lưu ý rằng quá trình này giả định rằng đa giác khuôn mặt là lồi, trong trường hợp của bạn. Nếu âm lượng của bạn là lõm, bạn sẽ có nhiều hình dạng giao nhau riêng biệt và vì vậy bạn cần phải lặp lại quy trình này cho đến khi tất cả các cạnh đã được kiểm tra.

Có một số mã java thực hiện điều này here và một ứng dụng thử nghiệm khá tiện lợi here.

Controls:

• 1-5 để thay đổi âm lượng kiểm tra
• q và w để thay đổi số lượng máy bay truy vấn
• một, s, d để thay đổi tốc độ quét của truy vấn máy bay
• nhấp chuột trái và kéo để xoay xem
• nhấn phải chuột và kéo để xoay máy bay truy vấn

Answer 2

Thuật toán/mã từ câu trả lời được chấp nhận không hoạt động đối với các trường hợp đặc biệt phức tạp, khi mặt phẳng cắt một số đỉnh của bề mặt lõm. Trong trường hợp này "đi bộ" đồ thị kết nối cạnh-mặt tham lam có thể đóng một số đa giác trước thời gian.

Điều gì xảy ra là vì mặt phẳng cắt một đỉnh, tại một điểm khi đi bộ đồ thị có hai khả năng cho cạnh tiếp theo, và nó quan trọng cái nào được chọn.

Giải pháp có thể là triển khai thuật toán truyền tải đồ thị (ví dụ: tìm kiếm theo chiều sâu đầu tiên) và chọn vòng lặp dài nhất có chứa cạnh bắt đầu.