Có thực sự ba phần cho câu hỏi của bạn, chứ không phải hai:
- cấu trúc dữ liệu gì nên được sử dụng để đại diện cho lưới?
- Tôi nên sử dụng thuật toán nào để trích xuất các cạnh từ cấu trúc dữ liệu lưới?
- Tập hợp các cạnh kết quả sẽ như thế nào?
Bạn phải đặt thêm câu hỏi để tìm câu trả lời phù hợp.
Cấu trúc dữ liệu nào nên được sử dụng để thể hiện lưới?
Bạn cần xử lý loại yếu tố nào?
Nếu bạn chỉ cần xử lý đa giác (vòng khép kín) và đơn giản (mỗi nút được kết nối với mọi nút khác trong phần tử, chẳng hạn như tứ diện), thì danh sách nút được sắp xếp đủ vì các cạnh có thể được ngụ ý từ danh sách các nút. Nếu, mặt khác, bạn cần phải xử lý các loại phần tử như hexahedra, lăng kính, hoặc polyhedra chung sau đó bạn cần thêm thông tin về cấu trúc liên kết phần tử. Một mảng ánh xạ cạnh đơn giản thường là đủ. Nó chỉ là một mảng [] [2] của các chỉ mục vào danh sách các nút của phần tử cho bạn biết cách kết nối các dấu chấm cho một kiểu phần tử đã cho.
Cấu trúc nửa cạnh được mô tả bởi Chris là lựa chọn tốt cho chỉ 2D. Trong 3D, có thể có một số phần tử tùy ý được gắn vào mỗi cạnh chứ không phải chỉ hai phần tử. Có một phần mở rộng 3D cho biểu diễn nửa cạnh mà tôi nghĩ được gọi là cấu trúc vòng hoa.
Nếu bạn phải hỗ trợ các loại phần tử tùy ý, tôi thích cấu trúc dữ liệu hoàn chỉnh hơn để thể hiện cấu trúc liên kết phần tử. Một lựa chọn phổ biến là sử dụng các cạnh và các cạnh đồng. Có một cấu trúc cạnh cho mỗi cặp nút được kết nối và một cạnh co cho mỗi lần sử dụng cạnh đó trong một phần tử. Nó tương tự như cách tiếp cận vòng hoa, nhưng rõ ràng hơn một chút.
Tôi nên sử dụng thuật toán nào để trích xuất các cạnh từ các phần tử?
Tốc độ hoặc bộ nhớ quan trọng như thế nào? Kết quả có nên bao gồm mỗi cạnh một lần cho mỗi phần tử hay chỉ một lần cho dù có bao nhiêu phần tử đang sử dụng nó? Thứ tự các cạnh trong kết quả có quan trọng không? Thứ tự các nút của mỗi cạnh có quan trọng không?
Thật khó để đưa ra thuật toán cho các loại phần tử tùy ý sẽ chỉ truy cập từng cạnh một lần. Để đảm bảo mỗi cạnh chỉ xuất hiện một lần, bạn có thể lọc kết quả, hoặc bạn có thể hơi bị hack và giữ một bit "truy cập" trên mỗi cạnh để đảm bảo bạn không dính nó vào kết quả hai lần.
Tôi nên trình bày kết quả như thế nào?
Điều gì quan trọng về cách tôi sẽ sử dụng kết quả?
Nếu bạn định sử dụng kết quả tính toán chuyên sâu tính toán, một mảng tọa độ lớn có thể là tùy chọn tốt nhất. Bạn không muốn lấy lại các tọa độ nút nhiều lần trong quá trình tính toán của bạn. Tuy nhiên, nếu bạn lọc kết quả để loại bỏ các cạnh trùng lặp, so sánh các tọa độ (6 đôi cho một cặp nút) không phải là cách để đi. Nếu bạn đang lọc, trước tiên hãy tạo danh sách các con trỏ tới cấu trúc cạnh, sau đó lọc ra các từ khóa trùng lặp và rồi tạo danh sách tọa độ của bạn. Bạn cũng có thể sử dụng phương pháp này với các cặp nút, nhưng sau đó bạn phải lọc theo cả hai lệnh có thể trên mỗi cạnh, tăng gấp đôi lượng thời gian cần thiết để lọc.
Danh sách các con trỏ cạnh cũng là cách để đi nếu bộ nhớ quan trọng hơn hiệu suất. Thay vì chuyển đổi danh sách cạnh của bạn thành một danh sách toạ độ, tuy nhiên, bạn tra cứu các tọa độ trong khi tính toán. Bắt các tọa độ nút là chậm hơn theo cách đó, nhưng bạn tránh tạo ra một danh sách lớn các tọa độ - bạn lưu trữ một con trỏ trên mỗi cạnh thay vì 6 đôi mỗi cạnh.
Nhiều ứng dụng lưới lưu trữ tất cả tọa độ trong một mảng toàn cầu lớn, với mỗi nút có chỉ mục vào mảng. Nếu trường hợp này xảy ra, thay vì chuyển đổi danh sách cạnh của bạn thành một mảng tọa độ, hãy chuyển đổi nó thành danh sách các chỉ mục thành mảng tọa độ chung. Hiệu suất không được nhiều từ một mảng tọa độ cục bộ, nhưng không có bộ nhớ và tổng chi phí của bộ nhớ.
