Metadata-Version: 2.4
Name: adaptive-voronoi-mapping
Version: 0.1.0
Summary: User-focused visualisation of large labelled spatial datasets via adaptive Voronoi mapping.
Author: Tekin Ertekin
Keywords: voronoi,quadtree,spatial,visualization,gis
Classifier: Programming Language :: Python :: 3
Classifier: Topic :: Scientific/Engineering :: Visualization
Classifier: Intended Audience :: Science/Research
Requires-Python: >=3.9
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: numpy
Requires-Dist: scipy
Requires-Dist: scikit-learn
Requires-Dist: matplotlib
Dynamic: license-file

# Adaptive Voronoi Mapping

**User-focused visualisation of very large labelled spatial datasets.**

Given millions of geolocated points, each carrying a binary class label (0 or
1), plotting every point produces an unreadable, overplotted smear. This
package instead builds an **adaptive Voronoi map**: it refines the domain
*finely* where the two classes meet and *coarsely* where one class dominates,
then summarises each region by its majority class. The result is a compact,
legible picture of *where each class prevails* — a map the eye can read at a
glance.

![raw overplotted points versus the adaptive Voronoi map and its region edges](https://raw.githubusercontent.com/tekinertekin/adaptive-voronoi-mapping/main/assets/hero.png)

*Left:* 60,000 labelled points, overplotted into noise. *Middle:* the adaptive
Voronoi map — one crisp boundary. *Right:* the region edges, automatically
**fine along the class boundary and coarse in the uniform interior**.

## Why Voronoi — and why it suits the human eye

This is the idea behind the master's thesis *"Çok Büyük Konumsal Verinin
Kullanıcı Odaklı Görselleştirilmesi"* (**user-focused** visualisation of very
large spatial data). "User-focused" means built for **human perception**: the
goal is not a pixel-perfect scatter but a picture the visual system parses
effortlessly.

Voronoi tessellations are a natural fit because the eye already reads them
everywhere — a giraffe's coat, cracked soil, the veins of a leaf are all
Voronoi-like partitions of space into locally-dominant cells:

![Voronoi-like tessellations in nature: giraffe coat, cracked soil, leaf venation](https://raw.githubusercontent.com/tekinertekin/adaptive-voronoi-mapping/main/assets/nature_voronoi.png)

By collapsing a dense point cloud into majority-class Voronoi regions — small
where detail matters (class boundaries), large where it does not — the map
matches how people naturally segment a scene into regions, instead of asking
them to integrate millions of overlapping dots.

## How it works

1. **Adaptive quadtree partition** (`quadtree.py`). The domain is covered by a
   uniform grid of square cells; each cell is recursively split into four
   quadrants while it is *too sparse* (point density below `min_density`) **or**
   *too mixed* (class dominance below `min_dominance`), stopping at `max_depth`.
   Cells therefore cluster around class boundaries and stay large in uniform
   areas.
2. **Voronoi diagram** (`mapping.py`). One seed is dropped inside each leaf cell
   and a Voronoi diagram is built over the seeds (plus four far-away frame
   points that bound the outer regions).
3. **Region colouring** (`mapping.py`). Every data point is assigned to its
   nearest seed via a ball tree; each region is coloured by the majority class
   of the points inside it — green for class 0, red for class 1, blue where
   empty.
4. **Neighbour filter** (optional). A region whose coloured neighbours are all
   the opposite class is flipped, removing isolated speckles.
5. **Rendering** (`plotting.py`) with matplotlib — optional region edges,
   overlaid raw points, and a background image.

An `average_entropy` metric (point-weighted mean binary entropy per region)
quantifies how class-pure the resulting map is; lower is better, and it lets
you compare parameter settings objectively.

## Install

```bash
pip install adaptive-voronoi-mapping
```

Requires Python ≥ 3.9 (numpy, scipy, scikit-learn and matplotlib are pulled in
automatically).

From a checkout, for development:

```bash
pip install -e .
```

## Quick start

Reproduce the header figure end-to-end on a generated dataset (no data needed):

```bash
python examples/demo_synthetic.py     # writes assets/hero.png
```

A real dataset ships with the repo (**clone it to get the file** — it lives
under `examples/` and is deliberately left out of the pip wheel):
`examples/worlddatas.txt`, ~245k labelled world points that the `world` preset
is tuned for. A `pip install`-only user brings their own `row col label` file
instead.

```bash
# from a repo checkout: run the bundled real dataset with a ready-made preset
avmap examples/worlddatas.txt --preset world --save world.png

# or set parameters explicitly
avmap mydata.txt --height 180 --width 360 --cell-size 30 \
      --max-depth 6 --min-density 17 --min-dominance 0.4 --filter --entropy
```

Library:

```python
from adaptive_voronoi import read_points, build_map, plot_map, PRESETS
import matplotlib.pyplot as plt

points = read_points("examples/worlddatas.txt")
vmap = build_map(points, **PRESETS["world"]["build"])
plot_map(vmap, points=points, **PRESETS["world"]["plot"])
plt.show()
```

## Data format

One point per line — three whitespace-separated integers:

```
row col label
```

`row` and `col` are integer coordinates scaled by `scale` (100 in the thesis
datasets, i.e. hundredths of a degree); `label` is `0` or `1`.

## Presets

Three presets (`turkey`, `world`, `airpollution`) reproduce the thesis
experiments — each bundles the domain size and refinement parameters for one
dataset. Explicit CLI flags override any preset value.

## Origin & credits

This is a clean reimplementation of the code behind the thesis above; the
algorithm and behaviour are unchanged — only the code was reorganised for
clarity and packaging. The three nature photographs are illustrative external
images included only to motivate the Voronoi idea (they are not produced by
this code and are not part of the dataset pipeline).

## License

MIT — see [LICENSE](LICENSE).
