# How UrbanGroundLookup Identifies and Classifies Urban Areas in Arnis

> Discover how UrbanGroundLookup uses density-based clustering to classify urban areas, converting building centroids into an efficient hash set for O(1) ground generation.

- Repository: [Louis Erbkamm/arnis](https://github.com/louis-e/arnis)
- Tags: how-to-guide
- Published: 2026-03-20

---

**`UrbanGroundLookup` employs an eight-stage density-based clustering pipeline that converts building centroids into a compact cell-based hash set, enabling O(1) classification of urban zones for stone ground generation.**

The `UrbanGroundLookup` struct serves as the core classification engine in the [Arnis](https://github.com/louis-e/arnis) repository, determining where the procedural world generator should place stone ground blocks instead of default grass. Implemented entirely in **src/urban_ground.rs**, this system processes OpenStreetMap building data through a spatial clustering pipeline that balances detection accuracy with memory efficiency.

## The Eight-Stage Urban Detection Pipeline

The classification logic operates as a sequential pipeline, transforming raw building coordinates into a queryable urban mask. Each stage is implemented as a distinct function within [`src/urban_ground.rs`](https://github.com/louis-e/arnis/blob/main/src/urban_ground.rs).

### 1. Density Grid Creation

The algorithm first quantizes the world into a uniform spatial grid to reduce computational complexity. The `create_density_grid()` function (lines 308–317) buckets every building centroid into square cells of approximately **64 blocks**, recording which buildings occupy each cell. This converts O(n) building coordinates into a sparse grid structure where n is the number of cells rather than individual buildings.

### 2. Identifying Dense Cells

Next, `find_urban_clusters()` (lines 326–331) filters the grid to identify **potentially urban cells**—those containing at least `min_buildings_per_cell` buildings. This threshold eliminates isolated structures like rural farmhouses while retaining areas with genuine building density.

### 3. Adaptive Expansion Calculation

To prevent fragmented detection in spread-out towns, `calculate_adaptive_expansion()` (lines 401–466) computes a dynamic expansion radius. When the algorithm detects low building density (low average buildings per cell or low occupancy rates), it automatically increases the expansion radius. This adaptive behavior ensures that sprawling suburban areas are recognized as single contiguous urban zones rather than disconnected clusters.

### 4. Cell Expansion

The `expand_cells_adaptive()` function (lines 468–488) grows all dense cells by the adaptive radius calculated in stage 3. Using 8-connected neighborhood expansion, it adds adjacent cells to the urban set, effectively "smoothing" the detection boundary and bridging small gaps between building groups.

### 5. Connected Component Detection

A flood-fill BFS algorithm (lines 345–382 within `find_urban_clusters()`) traverses the expanded cell set to identify **connected components**. Each contiguous group of touching cells forms a candidate urban cluster. This topological separation prevents merging distinct towns that happen to lie close together but are separated by non-urban space.

### 6. Cluster Filtering

The pipeline filters candidate clusters by total building count (lines 385–393). Only clusters containing at least `min_buildings_for_cluster` buildings survive this stage. This eliminates small villages or isolated commercial strips that should retain grass ground rather than urban stone.

### 7. Compact Lookup Construction

The `compute_lookup()` function (lines 236–267) converts surviving clusters into a `HashSet<(cx, cz)>` containing only the cell coordinates classified as urban. By storing cell indices rather than individual world blocks, the structure achieves approximately **4000× memory savings** compared to a per-block boolean array.

### 8. O(1) Query Classification

Finally, `is_urban()` (lines 119–126) provides constant-time classification. It converts world coordinates `(x, z)` to cell indices and tests membership in the hash set. This O(1) performance allows the terrain generator to query millions of blocks during world generation without bottlenecking the pipeline.

## Memory-Efficient Query Design

The `UrbanGroundLookup` struct prioritizes **memory density** over geometric precision. Rather than storing a polygonal hull or per-block bitmap, it maintains a sparse hash set of cell coordinates. This design choice reflects the specific constraints of Minecraft world generation, where:

- **Lookup speed** is critical during chunk generation
- **Memory overhead** must remain low for large cities (e.g., 10km² maps)
- **False positives** (stone in grassy areas) are visually acceptable within the 64-block cell resolution

The cell-based approach naturally handles both **compact cities** (high density, tight clusters) and **spread-out towns** (low density, large expansion radius) through the adaptive expansion logic described in stage 3.

## Using UrbanGroundLookup in Your Code

The Arnis codebase exposes both high-level convenience functions and low-level configuration APIs for ground classification.

### Basic Usage with `compute_urban_ground_lookup`

For most use cases, the `compute_urban_ground_lookup` function provides the simplest entry point:

```rust
use arnis::urban_ground::{compute_urban_ground_lookup, UrbanGroundLookup};
use arnis::coordinate_system::cartesian::XZBBox;

// Define a 1km × 1km world area
let world = XZBBox::rect_from_xz_lengths(1000.0, 1000.0).unwrap();

// Building centroids from OSM parsing (example data)
let buildings = vec![(120, 140), (130, 150), (125, 160), (800, 800)];

// Build the compact lookup
let lookup: UrbanGroundLookup = compute_urban_ground_lookup(buildings, &world);

// Query specific coordinates
assert!(lookup.is_urban(125, 150));  // Returns true (stone ground)
assert!(!lookup.is_urban(900, 900)); // Returns false (grass ground)

```

### Advanced Configuration with `UrbanGroundComputer`

For custom terrain generation requiring fine-tuned detection parameters, use the lower-level `UrbanGroundComputer` API:

```rust
use arnis::urban_ground::{UrbanGroundComputer, UrbanGroundConfig};
use arnis::coordinate_system::cartesian::XZBBox;

let bbox = XZBBox::rect_from_xz_lengths(2000.0, 2000.0).unwrap();

// Configure detection sensitivity
let cfg = UrbanGroundConfig {
    cell_size: 32,                    // Finer 32-block cells (default is 64)
    min_buildings_per_cell: 2,        // Lower density threshold per cell
    min_buildings_for_cluster: 8,     // Minimum buildings per urban zone
    concavity: 3.0,
    expand_hull: false,
    cell_expansion: 3,                  // Expansion radius in cells
};

let mut computer = UrbanGroundComputer::new(bbox, cfg);
computer.add_building_centroids(my_building_iter);
let lookup = computer.compute_lookup();

// Generate terrain based on classification
if lookup.is_urban(x, z) {
    // Place smooth stone or cobblestone
} else {
    // Place grass or dirt
}

```

## Summary

- **`UrbanGroundLookup`** classifies urban zones through an eight-stage pipeline implemented in **src/urban_ground.rs**, converting building centroids into a memory-efficient cell-based hash set.
- **Density-based detection** uses 64-block grid cells to identify high-building areas, with adaptive expansion logic that prevents fragmented detection in sprawling towns.
- **Connected component analysis** groups touching cells into clusters, filtering out small villages below the `min_buildings_for_cluster` threshold.
- **O(1) query performance** is achieved through coordinate-to-cell conversion and hash set membership tests, supporting real-time terrain generation during Minecraft world creation.
- **Configurable parameters** via `UrbanGroundConfig` allow tuning of cell size, density thresholds, and expansion radii for different map scales and urban morphologies.

## Frequently Asked Questions

### How does UrbanGroundLookup handle large rural areas with scattered buildings?

The `min_buildings_per_cell` and `min_buildings_for_cluster` thresholds act as filters during stages 2 and 6 of the pipeline. Scattered rural buildings typically fail to meet the density requirements for their grid cells, or they form clusters below the minimum building count. These areas are excluded from the `HashSet`, causing `is_urban()` to return false and ensuring grass ground generation.

### What is the memory advantage of using cell-based coordinates instead of block-level storage?

Storing cell coordinates in a `HashSet<(cx, cz)>` reduces memory usage by approximately **4000×** compared to a per-block boolean array. With a default **cell_size** of 64 blocks, each cell represents a 4096 m² area (64×64). The algorithm only stores coordinates for urban cells, making it feasible to process city-scale maps (10 km² or larger) without exhausting RAM during Minecraft world generation.

### Can the detection sensitivity be adjusted for different types of urban development?

Yes, the `UrbanGroundConfig` struct exposes multiple tuning parameters. Increasing `cell_expansion` and reducing `min_buildings_per_cell` captures sprawling suburban development, while decreasing `cell_size` and increasing `min_buildings_for_cluster` targets dense metropolitan cores. The `concavity` parameter further controls the geometric complexity of cluster boundaries, allowing customization for medieval town layouts versus modern grid cities.

### How does the adaptive expansion logic prevent over-segmentation of towns?

The `calculate_adaptive_expansion()` function (lines 401–466) computes a dynamic radius that **inversely scales with building density**. When the algorithm detects low average buildings per cell or low occupancy rates—indicating a spread-out town—it automatically increases the expansion radius. This bridges gaps between distant buildings during the `expand_cells_adaptive()` stage, ensuring the subsequent BFS groups them into a single connected cluster rather than fragmenting the town into multiple tiny urban zones.