Làm thế nào để tìm thấy ngã tư đầu tiên của một ray với vòng tròn di chuyển

Question

tôi đã phải vật lộn với một vấn đề trong một thời gian và cho đến nay vẫn chưa tìm thấy bất kỳ giải pháp tốt hơn thì ngây thơ một:

N vòng tròn được cho rằng đang di chuyển theo theo luật tuyến tính. Đối với mỗi vòng tròn, chúng ta có bán kính ban đầu (tại thời điểm 0.0), tọa độ ban đầu và bán kính và tọa độ của nó tại thời điểm 1.0 (thời điểm kết thúc). Chúng ta cũng có các tia k với các tọa độ nguồn gốc của chúng và một vectơ dọc theo tia. Mỗi tia chỉ tồn tại tại một thời điểm cụ thể t _k. Tôi cần để có thể tìm thấy giao điểm đầu tiên của một tia với bất kỳ vòng tròn nào. Số k dự kiến ​​là khá lớn (hàng triệu hoặc hàng tỷ) cũng như số vòng tròn dự kiến ​​(hàng nghìn). Tôi cần giải pháp nhanh hơn sau đó kiểm tra tất cả các tia đối với tất cả các vòng tròn.

Tôi đã tìm kiếm trên internet một thời gian nhưng tôi đã không tìm thấy phương pháp tiếp cận giải pháp tốt. Ngay cả một ý tưởng cho các vấn đề dễ dàng hơn của các vòng tròn không di chuyển sẽ được đánh giá cao.

Tôi có cảm giác rằng cây kd nên phù hợp với trường hợp tĩnh và có thể một kdetic kd-tree sẽ giải quyết vấn đề khó hơn. Tuy nhiên tôi không thể tìm ra cách sử dụng cây kd ngay cả đối với cây dễ dàng hơn.

Answer 1

Bạn có thể xem trường hợp này là trường hợp tĩnh trong 3D với thời gian dưới dạng toạ độ bổ sung. Đường tròn có đường dẫn trở nên thất vọng và tia nằm trong mặt phẳng thời gian = t _k. Nếu thất vọng không được định vị quá dày đặc hơn phân vùng không gian nhị phân (cây k-d, ...) có thể giúp.

Để tìm tất cả các phân vùng được vượt qua bằng tia, trước tiên hãy tìm phân vùng có nguồn gốc và vượt qua (trong cây) bằng phân vùng lân cận theo hướng tia. Nó phụ thuộc vào phương pháp phân vùng được sử dụng. Nó là tuyến tính trong số các phân vùng bị xuyên qua bởi tia.

Cập nhật: Đó là ý tưởng để đặt sự thất vọng trong mỗi phân vùng mà nó đang chạm vào. Một bực bội sẽ có nhiều phân vùng hơn.

Đây là ví dụ trong 1 thứ nguyên cộng với thời gian. Mọi thứ đều giống nhau, các vòng tròn có điểm bắt đầu và kết thúc và bán kính bắt đầu và kết thúc.

1 | E /
    | . /
    | ./
    | ./
    | ./
0 | S/
t/X 

Phân vùng theo hướng X:

| E :/
    | . :/ 
    | . : 
    | . /: 
    | ./: 
    | S/: 
      X 

hình thang này sẽ đi theo hai phân vùng.

Phân vùng theo hướng thời gian:

| E :/
    | . :/ 
    | . : 
t------------------- 
    | ./: 
    | S/: 
      X 

hình thang từ X phân vùng còn lại sẽ đi theo hai phân vùng thời gian, trong khi ở phân vùng đúng X nó sẽ đi chỉ trong phân vùng trên.

Để thực hiện nó cần thiết để tính toán là có một giao điểm giữa đường và mặt phẳng trục trên một số mặt phẳng và nếu không có giao lộ ở bên nào của mặt phẳng là đường thẳng. Tính toán là giống nhau trong trường hợp 2D, hoặc thậm chí ở kích thước cao hơn.

Answer 2

(Suy nghĩ to) Bạn có thể muốn sử dụng lưới octree hoặc đa độ phân giải với thuật toán của Bresenham để nhanh chóng loại bỏ nhiều kiểm tra?