Android Loading markers dynamically best strategy

Question

I have an android map with google maps that dynamically loads markers from the server based on user screen position. So for example if user moves the map I simply made request to the server and I'm sending screen bounds and based on that I get markers data (id and corrdinates) which is later parsed and created to actual pointers. Problem is that when user goes back to the same area (which markers was previously created) I still making same request and get same data (but obviously I won't let to recreate that marker so I just run for loop throught all markers that there are on map and check if map marker id is equal server send data marker id and if it is equal I simply break the loop)

try {
                Collection<MarkerItemData> mapMarkers = algorithm.getItems();
                JSONObject jsonObject = new JSONObject(strings[0]);
                JSONArray respondArray = jsonObject.getJSONArray("respond");
                list = new ArrayList();
                for (int i = 0; i < respondArray.length(); i++) {
                    JSONObject station = respondArray.getJSONObject(i);
                    int id = station.getInt("_id");
                    boolean skip = false;
                    for (final MarkerItemData m : mapMarkers) {
                        if (m.getId() == id) {
                            skip = true;
                            break;
                        }
                    }
                }
            }

However I don't think that this approach is the best. I also have other ideas that should work (at least I think)

• send to server screen bounds and also all marker id's that are visible on the screen (I could select all markers that is in screen range and which ids are not in screen bounds)
• each time delete markers from android app and basically recreate all the markers from server each time (Personally I think this is a bad solution)

So which of those ideas are the best? Any other ideas? (Sorry for my english)

Answer 1

Sending screen bounds to the server and id-s of currently visible markers on screen is your best bet. But still there are a couple of troublesome issues. How will you find all markers contained within the range you specified with screen bounds? What if new markers come to your server or some markers are deleted? Can you come with a maintainable structure in such a situation or will you test each point that corresponds a marker in the database one by one to see whether it locates in the range or not? Considering all these, you need to find a way to optimize storing and querying points, in other words latitude and longitude pairs that point markers. You should perform spatial indexing by using one of the common spatial index methods.

There are lots of methods for spatial indexing and one might be slightly better than the other one depending on use case. To make long story short, since you need to query range in this scenario, you should implement a quadtree. The quadtree is called as a tree data structure in which each internal node has exactly four children (northwest, northeast, southwest, southeast). If you have no knowledge about this structure, I believe you can understand its basics in an hour but explaining it in detail from scratch will cause loss of too much time for me. Therefore, I am skipping implementation details about quadtrees. There are several sources which already explained this structure much better than I could, and you can easily find an open source library.

I will only give pseudo-ish Java method for your quadtree to find all points that appear within the range of screen bounds excluding the ones that are already in the previous screen:

ArrayList<LatLng> queryRange(QuadLevel level, float[] screenBounds, ArrayList<LatLng> prevPoints) { 

    // Initialize a list to hold the found points
    ArrayList<LatLng> pointsInRange = new ArrayList<>();

    if (!quadtreeBounds.intersects(screenBounds))
        return pointsInRange;

    // Find the points that are in the current quad level
    for (LatLng point : level.getPoints()) {
        // If the current point is in screen bounds and it is not contained by prevPoints
        if (point.isInRange(screenBounds) 
            && !prevPoints.contains(point))
            pointsInRange.add(point);
    }

    // If there are no children, return
    if (level.hasNoChildren())
        return pointsInRange;

    // Else, continue to look up children
    pointsInRange.addAll(queryRange(level.northwest, screenBounds, prevPoints));
    pointsInRange.addAll(queryRange(level.northeast, screenBounds, prevPoints));
    pointsInRange.addAll(queryRange(level.southwest, screenBounds, prevPoints));
    pointsInRange.addAll(queryRange(level.southeast, screenBounds, prevPoints));

    return pointsInRange;
}