Recycling marker views

[sdargutev]

The TileView crashes when adding a few thousand markers.
Is there anyway to make the marker's views to recycle... Similar to RecyclerView - when a marker is offscreen to reuse it's view for some marker that is onscreen, in order to avoid creating thousands of marker views.

Thank you,
S. Dargutev

[p-lr]

This is an interesting question. But the main difference between the TileView and a RecyclerView is that a RecyclerView has a maximum number of item to display. What would be the expected behavior of the TileView if you zoom out completely? All markers would be eligible to be rendered and that's an OOM again.
I'm not saying this is a bad idea. Having an adapter with onBindViewHolder and onCreateViewHoldercallbacks like in a RecyclerView would be interesting if you have large amount of markers, but some sort of limit has to be set to the number of views to render.

[p-lr]

Coupled with markers grouping like the image below, with the grouping happening if the limit is reached (let's say ~100 markers) would be a way to go.

This represents a lot of work...

[sdargutev]

The idea is to set a high enough min scale limit so that only a subset of the markers is shown at once. This is still a chance to place many markers on a big enough area. The user will have to scroll, but that is fine. Right now i have a very big area with many markers on it. It is so big that it will never be scaled down enough (scale limit 0.1) to have to show all markers on the screen. The problem is that right now the app crashes when i try to inflate so many marker views at once.

[p-lr]

As you may know, the TileView library is about to evolve in a more modular architecture. You should be able to opt-in for makers (and btw there's already a feature request for markers clustering : #324).
In v3 you should be able to use a different plugin to manage markers that recycles and clusters
markers but i'm afraid this feature will come from a contribution. We will have a lot of work just with the v3 and this feature won't be the priority.
But hey, this is GitHub. Who's better motivated than you to implement this feature? In the meantime, i suggest that you do the following :

• Extend TileView and implement your own MarkerRecyclerLayout which recycles markers. Look at the source code : the MarkerLayout is just a ViewGroup
• Add your MarkerRecyclerLayout to your TileViewCustom by overriding the constructor, call super() and add the view. Actually, you may have to replace the existing MarkerLayout by removing it with TileView.removeView() and then add your MarkerRecyclerLayout at the right index. Just remember the CalloutLayout must be the last children.
• Override every methods related to markers like TileView.addMarker()
• Use your TileViewCustom everywhere you previously used the TileView

To sum up, it's possible and it would be very nice if you could do that so it would be later integrated as plugin for the v3.

GL

[moagrius]

i agree with everything Peter said. there are several existing viewport apis already so i'd imagine this wouldn't be too tough to implement.

you could also create a custom ViewGroup that managed the marker, which takes a TileView reference, then add it to the view tree, that way you could continue to get updates to the core lib.

[sdargutev]

ok i will see how it goes...
thank you

[sdargutev]

Actually for such a scenario with many many many markers, it probably makes more sense to use raw drawables as markers than views. I just tried that and it is very smooth that way, without making my device burning hot :) ...
Basically, i added a View very similar to the CompositePathView, with the only difference is that instead of drawing Paths, i draw bitmaps... One has to pass the CoordinateTranslater instance and the current scale value as it changes to this view, so that in the onDraw method we can use them.
e.g.:
canvas.drawCircle(coordinateTranslater.translateAndScaleX(marker.getX(), currentScale), coordinateTranslater.translateAndScaleY(marker.getY(), currentScale), 50 * currentScale, somePaintInstance);

[moagrius]

very cool. if you don't mind posting your code (or the basic idea), other users might be able to use the technique

[p-lr]

I'm not sure what you did wrong before, but anyway this is impressive that a device can handle so many markers :)

@sdargutev As Mike said, it would be have to have a sample of your before/after code. I could then add it to the wiki.

[sdargutev]

Well technically all the markers are contained in one single view. They are just drawables. No need to inflate a view for each marker. The conventional markers layout would still not be able to handle that many marker Views. There are 2 things that would improve performance though:

1. In the MarkerLayout.onLayout(...) would be a good idea to check if the marker is currently visible in the ViewPort, and if not then don't layout it.
2. Implementing recycling markers would still not solve the problem with very many markers when zoomed out, but it would be a great improvement when zoomed in, or when on a very large area. And in general I think it makes sense to make the views recycable, saves RAM and Battery :)

What i did to solve my problem with the thousands of markers is:

// Subclass TileView

public class MyTileView extends TileView {

    private MyMarkersView markersView;

    public MyTileView(Context context) {
        super(context);
        init();
    }

