Drawing (filtering) 100k+ points to MapView in Android

Question

I am trying to solve a problem with drawing a path from huge (100k+) set of GeoPoints to a MapView on Android. Firstly I would like to say, I searched through StackOverflow a lot and haven't found an answer.The bottleneck of my code is not actually drawing into canvas, but Projection.toPixels(GeoPoint, Point) or Rect.contains(point.x, point.y) method..I am skipping points not visible on screen and also displaying only every nth point according to current zoom-level. When the map is zoomed-in I want to display as accurate path as possible so I skipping zero (or nearly to zero) points, so that when finding visible points I need to call the projection method for every single point in the collection. And that is what really takes a lot of time (not seconds, but map panning is not fluid and I am not testing it on HTC Wildfire:)). I tried caching calculated points, but since points be recalculated after every map pan/zoom it haven't helped at all.

I thought about usage of some kind of prune and search algorithm instead of iterate the array, but I figured out the input data is not sorted (I can't throw away any branch stacked between two invisible points). That could I possible solve with simple sort at the beginning, but I am still not sure even the logarithmic count of getProjection() and Rect.contains(point.x, point.y) calls instead of linear would solve the performance problem.

Bellow is my current code. Please help me if you know how to make this better. Thanks a lot!

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);

}

Answer 1

So I figured out how to make it all much faster! I will post it here, somebody could possibly found it useful in the future. It has emerged that usage of projection.toPixels() can really harm application performance. So I figured out that way better than take every single GeoPoint, convert it to Point and then check if it is contained in map viewport is, when I count actuall viewport radius of the map as following:

    mapView.getGlobalVisibleRect(currentMapBoundsRect);
    GeoPoint point1 = projection.fromPixels(currentMapBoundsRect.centerX(), currentMapBoundsRect.centerY());
    GeoPoint point2 = projection.fromPixels(currentMapBoundsRect.left, currentMapBoundsRect.top);
    float[] results2 = new float[3];
    Location.distanceBetween(point1.getLatitudeE6()/1E6, point1.getLongitudeE6()/1E6, point2.getLatitudeE6()/1E6, point2.getLongitudeE6()/1E6, results2);

The radius is in results2[0]..

Then I can take every single GeoPoint and count the distance between it and the center of the map mapView.getMapCenter(). Then I can compare the radius with computed distance and decide whether ot not diplay the point.

So that's it, hope It will be helpful.