Estructura de datos espaciales 2D adecuada para Bocking Flocked en Java

Question

Estoy trabajando en una simulación de boiled flock solo por diversión, y quiero optimizarlo un poco. El área que necesita trabajo es encontrar boids cerca de un boid dado. Me imagino que para hacer eso, algún tipo de estructura espacial de datos adecuada para la tarea sería mi mejor opción (ver here y desplazarte hacia abajo un poco).

Sea lo que sea que vaya, me implementaré, desde cero, en Java. De esa forma aprenderé más sobre la estructura de datos que elijo que si hubiera llamado a un conjunto de funciones de la biblioteca.

Conozco R-Trees, k-d trees y Quadtrees. Todas son opciones factibles, en mi opinión. Pero no tengo ninguna experiencia con estas estructuras de datos y no estoy totalmente seguro de lo que mejor se adapta a mi propósito. No necesito nada en this scale - Estoy hablando quizás de unos cientos de boids, quizás como mucho mil, en lugar de un millón, aunque tenga en cuenta que podría terminar ejecutándolo en un teléfono Android con el tiempo.

favor me recomiendan una estructura de datos (no limitada a lo anterior, por supuesto) para esto, y me da una buena razón para elegir por encima de las alternativas.

Sí, he visto this question. No, no estoy satisfecho con la respuesta, no hay ningún razonamiento dado.

Oh, otra cosa, como dice el título, esto es estrictamente solo para dos dimensiones.

Answer 1

Honestamente, me gustaría empezar con una versión sin optimizar y ver hasta qué punto se puede tomar (¿cuántos boids). Después de eso, pruebe diferentes métodos y mida qué diferencia hacen. Creo que esa sería la mejor manera de aprender.