graph.intersects really slow with many entities

openstreetmap / iD

🆔 The easy-to-use OpenStreetMap editor in JavaScript.

https://www.openstreetmap.org/edit?editor=id

ISC License

3.36k stars 1.21k forks source link

graph.intersects really slow with many entities #479

Closed ansis closed 11 years ago

ansis commented 11 years ago

After panning around a bit, the number of entities gets high, and graph.intersects (linear) gets really slow, taking about 1s each full redraw. Probably a good idea to use a quadtree or rtree. rtree would be perfect, but I'm looking at dropping the dependency because its probably not needed for labelling.

jfirebaugh commented 11 years ago

:+1:

jfirebaugh commented 11 years ago

Yeah, this comes up in profiling. Ideally we'd have some sort of persistent RTree with unchanged branches shared between graphs. This paper looks like a promising start: The temporal R-tree G Zimbrão et al.

ansis commented 11 years ago

I haven't look at the paper yet, but we could also just have a single tree store on the history, and just remove and reinsert based on difference. Might be worth trying out quad trees.

jfirebaugh commented 11 years ago

Tracking in #753 now.