Re: GSOC 2016 Enquiry (boolean operations on polygons)

[Juan Pablo Carbajal]

On Mon, Apr 25, 2016 at 7:09 AM, John Swensen <address@hidden> wrote:
>
> 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.
>
The license seems to be the Modified BSD lincense (3-Clause BSD) which
is GPL-Compatible
https://en.wikipedia.org/wiki/BSD_licenses#3-clause_license_.28.22Revised_BSD_License.22.2C_.22New_BSD_License.22.2C_or_.22Modified_BSD_License.22.29

> 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.
>
>
>
>