Skip to content

Mapping a set of random points to a uniform lattice

Notifications You must be signed in to change notification settings

phil8192/tile-maps

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

35 Commits
 
 
 
 
 
 
 
 

Repository files navigation

Tile maps

Mapping a set of random points to a uniform lattice

Problem

Given a set of N polygons corresponding to countries/regions/municipalities find a regular tessellation of N triangles, squares, or hexagons where each tile corresponds to a country such that the original spatial arrangement is preserved as much as possible.

More generally, find a mapping from a set of N arbitrary/random points whilst preserving the original arrangement.

The code in this repository is experimental. For an excellent/stable R package solution to this problem, see Joseph Bailey's geogrid.

Integer Linear Programming (ILP) approach

My first approach to this problem makes use of Linear Programming.

Installing COIN-OR

Cbc (Coin-or branch and cut) is an open-source mixed integer programming solver. It is faster than the GNU Linear Programming Kit (GLPK).

git clone --branch=stable/2.9 https://github.com/coin-or/Cbc Cbc-2.9
cd Cbc-2.9
git clone --branch=stable/0.8 https://github.com/coin-or-tools/BuildTools/
chmod 0700 BuildTools/get.dependencies.sh
BuildTools/get.dependencies.sh fetch
./configure --prefix=/usr/local --enable-cbc-parallel
make
sudo make install

verify parallel enabled

cbc -threads 8 -unitTest -dirMiplib=_MIPLIB3DIR_ -miplib

Simulated Annealing (SA) approach

My second approach to this problem makes use of the popular Simulated Annealing metaheuristic.

References

Releases

No releases published

Packages

No packages published

Languages