    public MyTileView(Context context, AttributeSet attrs) {
        super(context, attrs);
        init();
    }

    private void init() {
        markersView = new MyMarkersView(getContext(), getCoordinateTranslater());
        addView(markersView, 4); // added before the callout view
        // ..... other code
    }

    public void addMarker(Bitmap bitmap, float x, float y) {
            MyMarker marker = new MyMarker();
            marker.x = x;
            marker.y = y;
            marker.bitmap = bitmap;
            markersView.addMarker(marker);
    }

    // pass the current scale to the markers view
    @Override
    public void onScaleChanged(float scale, float previous) {
        super.onScaleChanged(scale, previous);
        markersView.onScale(scale);
    }
}

// Create my own MarkersView that will draw all the markers. I added it to the TileView (see above)
public class MyMarkersView extends View {
     
    private static final int MARKER_SIZE = 100;
    
    private float scale = 1;
    private CoordinateTranslater translator;
    private Set<MyMarker> markers = new HashSet<>();

    public MyMarkersView(Context context) {
        super(context);
        init();
    }

    public MyMarkersView(Context context, CoordinateTranslater translator) {
        this(context);
        this.translator = translator;
    }

    @Override
    protected void onDraw(Canvas canvas) {
        for (MyMarker marker : markers) {

            // use the translator to translate and scale to the correct position on the TileView's coordinate system
            float adaptedX = translator.translateAndScaleX(marker.x, scale);
            float adaptedY = translator.translateAndScaleY(marker.y, scale);
            float left = adaptedX - MARKER_SIZE * scale;
            float top = adaptedY - MARKER_SIZE * scale;
            float right = adaptedX + MARKER_SIZE * scale;
            float bottom = adaptedY + MARKER_SIZE * scale;
            RectF markerBounds= new RectF(left, top, right, bottom);

            // don't draw if outside the current display viewport
            if (!canvas.quickReject(markerBounds, Canvas.EdgeType.BW)) {
                // draw the marker bitmap
                canvas.drawBitmap(marker.bitmap, null, markerBounds, null);
            }
        }
    }

    public void onScale(float scale) {
        this.scale = scale;
        invalidate();
    }

}

    public void addMarker(MyMarker marker) {
        markers.add(marker);
        invalidate();
    }
//...............................
}

public class MyMarker {
    public float x;
    public float y;
    public Bitmap bitmap;
}

Now even with thousands of markers on the screen it still runs smoothly. Of course, bitmap caching is a must.
This implementation is for markers that get scaled up/down with zooming. That is what i needed.
As for making the markers respond to clicks, i guess setting HotSpots on the same positions as the markers will do just fine.
Drawback is that if you want to draw some complex composite markers, then it will take some more effort and code to style them.

[p-lr]

Nice, thank you very much for your detailed answer. We definitely have some improvement to do on the MarkerLayout.
And on the other hand, your custom MarkerLayout is very well suited for Bitmaps.

@moagrius in v3 we could indeed invalidate only the current viewport on the MarkerLayout, that would at least improve performance when zoomed in. I know you tried to use the invalidate(Rect), but I don't know how it turned out.
His implementation could be an alternate plugin for markers when they are just Bitmap or when the developper wants to draw them directly in the onDraw method.

[moagrius]

In the MarkerLayout.onLayout(...) would be a good idea to check if the marker is currently visible in the ViewPort, and if not then don't layout it.

@sdargutev You'd need to check during each scroll change - running layout passes that often is not feasible. thanks for sharing your code though!

@peterLaurence it wouldn't work with Views, invalidating only tell the canvas what area to redraw - if it's not laid out, it's not drawn. the only thing i can think is to draw bitmaps and maintain hit areas with something like a hot spot, but then you lose things like nested views with their own hit areas, etc. maybe we can figure something out as things develop organically

[sdargutev]

Would something like this not be possible?

public View addMarker(View view, LayoutParams params) {
        addView(view, params);
        markersList.add(view);
        return view;
    }

public void removeMarker(View view) {
        removeView(view);
        markersList.remove(view);
    }

