DOCSEARCHbyAlgolia
Submit Docs

polylabel

repository·master·Indexed 23 days ago

https://github.com/mapbox/polylabel

A fast JavaScript library for finding the 'pole of inaccessibility' of a polygon—the point within the polygon furthest from its edges. Primarily used for optimal label placement in maps, it uses an iterative grid-based algorithm to find the global optimum based on a specified precision.

Tokens
537
Snippets
2
Records
3
Agent score
32%

What's inside polylabel

  1. How the polylabel algorithm works

    master

    Polylabel uses an iterative grid-based algorithm to find the global optimum within a given precision. It works by:

    1. Initial Grid Generation: Covers the polygon with large square cells (size equal to the smaller dimension of the polygon). It calculates the distance from each cell center to the polygon boundary (using negative values for points outside via ray-casting).
    2. Priority Queue: Places cells into a priority queue sorted by their maximum potential distance (center distance + cell radius).
    3. Initial Best: Uses the polygon's centroid as the first "best so far" candidate.
    4. Iterative Refinement: Pulls cells from the queue. If a cell's potential distance is greater than the current best (specifically cell_max - best_dist > precision), the cell is split into 4 children and re-queued. If a cell's distance is better than the current best, it becomes the new "best so far."
    5. Termination: Stops when the queue is exhausted, returning the center of the best cell found.

  2. Use polylabel to find the pole of inaccessibility

    master

    Polylabel finds the 'pole of inaccessibility'—the most distant internal point from a polygon's outline. This is ideal for placing text labels optimally inside a polygon.

    Input requirements:

    • Polygon coordinates: An array of arrays of [x, y] points (GeoJSON-like format).
    • Precision: A numeric value defining the stopping condition. The default is 1.0.

    Important: Choose precision based on your input units. For geographic coordinates (longitude/latitude), use a small value like 0.000001. Using the default 1.0 with geographic coordinates will be too imprecise.

    Output: The function returns an object containing:

    • The pole coordinate in [x, y] format.
    • A distance property representing the distance to the closest polygon point in the input units.
    const p = polylabel([[[0, 0], [1, 0], ...]], 1.0);
const distance = p.distance;