У меня есть большое количество объектов (шарики, для начала), которые движутся ступенчато в пространстве, по одному за раз, и не должны пересекаться.В настоящее время для каждого хода я проверяю столкновение с любым другим объектом. Несколько другие вопросы здесь имеют дело с этим, однако я подумал о, казалось бы, простом решении, которое, похоже, не подходит в этомконтекст, и мне интересно, почему.
Почему бы просто не сохранить 2 коллекции (для 2D или 3 в трех измерениях) всех объектов, отсортированных по координатам x и y (и z), соответственно, и в каждомпереместить поиск всех других объектов на заданном расстоянии (здесь диаметр шарика) в каждом измерении и выполнить фактическую проверку столкновения только для объектов в обоих (или во всех 3) наборах результатов?
Я понимаю, что это работает только для одинаковообъекты, но в качестве альтернативы можно использовать в два раза больше коллекций, отсортированных по (1) самой высокой (2) самой низкой координате каждого объекта для каждого измерения.Любая причина, почему это не будет работать, или даст значительно меньшее улучшение по сравнению с переходом от O (n) «парная проверка» к « метод сетки » или «квад / октре»?Я рассматриваю обновление этих отсортированных коллекций как дорогостоящую операцию, но при использовании, например, TreeSet (моя реализация была бы в Java), оно все равно должно быть значительно меньше, чем O (n), верно?