Does anyone know of any GIS tool that reorders polygons so that the path through all polygons is minimized, i.e. it solves the travelling salesman problem? Here's an example of just how poorly optimized a shapefile can be:

enter image description here

  • I'm not sure from your brief description what you have and what you need. Reordering polygons in a shapefile is technically and logically impossible, their order is set by the FID which can't be manually changed, features will reorder but you have absolutely no control over how this happens. – Michael Stimson Mar 26 at 2:04
  • 1
    @MichaelStimson If you write the features to a new shapefile, you can control the order, though you'd need to use something like a cursor to get the needed granularity. I actually optimize my file geodatabase and PostgreSQL table feature order for optimal draw performance all the time (I don't use shapefiles anymore). – Vince Mar 26 at 2:15
  • Isn't that what a spatial index is for @Vince? You're right, it is possible to write to a shapefile in a particular order but that order is so fragile I wouldn't depend on it, geodatabases on the other hand where the OID is kept for the lifetime of the row can be ordered as you say. – Michael Stimson Mar 26 at 2:19
  • 2
    @MichaelPeters This isn't a traditional travelling salesman, though if you populated centroids and connected them in a network of near neighbors, that would bend the existing tools to work for you. – Vince Mar 26 at 2:21
  • @MichaelStimson No, the spatial index is still impacted by spatial fragmentation, especially choosing thousands out of millions, so physical order can have a measureable impact on draw time. BTW: The FID in shapefiles isn't all that fragile; I just prefer a format that supports numeric NULLs and datetime values – Vince Mar 26 at 2:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.