Tinfour.NET Architecture Overview

November 27, 2025 · View on GitHub

Version: 2.1.9 (Port)
Date: November 26, 2025
Status: Production-Ready Core Implementation

Executive Summary

Tinfour.NET is a faithful C# port of the Tinfour Java library, providing high-performance Constrained Delaunay Triangulation (CDT), Voronoi diagram generation, and advanced terrain analysis capabilities for .NET applications. The library maintains mathematical correctness and algorithmic fidelity to the original while leveraging .NET-specific optimizations and idioms.

Project Origins

This project is a complete port of the Tinfour Java library to .NET, preserving:

Core algorithms and mathematical operations
Data structures and memory management patterns
API surface and usage patterns
Test cases and validation methods

Original Java Repository: https://github.com/gwlucastrig/Tinfour

The port was undertaken to bring Tinfour's proven triangulation and terrain analysis capabilities to the .NET ecosystem, enabling integration with .NET GIS applications, visualization frameworks, and data processing pipelines.

Solution Structure

The Tinfour.NET solution consists of multiple projects organized by functionality:

Core Libraries

Tinfour.Core - Core triangulation, interpolation, and data structures
Tinfour.GIS - GIS-specific utilities and file format support (stub)
Tinfour.SVM - Semi-Virtual Memory for large dataset handling (stub)
Tinfour.Analysis - Advanced terrain analysis tools (stub)

Application & Testing

Tinfour.Visualiser - Cross-platform visualization application (Uno Platform)
Tinfour.Demo - Console demonstrations and examples
Tinfour.Benchmarks - Performance benchmarking suite (BenchmarkDotNet)
Tinfour.DiagnosticsRunner - Diagnostic and profiling utilities
Tinfour.*.Tests - Comprehensive unit test suites (xUnit)

Core Capabilities

1. Delaunay Triangulation

Details: Core Triangulation

Incremental construction using Bowyer-Watson algorithm
Constrained Delaunay Triangulation (CDT) with linear and polygon constraints
Point location using Stochastic Lawson's Walk
Ghost vertex handling for infinite regions
Supports millions of vertices with efficient memory management

2. Interpolation

Details: Interpolation Methods

Triangular Facet - Fast linear interpolation using barycentric coordinates
Natural Neighbor - High-quality smooth interpolation using Sibson's method
Inverse Distance Weighting - Configurable distance-based interpolation

3. Contour Generation

Details: Contour Generation

Isoline extraction at specified elevation levels
Closed polygon regions with hierarchical nesting
Perimeter boundary integration
Point-in-polygon testing and area calculation

4. Voronoi Diagrams

Details: Voronoi Diagrams

Bounded Voronoi generation from Delaunay triangulation
Thiessen polygons with containment testing
Leverages Delaunay-Voronoi duality for O(n) construction

Architecture Principles

Faithful Porting Strategy

The port prioritizes mathematical correctness and algorithmic fidelity:

Same algorithms - Bowyer-Watson, Lawson's Walk, Sibson interpolation
Identical predicates - Orientation tests, in-circle tests, circumcircle calculations
Compatible data structures - Quad-edge, edge pools, vertex representations
API parity - Interface hierarchies and method signatures match Java where possible

.NET Optimizations

While maintaining algorithmic integrity, the port leverages .NET capabilities:

Value types (structs) - Vertex as readonly struct for cache efficiency
Span and Memory - Zero-allocation array operations where applicable
Aggressive inlining - Critical path methods marked for inlining
Object pooling - EdgePool for memory reuse and reduced GC pressure
Modern C# features - Nullable reference types, pattern matching, tuples

Memory Efficiency

Details: Memory Management

NullVertex pattern - Efficient null semantics without boxing
Paged edge allocation - EdgePool/EdgePage for controlled allocation
Hilbert pre-ordering - Improved spatial locality for insertions
Preallocation hints - Reduce allocation overhead for known dataset sizes

Key Data Structures

