5

I have lots of long polylines on a map. I'd like to optimize their drawing, because at a few thousand points the polylines are drawn incredibly slow.

My drawMapRect looks like this : 

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

Which does great if there aren't too many points. But when there are 8-16 maprects visible and 2-3000 points, they are incredibly slow running throught the for.

If they would be only locations, a solution would be to implement some kind of quadtree/r-tree structure and only filter for those locations in the currently drawn MKMapRect, but I'm not sure about if that would be appropiate for the polylines themselves.

If I filter only for the segment endpoints inside the current maprect, then some line segments might not be drawn. For example, the two red maprects between points 1-2 have no segment endpoints in them but still need to draw ...

enter image description here

Is there some kind of algorithm similar to quadtrees or some kind of approach for this problem ?

Templar
  • 1,694
  • 1
  • 14
  • 32

1 Answers1

0

Unfortunately, I don’t know such a data structure that would allow to check line intersection with a rectangle.
However, one approach to solve the problem might be the following:
Draw all polylines in a map of very low resolution (a 2 dim array), and note for every pixel which polyline has drawn it. Then scan in this low-res map the relevant rectangles for drawn pixels, and store all relevant polylines. These can then be drawn in the full resolution map.
Maybe this approximate algorithm is faster than the precise algorithm that you use right now.

EDIT:

I assume you use for the polyline MKMapRect intersection check an effective algorithm such as shown in How to find the intersection point between a line and a rectangle?.

Community
  • 1
  • 1
Reinhard Männer
  • 14,022
  • 5
  • 54
  • 116
  • Will give this a try if can't find anything else. Currently for each segment I calculate its bounding maprect and just check for mkmparect intersection/containment with the currently drawn maprect. – Templar Dec 03 '15 at 10:25