Làm thế nào để đơn giản hóa một lưới vuông diễu hành?

Question

Tôi đang chạy thuật toán marching squares (tương đối của các hình khối diễu hành) trên một mặt phẳng iso, sau đó dịch dữ liệu thành lưới tam giác.

Công trình này, nhưng tạo ra dữ liệu lưới rất phức tạp. Tôi muốn đơn giản hóa này đến tam giác tối thiểu cần thiết, như đã thấy minh họa dưới đây:

Tôi đã cố gắng lặp xung quanh đường viền (điểm -> phân khúc -> điểm -> ...), nhưng các đường viền có thể bị đảo ngược nếu một điểm có nhiều hơn 2 đoạn đính kèm.

Lý tưởng nhất là giải pháp nên khá nhanh để có thể thực hiện được khi chạy. Ngôn ngữ tôi đang sử dụng là C#, nhưng có thể chuyển ngôn ngữ đó từ hầu hết các ngôn ngữ khác của C.

Answer 1

Thực hiện bước này ngay lập tức, chuyển từ biểu diễn âm lượng sang biểu diễn lưới.

Sau đó, bạn có thể nhóm các khu vực với trường hợp 3,6,9,12 thành các phiên bản lớn hơn/dài hơn.

Bạn cũng có thể thử nhóm hình vuông thành hình vuông lớn hơn, nhưng vấn đề NP của nó để tối ưu hóa lý tưởng có thể mất nhiều thời gian.

Sau đó, bạn có thể chuyển đổi nó thành phiên bản đa giác.

Sau khi chuyển đổi thành đa giác, bạn có thể hợp nhất các cạnh.

Answer 2

Sử dụng tai Clipping không diễu hành ô vuông cho loại vấn đề:

http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf

Answer 3

Đây là vấn đề rất phổ biến trong đồ họa máy tính 3D. Các thuật toán giải quyết vấn đề này được gọi là thuật toán đơn giản hóa lưới. Tuy nhiên, vấn đề là đơn giản hơn nhiều trong việc giải quyết trong trường hợp 2D, vì không cần phải xem xét các tiêu chuẩn bề mặt.

Điều quan trọng đầu tiên là phải có cấu trúc dữ liệu lưới đáng tin cậy, cung cấp các hoạt động để sửa đổi lưới. Một tập hợp các hoạt động, có thể sản xuất và sửa đổi bất kỳ lưới nào chẳng hạn như tập hợp các "toán tử Euler".

Để đơn giản hóa lưới 2D cung cấp một phiên bản dày đặc của lưới 2D. Bạn chỉ cần chuyển đổi lưới tứ giác thành lưới tam giác bằng cách tách từng quad tại đường chéo của nó.

tam giác rậm lưới:

Sau đó lặp đi lặp lại sụp đổ các cạnh ngắn nhất, mà không phải là ở ranh giới. "Cạnh sụp đổ" là một hoạt động lưới điển hình, được miêu tả ở đây:

Sau một số bước lưới của bạn sẽ trông như thế:

Answer 4

Đơn giản hóa một lưới được tạo ra bởi hành quân hình vuông (như gợi ý trong câu trả lời ở trên) rất kém hiệu quả.Để lấy một đa giác ra khỏi trường vô hướng (ví dụ bitmap), trước tiên bạn nên chạy một phiên bản sửa đổi của hình vuông diễu hành chỉ tạo đường bao đa giác (ví dụ: trong 16 trường hợp hình vuông hành bạn không tạo hình, bạn chỉ cần thêm điểm đến một đa giác), và sau đó bạn chạy một thuật toán tam giác (ví dụ: Delaunay hoặc Ear Clipping).