Details: Data Structures Overview

Vertex

Details: Vertex Structure

Immutable readonly struct with double (x, y) and float (z) precision
NullVertex pattern for ghost vertices
Index and bit flags for metadata

QuadEdge

Details: Edge Representation

Dual-edge structure (QuadEdge / QuadEdgePartner)
Forward/reverse navigation links
Constraint metadata and region marking
Memory-managed via EdgePool

IncrementalTin

Details: TIN Implementation

Main triangulation engine
Incremental vertex insertion
Bootstrap utility for initial triangle
Integration point for constraints and queries

Development Workflow

Building and Testing

The solution targets .NET 8.0 and uses standard tooling:

# Build solution
dotnet build Tinfour.Net.sln

# Run tests
dotnet test

# Run benchmarks
cd Tinfour.Benchmarks
dotnet run -c Release

Performance Characteristics

Current performance (November 2025):

Vertex Count	Build Time	Memory Usage	Notes
1,000	~1 ms	~1.15 MB	Hilbert sorted + prealloc
10,000	~15.5 ms	~11.7 MB	Typical GIS feature
100,000	~196 ms	~112.6 MB	Large terrain model
1,000,000	~1.4 s	~750 MB	Very large dataset

Performance is approximately 2.5× slower than Java for large datasets, with ongoing optimization work targeting parity.

Component	Status	Completion
Core Triangulation	✅ Complete	100%
Constraint Processing (CDT)	✅ Complete	100%
Triangular Facet Interpolation	✅ Complete	100%
Natural Neighbor Interpolation	✅ Complete	100%
Inverse Distance Weighting	✅ Complete	100%
Contour Generation	✅ Complete	100%
Voronoi Diagrams	✅ Complete	100%
GIS Integration	🔄 Stub	10%
SVM (Semi-Virtual Memory)	🔄 Stub	10%
Advanced Terrain Analysis	🔄 Stub	10%
Performance Optimization	🔄 Ongoing	70%
Documentation	🔄 Ongoing	80%

Usage Example

using Tinfour.Core.Common;
using Tinfour.Core.Standard;
using Tinfour.Core.Interpolation;

// Create vertices
var vertices = new List<IVertex>();
for (int i = 0; i < 1000; i++)
{
    vertices.Add(new Vertex(x, y, z, i));
}

// Build TIN with optimizations
using var tin = new IncrementalTin(1.0);
tin.PreAllocateForVertices(vertices.Count);
tin.AddSorted(vertices); // Hilbert sorted

// Interpolate at a point
var interpolator = new NaturalNeighborInterpolator(tin);
double interpolatedZ = interpolator.Interpolate(queryX, queryY, null);

// Generate contours
var contourBuilder = new ContourBuilderForTin(tin, null, 
    new[] { 100.0, 200.0, 300.0 }, buildRegions: true);
var contours = contourBuilder.GetContours();
var regions = contourBuilder.GetRegions();

// Create Voronoi diagram
var voronoi = new BoundedVoronoiDiagram(tin);
var polygons = voronoi.GetPolygons();

References

Original Java Library

Repository: https://github.com/gwlucastrig/Tinfour
Documentation: http://www.tinfour.org
License: Apache License 2.0

Key Papers and Algorithms

Guibas & Stolfi (1985) - "Primitives for the manipulation of subdivisions and the computation of Voronoi diagrams"
Sloan, S.W. (1993) - "A Fast Algorithm for Generating Constrained Delaunay Triangulations"
Sibson, R. (1981) - "A Brief Description of Natural Neighbour Interpolation"

License

This project maintains the Apache License 2.0 from the original Tinfour library.

Contributing

When contributing to Tinfour.NET:

Maintain algorithmic fidelity to the Java implementation
Follow the coding standards
Include tests with reference validation against Java
Document performance implications of any changes
Update architecture documentation for significant features

Document Version: 1.0
Last Updated: November 26, 2025
Maintained By: Tinfour.NET Development Team