[vc_row][vc_column width=“1/6″][/vc_column][vc_column width=“2/3″][vc_column_text]Kürzlich standen wir vor der Herausforderung, aus einer großen Menge von Objekten mit geographischen Koordinaten und einer Gewichtung eine Auswahl zu treffen, die auf einer Karte gleichmäßig verteilt ist und die höchste Gewichtung hat. Diese Menge an Objekten sollte auf einer Google Map dargestellt werden.

Für die Erstellung der App galt es, verschiedene Herausforderungen zu bewältigen. Einige davon sollen in diesem Artikel kurz skizziert werden:

Verteilung der Objekte auf der Karte

Eine dieser Herausforderungen hierbei war, dass die Verteilung der Objekte nicht gleichmäßig, sondern eher auf speziellen Zentren konzentriert war.

Gelöst wurde dieses Problem, indem die Karte in mehrere Sektionen unterteilt und je Sektion das Objekt mit der größten Gewichtung ausgewählt wurde.

Hier ein Beispielcode:


for (int x = 0; x & amp; lt; xTiles; x++) {
for (int y = 0; y & amp; lt; yTiles; y++) {
LatLngBounds tileBounds = calculateTileBounds(bounds, xTiles, yTiles, x, y);
if (howManyItemsInArea(tileBounds) == 0) {
ObjectOnMap objectOnMap = fetchNewObjectOnMap(tileBounds);
mapOverlay.putObjectOnMap(objectOnMap);
}
}
}

private LatLngBounds calculateTileBounds(LatLngBounds bounds, int xTiles, int yTiles, int x, int y) {
double width = bounds.northeast.longitude – bounds.southwest.longitude;
double height = bounds.northeast.latitude – bounds.southwest.latitude;

LatLngBounds rtnBounds = new LatLngBounds(
new LatLng(bounds.southwest.latitude + height / yTiles * y,
bounds.southwest.longitude + width / xTiles * x),
new LatLng(bounds.southwest.latitude + height / yTiles * (y + 1),
bounds.southwest.longitude + width / xTiles * (x + 1)));
return rtnBounds;
}

public int howManyItemsInArea(LatLngBounds area) {
int itemCount = 0;
for (OverlayItem i: AllOverlayItems) {
if (isInArea(area, i.position)) {
itemCount++;
}
}
return itemCount;
}

private boolean isInArea(LatLngBounds area, LatLng position) {
if (area.southwest.latitude & amp; lt; position.latitude || position.latitude & amp; lt; area.northeast.latitude || area.southwest.longitude & amp; lt; position.longitude || position.longitude & amp; lt; area.northeast.longitude) {
return true;
} else {
return false;
}
}

Gewichtung veranschaulichen

Eine weitere Herausforderung ergab sich dadurch, dass die Gewichtung dieser Objekte in der Karte zu veranschaulichen war. Der Mindestwert für die Gewichtung betrug 0. Das Problem, welches sich stellte, war, dass der höchste Gewichtungswert nicht definiert war. Zudem hatten die meisten Gewichtungen einen sehr kleinen Wert, verglichen mit dem größtmöglichen aller Werte.

Die Gewichtung dieser Objekte wurde durch Variation der Objektgröße auf der Map veranschaulicht. Dabei wurde die Größe der Objekte durch eine Logarithmus-Funktion berechnet. So ist es möglich, Objekte mit ähnlich kleinen Gewichtungen besser zu unterscheiden. Ausserdem verdecken Objekte mit sehr großen Gewichtungen nicht die gesamte Karte.

Beispielcode:


int itemSize = (int) Math.log(item.weight + 1) * 30;
itemSize  = Math.max(20, itemSize);
itemSize  = Math.min(120, itemSize);

Zoom in/aus der Karte

Wenn man nun in die Karte hinein- oder herauszoomt oder sie bewegt, so können Objekte aus dem sichtbaren Bereich der Karte verschwinden, von einer Sektion der Karte in die nächste verschoben werden oder in ihrer Ursprungs-Sektion bleiben. Für das Nachladen oder Löschen bestimmter Objekte von der Karte wurden folgende Regeln definiert:

Falls sich zwei Objekte überlappen, wird eins von beiden Objekten von der Karte gelöscht:


private void removeTooCloseItems() {
int itemCount = size();
for (int i = 0; i & amp; lt; itemCount; i++) {
for (int j = i + 1; j & amp; lt; itemCount; j++) {
if (isOverlaysOverlap(get(i), get(j))) {
remove(i);
i--;
j = itemCount;
itemCount--;
}
}
}
}

private boolean isOverlaysOverlap(OverlayItem item1, OverlayItem item2) {
Rect item1Rect = getMarkerRect(item1.marker, item1.bitmap);
Rect item2Rect = getMarkerRect(item2.marker, item2.bitmap);

if (isRectInsideRect(item1Rect, item2Rect)) {
return true;
}
if (isRectInsideRect(item2Rect, item1Rect)) {
return true;
}
return false;
}

private boolean isRectInsideRect(Rect big, Rect small) {
ArrayList & amp;
lt;
Point & amp;
gt;
points = new ArrayList & amp;
lt;
Point & amp;
gt;
();
points.add(new Point(small.left, small.bottom));
points.add(new Point(small.left, small.top));
points.add(new Point(small.right, small.bottom));
points.add(new Point(small.right, small.top));

for (Point p: points) {
if (isInRect(big, p)) {
return true;
}
}
return false;
}

private boolean isInRect(Rect area, Point position) {
if (area.bottom & amp; lt; = position.y || position.y & amp; lt; area.top || area.left & amp; lt; position.x || position.x & amp; lt; area.right) {
return true;
} else {
return false;
}
}

 

Falls Objekte vom Mittelpunkt des sichtbaren Kartenausschnitts weiter als eine Kartenlänge entfernt sind, so werden sie ebenfalls von der Karte gelöscht:


private void removeTooFarFromVisibleMapsArea() {
LatLngBounds mapBounds = getMapBounds();
double mapWidth = mapBounds.northeast.longitude - mapBounds.southwest.longitude;
double mapHeight = mapBounds.northeast.latitude - mapBounds.southwest.latitude;
LatLngBounds allowedArea = new LatLngBounds(
new LatLng(mapBounds.southwest.latitude - mapHeight / 2, mapBounds.southwest.longitude - mapWidth / 2),
new LatLng(mapBounds.northeast.latitude + mapHeight / 2, mapBounds.northeast.longitude + mapWidth / 2));
for (int i = 0; i & amp; lt; size(); i++) {
if (!isInArea(allowedArea, get(i).position)) {
remove(i);
i--;
}
}
}

private boolean isInArea(LatLngBounds area, LatLng position) {
if (area.southwest.latitude & amp; lt; position.latitude || position.latitude & amp; lt; area.northeast.latitude || area.southwest.longitude & amp; lt; position.longitude || position.longitude & amp; lt; area.northeast.longitude) {
return true;
} else {
return false;
}
}

Nun wird der sichtbare Kartenausschnitt wieder in Sektionen eingeteilt. Befindet sich in einer der Sektionen auf der Karte kein Objekt, so wird ein neues Objekt dort hineingeladen (Beispielcode bereits ganz oben unter „Verteilung der Objekte auf der Karte“ erklärt).

Aus der Vielzahl der Fragestellungen und Aufgaben, die sich beim Programmieren einer App ergeben, die in möglichst kurzer Zeit effektive Berechungen durchführt, stellen die oben genannten Problemstellungen natürlich nur einen kleinen Anteil dar.[/vc_column_text][/vc_column][vc_column width=“1/6″][/vc_column][/vc_row]