1 Introduction

Only positions of persons can be measured directly, all other values are derived by more (density) or less (speed) involved computations. The density, quantifying the spatial proximity of the pedestrians, is in particular a fundamental variable to assess the safety of a crowd gathering and is considered a classic indicator for the level of service and safety of pedestrian facilities [1,2,3,4]. The density is also central when analysing the individual fundamental diagram, a characteristic phenomenological relationship linking the flow rate and the density [5, 6]. Different definitions for the density for pedestrians can be found in the literature. Some of them are based on kernels [6, 7], Voronoi diagram [8], Minkowski fractal dimension [9], features tracks (and the distinction between moving and static features) [7], or background removal and pattern recognition [10]. See [11,12,13] for a comprehensive comparison and survey on techniques used to estimate the density.

The use of Voronoi diagrams for the analysis of pedestrian density was first developed and described for high density situations in simple geometries without the influence of walls and inside a crowd. The resulting density distribution was used also to calculate averages of quantities of interest over certain regions. However, more complicated geometries need more complicated distance calculations. Partially empty spaces require some modifications, too; an additional mechanism of limiting the (indifinte) size of the Voronoi cells is needed. These problems are only sketched in the original paper [8] and therefore subsequently not always handled correctly. Similarly, the averaging process is not always a trivial choice to make. Depending on the quantity obtained, different averages have to be used for optimal results. In this paper we address these issues and propose new methodologies to solve them.

2 Voronoi Diagrams in the Presence of Obstacles

It is obvious that obstacles (walls, barriers, gates) do not belong to the personal space of the person and the Voronoi cell has to be cut with the obstacle. But the effect of an obstacle is possibly more elaborated than simply cutting off the Voronoi cell—the shape of the Voronoi cell changes, too. The distance between points in space in the presence of obstacles should not be the standard Euclidian distance, but the length of the shortest possible path. For an example let us consider the dividing line for the cells of two persons, one standing at \( (-1,0)\) and the other at \((0,-2)\) with a wall between them from (0,0) to \((-100,-100)\), with a cutoff of 4 (see Fig. 5.1). The normal dividing line \( (-0.5,-1) + \alpha (1,2) \) is correct only for \( y \ge \ 0 \) (above the end of the wall), for \(y \le 0 \) the division line due to the wall is given by the equation

$$\sqrt{ x^2 + y^2} + 1 = \sqrt{x^2 + (y+2)^2},$$

which gives a hyperbola

$$x = \sqrt{3 y^2 + 6y + 2.25},$$

and, above of the wall, all space belongs to the first person or to no one.

This is still a fairly simple situation to compute, where the distance from point 1 is either the Euclidian distance or the Euclidian distance from the endpoint of the wall plus the distance from the agents to this endpoint. In more complicated situations—multi corner, rounded or multiple obstacles—the dividing line may be made up of many pieces of analytic functions or require numerical calculation. This exact dividing line is much more complicated for computation than the line based on Euclidean distance. Fortunately, this will usually be needed only for very few cells. As people have a non-zero extend, it seems appropriate not to allow a path to touch an obstacle, but keep some distance, for instance half shoulder width. In the examples used in this work we set this minimal distance to 0 cm and 15 cm, although the proper value depends on many factors. See also Fig. 5.2.

Fig. 5.1
figure 1

Calculation of Voronoi diagram with an obstacle. Left: all area; right: center part. The black curve is the obstacle while the curve is the dividing line. The green and blue curves are respectively the equidistance lines for the pedestrian located at (−1,0) and the pedestrian located at (0,−2)

Full size image
Fig. 5.2
figure 2

Examples of obstacles with 15 cm distance required. Left: wall from Fig. 5.1; right: vertical pole. See Fig. 5.1 for the legends

Full size image

3 Cutoff and Construction of a Density Distribution

Basic proxemics rules show that the personal space should not extend too far out, therefore some kind of a cutoff is necessary to limit the size of the cells. The simplest case is a constant cutoff, e.g. cutting all the cells at 0.5 m from the person. Unfortunately, this distance is variable and depends on the actual situation and density. While 0.5 m is probably sufficient for an evacuation situation with an homogeneous density, it may be too short for a relaxed waiting situation, where 1 m for instance will be more appropriate. A reasonable adaptive cutoff would be cutting at the minimal distance to another person, maximal at 1 m. If the cutoff is required to be the same for all persons, the 25% quantile or the mean of the minimal distance may be reasonable.

