<commit_before>module OpenSolid.Geometry.Approximate exposing (..)

import OpenSolid.Geometry.SegmentTree2d as SegmentTree2d exposing (..)
import OpenSolid.Point2d as Point2d exposing (Point2d)
import OpenSolid.Polyline2d as Polyline2d exposing (Polyline2d)


type alias LengthConfig a =
    { split : Float -> a -> ( a, a )
    , percentageError : Float
    , startAndEndpoint : a -> ( Point2d, Point2d )
    }


{-| Approximate the length of some curve
-}
length : LengthConfig a -> a -> Float
length config object =
    {-
       asPolyline config object
           |> Polyline2d.length
    -}
    asPolyline config object
        |> Polyline2d.segments
        |> SegmentTree2d.fromList
        |> Maybe.map SegmentTree2d.recalculateLengths
        |> Maybe.map SegmentTree2d.length
        |> Maybe.withDefault 0


{-| The approximation of some curve as a polyline
-}
asPolyline : LengthConfig a -> a -> Polyline2d
asPolyline config curve =
    helper config [ curve ] []
        |> segments config
        |> Polyline2d.withVertices


{-| Recursively approximate a curve, gives points that can be assembled into a polyline
-}
segments : LengthConfig a -> List a -> List Point2d
segments config elements =
    case elements of
        [] ->
            []

        [ x ] ->
            []

        [ x, y ] ->
            let
                ( start, _ ) =
                    config.startAndEndpoint x

                ( _, end ) =
                    config.startAndEndpoint y
            in
            [ start, end ]

        x :: rest ->
            let
                ( start, _ ) =
                    config.startAndEndpoint x
            in
            start :: segments config rest


{-| make the split function tail-recursive
-}
helper : LengthConfig a -> List a -> List a -> List a
helper config remaining accum =
    case remaining of
        [] ->
            accum

        curve :: rest ->
            let
                length item =
                    let
                        ( start, end ) =
                            config.startAndEndpoint item
                    in
                    Point2d.distanceFrom start end

                ( left, right ) =
                    config.split 0.5 curve

                lessAccurate =
                    length curve

                moreAccurate =
                    length left + length right

                average =
                    (lessAccurate + moreAccurate) / 2
            in
            if (average - lessAccurate) / average > config.percentageError then
                helper config (right :: left :: rest) accum
            else
                helper config rest (left :: right :: accum)


{-| Given a length along the curve, give back the 2D location at that point
-}
arcLengthParameterization : LengthConfig a -> a -> (Float -> Maybe Point2d)
arcLengthParameterization config data =
    let
        tree =
            asPolyline config data |> Polyline2d.segments |> SegmentTree2d.fromList |> Maybe.map SegmentTree2d.recalculateLengths
    in
    case tree of
        Nothing ->
            \_ -> Nothing<commit_msg>remove extra recalculation of lengths<commit_after>module OpenSolid.Geometry.Approximate exposing (..)

import OpenSolid.Geometry.SegmentTree2d as SegmentTree2d exposing (..)
import OpenSolid.Point2d as Point2d exposing (Point2d)
import OpenSolid.Polyline2d as Polyline2d exposing (Polyline2d)


type alias LengthConfig a =
    { split : Float -> a -> ( a, a )
    , percentageError : Float
    , startAndEndpoint : a -> ( Point2d, Point2d )
    }


{-| Approximate the length of some curve
-}
length : LengthConfig a -> a -> Float
length config object =
    {-
       asPolyline config object
           |> Polyline2d.length
    -}
    asPolyline config object
        |> Polyline2d.segments
        |> SegmentTree2d.fromList
        |> Maybe.map SegmentTree2d.length
        |> Maybe.withDefault 0


{-| The approximation of some curve as a polyline
-}
asPolyline : LengthConfig a -> a -> Polyline2d
asPolyline config curve =
    helper config [ curve ] []
        |> segments config
        |> Polyline2d.withVertices


{-| Recursively approximate a curve, gives points that can be assembled into a polyline
-}
segments : LengthConfig a -> List a -> List Point2d
segments config elements =
    case elements of
        [] ->
            []

        [ x ] ->
            []

        [ x, y ] ->
            let
                ( start, _ ) =
                    config.startAndEndpoint x

                ( _, end ) =
                    config.startAndEndpoint y
            in
            [ start, end ]

        x :: rest ->
            let
                ( start, _ ) =
                    config.startAndEndpoint x
            in
            start :: segments config rest


{-| make the split function tail-recursive
-}
helper : LengthConfig a -> List a -> List a -> List a
helper config remaining accum =
    case remaining of
        [] ->
            accum

        curve :: rest ->
            let
                length item =
                    let
                        ( start, end ) =
                            config.startAndEndpoint item
                    in
                    Point2d.distanceFrom start end

                ( left, right ) =
                    config.split 0.5 curve

                lessAccurate =
                    length curve

                moreAccurate =
                    length left + length right

                average =
                    (lessAccurate + moreAccurate) / 2
            in
            if (average - lessAccurate) / average > config.percentageError then
                helper config (right :: left :: rest) accum
            else
                helper config rest (left :: right :: accum)


{-| Given a length along the curve, give back the 2D location at that point
-}
arcLengthParameterization : LengthConfig a -> a -> (Float -> Maybe Point2d)
arcLengthParameterization config data =
    let
        tree =
            asPolyline config data |> Polyline2d.segments |> SegmentTree2d.fromList
    in
    case tree of
        Nothing ->
            \_ -> Nothing
{'fraction_non_alphanumeric': 0.07724764686790003, 'fraction_numerical': 0.008763388510223954, 'mean_word_length': 1.4941319303925535, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 71, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7234388', 'n_tokens_mistral': 1672, 'n_tokens_neox': 1536, 'n_words': 495}