Polyline drawMapRect optimierte Zeichnung

Question

Ich habe viele lange Polylinien auf einer Karte. Ich möchte ihre Zeichnung optimieren, denn an einigen tausend Punkten werden die Polylinien unglaublich langsam gezeichnet.

Meine drawMapRect sieht wie folgt aus:

- for each polyline segment 
- verify if it's bounding box intersects the currently drawn MKMapRect 
- if id does, draw it 

Welche große tut, wenn es nicht zu viele Punkte sind. Aber wenn 8-16 Maprets sichtbar und 2-3000 Punkte sind, laufen sie unglaublich langsam durch die for.

Wenn sie nur Standorte wären, wäre eine Lösung, eine Art Quadtree/r-Tree-Struktur zu implementieren und nur für diese Orte in der aktuell gezogenen MKMapRect zu filtern, aber ich bin mir nicht sicher, ob das angemessen wäre für die Polylinien selbst.

Wenn ich nur für die Segmentendpunkte innerhalb des aktuellen Maprect filtere, werden einige Liniensegmente möglicherweise nicht gezeichnet. Zum Beispiel haben die beiden roten maprects zwischen den Punkten 1-2 keine Segment-Endpunkte in ihnen müssen aber noch ziehen ...

Gibt es irgendeine Art von Algorithmus ähnlich wie Quadtrees oder irgendeine Art von Ansatz für dieses Problem ?

Answer 1

Leider kenne ich keine solche Datenstruktur, die es erlauben würde, den Schnittpunkt einer Linie mit einem Rechteck zu überprüfen.
Ein Ansatz zur Lösung des Problems könnte jedoch folgender sein:
Zeichnen Sie alle Polylinien in einer Karte mit sehr niedriger Auflösung (ein 2 Dim-Array), und beachten Sie für jedes Pixel, die Polylinie es gezeichnet hat. Dann scannen Sie in dieser Karte mit niedriger Auflösung die relevanten Rechtecke für gezeichnete Pixel und speichern Sie alle relevanten Polylinien. Diese können dann in der Karte mit voller Auflösung gezeichnet werden.
Vielleicht ist dieser ungefähre Algorithmus schneller als der genaue Algorithmus, den Sie gerade verwenden.

EDIT:

Ich nehme an, Sie für den Linienzug MKMapRect Kreuzung verwenden, um einen effektiven Algorithmus überprüfen wie in How to find the intersection point between a line and a rectangle? gezeigt.