It is possible to use a “soft” cutoff, e.g a linear drop of density at the distance 0.4 to 0.6 m, or even a differentiable density, but this leads to complicated computations with little benefit. The cutoff proposed in [14]—restricting the whole space to the convex hull of the persons and additionally for each cell extending beyond the convex hull cutting out the triangle made of the position of the cells person and the two intersection points with the convex hull—is not systematically applicable. A density distribution can also be constructed by attaching a standard density kernel to every person. The Gaussian is the common choice, but others are possible. These functions have the same problems with obstacles, and the choice of the size of the kernel needs the same considerations as the cutoff choice, but is needed everywhere and not just for the edge of a group. A possible combination would be choosing Gaussians with \(\sigma \) such that the corresponding circle around a person has the same area as the Voronoi cell [13].

4 Averaging

The density function allows to define pointwise other quantities of interest for the entire area. These are for instance velocity \(\mathbf {v}\), speed \(v = ||\mathbf {v}||\), flux \( J = \mathbf {v}\cdot \rho \). While this can lead over time to a rich data set, for most purposes, a drastic reduction in the amount of data is necessary. This is usually achieved by averaging the obtained data over time or space. In stationary situations , e.g. the neighbourhood of a bottleneck for most of the evacuation time, averages over time [15] can give useful insights into the system. Similarly, averages over space or space and time may contain most of the important information of an experiment. However, there are pitfalls. It is necessary that the averages to allow the same algebra as the initial quantities, at least approximately. This means that the average speed times average density should be average flow, length divided by speed should be time needed (space mean speed, see [16]), etc. In the presence of large fluctuations, this requires care in the choice of the average.

The simplest problem is averaging density, the formulas for average over space D, time \(T_2-T_1\), and space and time are

$$\frac{1}{|D|}\int \rho (x,t)dx, \quad \frac{1}{T_2-T_1}\int \rho (x,t)dt, \quad \frac{1}{|D|}\frac{1}{T_2-T_1}\int \rho (x,t) dx dt.$$

Some quantities—like speed, direction are defined only where there is a person, and undefined where \(\rho (x)=0\). Here two different averages are possible, e.g. for speed, over the area occupied (5.1) or over (partial) persons (5.2):

$$\begin{aligned} \frac{\int v(x)\chi (\rho (x))dx}{\int \chi (\rho (x))dx} \end{aligned}$$
(5.1)
$$\begin{aligned} \frac{\int v(x) \rho (x)dx}{\int \rho (x)dx} \end{aligned}$$
(5.2)

Here \(\chi (\cdot )\) is the characteristic function. These averages differ, but both may be used in different contexts (5.1) may be used to predict behaviour if the speed is mostly determined by the floor (e.g. uphill, rough, slippery), (5.2) shows the movement of groups. Using

$$\frac{1}{|D|} \int |v(x)| \chi (\rho (x))dx $$

for an average means setting the undefined speed to zero and is definitely not reasonable. Here the average speed depends on the size of the empty area.

The velocity is important for the calculation of two inherently different quantities—the flux and the required passing time. These two uses require different averages. The average speed along a path is the harmonic average of the local speed (see (5.3))

$$\begin{aligned} \frac{\int d\mathbf{s}}{ \int {d\mathbf{s}}/{\mathbf {v}(\mathbf{s})}} \end{aligned}$$
(5.3)
$$\begin{aligned} \frac{\int <\mathbf {v}(\mathbf{s}), \mathbf {n}(\mathbf{s})> d\mathbf{s}}{\int d\mathbf{s}} \end{aligned}$$
(5.4)

while the average speed across a line is the arithmetic average of the normal component (5.4). If (5.3) is useful to predict timings, (5.4) gives fluxes across lines.

There is a general problem with the algebra of averages—the average of a product of two values is the product of the averages only if the values are uncorrelated, a condition that is definitely not present for the quantities of interest in pedestrian dynamics unless the dynamics can be mainly described in steady state.