I recently came across this web site from back in 1998, which is happily still around. It has a good list of implementations of what it calls Polygon Boolean operations. (This is the same thing as the JTS overlay operations - I chose to use a different term to avoid confusion with the spatial predicates). Perhaps some of these sites have done a better job of documentation! There's also some useful references to academic papers covering aspects of the issue.
It would be interesting a performance comparison between original Polygon Boolean and JTS!
ReplyDeleteYeah, this would definitley be interesting. PB is available in C# and
ReplyDeleteC++, and unfortunately I don't have the ability/inclination to create
environments to run these. Also, as I have seen with JTS and GEOS,
the implementation language can make a huge difference in relative
performance (GEOS is quite a bit slower than JTS).
But maybe I might look at trying to port the C# version to Java -
hopefully this wouldn't be too hard.
I'd also like to do this for Alan Murta's GPC, which does have a Java
port. I'll post the results if and when I get around to this.
I have to say, I had a very hard time following the GPC code, so even
if it was faster I'n not sure I'd be keen to try and use the same
approach in JTS.
The other interesting thing to do a comparison on would be the
robustness of the algorithms. PB sounds like it's supposed to be very
robust. GPC I suspect is not, because I don't see anything in the
code which is trying to maintain robustness. And then of course
algorithms which *are* robust have to obtain this robustness by
perturbing or rounding the geometry they are processing, so you should
compare the quality of their output as well (i.e to ensure they aren't
doing something outrageous like collapsing everything to a point).
Much fun to be had!