多段线drawMapRect优化绘图

Question

我在地图上有很多长多段线。我想优化他们的绘图，因为在几千个点上绘制多段线的速度非常慢。

我的drawMapRect看起来像这样：

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

如果没有太多的点，这是很好的。但是当有8-16个可见的maprect和2-3000个点时，它们在for上的运行速度是令人难以置信的慢。

如果它们仅仅是位置，一个解决方案是实现某种类型的四叉树/r-树结构，并且只过滤当前绘制的MKMapRect中的那些位置，但我不确定这是否适合折线本身。

如果仅过滤当前maprect内的线段端点，则可能无法绘制某些线段。例如，点1-2之间的两个红色地图中没有线段端点，但仍需要绘制...

​

​

有没有某种类似于四叉树的算法或某种方法来解决这个问题？

Answer 1

不幸的是，我不知道这样的数据结构，可以允许检查与矩形的线相交。

但是，解决该问题的一种方法可能是：

在一个非常低分辨率的地图中绘制所有的折线(一个2维的数组)，并注意每个像素是哪个折线绘制的。然后在此低分辨率映射中扫描绘制像素的相关矩形，并存储所有相关折线。然后可以在全分辨率地图中绘制这些内容。

也许这个近似算法比你现在使用的精确算法更快。

编辑：

我假设您使用一种有效的算法进行折线MKMapRect相交检查，如How to find the intersection point between a line and a rectangle?中所示。