3D Math - Chỉ giữ các vị trí trong một số lượng bãi nhất định

Question

Tôi đang cố gắng xác định từ một tập hợp lớn các vị trí cách thu hẹp danh sách của mình xuống đáng kể.

Hiện tại tôi có khoảng 3000 vị trí (x, y, z) và tôi muốn giữ các vị trí cách xa nhau nhất (tôi không cần giữ 100 vị trí trong vòng 2 yard) bán kính từ nhau).

Ngoài việc thực hiện phương pháp bạo lực và theo nghĩa đen thực hiện so sánh 3000^2, có ai có bất kỳ ý tưởng nào về cách tôi có thể thu hẹp danh sách này xuống hơn nữa không?

Tôi hơi bối rối về cách tôi nên tiếp cận điều này từ góc nhìn toán học.

Answer 1

Vâng, tôi không thể nhớ tên cho thuật toán này, nhưng tôi sẽ cho bạn biết một kỹ thuật thú vị để xử lý việc này. Tôi sẽ giả định rằng có một sự phân tán điểm ngẫu nhiên trong môi trường 3D.

Version đơn giản: Divide and Conquer

1. Divide không gian của bạn thành một lưới 3D của hình khối. Mỗi khối lập phương sẽ là X yards ở mỗi bên.
2. Khai báo mảng đa chiều [x, y, z] sao cho bạn có phần tử cho mỗi khối trong lưới của bạn.
3. Mọi phần tử của mảng phải là một đỉnh hoặc tham chiếu đến cấu trúc đỉnh (x, y, z) và mỗi tham số sẽ mặc định là NULL
4. Lặp lại từng đỉnh trong tập dữ liệu của bạn. in.
   • Làm cách nào? Vâng, bạn có thể giả sử rằng đỉnh (5.5, 8.2, 9.1) thuộc về MyCubes [5,8,9], giả sử X (chiều dài khối lập phương) có kích thước 1. Lưu ý: Tôi chỉ cắt ngắn các số thập phân/phao sang xác định khối lập phương nào.
5. Kiểm tra xem khối lập phương có liên quan đã được lấy bởi đỉnh chưa. Kiểm tra: Nếu MyCubes [5,8,9] == NULL sau đó (tiêm đỉnh của tôi) khác (không làm gì cả, quăng nó ra chỗ lấy, anh bạn!)

Hãy tiết kiệm một số bộ nhớ

Điều này sẽ cung cấp cho bạn một tập dữ liệu đơn giản hóa độc đáo trong một lần truyền, nhưng với chi phí của một lượng bộ nhớ lớn.

Vì vậy, làm thế nào để bạn thực hiện điều đó mà không cần sử dụng quá nhiều bộ nhớ?

Tôi muốn sử dụng một hashtable sao cho khóa của tôi là tọa độ Grid-Cube (5,8,9) trong mẫu của tôi ở trên.

If MyHashTable.contains({5,8,9}) then DoNothing else InsertCurrentVertex(...) 

Bây giờ, bạn sẽ có một giải pháp một đường chuyền với việc sử dụng bộ nhớ tối thiểu (không mảng khổng lồ với một số tiềm năng lớn của khối rỗng. Chi phí là bao nhiêu? Vâng, thời gian lập trình để thiết lập cấu trúc của bạn/lớp để bạn có thể thực hiện hành động Chứa trong một Hashtable (hoặc bạn ngôn ngữ tương đương)

Hey, kết quả của tôi là chunky!

đúng vậy, bởi vì chúng tôi đã lấy kết quả đầu tiên mà phù hợp với bất kỳ khối .Trung bình, chúng ta sẽ đạt được sự phân tách X giữa các đỉnh, nhưng như bạn có thể hình dung ra bây giờ, một số đỉnh sẽ vẫn gần nhau (ở các cạnh của hình khối).

Vì vậy, chúng tôi xử lý nó như thế nào? Vâng, chúng ta hãy quay trở lại phương pháp mảng ở đầu (bộ nhớ chuyên sâu!).

Thay vì chỉ kiểm tra để xem nếu một đỉnh đã nằm trong câu hỏi cube-in-, cũng thực hiện việc kiểm tra này khác:

If Not ThisCubeIsTaken() 
    For each SurroundingCube 
     If not Is_Your_Vertex_Sufficiently_Far_Away_From_Me() 
     exit_loop_and_outer_if_statement() 
     end if 
    Next 
    //Ok, we got here, we can add the vertex to the current cube because the cube is not only available, but the neighbors are far enough away from me 
End If 

Tôi nghĩ rằng bạn có lẽ có thể nhìn thấy vẻ đẹp của này, vì nó là thực sự dễ dàng để có được khối lân cận nếu bạn có một mảng 3D.

Nếu bạn làm một số làm mịn như thế này, bạn có thể thực thi chính sách 'không thêm nếu nó có 0.25X' hay gì đó. Bạn sẽ không phải quá nghiêm khắc để đạt được hiệu ứng làm mịn đáng chú ý.

Vẫn còn quá chunky, tôi muốn nó mịn

Trong sự thay đổi này, chúng tôi sẽ thay đổi hành động đủ điều kiện cho dù một đỉnh được phép mất nơi cư trú trong một khối lập phương.

If TheCube is empty OR if ThisVertex is closer to the center of TheCube than the Cube's current vertex 
    InsertVertex (overwrite any existing vertex in the cube 
End If 

Lưu ý, chúng tôi không phải thực hiện phát hiện lân cận cho thiết bị này. Chúng tôi chỉ tối ưu hóa về phía trung tâm của mỗi khối lập phương.

Nếu muốn, bạn có thể hợp nhất biến thể này với biến thể trước đó.

Cheat Chế độ

Đối với một số người trong tình huống này, bạn chỉ có thể tham gia một lựa chọn ngẫu nhiên 10% dữ liệu của bạn và đó sẽ là một việc đơn giản hóa đủ tốt. Tuy nhiên, nó sẽ rất chunky với một số điểm rất gần nhau. Ở mặt tươi sáng, phải mất tối thiểu vài phút. Tôi không khuyên bạn nên trừ khi bạn đang tạo mẫu.