Add Voronoi tessellation space
EwoutH opened this issue · 13 comments
Voronoi Tessellations can be useful in ABM scenarios where the concept of influence or control based on proximity is important. For instance, in urban planning, they can be employed to model the service areas of facilities like hospitals or fire stations, where each facility's influence is determined by the closest access for the population. In ecological studies, Voronoi diagrams can simulate animal territories, where each animal's territory is defined by the space closest to it relative to others, aiding in understanding spatial behaviors and interactions. In telecommunications, they can optimize cell tower placements by delineating areas of signal coverage, ensuring efficient network service with minimal overlap. These tessellations are also beneficial in retail and market analysis for determining the catchment areas of stores, helping businesses understand their direct market influence based on customer proximity.
We might want to implement two subtypes:
- A discrete variant, directly based on the new cell space. Agents are at a cell, and the Vonoroi space is utilized to determine cell area and neighbors.
PR: #2084 - A variant in which the cells are discrete, but agents move in continuous space. In here agents can be anywhere and check in which cell they are (basically what’s the closest centroid). This can be useful for clustering and geographical borders for example.
I would like to implement this feature, but some questions emerged when reading this and #1994.
- What should be considered centroid of the cell? The average agent position?
- If not, should I consider only relative distances to create the tesselation?
- Could you give more details about visualization? It is possible to use Scipy?
- What should be considered centroid of the cell? The average agent position?
In my view, that's fixed and user definable. So on creation you input a list / datastructure of centroid. Optionally it could be a CellAgent.
It would be interesting to have a dynamic Vonoroi space, like with (groups of) agents that represent a cell. But maybe do the fixed one first.
Haven't thought about visualisation yet, that would be something to investigate. Could be in an separate PR.
So on creation you input a list / datastructure of centroid.
This way, the tessellation is defined only by the listed centroids & euclidean distances and have nothing to do with Moore/Neumann grid neighborhoods?
This way, the tessellation is defined only by the listed centroids & euclidean distance
To initialize it, in my view, yes. Maybe @quaquel also has some thoughts.
have nothing to do with Moore/Neumann grid neighborhoods?
Yes. However, after initialisation it might be beneficial to calculate the borders of each cell and/or the neighbours of each cell once. This will take some initialisation time, but allows to check quickly in which cell agents are and which cells neighbour each other.
For an initial implementation, I would be okay with a static set of cells. Meaning, at initialisation, you input a set of coordinates which can't be changed afterwards. In the long term, we might want to add functionality to add or remove centroids (and thus cells, and recalculate borders and neighbors) or to dynamically move centroids.
Maybe @wang-boyu also has some thoughts on it from his mesa-geo experience.
Thanks for asking! Can I ask why it's based on discrete space? Does this mean the locations of facilities can only be integers? It seems to me that the space is continuous, with facilities having Point locations and service areas being Polygons.
In reality this should be a bit of a mixture I think. In my vision, the cells are discrete, can have properties and neighbours, but agents move in continuous space.
but maybe we need multiple variants to cover all use cases.
Yeah but I'm not thinking about moving agents (e.g., residents) yet here. For a facility with location (x, y) and an arbitrary shape of service area, why do we need to discretize its location, and rasterize its service area? Polygons can have properties and touch neighbors too.
why do we need to discretize its location, and rasterize its service area?
I dont think we need, this was a choice of implementation given the discussion above. The vertices of each polygon at the voronoi tesselation can be computed using PyHull's VoronoiTess (altough im a little worried about computational costs)
If the VoronoiSpace is based on discrete space, the agent's position should be a specific cell. This really is a very different use case from having agents moving in continuous space but having discrete property layers, and it makes no sense to me to mix these two very different use cases. In fact, this second case currently does not exist in MESA but has been mentioned in the context of PropertyGrids as a potential future extension.
If VoronoiSpace is based on discrete space, you need to compute the tessellation only once and use this to build up the connections between Cells. After initialization, there should be no need at all to recompute the tessellation.
Totally agree with you, @quaquel. For now should I finish the discrete case implementation (ignore voronoi tessellation cells boundaries and only consider its neighbors)?
I think the continuous agent movement case viability should be analyzed and implemented in a different PR. It would be interesting to implement a direct relation between cell capacity and polygon area, but I dont know what would be the benefits of a continuous movement agent.
Sounds good, I was thinking in that direction indeed. I updated the first post of that issue with the two cases.