Tell me more ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.
up vote 1 down vote favorite
1

I am looking to make efficient algorithms for those vector GIS operation that take a long time for GIS software like Arc-GIS, Grass etc. I have considered polygon overlay but looking for other operations as well.

share|improve this question
2  
Please clarify the question. Are you looking for a list of compute intensive GIS operations? Or are you looking for efficient algorithms? For all possible intensive operations? – underdark♦ Jan 21 '12 at 11:39
@underdark for all intensive operations. – justin waugh Jan 21 '12 at 15:08
4  
Is this an academic exercise or for a specific situation where performance is a problem? If a specific situation, prior knowledge of the data could be your best weapon in improving performance. If not, I would imagine many effort-hours have already been expended in this area (imagine doing point-in-polygon on a 1980s workstation - you would make sure the algorithm was efficient) – tomfumb Jan 22 '12 at 23:35
2  
This question would benefit from greater precision and, perhaps, some elaboration. In particular, what do you mean exactly by "take a long time"? This qualitative phrase will mean different things to different people. Do you mean operations that scale badly with the size of the input data? Would you include operations that scale well but have an inherently large implicit constant? (That is, operations that may be asymptotically efficient but still take a "long" time on small problems.) Note that "long" in a real-time application can be much shorter than "long" in another context, too. – whuber♦ Jan 23 '12 at 14:50

4 Answers

up vote 3 down vote accepted

Of the top of my head, some non trivial vector operations:

  • Generate a polygon layer from a GRID / DEM / RASTER
  • Build a triangular irregular network from a GRID / DEM
  • Functions on large datasets (buffer, generalize, reproject, check topology)
  • Build / Rebuild spatial indexes on a vector layer
  • GIS Analysis (Hill shade, flood map)
share|improve this answer
up vote 6 down vote

I'm not exactly sure what the question is, but if you're looking for complex geometry operations to implement by yourself, there are many sources for those. You could start by reading http://en.wikipedia.org/wiki/Computational_geometry#Problem_classes.

share|improve this answer
1  
+1 I would also add Travelling Salesman Problem, not a vector problem strickly speaking, but from a practical standpoint I think including vectors makes the solution more meaningful. – Kirk Kuykendall Jan 21 '12 at 21:04
@Kirk: Good point. Other network analysis problems would probably fit here as well. – radek Jan 23 '12 at 11:49
up vote 0 down vote

In GRASS GIS 7 the vector algorithms have been significantly improved for speed, consumption of computational resources and especially the possibility to analyze huge datasets (where most other GIS fail).

Download: http://grass.osgeo.org/download/software.php#g70x

To make a performance test, download the CORINE vector data from EEA and reconstruct the topology.

share|improve this answer
up vote 0 down vote

You've got a lot of suggestions already so I won't repeat anything except to add one obvious option and another slightly "left-field" thing-to-try.

The obvious option is to go down the route of multiprocessesing (depending on exactly what your problem is). Ignore any statements about how ArcGIS is/was single threaded etc. That is irrelevant. Spawn multiple subprocesses and use a queue to feed them. I have done this successfully with ArcGIS and GGDAL/OGR (but never tried it in GRASS) and even had a single ArcGIS licence running (with a bit of help) on a bank of networked computers in a geoprocessing farm. However, don't overload your machine. You'll need to gauge how intense any one process is and you might only get one per core (excessive subprocesses can actually result in you INCREASING the overall processing time if you're not careful) and you should leave some spare capacity for the operating system to do its stuff too. How many you can run depends a lot on your use-case and hardware.

The "slightly left-field" option is to re-think how you are accessing your geometry. This might or might not be relevant (I can't tell from your question). However, if you are using cursors to loop through your features and then more cursors to loop through your geometry, this can be slow. Under some circumstances, dumping the geometry into a container in one go can save a few milliseconds per operation and if you have hundreds of thousands of features, that can equate to time worth saving. OGR can help here. ArcPy is not so helpful for this approach.

If you need to squeeze more speed out of the set-up, think laterally about your algorithm. In GIS there is never a single correct way to do geoprocessing and alternative modules or re-ordering calculations can give good results. One simple example of lateral thinking is so obvious it is hardly worth mentioning but is often forgotten, viz. do you really need that 13 decimal place resolution in your data? A simplification pass before you start can give a real boost.

Finally, check your spatial indexing. ArcGIS is pretty good at this usually but some other databases like SpatiaLite, you need to explicitly tell it to use R-trees. On that note: your choice of database can also impact your speed.

share|improve this answer

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.