Четырехъядерные деревья, относящиеся к 2d столкновению - PullRequest
Новая
       18

Четырехъядерные деревья, относящиеся к 2d столкновению

6 голосов
/ 19 марта 2012

Я изучал это:

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

и я полагаю, что понимаю общую идею о четырехугольных деревьях, хотя у меня есть два вопроса о том, как они работают, и о реализации выше:

  1. Разве вам не нужно перестраивать все дерево каждые несколько мс? В Javascript это не будет слишком медленно делать?

  2. Если у меня есть что-то вроде этого: http://davzy.com/screenshots/skitched-20120318-180324.png,, тогда достаточно легко найти другие точки в том же четырехугольнике, но у меня есть прямоугольник, который попадает в 3 различных четырехугольника, есть ли способ сделать он отображается как дочерний элемент всех этих четырех четырехугольников?

  3. В 144 из приведенного выше примера написано, что это Node.prototype._classConstructor = Node; мне просто любопытно, что происходит. Я думал, что прототип - это способ определить функцию или переменную для будущего использования в классе, поэтому я не уверен, что делает эта строка.

1 Ответ

6 голосов
/ 26 марта 2012

1. Разве вам не нужно перестраивать все дерево каждые несколько мс?В Javascript это не будет слишком медленно делать?

Полагаю, это зависит от того, для чего вы его используете;но да, пример обнаружения столкновений автора в его посте в блоге о его реализации QuadTree очистит дерево и заполнит его примерно 24 раза в секунду (так, примерно один раз в 40 мс).Вы можете судить сами, является ли это "чрезвычайно медленным";на моей машине это выглядит довольно гладко.(И даже если нет, я бы ожидал, что восстановление QuadTree будет на самом деле дешевле / быстрее, чем перерисовка всех кругов на холсте.)

2. […] У меня естьпрямоугольник, который попадает в 3 разных квадра, есть ли способ сделать так, чтобы он отображался как дочерний элемент всех этих трех квадов?

Я не уверен, что вы подразумеваете под «показом», но:если вы вызываете конструктор с параметром pointQuad, установленным на false, то элементы являются двумерными (т. е. имеют width и height в дополнение к x и y) и каждый элементбудет ребенком самого маленького четырехугольника, который он полностью поместит внутрь.В вашем примере, поскольку прямоугольник пересекает вертикальную среднюю линию холста, он будет прямым потомком корневого четырехугольника.

3. На 144 из приведенного выше примера он говорит этот Node.prototype._classConstructor = Node ;, мне просто интересно, что происходит.[…]

У Node «класса» есть «подкласс» с именем BoundsNode (используется, когда элементы двумерные), а для BoundsNode.prototype._classConstructor установлено значение BoundsNode (который переопределяет унаследованный Node.prototype._classConstructor).Это позволяет методу Node subdivide записать new this._classConstructor(...) для создания нового BoundsNode, если this является BoundsNode, и нового простого Node, если this является простым Node.

...