Im cố gắng để tam giác một đa giác để sử dụng trong một mô hình 3d. Khi tôi thử sử dụng phương pháp tai trên một đa giác với các điểm như chấm dưới đây, tôi nhận được hình tam giác, nơi các đường màu đỏ. Vì không có điểm nào khác bên trong các hình tam giác này có lẽ là chính xác. Nhưng tôi muốn nó triangulate khu vực bên trong các đường màu đen chỉ. Bất cứ ai biết về bất kỳ thuật toán sẽ làm điều này?Triangulation đa giác
Có nhiều thuật toán để tam giác một đa giác không cần phân vùng thành đa giác đơn điệu trước. Một được mô tả trong sách giáo khoa của tôi Computational Geometry in C, có mã liên kết với nó có thể được tải xuống miễn phí từ liên kết đó (trong C hoặc trong Java). Trước tiên, bạn phải có các điểm theo thứ tự tương ứng với một đường ngang. Mã của tôi giả định ngược chiều kim đồng hồ, nhưng tất nhiên là dễ thay đổi. Xem thêm Wikipedia article. Có lẽ đó là vấn đề của bạn, rằng bạn không có các điểm ranh giới được tổ chức một cách nhất quán?
Yêu sách Joseph của bạn, có một vài phiên bản của nó ngồi trên kệ phía sau tôi. Ngồi trong niềm tự hào của nơi giữa Edelsbrunner, Shamos & Perparata, và Hjelle & Daehlen. Một thực tế phải có cho bất cứ ai làm việc với TIN. –
@Shane: Cảm ơn những lời tốt đẹp! :-) –
Có lẽ bạn có thể đưa mã cho biết vào câu trả lời của mình? – Jonny
Wikipedia suggest rằng bạn phá vỡ các đa giác thành đa giác đơn điệu. Bạn kiểm tra xem đa giác có bị lõm không đơn giản bằng cách kiểm tra tất cả các góc nhỏ hơn 180 độ - bất kỳ góc nào có góc trên 180 là lõm, và bạn cần phải phá nó ở góc đó.
Cách tiếp cận thông thường là chia đa giác đơn giản thành đa giác đơn điệu bằng cách sử dụng phân tích hình thang và sau đó tam giác các đa giác đơn điệu. Phần đầu tiên có thể đạt được bằng thuật toán đường quét. Và có thể tăng tốc với cấu trúc dữ liệu phù hợp (ví dụ: danh sách cạnh được kết nối gấp đôi). Mô tả tốt nhất về điều này, mà tôi biết, có thể được tìm thấy trong Computational Geometry. This và this cũng có vẻ hữu ích.
Bạn cần sử dụng thuật toán EarClipping, không phải là Delaunay. Xem giấy trắng sau: http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf
Bạn có thể cắt hình thành các phần lồi và triangulate các phần này. Tuy nhiên, mặc dù bị lộn xộn với những con số phức tạp. –
Có triangulation của bạn bất kỳ khó khăn (Delaunay?) Hoặc làm bạn có bất kỳ hạn chế thời gian? Nếu không câu trả lời sẽ khá rộng. – pmr
Không có ràng buộc, mô hình được tạo ra một lần, vì vậy thời gian không phải là một vấn đề lớn. – user978281