Voronoi Geometry cut-off

[schroedtert]

Due to the fact how the Voronoi cells are computed with PedPy, obstacles/walls can introduce unexpected (wrong behavior).

See this scenario:

The expected output would look like this:

But actually it looks like this:

The reason for this is how the Voronoi cells, and their geometry interaction are computed:

1. Compute the Voronoi Cells (ignoring the geometry):
   
2. Cut these cells with any obstacle:
   
3. When a cell is cut in multiple parts, keep only the part where the pedestrian is located:
   

We need to discuss a better way to compute the Voronoi cells within geometries, such that these cases are handled correctly. At the same time the new algorithm should not excessively increase the compute time. Any ideas and suggestions are welcome!

[schroedtert]

From a former discussion with @MaikFZJ :

[an363]

My impression is that this is not an issue that should be solved with algorithmic "tricks", but rather pertains to a more general mathematical question associated with the Voronoi tessellation.

Consider that crossing a wall is tantamount to crossing a very large distance L (that will diverge to infinity). In this sense, the problem occurring for crowds is not a problem that emerges only after space has been tessellated, but during the Voronoi tessellation: Space should be tessellated based on the effective distance (accounting for L) and not based on Euclidean distances. As L is large, this implies that the boundary between cells in the above example (which should be equally distant, in the effective sense, to both agents) will follow the line of the wall.

After a quick check, and not surprisingly, this problem is well-known in other communities. It seems to be called "geodesic" Voronoi tessellation:

• Meng, W., Bo, P., Zhang, X., Hong, J., Xin, S., & Tu, C. (2023). An efficient algorithm for approximate Voronoi diagram construction on triangulated surfaces. Computational Visual Media, 9(3), 443-459. https://link.springer.com/content/pdf/10.1007/s41095-022-0326-0.pdf?pdf=button
• Qi, Y., Zong, C., Zhang, Y., Chen, S., Xu, M., Ran, L., ... & He, Y. (2023). GBGVD: Growth-based geodesic Voronoi diagrams. Graphical Models, 129, 101196. https://www.sciencedirect.com/science/article/pii/S1524070323000267
  but I am not familiar with this topic and I don't know if it is implemented in Python.

[chraibi]

One more term I found relevant is "Visibility-Voronoi diagram".
https://sharif.edu/~ghodsi/papers/mojtaba-ewcg07.pdf
https://www.sciencedirect.com/science/article/pii/S0925772106000496