Thuật toán hiệu quả để tìm các hình cầu cách xa nhau nhất trong bộ sưu tập lớn

Question

Tôi có một bộ sưu tập 10000 - 100000 hình cầu và tôi cần phải tìm ra những khoảng cách xa nhất.

Một cách đơn giản để làm điều này là chỉ cần so sánh tất cả các hình cầu với nhau và lưu trữ khoảng cách lớn nhất, nhưng điều này giống như một con heo tài nguyên thực sự của một thuật toán.

Các Sphere được lưu trữ trong các cách sau:

Sphere (float x, float y, float z, float radius); 

Phương pháp này Sphere :: distanceTo (Sphere & s) trả về khoảng cách giữa hai điểm trung tâm của vũ trụ.

Ví dụ:

Sphere *spheres; 
float biggestDistance; 

for (int i = 0; i < nOfSpheres; i++) { 
    for (int j = 0; j < nOfSpheres; j++) { 
     if (spheres[i].distanceTo(spheres[j]) > biggestDistance) { 
      biggestDistance = spheres[i].distanceTo(spheres[j]) > biggestDistance; 
     } 
    } 
} 

Những gì tôi đang tìm kiếm là một thuật toán nào đó vòng qua tất cả các kết hợp có thể theo một cách thông minh hơn, nếu có bất kỳ.

Dự án được viết bằng C++ (phải có), vì vậy mọi giải pháp chỉ hoạt động bằng các ngôn ngữ khác với C/C++ ít được quan tâm hơn.

Answer 1

Khoảng cách lớn nhất giữa hai điểm trong một tập hợp S của các điểm được gọi là diameter. Tìm đường kính của một tập hợp các điểm là một vấn đề nổi tiếng trong hình học tính toán. Nói chung, có hai bước ở đây:

1. Tìm thân lồi ba chiều bao gồm các trung tâm của mỗi quả cầu - nói, sử dụng thực hiện quickhull trong CGAL.

2. Tìm các điểm trên thân tàu cách xa nhau nhất. (Hai điểm trên bên trong của thân không thể là một phần của đường kính, hoặc nếu không họ sẽ là trên thân tàu, mà là một sự mâu thuẫn.)

Với quickhull, bạn có thể làm là bước đầu tiên trong thời gian O (n log n) trong trường hợp trung bình và O (n) thời gian chạy trường hợp xấu nhất. Nó có thể đảm bảo một trường hợp xấu nhất tốt hơn bị ràng buộc nếu bạn có thể đảm bảo tài sản nhất định về thứ tự của các lĩnh vực, nhưng đó là một chủ đề khác nhau.

Bước thứ hai có thể được thực hiện trong Ω (h log h), trong đó h là số điểm trên thân tàu. Trong trường hợp xấu nhất, h = n (mọi điểm đều nằm trên thân tàu), nhưng đó là điều không chắc nếu bạn có hàng nghìn quả cầu ngẫu nhiên. Nói chung, h sẽ nhỏ hơn nhiều so với n. Đây là an overview of this method.

Answer 2

Bạn có thể lưu trữ các hình cầu này trong một số BSP Tree không? Nếu đó là chấp nhận được, sau đó bạn có thể bắt đầu bằng cách tìm kiếm các nút của cây có chứa các hình cầu cách xa nhau nhất. Sau đó, bạn có thể tiếp tục xuống cây cho đến khi bạn đến các lĩnh vực riêng lẻ.

Answer 3

Vấn đề của bạn trông giống như một thứ có thể được giải quyết bằng đồ thị. Vì khoảng cách từ Sphere A đến Sphere B giống với khoảng cách từ Sphere B đến Sphere A, bạn có thể giảm thiểu số lượng so sánh bạn phải thực hiện.

Tôi nghĩ rằng những gì bạn đang xem tại đây được gọi là Adjacency List. Bạn có thể xây dựng một, và sau đó đi qua đó để tìm khoảng cách dài nhất.

Một cách tiếp cận khác mà bạn có thể sử dụng sẽ vẫn cung cấp cho bạn O (n^2) nhưng bạn có thể giảm thiểu số lượng so sánh bạn phải thực hiện. Bạn có thể lưu kết quả tính toán của bạn vào bảng băm trong đó khóa là tên của cạnh (vì vậy AB sẽ giữ độ dài từ A đến B). Trước khi bạn thực hiện phép tính khoảng cách, hãy kiểm tra xem AB hoặc BA có tồn tại trong bảng băm hay không.

EDIT

Sử dụng phương pháp kề-list (mà về cơ bản là một Breadth-First Search) bạn sẽ có được O (b^d) hoặc trường hợp xấu nhất O (| E | + | V |) phức tạp.

Answer 4

Paul đã suy nghĩ não của tôi và bạn có thể tối ưu hóa một chút bằng cách thay đổi

for (int j=0; j < nOfSpheres; j++) 

để

for (int j=i+1; j < nOfSpheres; j++) 

Bạn không cần phải so sánh cầu A đến B VÀ B đến A. Điều này sẽ thực hiện tìm kiếm O (n log n).

--- Bổ sung -------

Một điều khác làm cho phép tính này tốn kém là khoảng cách DistanceTo.

distance = sqrt((x2 - x1)^2 + (y2 - y1)^2 + (z2 - z1)^2) 

Rất nhiều bài toán. Bạn có thể cắt giảm bằng cách kiểm tra xem liệu

((x2 - x1)^2 + (y2 - y1)^2 + (z2 - z1)^2 > maxdist^2 

Xóa sqrt cho đến khi kết thúc.