GSOC 2016 Enquiry

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

GSOC 2016 Enquiry

AMR_KELEG

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

Reply | Threaded
Open this post in threaded view
|

Re: GSOC 2016 Enquiry

John Swensen-3

On Mar 25, 2016, at 8:46 AM, <[hidden email]> <[hidden email]> 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.

John S.
Reply | Threaded
Open this post in threaded view
|

Re: GSOC 2016 Enquiry (boolean operations on polygons)

PhilipNienhuis
John Swensen-3 wrote
> On Mar 25, 2016, at 8:46 AM, <[hidden email]> <[hidden email]> 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
Reply | Threaded
Open this post in threaded view
|

Re: GSOC 2016 Enquiry (boolean operations on polygons)

John Swensen-3

On Apr 24, 2016, at 9:49 AM, PhilipNienhuis <[hidden email]> 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.




Reply | Threaded
Open this post in threaded view
|

Re: GSOC 2016 Enquiry (boolean operations on polygons)

Juan Pablo Carbajal-2
On Mon, Apr 25, 2016 at 7:09 AM, John Swensen <[hidden email]> wrote:

>
> On Apr 24, 2016, at 9:49 AM, PhilipNienhuis <[hidden email]> 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.
>
>
>
>

Reply | Threaded
Open this post in threaded view
|

Re: GSOC 2016 Enquiry (boolean operations on polygons)

PhilipNienhuis
In reply to this post by John Swensen-3
John Swensen-3 wrote
> On Apr 24, 2016, at 9:49 AM, PhilipNienhuis <[hidden email]> wrote:
>
> 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).

<snip>

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

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.
True, but from my -limited- experience (just this weekend :-) ) that doesn't look like a showstopper.
I worked around it by computing mean(X), mean(Y) + subtracting, isotropic scaling based on the resulting max/min values, clipping, and back-scaling and -translating the solution afterwards.
For small problems this doesn't quite hurt as it is easily vectorized.  As soon as complicated geometries with > several 10,000s of patches are drawn the CPU time needed for this pre- and postprocessing is still negligible compared to clipping itself + especially drawing time.

2) For drawing polygons with holes in the past, I have use the poly2tri library (https://github.com/greenm01/poly2tri <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.
Does that mix well with Octave's graphics output? One of my aims is to draw polygons over background maps.
For anything more fancy I tend to invoke dedicated GIS SW.

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.
Well, you did mention your preference in a recent post here. As you are the mentor I think it's your party :-)

Just to clarify, I had a Clipper-based solution lying around to solve a somewhat urgent need, other than that I'm fairly indifferent as to what library will be chosen.
My only hope is that the final result will be reliable, fast and the Octave wrapper around it (.m-file or .oct file function) doesn't require too much data preparation and -analysis in advance (like manual hole detection, winding directions, self-intersections, rigid input/output format demands).

BTW, Clipper allows several hole/fill detection algorithms that I found to come in handy; hopefully Boost will offer similar choices.
Oh and it offers Z-value processing, something I often need.  Matlab's mapping toolbox is fairly limiting in that it discards Z values when reading shape files (and doesn't even read .dxf); I regularly need to draw/process 3D stuff from shapeZ files.  So from my POV that would be another wish for a Boost-based solution: that it offers at least some hooks for interpolating Z-values on clipped edges.

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.
Right; if you need help or test cases I'm available (time permitting, as always).

Philip