Limit of Voronoi diagrams in soccer analysis, 2, simple numerical calculation

In this article, shown is simple numerical calculation for estimating players' occupying regions, with velocities of the players' movement.

("Player's occupying region" means a region where a player can cover without being disturbed by the other players. These regions are similar to Voronoi cells in a Voronoi diagram, if all players are in stationary state at a certain moment.)

The contents of the numerical calculation may be meaningless to inexperienced people.

I recommend them only to look at images.

The numerical calculation is not complicated.

The calculation scheme used is the 2D version of the 4th order Runge-Kutta method. (undergraduate level?)



Again I write, considering the velocity of the players, player's occupying region is far from Voronoi cell.

As an alternative to the Voronoi diagram, I suggest to illustrate regions (boundary lines) that players will cover a few seconds later.



The contents of this article are as follows.

• Reproduction of a Voronoi diagram 
• When there is initial velocity
• Calculation of collision boundary line from model speed
• Practical figure?

Figures in this articles is made with this program (jupiter notebook) on google colaboratory.

Reproduction of a Voronoi diagram

First, I reproduce a Voronoi diagram via test-particle calculation.

Fig. 1, a Voronoi diagram from 22 random points. Calculated from a python module (from scipy.spatial import Voronoi, voronoi_plot_2d). Width 105 m and height 65 m.

Fig. 2, boundary lines obtained from the test particle calculation.

Fig. 3, colors and symbols unique to each point.

Main contents of the calculation are as follows.

• The test particles have the same acceleration and the max speed, similar to those of 100 m runners.
• Calculated are temporal variations of the test particles.
• Finally, detected are particles having distances shorter than the threshold value.  This detection indicate particle collisions.

The max speed of the test particles is set to 9 m/s, and the acceleration is set to 3 m/s^2. (Equal in any direction)

The fourth-order Runge-Kutta method is used in calculating temporal variations of positions and speed of the test particles.

Calculation is performed during 7 seconds, and the time step is  0.1 seconds.

(If the initial speed is 0 m/s, moving distance is about 50 m in this 7 seconds. This distance would be enough for particles' collisions.)

Each point has 360 test particles.

If distance between two test particles are shorter than 1 m, it is regarded as a collision.


As is shown in the above figures 1-3, this  Voronoi diagram was reproduced via the test-particle calculation, with zero initial velocity.

In figure 2, one can see that the detected particles look like the borderline of the Voronoi diagram shown in figure 1.

In figure 3,  the test particles have own colors and symbols as same as the departure points.

If all test particles has zero initial velocity, namely if all players are in stationary state, the test-particle calculations can reproduce the Voronoi diagrams.

As is described in the previous article, this zero initial velocity is a implicit assumption in the soccer analysis.

In the above calculation, I applied the limited acceleration.

However, other velocity profile can reproduce the Voronoi diagrams (e.g., constant velocity, continuous acceleration, and others. Probably acceleration larger than 0).

Initial velocity

Next, I gave the points limited velocities, slower than 9 m/s.

These velocities are initial velocities of the test particles departuring from each point.

Its absolute value and direction of a velocity is given with uniform random numbers.

Fig. 4, speed ​​of generating points given randomly. If the length of the arrow is 5 m, the speed is 5 m / s. Even if the arrow can not be seen, the given speed is not 0 m / s.

Fig. 5, time change of the position (blue line circle) and speed (red arrow) of 360 particles leaving a certain point. Every second.

Figure 4 shows the random initial velocities, and figure 5 shows temporal variations of positions and velocities of 360 test particles from a point.

Due to the initial velocity and the upper velocity limit, the positions of the test particles are different from circles, and become ellipses.

And center positions of the test particles moves.

With these initial values, I calculated temporal variations of positions and velocities of all test particles, and detected paired particles.

The following figure shows the result.

The colors and symbols are the same as in figure 3.

Fig. 6, boundary particles from the initial velocities.

In figure 6, there are broken and isolated paired particles, while there are paired particles completely closing some points.

This figure would not be useful in soccer analysis.

However, this figure is more realistic than the Voronoi diagrams.

As is shown in the following panels, the Voroni diagrams are different from calculated results considering initial velocities.

Fig. 7, left, initial velocity 0 m/s. Right, random initial velocity.

If initial velocities are equal to zero, detected paired particles reproduce a Voronoi diagram.

If initial velocities are finite values, and if their directions are complicated, detected paired particles make shapes far from the Voronoi diagrams.

Do not rely on the Voronoi diagrams unlimitedly.

It is difficult to apply Voronoi diagrams in situations where players move fast.

An advantage of the Voronoi diagrams is to obtain players' LIKELY occupying regions without mathematical contradiction.

Paired particles from model velocities

Let's consider broken and isolated paired particles (boundary lines).

These particles are strange, and are undoubtedly influenced by the given initial velocities.

However, the initial velocities are so complicated that one cannot simplify the causal relationship.

Here, to understand these broken and isolated paired particles, modeled velocities are investigated.

• Three points are located on three vertices of an equilateral triangle.
• Two points have a constant initial velocity, 5 m/s, and one point has no velocity.
• Directions of two velocity vectors changes; 0, pi/2, pi, and pi*3/2 radian.
• Test particles have 3 m/s^2 acceleration, their maximum speed is 9 m/s.
• Calculations are for 7 seconds.

Fig. 8, filled symbols indicate paired particles. Open symbols indicate non-collidion particles. In this case, no initial velocity. Distances between the points are 20 m.

Fig. 9, paired and unpaired particles. Two black arrows show initial velocities of two points. The red filled circle has no velocity.

Fig. 10, paired and unpaired particles, in another initial velocity setting .

From these calculations, it is found that broken and isolated paired particles occur due to position and velocity settings of the points.

And some test particles do not collide with each other, and move in parallel.

These non-collision particles may make isolated paired particles far from points.

These behaviors make complicated distribution of paired test particles.

Practical one?

In the above calculations, calculation time is set to be 7 seconds.

In this 7 seconds,  a particle can travel 50 meters.

This LONG distance movement may be the cause of isolated paired particles far from points.

And this 7 seconds are much longer than time scale of playings in the soccer matches.

Positional relationship between players easily change in a few seconds.

Therefore, time scale of a few seconds is practical to investigate future in soccer analysis.

The following figure shows players' occupying regions in 3 seconds.

Fig. 11, players' occupying regions in 3 seconds. 

Even in this "3 seconds figure", there are broken and isolated paired particles.

For some playings (e.g., a long counter attack), other time scales would be practical.

Again note that the Voronoi diagrams are not always appropriate for soccer analysis.

If players move fast, one should avoid to use the Voronoi diagrams.

At least, do not rely on the Voronoi diagrams unlimitedly.