cây Quad liên quan đến vụ va chạm 2d

Question

Tôi đã nghiên cứu này:

https://github.com/mikechambers/ExamplesByMesh/blob/master/JavaScript/QuadTree/src/QuadTree.js

và tôi tin rằng tôi hiểu được ý tưởng chung về cây quad, mặc dù tôi làm có hai câu hỏi về cách thức hoạt động, và triển khai ở trên:

1. Bạn không phải xây dựng lại toàn bộ cây mỗi vài ms? Trong Javascript wouldnt này là cực kỳ chậm để làm gì?

2. Nếu tôi có một cái gì đó như thế này: http://davzy.com/screenshots/skitched-20120318-180324.png, sau đó nó đủ dễ dàng để tìm các dấu chấm khác trong cùng một quad nhưng tôi có một hình chữ nhật chạm 3 quads khác nhau, có cách nào tôi có thể làm cho nó hiển thị như một đứa trẻ của tất cả 3 trong số những quad?

3. Trên 144 ví dụ trên, nó nói Node.prototype._classConstructor = Node ;, Tôi chỉ tò mò điều gì đang xảy ra. Tôi nghĩ nguyên mẫu là một cách để xác định một chức năng hoặc biến để sử dụng trong tương lai trong một lớp, vì vậy tôi không chắc chắn những gì dòng này không.

Answer 1

1. Bạn không phải xây dựng lại toàn bộ cây mỗi vài ms? Trong Javascript wouldnt này là cực kỳ chậm để làm gì?

Tôi cho rằng điều đó phụ thuộc vào những gì bạn đang sử dụng; nhưng có, ví dụ phát hiện va chạm của tác giả trong his blog post about his QuadTree implementation sẽ xóa cây và lặp lại nó khoảng 24 lần mỗi giây (vì vậy, khoảng một lần mỗi 40 ms). Bạn có thể đánh giá cho chính mình cho dù đó là "cực kỳ chậm"; trên máy của tôi có vẻ khá trơn tru. (Và thậm chí nếu không, tôi hy vọng việc xây dựng lại QuadTree thực sự rẻ hơn/nhanh hơn việc vẽ lại tất cả các vòng tròn trên canvas.)

2. [& hellip;] Tôi có một hình chữ nhật trúng 3 quads khác nhau, có cách nào tôi có thể làm cho nó hiển thị như một đứa trẻ của tất cả 3 của những quads?

Tôi không chắc chắn những gì bạn có nghĩa là bằng cách "trưng bày", nhưng: nếu bạn gọi các nhà xây dựng với pointQuad tham số thiết lập để false thì các chi tiết hai chiều (ví dụ, họ có width và height ngoài đến x và y) và mọi mục sẽ là con của tứ giác nhỏ nhất phù hợp hoàn toàn bên trong. Trong ví dụ của bạn, vì hình chữ nhật cắt ngang đường giữa của canvas, nó sẽ là một con trực tiếp của quad gốc.

3. Trên 144 ví dụ trên, nó nói Node.prototype._classConstructor = Node ;, Tôi chỉ tò mò những gì đang xảy ra. [& Hellip;]

Các "lớp" Node có một "phân lớp" tên BoundsNode (sử dụng khi mục là hai chiều), và BoundsNode.prototype._classConstructor được thiết lập để BoundsNode (mà đè thừa hưởng Node.prototype._classConstructor). Điều này cho phép subdivide phương pháp Node 's để viết new this._classConstructor(...) để xây dựng một mới BoundsNode nếu this là một BoundsNode và mới đồng bằng Node nếu this là một đồng bằng Node.