Re: GSOC 2016 Enquiry (boolean operations on polygons)

[John Swensen]

On Apr 24, 2016, at 9:49 AM, PhilipNienhuis <address@hidden> wrote:

John Swensen-3 wrote

On Mar 25, 2016, at 8:46 AM, &lt;

amr_mohamed@

&gt; &lt;

amr_mohamed@

&gt; wrote:

Dear Mr John,
I noticed that the implementation of boolean operations on polygons
project was moved to packages projects ...
Will the project probably be discarded ?
Regards,
Amr Mohamed

I don’t think the project is being discarded. I had just mistakenly
thought that the polygon functions were part of the core of Matlab. They
are actually in the Matlab Mapping Toolbox, so they re-arranged the GSoC
wiki page to indicated that the results of this project would end up being
included in the Octave Mapping Package, rather than in the core of Octave.
As far as I know, it was more of just an organizational correction to the
wiki page, rather than an actual change in scope or importance.

Just to jump in, as regards this project I wonder if it is really enough for
a GSoC project.

I already had a partial implementation lying around I made early last year
based on Clipperlib (based on a mex function in the Third Party/Matlab/
subdir in the clipper archive), and in the wiki John Swensen pointed to Ulf
Griesmann's web page where another working implementation for Octave is
present (also based on Clipperlib).
Both implementations provide much more functionality than just polybool()
and ispolycw() in Matlab's mapping toolbox.

Recently I urgently needed a decent polyclip function for a project so I set
to finishing my own version - took me just two evenings.  Looking at Ulf
Griessman's polybool function I think that also only needs one or two
evenings of work.
polybool() and ispolycw() in the mapping package would only need to be a
very thin m-file wrapper n top of one of these implementations.

One advantage of clipperlib is that there is no need to build, or rely on, a
separate library for it. Just copying the clipper.cpp and clipper.hpp files
over + the mex wrappers supplied in clipperlib itself or from Ulf Griesmann
will do for the binary parts; mkoctfile will do the rest during package
installation.
In addition I know that clipperlib offers an option to also process Z-values
+ interpolation (using a user-supplied callback). I haven't found that in
Boost.geometry or any other polygon clipping library yet (but maybe it is
there).

If we go for Clipperlib, I think that this GSoC project as it stands is too
small to fill 3 months, because most of the work has already been done. It's
just a matter of polishing existing code.

But then additional functionality can be thought up:

- How to properly draw polygons with holes. AFAIK (but I hope there is a
better solution) both Octave and Matlab need "branch cuts" to be able to
draw, or better: leave holes in polygons. A clever algorithm is required to
avoid those branch cuts screwing up drawings, esp. in case of multiple
and/or concentric holes.
There is already a partial implementation for that (in shapedraw.m in the
current mapping package) but I wouldn't call it a clever one.

- Implementing efficient interpolation of vertex Z-values, maybe multiple
Z-values, on clipped polygon sides.

- Maybe 3D-clipping of 3D polygons (maybe even more dimensions).

- ????


Thoughts ?

Philip

Based on my past experience with ClipperLib, it has some issues:

1) It only does integer math. Some of this can be worked around by scaling, using ClipperLib, then scaling the back. The problem with this is that to ensure you are scaling properly, you have to really scan the entire set of points first. This may end up being prohibitive and still may produce incorrect results.

2) For drawing polygons with holes in the past, I have use the poly2tri library (https://github.com/greenm01/poly2tri) with both Boost, gpc, and ClipperLib in the past. It has a non-standard license, but seems like a pretty permissive license. I’m not sure what actually counts as GPL-compatible.

I guess I was under the impression we had decided to use Boost, rather than ClipperLib for a variety of reasons (it is still maintained, it handles self-intersections better, it is used by a lot of other GIS/mapping professionals, etc,). I think that implementing this functionality using a new library and writing a suite of tests for regressions, as well as transitioning any other slower functionality of the existing polygon functions, could easily take the full three months. If we want to tack on a few other things, then I guess that could be reasonable.

I was going to have a kick-off Google Hangout meeting with him tomorrow to start discussing the timeline and goals, so I guess we should make a decision about the approach we want him to take before we meet.

John S.