search

MarcusWolschon / osmeditor4android

Vespucci is a OpenStreetMap editor for Android
http://vespucci.io
Other
374 stars 83 forks source link

Use spatial index for referencing OSM objects #227

Open GoogleCodeExporter opened 9 years ago

GoogleCodeExporter commented 9 years ago 
Currently de.blau.android.osm.Storage class uses ArrayLists to store references 
to OSM objects. While this works for a small number of objects, it makes any 
spatial queries painful, particularly for ways. 

Unluckily implementing this will require tracking geometry changes (for example 
moving a node that is part of way would require removal and reinsertion of both 
the node and the way in the indices). 

Example use: determining which objects need to be drawn for the display.

Original issue reported on code.google.com by sp8...@gmail.com on 6 Jul 2014 at 9:37

GoogleCodeExporter commented 9 years ago

Original comment by sp8...@gmail.com on 29 Jul 2014 at 10:37

MarcusWolschon commented 9 years ago

Do you have any geometric data structures that are mutable? I'm not aware of any kind of trees or other 2D indice that stay balanced when modified.

simonpoole commented 9 years ago

@MarcusWolschon I'm assuming that modifying the geometry of an element would require deleting it and then re-inserting (tag mods etc naturally not). Which makes that a lot more expensive than the current solution, however everything else should be far cheaper. Currently my inclination is to do the reimplementation of the bugs/notes code with R-Trees and see how well that works.

MarcusWolschon commented 9 years ago

The problem is not the re-insertion but how to balance the tree when elements get inserted. This was a major problem in my Traveling Salesman navigation software. Am 24.04.2015 12:34 nachm. schrieb "simonpoole" notifications@github.com:

@MarcusWolschon https://github.com/MarcusWolschon I'm assuming that modifying the geometry of an element would require deleting it and then re-inserting (tag mods etc naturally not). Which makes that a lot more expensive than the current solution, however everything else should be far cheaper. Currently my inclination is to do the reimplementation of the bugs/notes code with R-Trees and see how well that works.

— Reply to this email directly or view it on GitHub https://github.com/MarcusWolschon/osmeditor4android/issues/227#issuecomment-95885061 .