Tìm các đỉnh độc đáo từ 'canh tam giác'

Question

Tôi đang xây dựng bộ chuyển đổi tệp CAD trên hai thư viện (Opencascade và DWF Toolkit).

Tuy nhiên, câu hỏi của tôi là plattform thuyết bất khả tri:

Given:

tôi đã tạo ra một lưới như một danh sách các mặt hình tam giác tạo thành một mô hình được xây dựng thông qua ứng dụng của tôi. Mỗi tam giác được xác định thông qua ba đỉnh, trong đó bao gồm ba phao (x, y & z tọa độ). Kể từ khi hình tam giác tạo thành một lưới, hầu hết các đỉnh được chia sẻ bởi nhiều hơn sau đó một hình tam giác.

Mục tiêu:

tôi cần phải tìm ra danh sách các đỉnh độc đáo, và để tạo ra một loạt các gương mặt bao gồm các bộ ba chỉ số trong danh sách này.

//step 1: build a list of unique vertices 
for each triangle 
    for each vertex in triangle 
     if not vertex in listOfVertices 
     Add vertex to listOfVertices 

//step 2: build a list of faces 
for each triangle 
    for each vertex in triangle 
     Get Vertex Index From listOfvertices 
     AddToMap(vertex Index, triangle) 

Trong khi tôi có một thực hiện mà thực hiện điều này, bước 1 (thế hệ của danh sách các đỉnh duy nhất) là rất chậm theo thứ tự của O (n:

gì tôi muốn làm điều này là !), vì mỗi đỉnh được so sánh với tất cả các đỉnh đã có trong danh sách. Tôi nghĩ "Này, cho phép xây dựng một hashmap của các thành phần đỉnh của tôi bằng cách sử dụng std :: map, để tăng tốc mọi thứ!", Chỉ để thấy rằng tạo ra một khóa duy nhất từ ​​ba giá trị dấu chấm động không phải là một nhiệm vụ tầm thường. Ở đây, các chuyên gia của stackoverflow đi vào chơi: Tôi cần một số loại hàm băm hoạt động trên 3 phao, hoặc bất kỳ chức năng nào khác tạo ra một giá trị duy nhất từ ​​một vị trí 3d-đỉnh.

Answer 1

Dump tất cả các đỉnh trong một mảng, sau đó thực hiện unique(sort(array)). Đây là O (k n log (n)), trong đó k là số tam giác trung bình có chung một đỉnh, thường là k < 7.

Thông báo trước duy nhất tôi có thể nghĩ đến là chức năng unique bạn sẽ có thể để có một con trỏ tới một hàm so sánh, kể từ khi bạn có thể muốn xem xét các đỉnh của bạn bằng nếu

distance(vertex1, vertex2) < threshold 

nhưng điều đó có vẻ là OK.

Answer 2

Ba giải pháp. Chắc chắn có những người khác

1. Sử dụng bản đồ băm. Điều này sẽ chỉ hoạt động nếu "giống nhau" có nghĩa là giống nhau
2. Sử dụng phân vùng không gian nhị phân để chia các điểm
3. Sử dụng lưới thông thường để chia điểm của bạn.

Trong trường hợp 2 và 3 nếu bạn muốn chỉ định một số dung sai, bạn sẽ cần phải tìm kiếm nhiều hơn một phần của cây hoặc lưới. Trong trường hợp BSP, điều này có nghĩa là kiểm tra xem bạn có nằm trong khả năng chịu đựng của mặt phẳng phân chia hay không và nếu như vậy đệ quy vào cả hai nửa. Trong trường hợp lưới, điều này có nghĩa là kiểm tra tất cả các ô lân cận nằm trong dung sai. Không phải là quá khó, nhưng có nghĩa là sẽ khó sử dụng một giải pháp "ngoài giá".

Answer 3

Ý tưởng chung để lấy hàm băm là nhân mỗi bitpattern của phao với prime và thêm chúng lại với nhau. Một cái gì đó như thế:

unsigned int hash_point(float x, float y, float z) 
{ 
    unsigned int* px = (unsigned int*)&x; 
    unsigned int* py = (unsigned int*)&y; 
    unsigned int* pz = (unsigned int*)&z; 

    return (*px)*PRIME1 + (*py)*PRIME2 + (*pz)*PRIME3; 
} 

Bạn nên lưu ý rằng sizeof (unsigned int) được coi là bằng sizeof (float) tại đây. Mẫu ở đây chỉ để minh họa ý tưởng chính, bạn nên điều chỉnh nó cho nhu cầu của bạn.