Thuật toán cho các cạnh tìm kiếm duy nhất từ ​​lưới đa giác

Question

Tôi đang tìm một thuật toán tốt có thể cho tôi các cạnh độc đáo từ một tập hợp dữ liệu đa giác. Trong trường hợp này, các đa giác được xác định bởi hai mảng. Một mảng là số điểm cho mỗi đa giác và mảng kia là danh sách các chỉ số đỉnh.

Tôi có phiên bản đang hoạt động nhưng hiệu suất sẽ chậm khi đạt hơn 500.000 polys. Phiên bản của tôi đi qua từng khuôn mặt và thêm các đỉnh được sắp xếp của mỗi cạnh vào một tập hợp :: stl. Tập dữ liệu của tôi sẽ chủ yếu là tam giác và tứ giác, và hầu hết các cạnh sẽ được chia sẻ.

Có thuật toán thông minh hơn cho điều này không?

Answer 1

Có
Sử dụng bản đồ băm đôi.
Mỗi cạnh có hai chỉ mục A, B. cho phép nói rằng A> B.
Bản đồ băm đầu tiên, cấp cao nhất A đến một bản đồ băm khác, lần lượt ánh xạ B thành một số giá trị đại diện cho thông tin bạn muốn về mọi cạnh. (hoặc chỉ là một bool nếu bạn không cần phải giữ thông tin cho các cạnh).
Về cơ bản, điều này tạo ra một cây hai cấp bao gồm các bản đồ băm.

Để tìm kiếm một cạnh trong cấu trúc này, bạn lấy chỉ mục lớn hơn, tìm kiếm chỉ mục ở cấp cao nhất và kết thúc với bản đồ băm. sau đó lấy chỉ mục nhỏ hơn và tìm nó trong bản đồ băm thứ hai này.

Answer 2

Chỉ cần làm rõ, bạn muốn, cho một danh sách đa giác như thế này:

A +-----+ B 
    \ |\ 
    \ 1 | \ 
    \ | \ 
     \ | 2 \ 
     \| \ 
     C +-----+ D 

Sau đó, thay vì cạnh như thế này:

A - B -+ 
B - C +- first polygon 
C - A -+ 

B - D -+ 
D - C +- second polygon 
C - B -+ 

sau đó bạn muốn loại bỏ trùng lặp B - C vs C - B cạnh và chia sẻ nó?

Bạn gặp phải vấn đề về hiệu suất nào với thuật toán của mình? Tôi muốn nói một tập hợp có thực hiện băm hợp lý nên thực hiện khá ok. Mặt khác, nếu băm của bạn không tối ưu cho dữ liệu, bạn sẽ có rất nhiều va chạm có thể ảnh hưởng xấu đến hiệu năng.

Answer 3

Cả hai đều chính xác. Sử dụng một hashset tốt đã nhận được hiệu suất vượt quá mức yêu cầu. Tôi đã kết thúc tập hợp băm nhỏ của riêng mình.

Tổng số cạnh sẽ nằm giữa N/2 và N. N là số đỉnh duy nhất trong lưới. Tất cả các cạnh được chia sẻ sẽ là N/2, và tất cả các cạnh độc đáo sẽ là N. Từ đó tôi phân bổ một bộ đệm của uint64 và đóng gói các chỉ số của tôi vào các giá trị này. Sử dụng một bộ nhỏ các bảng duy nhất tôi có thể tìm thấy các cạnh độc đáo nhanh chóng!

Answer 4

Trước tiên, bạn cần đảm bảo rằng các đỉnh của bạn là duy nhất. Đó là nếu bạn muốn chỉ có một cạnh tại một vị trí nhất định. Sau đó, tôi sử dụng cấu trúc dữ liệu này

typedef std::pair<int, int> Edge;

Edge sampleEdge;

std::map<Edge, bool> uniqueEdges;

Cạnh chứa các chỉ số đỉnh đó tạo nên lợi thế trong trật tự sắp xếp. Do đó nếu sampleEdge là một cạnh tạo thành các đỉnh với các số chỉ mục 12 và 5, sampleEdge.first = 5 và sampleEdge.12

Sau đó, bạn chỉ có thể làm

uniqueEdges[sampleEdge] = true;

cho tất cả các cạnh. uniqueEdges sẽ giữ tất cả các cạnh độc đáo.

Answer 5

heres C triển khai cạnh băm được sử dụng trong Blender chính xác với mục đích tạo nhanh các cạnh từ khuôn mặt, có thể cung cấp một số gợi ý cho người khác tự tạo.

http://gitorious.org/blenderprojects/blender/blobs/master/blender/source/blender/blenlib/intern/edgehash.c

http://gitorious.org/blenderprojects/blender/blobs/master/blender/source/blender/blenlib/BLI_edgehash.h

này sử dụng BLI_mempool, https://gitorious.org/blenderprojects/blender/blobs/master/blender/source/blender/blenlib/intern/BLI_mempool.c

https://gitorious.org/blenderprojects/blender/blobs/master/blender/source/blender/blenlib/BLI_mempool.h