Discrete Voronoi Topic Territories

Spatial Partitioning & Political Geography

This article explains how the Concept Atlas partitions its $40 \times 40$ grid into discrete, non-overlapping topic provinces using spatial Voronoi nearest-category assignment, and how contested border lines are rendered along shared hex sides.

The Challenge of Overlapping Territories

In early iterations of spatial concept maps, topic regions were rendered as overlapping translucent rectangles or ellipses. While simple to compute, overlapping shapes created visual clutter, blurred domain boundaries, and made it difficult for readers to discern which category governed a particular region of the map.

To create an intuitive map resembling a political atlas of countries, the grid is partitioned into discrete, mutually exclusive Voronoi provinces.

Spatial Voronoi Category Assignment

During atlas generation in som_atlas.py, every grid cell $(x, y)$ on the $40 \times 40$ map is evaluated for category affinity:

  1. The centroid $(\bar{x}_c, \bar{y}_c)$ of every topic category $c \in C$ is computed from the locations of its constituent document nodes.
  2. Each hex cell $(x, y)$ calculates its Euclidean distance $d((x,y), (\bar{x}_c, \bar{y}_c))$ to all category centroids.
  3. The cell is assigned to the nearest category $c^* = \min_{c} d((x,y), (\bar{x}_c, \bar{y}_c))$, generating a 2D matrix of category labels (grid_categories).

Rendering Contended Territory Borders

To visualize the borders separating neighboring country provinces, the SVG renderer inspects every hex cell $(x, y)$ and its adjacent neighbors $(nx, ny)$. When two neighboring cells belong to different categories ($c_{(x,y)} \neq c_{(nx,ny)}$), a dashed border line (<line class="atlas-territory-border">) is drawn along the shared hexagon side:

\[E_1 = M + \vec{u} \cdot \frac{L}{2}, \quad E_2 = M - \vec{u} \cdot \frac{L}{2}\]

Where $M$ is the midpoint between hex centers, $\vec{u}$ is the perpendicular unit vector along the shared edge, and $L = \frac{R}{\sqrt{3}}$ is the exact side length of the hexagon. This ensures border lines lie 100% flush along hexagon edges with zero orthogonal spikes or whiskers.

Interactive Territory Hover & Inspection

Hovering over any regional header text (e.g. ✦ SOFTWARE ENGINEERING ✦) or any hex tile within category $C$ activates territory inspection mode:

  • All hex tiles and border lines belonging to category $C$ highlight with the is-territory-hovered CSS class, displaying a subtle gold or crimson parchment glow.
  • The fixed 3-line inspection banner displays the territory domain title, province status, and navigation guidance.