ポリライン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の地図修正と2-3000ポイントがあるとき、彼らはforを通って信じられないほど遅いです。

もしそれらが唯一の場所になるのであれば、ある種のquadtree/r-tree構造を実装し、現在描画されている場所にフィルタをかけることになりますが、それが適切かどうかは分かりませんポリラインそのもの。

現在のmaprect内のセグメントエンドポイントのみをフィルタリングすると、一部の線分が描画されないことがあります。例えば、ポイント1-2間の2つの赤いmaprectsは、それらには、セグメントのエンドポイントを持っていないが、それでも描画する必要があります...

は四分木に似たアルゴリズムのいくつかの種類またはのためのアプローチのいくつかの種類がありますこの問題 ？

Answer 1

残念ながら、矩形との線の交差を確認できるデータ構造はわかりません。
しかし、問題を解決する1つのアプローチは、非常に低い解像度（2次元配列）のマップ内のポリラインとポリラインが描いたすべてのピクセルに注意してください。
描画すべて次に、この低解像度マップで描画されたピクセルの関連する長方形をスキャンし、関連するすべてのポリラインを保存します。これらは、完全な解像度マップで描くことができます。
この近似アルゴリズムは、現在使用している正確なアルゴリズムよりも高速かもしれません。

EDIT：

私はあなたがHow to find the intersection point between a line and a rectangle?に示すような効果的なアルゴリズムを確認するポリラインMKMapRect交差点に使用を前提としています。