[Gdal-dev] remove colinear points from polygon

Mateusz Loskot mateusz at loskot.net
Tue Mar 6 09:20:26 EST 2007

Martel, Christian wrote:
> Mateusz, I know many solutions to remove colinear point but I want to
> use the available tools in OGR and get a quick and simple function.
> So here is what I did in python. Don't know about performance againt
> another method.


I've not run your script but it looks OK.
About performance, everything depends on your requirements.
Observable relation here is:
- simple code - less efficient
- more complex code - efficiency tunning is possible

Although, the script combines a few quite complex algorithms
and I'm inclined to say that it will probably perform slower than
slope-comparison or DP algorithm.
The complexity of only Convex Hull computation is O(n) for simple and
sorted polygons, but - certainly depending on algorithm - it usually is
more complex O(nlogn). I'm not sure which one algorithm is used in GEOS
(OGR uses GEOS for this operation), but it's still slower than
linear only simplification.

Anyway, everything depends on how fast do you want to run it.

Mateusz Loskot

More information about the Gdal-dev mailing list