Polylabel C#

A fast, allocation-light C# port of Mapbox Polylabel. It finds the pole of inaccessibility — the point inside a polygon that is furthest from its outline, and therefore the best place to put a label.

• Allocation-light: Nothing is allocated per probe; cells, points and results are all value types. The spatial index rents its buffers from ArrayPool, so a warm application keeps 816 B to 6,264 B per call on the benchmark data below — essentially just the priority queue.
• Fast: A spatial index over the segments keeps the search from touching the whole outline on every probe — 567 µs for a 5,030 vertex GIS polygon, about 21× the throughput of the JavaScript reference on the same data (see Benchmarks).
• Broad Compatibility: Targets .NET 8.0 and .NET 10.0 — works in Rhino 8 and other .NET 8 hosts, while also supporting the latest runtime.
• Flexible Input: Point arrays, GeoJSON-style double[][][] coordinates, or your own geometry type via IPolygon<TPoint>.
• Custom Point Types: Use your own point/vector struct without boxing or virtual dispatch; types you cannot modify (System.Numerics.Vector2, Unity's Vector2) are covered by a small adapter struct.

Install the library directly from NuGet:

dotnet add package Polylabel

Or via the Package Manager Console:

Install-Package Polylabel

Version 2.0 renames the entry point from Polylabel to PoleOfInaccessibility and its method from Run to Find. In 1.x the class name collided with the Polylabel namespace, so Polylabel.Run(...) never compiled in consumer code — everyone had to write Polylabel.Polylabel.Run(...) or use an alias. The new name removes the collision:

// 1.x
var (point, distance) = Polylabel.Polylabel.Run(polygon, precision: 0.01);

// 2.0
using Polylabel;
var (point, distance) = PoleOfInaccessibility.Find(polygon, precision: 0.01);

Nothing else changed: Point, Polygon, Polygon<TPoint>, IPoint, IPolygon<TPoint>, PolylabelResult, the overload set, the parameters and the results are all identical.

A polygon is modeled as a list of closed rings. The first ring defines the outer boundary, while subsequent optional rings define holes.

using Polylabel;

// 1. Define a polygon with an outer ring and two holes (matching the diagram above)
var outerRing = new Point[]
{
    new Point(15, 15),
    new Point(135, 15),
    new Point(135, 135),
    new Point(15, 135),
    new Point(15, 15)
};

var holeA = new Point[]
{
    new Point(85, 35),
    new Point(125, 35),
    new Point(125, 85),
    new Point(85, 35)
};

var holeB = new Point[]
{
    new Point(25, 80),
    new Point(55, 80),
    new Point(55, 125),
    new Point(25, 125),
    new Point(25, 80)
};

var polygon = new Polygon(new Point[][] { outerRing, holeA, holeB });

// 2. Find the pole of inaccessibility
var (point, distance) = PoleOfInaccessibility.Find(polygon, precision: 0.01);

Console.WriteLine($"Optimal label position: X={point.X}, Y={point.Y}"); // Output: X=90.7, Y=99.3
Console.WriteLine($"Distance to closest boundary: {distance}");         // Output: Distance=35.7

The precision is an absolute length in the coordinate units of your polygon, not a relative tolerance. It must be clearly smaller than the shorter side of the polygon's bounding box, otherwise the search has nothing left to refine.

The default of 1.0 fits projected coordinates in metres. For geographic coordinates in degrees it is far too coarse — a polygon spanning half a degree is smaller than the default precision in its entirety:

// WGS84 polygon, roughly 0.7° x 0.56°
PoleOfInaccessibility.Find(polygon);              // precision 1.0: no refinement at all
PoleOfInaccessibility.Find(polygon, 1e-6);        // ~0.1 m at the equator

When the precision is at least as large as the shorter bounding box side, the better of the polygon centroid and the bounding box centre is returned, together with its true distance to the outline. That is still a point inside the polygon — just not a refined one. (The reference implementation returns the bounding box corner with a distance of zero here, which is usually a point outside the polygon; this port deliberately deviates.)

Find takes an optional callback that reports what the search did — useful when tuning the precision. Without it the library stays silent; it never writes to the console on its own.

PoleOfInaccessibility.Find(polygon, 1.0, Console.WriteLine);

// found best 7.0711 after 4 probes
// found best 11.7115 after 96 probes
// num probes: 99
// best distance: 11.711456063402194

If the precision was too coarse to refine anything, the callback says so explicitly:

precision 50 is not finer than the shorter bounding box side 10; returning the best initial guess without refinement
num probes: 2
best distance: 5

The polygon is checked when it is constructed:

Both arguments are checked again before the search starts:

These inputs are rejected rather than tolerated because they have no meaningful answer: a non-positive precision makes the search's termination condition unsatisfiable, and a non-finite coordinate either does the same to the initial grid or silently poisons the distance function. The check costs roughly 0.06 % of a typical search.

Empty is not null. An empty ring, or a polygon without any ring, is a valid degenerate value and yields (0, 0) with distance 0 — only null is treated as an error. A GeoJSON position may carry a third value (elevation); it is ignored.

Raw coordinate arrays from a GeoJSON deserialiser are accepted directly. The constructor copies them into Point arrays:

double[][][] geoJsonCoordinates = ...; // Outer boundary and hole coordinates
var polygon = new Polygon(geoJsonCoordinates);

var (point, distance) = PoleOfInaccessibility.Find(polygon, precision: 0.1);

If your application already has its own point or vector type, you can use it directly. It has to be a struct — the generic constraint is where TPoint : struct, IPoint — which is what lets the JIT specialise the search for your type instead of dispatching through an interface.

Implement IPoint on it and pass it to a generic Polygon<TPoint>:

using Polylabel;

// 1. Implement IPoint on your own struct
public readonly struct CustomVector2 : IPoint
{
    public double X => XCoordinate;
    public double Y => YCoordinate;

    public double XCoordinate { get; }
    public double YCoordinate { get; }

    public CustomVector2(double x, double y)
    {
        XCoordinate = x;
        YCoordinate = y;
    }
}

// 2. Wrap custom coordinates in a generic Polygon
CustomVector2[][] myRings = ...;
var polygon = new Polygon<CustomVector2>(myRings);

// 3. Find the pole; the JIT compiles a specialised version for CustomVector2
var (point, distance) = PoleOfInaccessibility.Find(polygon, precision: 1.0);

If the point type comes from an external package (like System.Numerics.Vector2 or Unity's Vector2) and cannot implement IPoint itself, wrap it in an adapter struct. The adapter costs nothing at run time — no boxing, no virtual dispatch, and the property accesses are inlined:

// 1. External type from another package (cannot implement IPoint directly)
using System.Numerics; // e.g., Vector2

// 2. Define an adapter struct
public readonly struct Vector2Adapter : IPoint
{
    private readonly Vector2 _vector;

    public double X => _vector.X;
    public double Y => _vector.Y;

    public Vector2Adapter(Vector2 vector) => _vector = vector;
}

// 3. Map your rings. Note that this copies the coordinates into new arrays.
Vector2[][] externalRings = ...;
Vector2Adapter[][] wrappedRings = Array.ConvertAll(externalRings,
    ring => Array.ConvertAll(ring, v => new Vector2Adapter(v)));

var polygon = new Polygon<Vector2Adapter>(wrappedRings);
var (point, distance) = PoleOfInaccessibility.Find(polygon);

To avoid that copy, implement IPolygon<TPoint> over the data you already have. The rings are consumed as ReadOnlySpan<TPoint>, so the search reads your existing memory directly:

using Polylabel;

// 1. Define a polygon adapter over your own storage
public readonly struct MyCustomPolygon : IPolygon<Point>
{
    private readonly Point[] _outerRing;

    public int RingCount => 1;

    public ReadOnlySpan<Point> GetRing(int index) => index == 0 ? _outerRing : ReadOnlySpan<Point>.Empty;

    public MyCustomPolygon(Point[] outerRing) => _outerRing = outerRing;
}

// 2. Pass it to Find; the JIT specialises the generic for your type
var polygon = new MyCustomPolygon(outerRingPoints);
var (point, distance) = PoleOfInaccessibility.Find<MyCustomPolygon, Point>(polygon);

Reproduce with dotnet run --project Polylabel.Benchmarks -c Release.

BenchmarkDotNet v0.15.8, macOS Tahoe 26.5 (25F71) [Darwin 25.5.0]
Apple M1 Pro, 1 CPU, 10 logical and 10 physical cores
.NET SDK 10.0.300, .NET 10.0.8, Arm64 RyuJIT armv8.0-a

The allocations are the priority queue and its growth buffer, plus 120 B for the index object; nothing is allocated per probe.

A plain implementation measures the distance to every segment of every ring on every probe — for water1 that is 209 probes over 5,030 segments, more than a million segment visits. Instead the segments are indexed in a uniform grid once per search, which costs about as much as a single probe and cuts the visits to 1–7 %:

The results are unchanged down to the last bit. A minimum does not depend on the order it is taken in, and the index only leaves out segments that provably cannot beat the best distance found so far; the inside/outside test stays exact because each segment is visited once per query. Polygons below 512 segments skip the index entirely — the linear scan is faster there and needs no memory at all.

Same fixtures, same precision, polylabel 2.0.1 on Node v26.1.0, same machine:

Both implementations walk the same probe sequence and produce the same poles; the difference is the spatial index, which is why the factor is far larger than the roughly 1.5× that RyuJIT gains over V8 on the identical linear scan.

The library uses the .NET PriorityQueue. For comparison, the benchmark project also contains a C# port of the JavaScript tinyqueue used by the original:

The two are indistinguishable in speed; earlier runs even had the ranking on water2 flip between repetitions. The .NET queue was kept because it is part of the framework.

Results generated directly from the JSON fixtures. The polygon centroid (blue cross) often falls outside the shape or into a narrow area, while the pole of inaccessibility (red circle, with its maximum inscribed circle) finds the optimal interior point.

This project is licensed under the ISC License – see the LICENSE file for details. Original algorithm copyright (c) 2016 Mapbox.