Polygon clipping performance

[asinghvi17]

For a lot of geospatial usecases, polygons of size > 100 are de rigueur. GeometryOps' performance on these polygons is horrible, more than 10x slower than LibGEOS.

This could probably be improved by a monotone chain optimization, which we should add. This will probably also need the prepared geometry interface.

[skygering]

Polygons with holes are also pretty bad. For example:

import GeoInterface as GI
import LibGEOS as GO
p25 = GI.Polygon([[(0.0, 0.0), (5.0, 0.0), (5.0, 8.0), (0.0, 8.0), (0.0, 0.0)], [(4.0, 0.5), (4.5, 0.5), (4.5, 3.5), (4.0, 3.5), (4.0, 0.5)], [(2.0, 4.0), (4.0, 4.0), (4.0, 6.0), (2.0, 6.0), (2.0, 4.0)]])
p26 = GI.Polygon([[(3.0, 1.0), (8.0, 1.0), (8.0, 7.0), (3.0, 7.0), (3.0, 5.0), (6.0, 5.0), (6.0, 3.0), (3.0, 3.0), (3.0, 1.0)], [(3.5, 5.5), (6.0, 5.5), (6.0, 6.5), (3.5, 6.5), (3.5, 5.5)],  [(5.5, 1.5), (5.5, 2.5), (3.5, 2.5), (3.5, 1.5), (5.5, 1.5)]])

[asinghvi17]

Huh! We should add the test suite polygons as benchmarks as well, so that all the bases are covered. That could be a good start to a PkgBenchmark type of thing, since the current benchmarks are more focused on scaling across number of vertices which there isn't really a good solution for (yet) in the benchmark world.

~This timing is without ExactPredicates as well I assume, so that probably isn't the issue.~ Is the timing done with ExactPredicates enabled?

[skygering]

This is with ExactPredicates since I was just testing a few of things in the REPL.

[asinghvi17]

I just ran an example with the number of vertices increased (using segmentize) and found the following: (this is pre-ExactPredicates but I will check that branch and post a plot as well)

[asinghvi17]

Huh...exactpredicates is really hitting performance hard here.

[rafaqz]

The problem is scaling... not ExactPredicates

Ugh no if that is one point on the left then the scaling is just from our head start.

[asinghvi17]

Yeah, looks like it...on the bright side, we at least have a head start :D

[asinghvi17]

The code for that plot is in https://github.com/Caltech-OCTO/GeometryOps.jl/pull/8