Earthmover distance

Python code for the post Earthmover Distance.

To install:

git clone https://github.com/j2kun/earthmover.git
cd earthmover
virtualenv -p python3 venv
source venv/bin/activate
pip install -r requirements.txt

To run:

$ python earthmover.py

Example usage

p1 = [
    (0, 0),
    (0, 1),
    (0, -1),
    (1, 0),
    (-1, 0),
]

p2 = [
    (0, 0),
    (0, 2),
    (0, -2),
    (2, 0),
    (-2, 0),
]

print(earthmover_distance(p1, p2))

Example output (with logging):

move 0.2 dirt from (0, 0) to (0, 0) for a cost of 0.0
move 0.2 dirt from (0, 1) to (0, 2) for a cost of 0.2
move 0.2 dirt from (0, -1) to (0, -2) for a cost of 0.2
move 0.2 dirt from (1, 0) to (2, 0) for a cost of 0.2
move 0.2 dirt from (-1, 0) to (-2, 0) for a cost of 0.2
0.8