Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

I have written a QGIS plugin and it iterates through all features in a layer using provider.select() and compares geometry. The problem, the plugin is very slow. If there are 114 features in a shapefile and it needs to iterate 80 times then it will have to repeat the code 9120 times.

How can I speed up the iteration process? Should I store all features in a list and then iterate thru the list? Store all features in a memory layer (not sure what that is yet)?

Thanks

Ed

share|improve this question
2  
Maybe you could add little more information what you are doing. Usually you speed spatial stuff by limiting date. For an example it is useless to compare geometries if they are more than 2km apart each other if you are calculating which geometries intersect. QGis Api for QgsVectorDataProvider.select gives you option to limit selection by attributes or rectangle –  simplexio Oct 31 '12 at 14:15
    
The plugin searches all features connected to a selected line. It does this by comparing upstream coordinate to downstream coordinate. If the distance between the coordinates is less than a tolerance than it will add the feature to a list and repeat the search for the newly selected feature. So I can't have a fixed rectangle but... –  GreyHippo Oct 31 '12 at 14:23
    
You just gave an idea. Instead of iterating through all features each time, I could set a selection buffer around my upstream point and only iterate thru those features. Thanks! –  GreyHippo Oct 31 '12 at 14:26
1  
What exactly are you trying to accomplish? An upstream or downstream trace? Having a better idea of your actual goals will help people point you in the right direction for the entire process, not just a single step. –  RyanDalton Oct 31 '12 at 16:14
    
I wrote a plugin that picks all features upstream of a selected line. I am finished with the first version. The only issue I was having was the length of time to iterate thru all features, which after reading Simplexio I realized I could greatly improve the iteration by using a spatial selection. The plugin will be called Flow Trace and will hopefully be available in the Qgis Plugin repository. –  GreyHippo Oct 31 '12 at 19:02

2 Answers 2

Sounds like you are solving a Graph problem (e.g network connectivity) using the wrong approach. Iterating 80 times over 114 (effectively a linear scan per edge hop) is not adequate and is a sign that your algorithm could be optimized. I will go out on a limp and guess that after your reach each edge, you are scanning through all the features to figure out which ones are connected, and you do that for every edge. What you want to do is built a connectivity graph once and then traverse that. If you give us more details about you are trying to do, perhaps we can steer you to a better approach.

share|improve this answer
1  
Ragi, I am no longer scanning thru all features and I have finished the first version. plugins.qgis.org/plugins/flowTrace –  GreyHippo Nov 2 '12 at 13:40
    
@GreyHippo Have you gotten around to updating this plugin for QGIS 2.0? –  user25976 Jul 2 at 22:54

I did something similiar last year with SQL. I had network with several sinks and sources and pipe direction didn't matter.

First i did SQL table #tree |source_id|target_id| (start point over start point or end point...), #closed table |id| and #reached table |id|. All id are pipes unique id

i inserted closed pipe id into #closed and first pipe id's from source to #reached table, then loop over #tree table until i didnt have anything to insert into #reached table. It is little bit slow way to do it but it works, only thing you need is tree


DECLARE @closed varchar(50)
SET @closed = '23'
DECLARE @root varchar(50)
SET @root = '42'

-- add all sources to reached insert into #reached values ( @root ) -- substitute root id as needed while ( @@rowcount > 0 ) begin insert into #reached (id ) select distinct child as id from tree e join #reached p on p.id = e.parent collate database_default where e.child collate database_default not in ( select id from #reached ) AND e.child != @closed AND e.parent != @closed -- change to : e.child not in #closed UNION
select distinct parent as id from tree e join #reached p on p.id = e.child collate database_default where e.parent collate database_default not in ( select id from #reached ) AND e.parent != @closed AND e.child != @closed

end

That solves whihc pipes are conencted to source or sources . It dosen't support several closed id , but it should be easy to fix.

Can't remember orginal author but i found base script from internet

share|improve this answer
    
I am using shapefiles –  GreyHippo Nov 2 '12 at 13:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.