Voronoi Tesselation based Discrete Space

[vitorfrois]

First version of Voronoi Tesselation based Discrete Space,

described on issue #1895 . This feature allows the user to build a discrete space based on a random sample of points, where neighbors are defined by Delaunay Triangulation.

More specifically, Delaunay Triangulation is a dual-graph representation of the Voronoi Tesselation. Using this algorithm, we can easily find nearest neighbors without delimiting cells edges.

The library chosen for the triangulation algorithm implementation was PyHull, a wrapper of qhull C library, which deals with spatial calculations. The choice was made considering performance, size and usability (SciPy has a similar module but much heavier).

Based on my discussion with @EwoutH on the issue thread, i thought it would be useful to inherit DiscreteSpace class.

class VoronoiGrid(DiscreteSpace):

Example

from mesa import Model
from mesa.experimental.cell_space import VoronoiGrid, CellAgent

class MyAgent(CellAgent):
    def __init__(self, unique_id, model):
        super().__init__(unique_id, model)

Users can input cells centroids

points = [
    [0, 0], [0, 1], [0, 2], 
    [1, 0], [1, 1], [1, 2],
    [2, 0], [2, 1], [2, 2]]
grid = VoronoiGrid(centroids_coordinates=points, capacity=1, random=model.random)

and cells neighborhoods are defined by Delaunay triangulation

agent = MyAgent(1, model)
cell = grid.select_random_empty_cell()
agent.move_to(cell)
print(cell)
print(cell.neighborhood())

Cell([1, 0], [<__main__.MyAgent object at 0x7f2177268450>])
CellCollection({Cell([0, 1], []): [], Cell([1, 1], []): [], Cell([0, 0], []): [], Cell([2, 1], []): [], Cell([2, 0], []): []})

Next Steps

Definitely, next steps involve computing the boundaries of each cell using Voronoi Tesselation. This allow us to define capacity of each cell based on its area/volume.

[EwoutH]

Thanks, it's a great start! Using DelaunayTri is a smart approach.

I guess move_to currently move an agent to the cells centroid? While that is logical behavior, I would also like to see an method in which agents are moved to A) the closest point in the cell from their current position and B) a random spot in the cell. This could be a separate PR.

Another thing that it's needed in the long term is a method to check in which cell a point (and thus an agent) is.

@wang-boyu I would also appreciate a review from your mesa-geo expertise.

For the currently functionality, I would like some additional docstring and unittests. Then you can decide if you want to add further functionality to this PR, or merge this first and follow up with new PRs.

Edit: One thought, also for the other maintainers: Would we need separate Discrete and Continuous Voronoi spaces?