...................

 @Override
    protected void onMeasure(int widthMeasureSpec, int heightMeasureSpec) {

        for (View child:markersList) {
           
            measureChild(child, widthMeasureSpec, heightMeasureSpec);

            if (child.getVisibility() != GONE) {
                MarkerLayout.LayoutParams layoutParams = (MarkerLayout.LayoutParams) child.getLayoutParams();
                // get anchor offsets
                float widthMultiplier = (layoutParams.anchorX == null) ? mAnchorX : layoutParams.anchorX;
                float heightMultiplier = (layoutParams.anchorY == null) ? mAnchorY : layoutParams.anchorY;
                // actual sizes of children
                int actualWidth = child.getMeasuredWidth();
                int actualHeight = child.getMeasuredHeight();
                // offset dimensions by anchor values
                float widthOffset = actualWidth * widthMultiplier;
                float heightOffset = actualHeight * heightMultiplier;
                // get offset position
                int scaledX = FloatMathHelper.scale(layoutParams.x, mScale);
                int scaledY = FloatMathHelper.scale(layoutParams.y, mScale);
                // save computed values
                layoutParams.mLeft = (int) (scaledX + widthOffset);
                layoutParams.mTop = (int) (scaledY + heightOffset);
                layoutParams.mRight = layoutParams.mLeft + actualWidth;
                layoutParams.mBottom = layoutParams.mTop + actualHeight;
                
                removeView(child);
                if(insideViewPort(child) )
                    addView(child);

            }
        }
        int availableWidth = MeasureSpec.getSize(widthMeasureSpec);
        int availableHeight = MeasureSpec.getSize(heightMeasureSpec);
        setMeasuredDimension(availableWidth, availableHeight);
    }

You can keep track of all the markers in a List field in MarkerLayout.
Then in onMeasure iterate over this list instead of iterating over getChildren(). You first remove the view from the layout and then check whether the marker is in the ViewPort. If it is, you add the view to the layout again.
That way only views that are inside the viewport will make it to the onLayout method.

[moagrius]

imagine someone flinging. what markers were in the viewport during the last measure pass are certainly not going to be there when the fling ends. the problem is that you have to calculate what's in the viewport at every scroll change, which is a lot, and how we manage what tiles to show. so it is possible (like i said, we do it with tiles), but if you try to do layout/measure stuff that frequently, everything will blow up.

[Alexander--]

the problem is that you have to calculate what's in the viewport at every scroll change

@moagrius Is this really a problem? I have tackled GIS matters a little bit in the past, and AFAIK intersection checks with < 10000000 fixed-size objects are very fast, when using appropriate tree structures for lookup.

Personally I had good experience with STRtree (found in com.vividsolutions.jts). Unlike the quadtree, used in Google's clustering library, STRtree needs to be recreated with each update to map objects, but the memory use is lower and lookup is blinding fast. It also has handy forEach API, so you don't create an iterator objects during rendering passes, — zero GC overhead when you don't perform tree modifications. I have used it to clip viewport with hundeds of polygons and thousands of markers and the performance was good.

[moagrius]

scroll events fire very quickly. yes, it's possible, and no i don't have any concrete metrics on how it'd impact performance.

that said, for v3 we're moving to a plugin architecture, so something like that would be perfect as an opt in plugin.

[Alexander--]

scroll events fire very quickly

@mariotaku Do you mean calls to onDraw? Either way, doing lookups in small, localized memory structures is much faster than actually drawing unnecessary objects to screen, especially if objects themselves are non-trivial to draw. I am currently trying to create a small test app, so I might cook up some kind of showcase for you.

[moagrius]

you pinged mariotaku, not moagrius :) no big deal; mariotaku feel free to ignore

Do you mean calls to onDraw?

No, I mean scroll events. onDraw fires when invalidated and is throttled to roughly once per frame (~16ms). The only thing we're drawing is the tile bitmaps; markers are laid out using the built-in AOSP View infrastructure. I think you may find that a few million hit tests on every scroll change event may add up pretty quickly.

That said, I'm not sure why you're talking about drawing. We're talking about detecting if a marker is in the visible viewport during a scroll or fling event, and if so, laying it out, not drawing it. Markers are much more likely than not to have touch events attached to them; again this means we can't just draw, we have to lay out. Drawing is very different from layout. Drawing is just pixels - layout includes hit areas, elevation, and most importantly: relative positioning and potential reflow, all of which is much more expensive than layout.

As I've said a couple times, it's definitely possible to do this, but it's going to take resources that are probably not appropriate to have for all implementations - this is a good candidate for an opt-in, which will be supported in V3. For now, if someone wants to implement it for V2 as a subclass, they're free to do so, but I'm not going to add it to the core of V2.

Thanks for your input.

[Alexander--]

@moagrius

you pinged mariotaku

Sorry, I have been a have been a bit negligent when writing my response :)

No, I mean scroll events.

I see.

