Рисование (фильтрация )100 000+ точек для MapView в Android

Я пытаюсь решить проблему с рисованием пути от огромного (100k+ )набора GeoPoints к MapView на Android. Во-первых, я хотел бы сказать, что я много искал в StackOverflow и не нашел ответа. Узким местом моего кода на самом деле является не рисование на холсте, а метод Projection.toPixels(GeoPoint, Point)или Rect.contains(point.x, point.y).. Я пропускаю невидимые точки на экране, а также отображать только каждую n-ю точку в соответствии с текущим уровнем масштабирования -. Когда карта увеличена -, я хочу отобразить как можно более точный путь, поэтому я пропускаю ноль (или почти ноль )точек, так что при поиске видимых точек мне нужно вызывать метод проекции для каждого отдельного точка в коллекции. И это то, что действительно занимает много времени (, а не секунд, но панорамирование карты не является плавным, и я не тестирую его на HTC Wildfire :)). Я пытался кэшировать рассчитанные точки, но поскольку точки пересчитываются после каждого панорамирования/масштабирования карты, это не помогло. вообще.

Я думал об использовании какого-то алгоритма обрезки и поиска вместо перебора массива, но понял, что входные данные не отсортированы (Я не могу отбросить ни одну ветку, расположенную между двумя невидимыми точками ). Это я мог бы решить с помощью простой сортировки в начале,но я все еще не уверен, что даже логарифмический подсчет вызовов getProjection()и Rect.contains(point.x, point.y)вместо линейного решит проблему производительности.

Ниже мой текущий код. Пожалуйста, помогите мне, если вы знаете, как сделать это лучше. Большое спасибо!

public void drawPath(MapView mv, Canvas canvas) {
    displayed = false;

    tmpPath.reset();

    int zoomLevel = mapView.getZoomLevel();
    int skippedPoints = (int) Math.pow(2, (Math.max((19 - zoomLevel), 0)));
    int mPointsSize = mPoints.size();
    int mPointsLastIndex = mPointsSize - 1;
    int stop = mPointsLastIndex - skippedPoints;

    mapView.getDrawingRect(currentMapBoundsRect);
    Projection projection = mv.getProjection();

    for (int i = 0; i < mPointsSize; i += skippedPoints) {

        if (i > stop) {
            break;
        }
//HERE IS THE PROBLEM I THINK - THIS METHOD AND THE IF CONDITION BELOW
        projection.toPixels(mPoints.get(i), point);

        if (currentMapBoundsRect.contains(point.x, point.y)) {
            if (!displayed) {
                Point tmpPoint = new Point();
                projection.toPixels(mPoints.get(Math.max(i - 1, 0)),
                        tmpPoint);
                tmpPath.moveTo(tmpPoint.x, tmpPoint.y);
                tmpPath.lineTo(point.x, point.y);
                displayed = true;
            } else {

                tmpPath.lineTo(point.x, point.y);

            }

        } else if (displayed) {
            tmpPath.lineTo(point.x, point.y);
            displayed = false;

        }

    }

    canvas.drawPath(tmpPath, this.pathPaint);

}