4

I'm in need of listing all features in a linestring layer that have dangles (that is, one or both of its boundaries do not touch another feature). This being done in GDAL/OGR.

What I'm doing is iterating feature by feature, getting the bounding box of it, using that to do a spatial filter so I only select the features close to the one I'm checking, and then doing topology checks between it and the selected features. Something like this:

for i in range(n_feats):
    feat = layer.GetFeature(i)
    # get start and end points of feature
    # get bounding box of feature

    layer.SetSpatialFilterRect(bbox[0], bbox[3], bbox[2], bbox[1])
    n_feats_select = layer.GetFeatureCount()
    for dummy_i in range(n_feats_select):
        feat_select = layer.GetNextFeature()
        # check if feature intersects with previously gotten start and end points
        # if they don't, feature has a dangle, do stuff

    layer.SetSpatialFilter(None)

Now, this script works, which certainly matters, but it's slow. Specifically, I'm dealing with a layer with about 2 million features, and the spatial filter is hogging a lot of overhead. Specifically, each feature is taking about 10 seconds to process (the filter method alone taking over 9 seconds), thus 2 million features at this pace would take 231 days to process, give or take.

Is there any GDAL method that already does this, or a better algorithm for accomplishing this task?

1 Answer 1

4

To speed up the algorithm you should use an Rtree. Now you are testing every feature against the other 2 million features, this is really slow. With the Rtree you can test only against the features close to the start and end points.

Check this snorfalorpagus post, so you can see how to use it:

https://snorfalorpagus.net/blog/2014/05/12/using-rtree-spatial-indexing-with-ogr/

2
  • 1
    I thought of using R-trees, but I had no idea how to go about it. Glad to know there's a library for that already, thanks for the tip! The warm-up testings were very promissing, the construction of the R-tree generates quite the overhead (about 5 minutes), but after that it goes lightning fast. Initial predictions are that it'll take about 47 minutes to go through all 2 million features, quite the gain from the previous 231 days! Commented Dec 20, 2017 at 21:27
  • Take care, R-trees are the gis programmer heroine. ;) Commented Dec 21, 2017 at 7:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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