Fast label points, and an outer run of the clip prefilter as its net path along the border
A map server labels hundreds of maps per second, and for a label a cheap point inside the polygon matters more than the best one. Polylabel (ADR 0026) is the nicest point but costs about 130 ms for a polygon of 100,000 vertices, and the centroid with Locate allocates megabytes. Two new methods give one interior point in two passes over the vertices without allocation and further points lazily, for when the first one collides with another label. In the same step, Clip of a large, noisy polygon lost its nearly quadratic cost (2.1 s and 930 MB for 100,000 vertices, up to an OutOfMemoryException).
German version: 0053-schnelle-beschriftungspunkte-und-clip-vorfilter.de.md
Consequences
Shapes.FastPolygonLabel(polygon)returnsCoordinate?,nullfor an empty polygon or one without area. Pass one: the area centroid; rings oriented like the largest ring add and the others subtract, so rings need not be typed as shell or hole. Pass two: the crossings of the horizontal line through the centroid with all rings. If the centroid lies between crossing 2k and 2k+1 (even-odd), it is the point; otherwise the middle of the widest stretch of that line. If the line meets nothing, the line through the middle of the envelope, thenPointOnSurface, thenPolylabel. Pooled buffers only; without Z and M.Shapes.FastAlternativePolygonLabelsLazy(polygon, seed, options)yields interior points lazily: nothing is computed before the first one is asked for. The points lie on horizontal scanlines, first the line through the seed, then lines that halve the envelope again and again (½, ¼, ¾, ⅛, …, van der Corput); on each line the points nearest to the seed come first, ties by x. Each scanline is one pass over the vertices; there is no index.AlternativeLabelOptions(a sealed record with init properties, to be kept and reused):Separation(to the seed and to every point before),MinClearance(to the boundary, holes included, an exact distance for each candidate),MaxCount(default 16),MaxScanlines(the work budget, default 32),CancellationToken(ends the sequence without an exception). Invalid options throwArgumentOutOfRangeExceptionat the call, not during the enumeration.- Guarantees: every point lies strictly inside by even-odd over all rings, with the same crossing formula for the scanlines and the inside test; the order is deterministic; an empty or degenerate polygon gives an empty sequence.
- Clip prefilter: the envelope prefilter of
Clip,IntersectionandDifference(RingClipper) replaced every vertex of a ring part outside the rectangle by its projection onto the border. A noisy outer run then became tens of thousands of overlapping segments on one border line, and the snap-rounding noder routed each through every hot pixel on it. An outer run is now replaced by its net path along the border: its start, the corners it passes in its unwrapped perimeter position, its end. Both paths are homotopic on the border, so the winding number of every interior point is unchanged and so are the results. The noder also looks up the hot pixels of a segment in an x or a y order, whichever range is shorter. - Measured (BenchmarkDotNet, smooth concave polygon of 5 km radius with fine noise):
Clipof 100,000 vertices 2,160 ms / 930 MB → 107 ms / 66 MB;FastPolygonLabel3.5 / 44 / 405 µs for 1,000 / 12,000 / 100,000 vertices without allocation; the first alternative 1.4 / 15 / 128 µs with about 300 bytes.
Considered Options
- Best-first search over quadtree cells by distance to the boundary, like
Polylabelbut lazy and with exclusion circles (rejected: every cell needs the distance to the boundary, without an index one pass per cell, with an index an allocation of O(n);Polylabelas its proxy is about 300 times slower than a scanline) - A ring of points around the centroid, each tested by Jordan, as in the classic gView labelling (rejected: one pass per candidate, while a scanline gives many candidates per pass)
- A dedicated rectangle clip (Sutherland–Hodgman or Weiler–Atherton) instead of the overlay (rejected for now: ADR 0022 rejected bridges along the border, results where the border cuts lie on the grid, and it would need a fallback for vertices on the border; it remains possible for the remaining allocation)
- Fixing only the noder (rejected: it halves the time, but the overlapping segments stay and so does the memory)