Оптимизация в GPXmagic

«Естественная» структура данных для GPXmagic — это список точек отслеживания. Ведь это и есть дорога. В большинстве случаев это совершенно нормально, но это очень дорого для случайного доступа к одной точке трека.

В частности, мне нужно найти точку отслеживания, ближайшую к тому месту, где пользователь нажимает на трехмерное изображение. Поскольку я оставляю вращение и масштабирование компоненту WebGL, у меня нет прямого способа интерпретировать местоположение клика. Лучшее, что я могу сделать, это создать «луч», по которому я могу измерить расстояние до любой точки. Учитывая луч и список точек, моим первым решением было просто найти точку с наименьшим расстоянием, что легко написать:

trackPointNearestRay : List TrackPoint -> Axis3d Meters LocalCoords -> Maybe TrackPoint
trackPointNearestRay track ray =
    track
        |> List.Extra.minimumBy
            (Length.inMeters << distanceFromAxis ray << .xyz)

Он обязательно сканирует весь список. Это приемлемо для сотен или даже нескольких тысяч точек, но явно не элегантно и неэффективно по мере роста списков. Тем не менее, для большинства треков он был достаточно быстрым, чтобы реагировать на ввод пользователя, поэтому не было срочной необходимости его менять. (Первоначальное утверждение Хора было: «Мы должны забыть о малой эффективности, скажем, в 97% случаев: преждевременная оптимизация — корень всех зол».)

Прошло время, и я придумал изящный способ обнаружения пересекающихся сегментов треков. Простой подход на основе списка требует времени, пропорционального квадрату количества точек. То, что может работать на сто очков, будет работать в миллион раз дольше на сто тысяч. Время исследовать структуры данных.

Короче говоря, есть несколько вариантов дерева квадрантов, которые могли бы работать, но все они казались странно сложными в реализации. Я решил попробовать очень, очень простой подход. Представьте, что вы отвечаете за прямоугольный регион и должны отслеживать все сегменты дорог в вашем регионе. Далее предположим, что вы делите свой регион на четыре квадранта (скажем: СЗ, СВ, ЮВ, ЮЗ). Вы реализуете следующее правило:

Если ограничивающая рамка сегмента дороги полностью помещается в квадрант, делегируйте ответственность этому квадранту. Если он охватывает два или более, добавьте его в список на моем уровне.

С добавлением правила, которое налагает ограничение на подразделение таким образом, что области меньше, чем (скажем) 10 метров, не подразделяются, это четко определенная и легко реализуемая древовидная структура. Конечно, для некоторых маршрутов он может быть сильно разбалансирован, но для большинства реальных маршрутов он ведет себя довольно хорошо.

Поиск прост: по ограничивающей рамке я ищу совпадения с записями на моем уровне и прошу своих делегатов сделать то же самое.

Намного проще, чем все эти хитроумные конструкции; значительно лучше, чем полный поиск, но достаточно легко объяснить на обратной стороне конверта.

Затем я подумал, что могу использовать это, чтобы помочь найти ближайший к лучу. Оказывается, это довольно просто. Если я проецирую луч на плоскость XY, я могу запросить структуру данных, спросив: «Какие из ваших ограничивающих прямоугольников пересекаются с этой линией?»

Но мы можем лучше. Вместо того, чтобы извлекать все пересекающиеся прямоугольники и находить ближайший, почему бы не «опустить» запрос, чтобы рекурсивный обход отслеживал все, что является «ближайшим», и просто возвращал единственный результат?

Вот «обход структуры данных», в котором используется функция valuation, которую мы стремимся минимизировать:

queryNearestToAxisUsing :
    SpatialNode contentType units coords
    -> Axis2d.Axis2d units coords
    -> (contentType -> Float)
    -> Maybe (SpatialContent contentType units coords)
queryNearestToAxisUsing current axis valuation =
    case current of
        Blank ->
            Nothing
        SpatialNode node ->
            let
                boxSides =
                    node.box
                        |> Rectangle2d.fromBoundingBox
                        |> Rectangle2d.toPolygon
                        |> Polygon2d.edges
                intersected =
                    List.any
                        (\edge -> LineSegment2d.intersectionWithAxis axis edge /= Nothing)
                        boxSides
            in
            if intersected then
                [ List.Extra.minimumBy (.content >> valuation) node.contents ]
                    ++ [ queryNearestToAxisUsing node.nw axis valuation
                       , queryNearestToAxisUsing node.ne axis valuation
                       , queryNearestToAxisUsing node.se axis valuation
                       , queryNearestToAxisUsing node.sw axis valuation
                       ]
                    |> List.filterMap identity
                    |> List.Extra.minimumBy (.content >> valuation)
            else
                Nothing

Вызов «на стороне приложения» довольно аккуратный:

trackPointNearestFromIndexFor3d :
    SpatialIndex.SpatialNode TrackPoint Length.Meters LocalCoords
    -> Axis3d Meters LocalCoords
    -> Maybe TrackPoint
trackPointNearestFromIndexFor3d index ray =
    let
        rayShadow =
            ray
                |> Axis3d.projectInto SketchPlane3d.xy
                |> Maybe.withDefault Axis2d.x
        distanceFunction =
            .xyz
                >> Point3d.distanceFromAxis ray
                >> Length.inMeters
    in
    SpatialIndex.queryNearestToAxisUsing index rayShadow distanceFunction
        |> Maybe.map .content

Что действительно интересно, так это то, что наличие этой структуры под рукой открыло множество возможностей применения, которые были бы невозможны без эффективного индекса. Но, я рад, что дождался, пока появится четко очерченная необходимость, и это не было из разряда «преждевременной оптимизации».