[gdal-dev] Complexity of algorithms

Frank Warmerdam warmerdam at pobox.com
Wed Sep 2 10:15:56 PDT 2020


The interesting geometry functions are essentially all from GEOS, so I'd
suggest investigating there for information.


Most GDAL raster operations are essentially linear in the number of pixels
though there are a few things (like hole filling, and polygonization, and
contour generation) that have more interesting properties.  I am not aware
an effort to characterize the complexity of these in the GDAL project
though at least some thought went into complexity analysis when
implementing some of these.

Best regards,

On Wed, Sep 2, 2020 at 12:50 PM Zachary D├ęziel <
Zachary.Deziel at usherbrooke.ca> wrote:

> Hi all,
> Sorry for disturbing and I hope I am passing through the right channel for
> my question. If not, please feel free to redirect me!
> I have been searching in the documentation and elsewhere for information
> regarding the time complexity of the algorithms of GDAL/OGR. More precisely
> around the classic operations on point, line and polygon data structures
> (buffer, intersect, etc). I have not found any mention of complexity in the
> documentation. Is there some hidden documentation gem somewhere that covers
> the time and/or memory complexity of the algorithms? If no such
> documentation exists, are there reasons for it not existing? Is it simply a
> matter of not being a priority in the development cycle?
> Sorry for the compact and numerous questions, if you have any interest in
> the subject please reach out.
> Sincerely,
> Zac
> _______________________________________________
> gdal-dev mailing list
> gdal-dev at lists.osgeo.org
> https://lists.osgeo.org/mailman/listinfo/gdal-dev

I set the clouds in motion - turn up   | Frank Warmerdam,
warmerdam at pobox.com
light and sound - activate the windows | +1 650-701-7823
and watch the world go round - Rush    | Geospatial Software Developer
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/gdal-dev/attachments/20200902/cbd3e527/attachment.html>

More information about the gdal-dev mailing list