Pathfinder: Contour Plots and Density Calculation

Posted: February 3rd, 2015 in News

Our next Pathfinder release will include color contour plots that allow you to dynamically display contoured data such as density or times remaining to exit.

pathfinder_contour — Pathfinder usage contours.

Because we want the contours to display and update smoothly as the user drags the time slider bar in the plot window, implementing this feature has presented some technical challenges. To get this working, here are some of the things we have had to do:

An example of Voronoi partitioning used to calculate local density. This is a Pathfinder verification calculation.

Select efficient algorithms to calculate the density (or other data).
Superimpose a finer mesh on the navigation mesh to provide detail for contour display.
Use multi-threading in the calculations.
Cache pre-calculated image frames and store them in a file for streaming to the display.
Use compression to reduce the file size.

Fundamental to the display of density is the algorithm actually used to calculate density. For a good discussion of the issues see the paper by Steffen and Seyfried, 2010. They present an approach using Voronoi diagrams, which we consider to be the most reliable method and use for verification calculations.

Given person positions, the Voronoi diagram partitions the plane into regions consisting of all points closest to each person. The resulting polygons are then the area assigned to each person and can be used to calculate the local density.

Artistically, the Voronoi diagram acquires meanings of personal space and “shows us that personal space exists only in relation to others and changes without our control.” See Boundary Functions, Scott Snibbe.

For speed, it is necessary that we use a simpler density calculation in which we identify all persons within a specified distance from a node in the contour mesh. The contribution of each person is used to calculate the density. We optimize this calculation by searching through persons, since in most cases there are significantly fewer people than occupied nodes. We use the Voronoi results to verify that the density calculation using the simplified approach is appropriate.

B. Steffen and A. Seyfried, 2010, “Methods for measuring pedestrian density, flow, speed and direction with minimal scatter,” Julich Supercomputing Centre (JSC), Physica A: Statistical Mechanics and its Applications, Volume 389, Issue 9, 1 May, Pages 1902–1910.