DOCSEARCHbyAlgolia
Submit Docs

concaveman

repository·master·Indexed 20 days ago

https://github.com/mapbox/concaveman

A high-performance JavaScript library for generating 2D concave hulls (outlines) from a set of points. It implements an algorithm with O(n log n) complexity and allows for customization of the resulting shape via concavity and lengthThreshold parameters.

Tokens
774
Snippets
3
Records
5
Agent score
22%

What's inside concaveman

  2. Understand concaveman parameters: concavity and lengthThreshold

    master

    The shape of the resulting concave hull is controlled by two main parameters:

    1. concavity: This is a relative measure. Increasing this value makes the hull more 'convex' (simpler), while decreasing it allows the hull to follow the points more closely (more complex/concave).
    2. lengthThreshold: This acts as a stopping condition for the refinement process. If an edge in the hull is shorter than this threshold, the algorithm stops trying to find points to 'flex' that edge inward. This helps prevent excessive complexity or tiny, jagged edges in the final polygon.

  3. Use concaveman to generate a 2D concave hull

    master

    The concaveman function generates a general outline (a concave hull) of a set of 2D points. It is a fast implementation with $O(n ext{ log } n)$ complexity.

    Function Signature: concaveman(points[, concavity = 2, lengthThreshold = 0])

    Parameters:

    • points: An array of [x, y] coordinate pairs.
    • concavity (optional): A relative measure of concavity.
      • 1 produces a relatively detailed shape.
      • Infinity results in a standard convex hull.
      • Values lower than 1 are supported but may produce irregular shapes.
    • lengthThreshold (optional): A threshold for segment length. When a segment length is below this value, the algorithm stops further detailing. Higher values result in simpler, less detailed shapes.
    import concaveman from 'concaveman';

const points = [[10, 20], [30, 12.5], ...];
const polygon = concaveman(points);

  5. Use the concaveman function to generate a concave hull

    master

    The concaveman function computes a concave hull from a set of points. It starts with a convex hull and iteratively 'drills down' into the edges to create a more tightly fitting boundary based on the provided concavity and length threshold parameters.

    Parameters:

    • points: An array of points, where each point is represented as an array of two numbers [x, y].
    • concavity (optional): A relative measure of concavity. A higher value results in a simpler, smoother hull. Defaults to 2.
    • lengthThreshold (optional): A threshold for segment length. When a segment's length falls below this value, the algorithm will not attempt to drill it down further. Defaults to 0.

    Returns: An array of points [[x, y], ...] representing the vertices of the concave hull in order.

    import concaveman from 'concaveman';

const points = [[0, 0], [1, 0], [1, 1], [0, 1], [0.5, 0.5]];
const hull = concaveman(points, 2, 0.1);
console.log(hull);