A comparative study of k‐nearest neighbour techniques in crowd simulation. (21st April 2017)

• Record Type: Journal Article
• Authors: Vermeulen, Jordi L.; Hillebrand, Arne; Geraerts, Roland
• Is Part Of: Computer animation and virtual worlds. Volume 28:Number 3/4(2017)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2017-04-21
• Subjects: comparative study -- crowd simulation -- nearest neighbours; Computer animation -- Periodicals; Visualization -- Periodicals; 006.6
• DOI: 10.1002/cav.1775
• Languages: English
• ISSNs: 1546-4261

Abstract

Abstract: The k ‐nearest neighbour ( k NN) problem appears in many different fields of computer science, such as computer animation and robotics. In crowd simulation, k NN queries are typically used by a collision‐avoidance method to prevent unnecessary computations. Many different methods for finding these neighbours exist, but it is unclear which will work best in crowd simulations, an application which is characterised by low dimensionality and frequent change of the data points. We therefore compare several data structures for performing k NN queries. We find that the nanoflann implementation of a k ‐d tree offers the best performance by far on many different scenarios, processing 100, 000 agents in about 35 ms on a fast consumer PC. Abstract : We compare nine different implementations of data structures used to answer k ‐nearest neighbour queries in the context of crowd simulation. We find that the nanoflann implementation of a k ‐d tree offers the best performance by far on many different scenarios, processing 100, 000 agents in about 35 ms on a fast consumer PC.