I have been reading the code and profiled things a bit. Apparently, the throttling of onDraw is one of the biggest contributors to the library performance. When I looked at few other mapping libraries (osmdroid, old Mapbox SDK), they created a comparable amount of garbage to yours, but literally chocked on GC each frame. Thanks to the throttling, TileView produces ~2000 new objects per second, which feels almost like nothing. Good job!

Of course, there are no reasons, why this can't be extended to TileView child Views.

That said, I'm not sure why you're talking about drawing. We're talking about detecting if a marker is in the visible viewport during a scroll or fling event, and if so, laying it out, not drawing it. Markers are much more likely than not to have touch events attached to them; again this means we can't just draw, we have to lay out.

Wrong. It seems like you are making a common mistake here. The ViewGroup does not have to lay out the Views after scrolling. No one does that. All Android components: ScrollView, RecyclerView, DrawerLayout and boatload of third-party Android libraries do not lay out children after scroll. They only do that once, initially, and shift them using ViewCompat.offset* calls, then invalidate self. Layout is too expensive to perform during animation. Shifting child Views is cheap in comparison.

This is why ScrollView, DrawerLayout and many other libraries are designed the way they are designed. There is a single parent, that dispatches scrolling events, and single child, that gets shifted in response to those events. In theory, there can be multiple children (and RecyclerView pulls that off), but calling offset* methods on multiple children is less slightly less efficient, and rather verbose, so most end up with single child.

Offset Views still correctly process input etc. and interact with underlying Views, only their layout position is not affected. When the layout pass finally happens, onLayout positions Views with consideration for their current offsets and offsets are reset.

Using this scheme, RecyclerView offsets and moves children around itself without actually laying them out most of time. It only performs the layout pass on them, if something actively causes it (such as changes to contents of it's children). This has been proven to be efficient in practice.

As I've said a couple times, it's definitely possible to do this, but it's going to take resources

It would much more efficient. You probably don't want to implement full functionality of RecyclerView. But some optimizations are considerably easy to take advantage of. When you feel, that a View can be reused, just move it inside the parent. When it can not be reused, detach and either modify, reuse and reattach or move to scrap.

Of course, that optimization could be even more appropriate for the older generation of the library (when tiles also were Views), effectively avoiding creation of throwaway Tile objects. It would also make Bitmap reuse more reliable: right now you have to delay Bitmap recycling to avoid "Bitmap in use errors" when HW acceleration is enabled; detached Views can have their Bitmaps recycled immediately, because detaching a View immediately removes it's Bitmaps from display lists.

[Alexander--]

@moagrius I hope, that the wall of text above has addressed the point that you have been making: about recycling the Views.

Now let's reiterate over the argument, that I have been making (and which you haven't actually addressed):

the problem is that you have to calculate what's in the viewport at every scroll change

Calculating, what's in the viewpoint is extremely fast when you use spatial trees to index your objects

This is irrespective of specific problem (layout, drawing etc.) That lookup is a very fast thing to do either way. You only need to store coordinates of centre (and sizes, for non-dot objects), and the tree will let you look up, which of them are in the current viewport. The "viewport" still has to be computed, which is already implemented in your code (when drawing tiles).

[moagrius]

i'm not sure how to state this any more clearly: i am declining to implement the feature in question (in this version). as i've said several times so far, i may implement this in v3.

i'm not sure where the confusion is - i'm aware of how view recycling works - there is neither new nor novel information in either of your posts - i'm telling you that i'm not going to implement that, at least for the current version (v2).

what little time i have for open source work will be directed at v3.

your tone is, at times, inappropriate - please post respectfully, or not at all. i would suggest that you edit your comments to show a more civil tone, but ultimately that's up to you. i have the option to edit, delete, or block, but am really reluctant to do so, and have not had to so far, and hope to never have to.

thanks you.

[Alexander--]

@moagrius

i'm not sure where the confusion is - i'm aware of how view recycling works - there is neither new nor novel information in either of your posts

My apologies, I have been confused by the following statement of yours: "We're talking about detecting if a marker is in the visible viewport during a scroll or fling event, and if so, laying it out, not drawing it". You have mentioned laying out Views, and I responded, that it is usually avoided during View recycling. Or did I misunderstood you?

what little time i have for open source work will be directed at v3

I am not really interested in this specific issue (View recycling) or when the next release is going to be. Your library is nice, and it was very useful to me as is, — thanks a lot for writing it. Because of that, I felt like commenting on this thread and offering you what little advice I could provide. Since there are no chats, mailing lists, forums or other reasonable means of contacting you about TileView, I have left a comment on this issue.

It is very unfortunate, that you have taken offence from tone of my posts. I hope, that this won't negatively affect future of this library.