ios - Polyline drawMapRect 优化绘图

Question

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

我的 drawMapRect 看起来像这样:

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

如果没有太多的点，这会很好。但是当有 8-16 个 maprects 可见和 2-3000 个点时，它们在 for 中的运行速度非常慢。

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

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

是否有某种类似于四叉树的算法或某种解决此问题的方法？

Answer 1

不幸的是，我不知道这样的数据结构可以检查线与矩形的交点。
但是，解决该问题的一种方法可能如下:
在分辨率非常低的 map (2 维阵列)中绘制所有 多段线，并注意多段线绘制它的每个像素。然后在这个低分辨率 map 中扫描绘制像素的相关矩形，并存储所有相关的折线。然后可以在全分辨率 map 中绘制这些。
也许这个近似算法比你现在使用的精确算法更快。

编辑:

我假设您对多段线 MKMapRect 交点使用了一种有效的算法，如 How to find the intersection point between a line and a rectangle? 中所示。 .