Discrete Voronoi Topic Territories

The Challenge of Overlapping Territories

InIn 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 — a nearest-centroid space partition named after Georgy Voronoi, whose 1908 work on quadratic forms formalised the construction, and now a standard tool of computational geometry [1]. The everyday intuition is the same one used to draw postcode-style catchment maps: every point on the plane belongs to whichever seed (here, a topic centroid) it is closest to, and the boundary between two neighbouring regions is always the perpendicular bisector between their seeds. Applied to a fixed hex grid rather than a continuous plane, that same rule is what produces the discrete province structure below.

The trade-off this legacy engine accepted was the one built into the nearest-centroid rule itself: every grid cell gets exactly one owner, however close the runner-up category's centroid actually was. A page sitting almost equidistant between two topics — borderline — still had to be coloured as belonging wholly to one province or the other, with no way to show that it was nearly as much the other. That is the specific limitation the current k-blade engine (linked above) was built to remove, by letting a page's territory membership be a real, renderable overlap rather than a forced single choice.

Spatial Voronoi Category Assignment

DuringDuring 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

ToTo visualise the borders separating neighbouring country provinces, the SVG renderer inspects every hex cell $(x, y)$ and its adjacent neighbours $(nx, ny)$. When two neighbouring 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 centres, $\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

HoveringHovering 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.

References

1. F. Aurenhammer, "Voronoi Diagrams — A Survey of a Fundamental Geometric Data Structure," ACM Computing Surveys, vol. 23, no. 3, pp. 345–405, 1991. https://doi.org/10.1145/116873.116880