Quantcast

GSoC 2017 - Implement boolean operations on polygons

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
30 messages Options
12
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: GSoC 2017 - Implement boolean operations on polygons

PhilipNienhuis
John,

John Swensen wrote:

>
>> On Mar 17, 2017, at 2:56 AM, Juan Pablo Carbajal
>> <[hidden email] <mailto:[hidden email]>> wrote:
>>
>> On Fri, Mar 17, 2017 at 9:41 AM, PhilipNienhuis <[hidden email]
>> <mailto:[hidden email]>> wrote:
>>> Juan Pablo Carbajal-2 wrote
>>>> On Thu, Mar 16, 2017 at 9:56 PM, piyushjain &lt;
>>>
>>>> piyushjain1sa@
>>>
>>>> &gt; wrote:
>>>>> Sir, I went through the current geometry package development and also
>>>>> read
>>>>> about mkoctfile command, and how to use oct create and use oct-files.
>>>>>
>>>>> So, can you tell me what are the milestones of the project? I
>>>>> mean,going
>>>>> step-wise, what do I need to implement?
>>>>>
>>>>>
>>>>>
>>>>> --
>>>>> View this message in context:
>>>>> http://octave.1599824.n4.nabble.com/GSoC-2017-Implement-boolean-operations-on-polygons-tp4682161p4682435.html
>>>>> Sent from the Octave - Maintainers mailing list archive at Nabble.com.
>>>>>
>>>> So you know what you want to pursue already?
>>>> 1. Cleanning up the boost interface
>>>> 2. Adding clipper interface, read this
>>>> https://savannah.gnu.org/patch/?func=detailitem&item_id=9000#options
>>>
>>> From my memory, the Clipper interface should be about done.
>>> I'm still busy with making it clip polylines (works now) and
>>> interpolating Z
>>> values (got stuck there); but for "ordinary" 2D polygons I think it just
>>> works as it is.
>>>
>>> Philip
>>>
>>>
>>>
>>> --
>>
>> In that case I suggest you provide patches to integrate Philip work
>> into geomtry, following the guidelines described in that savanah
>> thread.
>> I was planning to do this in Octconf so I will give you quick feedback
>> if you provide something beginning of next week.
>>
>
> One final comment. I know I pushed the Boost solution because at the
> time I thought it had the most robust solution for self-intersecting
> polygons, polygons with parallel lines, etc. I now feel a little bad
> that we spent all that time and it hasn’t been incorporated into the
> package. It is quite cumbersome to get Boost set up to compile with the
> version that supports self-intersection correction. I think that more
> work could be done to make it a much better solution by making a “Point
> concept abstraction” that would allow it to operate on the Octave
> variable data in-place without having to copy. For larger datasets, this
> could be a huge memory (and potentially performance) improvement over
> the other solutions where you have to transform the Octave data into the
> format required by the library.

I have been trying the Boost version by Amr for some time, using Amr's
unofficial geometry-3.0.0 version from github and the mapping package
(also an unofficial version, but I'm the mapping pkg maintainer :-) ).
AFAICS it does work fine, reliably and fast.
Also the poly2fv function is very useful for graphical output.

We (package maintainers JuanPi and me) didn't know that Boost is so big.
Later on Amr mentioned he has weeded it out but AFAICS that info is
nowhere.
FYI Boost (an enormous collection of include files) alone is > 10 % disk
space of an entire mxe-octave windows installer. That wouldn't be bad in
itself, but the fact that it's used for just a few specialized functions
puts that into another perspective.

Where you write "boost with self-intersection correction", I suppose
that's version 1.61 and up, and it would be desirable to be able to have
polybool be based on that version as well, depending on compile time
availability through configure.
So a GSOC project could be bringing the polybool/boost solution further
so that it can be included in OF-geometry.
I would really like that to happen.

> Has anyone ever explored the license for GPC
> (http://www.cs.man.ac.uk/~toby/gpc/
> <http://www.cs.man.ac.uk/%7Etoby/gpc/>)? It says it is free for
> private/hobbyist/education purposes, but I don’t know whether the
> license is compatible with the GPL and Octave. From my experience, GPC
> is one of the fastest and most robust polygon clipper out there. Maybe
> we overlooked it because of its split license and the fact that the
> license isn’t very well defined?

The GPL explicitly does not limit use of free SW. "Free for just
education purposes" is incompatible with the GPL.

There are several benchmarks out there, some or most of them outdated
now, that do not quite put GPC at #1. But I think many of those
benchmarks are a bit "colored" as they usually relate to a specific
polygon SW solution.
At my work we've been using it once (with matlab), my impression of that
one -probably atypical- occasion was that GPC isn't so very fast.
Therefore I'm glad you share with us your experience with several
polygon clipping libraries, I think that is very valuable, thanks.

Maybe we could find out what GIS SW like QGIS uses internally?

Philip


Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: GSoC 2017 - Implement boolean operations on polygons

John Swensen-3

On Mar 17, 2017, at 1:53 PM, Philip Nienhuis <[hidden email]> wrote:

John,

John Swensen wrote:

On Mar 17, 2017, at 2:56 AM, Juan Pablo Carbajal
<[hidden email] <[hidden email]>> wrote:

On Fri, Mar 17, 2017 at 9:41 AM, PhilipNienhuis <[hidden email]
<[hidden email]>> wrote:
Juan Pablo Carbajal-2 wrote
On Thu, Mar 16, 2017 at 9:56 PM, piyushjain &lt;

piyushjain1sa@

&gt; wrote:
Sir, I went through the current geometry package development and also
read
about mkoctfile command, and how to use oct create and use oct-files.

So, can you tell me what are the milestones of the project? I
mean,going
step-wise, what do I need to implement?



--
View this message in context:
http://octave.1599824.n4.nabble.com/GSoC-2017-Implement-boolean-operations-on-polygons-tp4682161p4682435.html
Sent from the Octave - Maintainers mailing list archive at Nabble.com.

So you know what you want to pursue already?
1. Cleanning up the boost interface
2. Adding clipper interface, read this
https://savannah.gnu.org/patch/?func=detailitem&item_id=9000#options

From my memory, the Clipper interface should be about done.
I'm still busy with making it clip polylines (works now) and
interpolating Z
values (got stuck there); but for "ordinary" 2D polygons I think it just
works as it is.

Philip



--

In that case I suggest you provide patches to integrate Philip work
into geomtry, following the guidelines described in that savanah
thread.
I was planning to do this in Octconf so I will give you quick feedback
if you provide something beginning of next week.


One final comment. I know I pushed the Boost solution because at the
time I thought it had the most robust solution for self-intersecting
polygons, polygons with parallel lines, etc. I now feel a little bad
that we spent all that time and it hasn’t been incorporated into the
package. It is quite cumbersome to get Boost set up to compile with the
version that supports self-intersection correction. I think that more
work could be done to make it a much better solution by making a “Point
concept abstraction” that would allow it to operate on the Octave
variable data in-place without having to copy. For larger datasets, this
could be a huge memory (and potentially performance) improvement over
the other solutions where you have to transform the Octave data into the
format required by the library.

I have been trying the Boost version by Amr for some time, using Amr's unofficial geometry-3.0.0 version from github and the mapping package (also an unofficial version, but I'm the mapping pkg maintainer :-) ).
AFAICS it does work fine, reliably and fast.
Also the poly2fv function is very useful for graphical output.

We (package maintainers JuanPi and me) didn't know that Boost is so big. Later on Amr mentioned he has weeded it out but AFAICS that info is nowhere.
FYI Boost (an enormous collection of include files) alone is > 10 % disk space of an entire mxe-octave windows installer. That wouldn't be bad in itself, but the fact that it's used for just a few specialized functions puts that into another perspective.

Where you write "boost with self-intersection correction", I suppose that's version 1.61 and up, and it would be desirable to be able to have polybool be based on that version as well, depending on compile time availability through configure.
So a GSOC project could be bringing the polybool/boost solution further so that it can be included in OF-geometry.
I would really like that to happen.

Has anyone ever explored the license for GPC
(http://www.cs.man.ac.uk/~toby/gpc/
<http://www.cs.man.ac.uk/%7Etoby/gpc/>)? It says it is free for
private/hobbyist/education purposes, but I don’t know whether the
license is compatible with the GPL and Octave. From my experience, GPC
is one of the fastest and most robust polygon clipper out there. Maybe
we overlooked it because of its split license and the fact that the
license isn’t very well defined?

The GPL explicitly does not limit use of free SW. "Free for just education purposes" is incompatible with the GPL.

There are several benchmarks out there, some or most of them outdated now, that do not quite put GPC at #1. But I think many of those benchmarks are a bit "colored" as they usually relate to a specific polygon SW solution.
At my work we've been using it once (with matlab), my impression of that one -probably atypical- occasion was that GPC isn't so very fast.
Therefore I'm glad you share with us your experience with several polygon clipping libraries, I think that is very valuable, thanks.

Maybe we could find out what GIS SW like QGIS uses internally?

Philip


I think QGIS uses GEOS [1]. I had never really even investigated that one because this website [2] said that is was significantly slow for larger datasets. 

One of the problems with the Boost self-intersection correction is that it is broken again as of 1.63. I had been under the impression they were going to try and make it “functional but unreleased” from 1.61 and onward. That appears to not be the case. 

I have been meaning to dig into the Boost::Geometry examples at [3] to see if I can implement an iterator facade for a custom polygon object that allows us to operate directly on the octave data input without having to copy all the points into the Boost::Geometry model for points, rings, polygons, and multi-polygons. I think it should be possible. It may speed up execution because we aren’t copying a bunch of double values, but it should most certainly reduce memory usage a ton. If we could push the performance/resources even better than now, it might be a compelling reason to keep Boost.

One other option is to use the Boost-provided bcp utility to create the subset of Boost headers that is are needed to compile Boost::Geometry and include it in the package release. This is still 30MB uncompressed, but it is much smaller than the whole Boost. this would also allow us to distribute a version that has the self-intersection correction.


John



Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: GSoC 2017 - Implement boolean operations on polygons

PhilipNienhuis
John Swensen wrote:

>
>> On Mar 17, 2017, at 1:53 PM, Philip Nienhuis <[hidden email]
>> <mailto:[hidden email]>> wrote:
>>
>> John,
>>
>> John Swensen wrote:
>>>
>>>> On Mar 17, 2017, at 2:56 AM, Juan Pablo Carbajal
>>>> <[hidden email] <mailto:[hidden email]>
>>>> <mailto:[hidden email]>> wrote:
>>>>
>>>> On Fri, Mar 17, 2017 at 9:41 AM, PhilipNienhuis
>>>> <[hidden email] <mailto:[hidden email]>
>>>> <mailto:[hidden email]>> wrote:
>>>>> Juan Pablo Carbajal-2 wrote
>>>>>> On Thu, Mar 16, 2017 at 9:56 PM, piyushjain &lt;
>>>>>
>>>>>> piyushjain1sa@
>>>>>
>>>>>> &gt; wrote:
>>>>>>> Sir, I went through the current geometry package development and also
>>>>>>> read
>>>>>>> about mkoctfile command, and how to use oct create and use oct-files.
>>>>>>>
>>>>>>> So, can you tell me what are the milestones of the project? I
>>>>>>> mean,going
>>>>>>> step-wise, what do I need to implement?
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> --
>>>>>>> View this message in context:
>>>>>>> http://octave.1599824.n4.nabble.com/GSoC-2017-Implement-boolean-operations-on-polygons-tp4682161p4682435.html
>>>>>>> Sent from the Octave - Maintainers mailing list archive at
>>>>>>> Nabble.com.
>>>>>>>
>>>>>> So you know what you want to pursue already?
>>>>>> 1. Cleanning up the boost interface
>>>>>> 2. Adding clipper interface, read this
>>>>>> https://savannah.gnu.org/patch/?func=detailitem&item_id=9000#options
>>>>>
>>>>> From my memory, the Clipper interface should be about done.
>>>>> I'm still busy with making it clip polylines (works now) and
>>>>> interpolating Z
>>>>> values (got stuck there); but for "ordinary" 2D polygons I think it
>>>>> just
>>>>> works as it is.
>>>>>
>>>>> Philip
>>>>>
>>>>>
>>>>>
>>>>> --
>>>>
>>>> In that case I suggest you provide patches to integrate Philip work
>>>> into geomtry, following the guidelines described in that savanah
>>>> thread.
>>>> I was planning to do this in Octconf so I will give you quick feedback
>>>> if you provide something beginning of next week.
>>>>
>>>
>>> One final comment. I know I pushed the Boost solution because at the
>>> time I thought it had the most robust solution for self-intersecting
>>> polygons, polygons with parallel lines, etc. I now feel a little bad
>>> that we spent all that time and it hasn’t been incorporated into the
>>> package. It is quite cumbersome to get Boost set up to compile with the
>>> version that supports self-intersection correction. I think that more
>>> work could be done to make it a much better solution by making a “Point
>>> concept abstraction” that would allow it to operate on the Octave
>>> variable data in-place without having to copy. For larger datasets, this
>>> could be a huge memory (and potentially performance) improvement over
>>> the other solutions where you have to transform the Octave data into the
>>> format required by the library.
>>
>> I have been trying the Boost version by Amr for some time, using Amr's
>> unofficial geometry-3.0.0 version from github and the mapping package
>> (also an unofficial version, but I'm the mapping pkg maintainer :-) ).
>> AFAICS it does work fine, reliably and fast.
>> Also the poly2fv function is very useful for graphical output.
>>
>> We (package maintainers JuanPi and me) didn't know that Boost is so
>> big. Later on Amr mentioned he has weeded it out but AFAICS that info
>> is nowhere.
>> FYI Boost (an enormous collection of include files) alone is > 10 %
>> disk space of an entire mxe-octave windows installer. That wouldn't be
>> bad in itself, but the fact that it's used for just a few specialized
>> functions puts that into another perspective.
>>
>> Where you write "boost with self-intersection correction", I suppose
>> that's version 1.61 and up, and it would be desirable to be able to
>> have polybool be based on that version as well, depending on compile
>> time availability through configure.
>> So a GSOC project could be bringing the polybool/boost solution
>> further so that it can be included in OF-geometry.
>> I would really like that to happen.
>>
>>> Has anyone ever explored the license for GPC
>>> (http://www.cs.man.ac.uk/~toby/gpc/
>>> <http://www.cs.man.ac.uk/%7Etoby/gpc/>
>>> <http://www.cs.man.ac.uk/%7Etoby/gpc/>)? It says it is free for
>>> private/hobbyist/education purposes, but I don’t know whether the
>>> license is compatible with the GPL and Octave. From my experience, GPC
>>> is one of the fastest and most robust polygon clipper out there. Maybe
>>> we overlooked it because of its split license and the fact that the
>>> license isn’t very well defined?
>>
>> The GPL explicitly does not limit use of free SW. "Free for just
>> education purposes" is incompatible with the GPL.
>>
>> There are several benchmarks out there, some or most of them outdated
>> now, that do not quite put GPC at #1. But I think many of those
>> benchmarks are a bit "colored" as they usually relate to a specific
>> polygon SW solution.
>> At my work we've been using it once (with matlab), my impression of
>> that one -probably atypical- occasion was that GPC isn't so very fast.
>> Therefore I'm glad you share with us your experience with several
>> polygon clipping libraries, I think that is very valuable, thanks.
>>
>> Maybe we could find out what GIS SW like QGIS uses internally?
>>
>> Philip
>>
>
> I think QGIS uses GEOS [1]. I had never really even investigated that
> one because this website [2] said that is was significantly slow for
> larger datasets.
>
> One of the problems with the Boost self-intersection correction is that
> it is broken again as of 1.63. I had been under the impression they were
> going to try and make it “functional but unreleased” from 1.61 and
> onward. That appears to not be the case.

So boost is a little unstable as well...
Anyway such issues related to specific versions can be catched in a
configure script.

> I have been meaning to dig into the Boost::Geometry examples at [3] to
> see if I can implement an iterator facade for a custom polygon object
> that allows us to operate directly on the octave data input without
> having to copy all the points into the Boost::Geometry model for points,
> rings, polygons, and multi-polygons. I think it should be possible. It
> may speed up execution because we aren’t copying a bunch of double
> values, but it should most certainly reduce memory usage a ton. If we
> could push the performance/resources even better than now, it might be a
> compelling reason to keep Boost.

(Maybe I do not fully understand your aim.)
For any polygon library the input data will have to be morphed somehow
from the application/use case at hand into a format that the polygon
library expects; vice versa for output.
I'm unsure if investing a lot of work in specialized data access in some
.oct file is better than clever and vectorized preprocessing at the
Octave side. The latter is much more flexible and adaptable to the use
case at hand.

The Clipper library currently comprises a .mex wrapper file (in the
Third party subdir, in recent Clipper releases pointing to Matlab
Central).
While working on polyline clipping I noted there's quite some code
required to copy info from/to the structs that constitute the IMO rigid
MEX data I/O structures.  I suppose some of that code can be avoided, or
reduced, by rewriting the .mex wrapper into a proper .oct file using
octave_value objects.  That'll give more flexibility as well. I suppose
even the double<->int64 preprocessing can be absorbed in the .oct file
(currently I've put that in an .m file wrapper).

> One other option is to use the Boost-provided bcp utility to create the
> subset of Boost headers that is are needed to compile Boost::Geometry
> and include it in the package release. This is still 30MB uncompressed,
> but it is much smaller than the whole Boost. this would also allow us to
> distribute a version that has the self-intersection correction.

IIRC Amr mentioned he had brought down the boost stuff to around 11 or
12 MB.
I think the Boost include files shouldn't be in the geometry package
directory; they'd rather live in /usr/include.

Philip


Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: GSoC 2017 - Implement boolean operations on polygons

piyushjain
In reply to this post by Juan Pablo Carbajal-2
Reminder:
Sir,
I have tried to implement polyUnion using Clipper library just to show you my work.
Link : https://github.com/piyush-jain1/Octave-geometry
Have a look at it and guide further.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: GSoC 2017 - Implement boolean operations on polygons

Juan Pablo Carbajal-2
On Sat, Mar 18, 2017 at 11:54 AM, piyushjain <[hidden email]> wrote:

> Reminder:
> Sir,
> I have tried to implement polyUnion using Clipper library just to show you
> my work.
> Link : https://github.com/piyush-jain1/Octave-geometry
> Have a look at it and guide further.
>
>
>
> --
> View this message in context: http://octave.1599824.n4.nabble.com/GSoC-2017-Implement-boolean-operations-on-polygons-tp4682161p4682465.html
> Sent from the Octave - Maintainers mailing list archive at Nabble.com.
>
At first sight looks pretty nice. Will check it in detail soon.

I noticed you added binary files to your repository, this is not a
good practice, because 1) git or mercurial cannot track changes in
binaries and they will upload/download the whole file everytime they
change, 2) one will compile this files locally, so it is useless to
share them.

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: GSoC 2017 - Implement boolean operations on polygons

piyushjain
Thanks for your suggestions , Sir.
I will surely keep that in mind.
I will wait for further guidance from your side to proceed in this project.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: GSoC 2017 - Implement boolean operations on polygons

piyushjain
In reply to this post by Juan Pablo Carbajal-2
Sir,
Can you tell me what should I keep studying or learning meanwhile, to contribute optimally to this project?
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: GSoC 2017 - Implement boolean operations on polygons

Leo Yi
In reply to this post by Juan Pablo Carbajal-2
Sir,
I'm Leo Yi, a sophomore in Computer science at Peking University, China. And I’m the very one who mailed to you personally instead of to the mailing list. Do you enjoy OctConf 2017?
I’ve been reading some papers about Boolean operations on polygons. Eh, I don’t intend to put any links here because they are written in Chinese and have almost nothing special... I notice that what you’ve been talking about is the library and interface stuff. Does that mean the main problem at present is not about algorithm but only integrating?
Please tell me, so that I can contribute more rather than waste time going in the wrong way. Thanks!
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: GSoC 2017 - Implement boolean operations on polygons

John Swensen-3
In reply to this post by PhilipNienhuis

> On Mar 17, 2017, at 3:12 PM, Philip Nienhuis <[hidden email]> wrote:
>
> I have been meaning to dig into the Boost::Geometry examples at [3] to
>> see if I can implement an iterator facade for a custom polygon object
>> that allows us to operate directly on the octave data input without
>> having to copy all the points into the Boost::Geometry model for points,
>> rings, polygons, and multi-polygons. I think it should be possible. It
>> may speed up execution because we aren’t copying a bunch of double
>> values, but it should most certainly reduce memory usage a ton. If we
>> could push the performance/resources even better than now, it might be a
>> compelling reason to keep Boost.
>
> (Maybe I do not fully understand your aim.)
> For any polygon library the input data will have to be morphed somehow from the application/use case at hand into a format that the polygon library expects; vice versa for output.
> I'm unsure if investing a lot of work in specialized data access in some .oct file is better than clever and vectorized preprocessing at the Octave side. The latter is much more flexible and adaptable to the use case at hand.
>
> The Clipper library currently comprises a .mex wrapper file (in the Third party subdir, in recent Clipper releases pointing to Matlab Central).
> While working on polyline clipping I noted there's quite some code required to copy info from/to the structs that constitute the IMO rigid MEX data I/O structures.  I suppose some of that code can be avoided, or reduced, by rewriting the .mex wrapper into a proper .oct file using octave_value objects.  That'll give more flexibility as well. I suppose even the double<->int64 preprocessing can be absorbed in the .oct file (currently I've put that in an .m file wrapper).
>

I was only planning on making the specialized data access for the inputs to Boost so that it could operate directly on the fortran_vec() data pointer directly. Then, there would be no need for a complete memory duplication of the polygons being passed in. For large datasets like coastlines and other GIS data, this could be both memory and computationally prohibitive. Of course, the result of the Boost::Geometry operation would always need to be transformed into the appropriate Octave datatype for return.


>> One other option is to use the Boost-provided bcp utility to create the
>> subset of Boost headers that is are needed to compile Boost::Geometry
>> and include it in the package release. This is still 30MB uncompressed,
>> but it is much smaller than the whole Boost. this would also allow us to
>> distribute a version that has the self-intersection correction.
>
> IIRC Amr mentioned he had brought down the boost stuff to around 11 or 12 MB.
> I think the Boost include files shouldn't be in the geometry package directory; they'd rather live in /usr/include.
>

I guess I am somewhat of the opinion that maybe the Boost headers should be included. Even the 30MB I was talking about compresses down to about 1.2MB and then we could ensure that they are always a set of headers that supports the code in the package and self-intersection correction. The uncompressed size is really only an issue for those who are building the package, but 30MB shouldn’t really be an issue for a temporary build step. I’m not sure what the Boost license looks like in terms of including headers in another project, though.


John S.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: GSoC 2017 - Implement boolean operations on polygons

John Swensen-3
In reply to this post by PhilipNienhuis

On Mar 17, 2017, at 1:53 PM, Philip Nienhuis <[hidden email]> wrote:

I have been trying the Boost version by Amr for some time, using Amr's unofficial geometry-3.0.0 version from github and the mapping package (also an unofficial version, but I'm the mapping pkg maintainer :-) ).
AFAICS it does work fine, reliably and fast.
Also the poly2fv function is very useful for graphical output.


If nothing else. I think that the poly2fv function (depends on the poly2tri library) and Amr’s implementation of all the tests from [1] and [2]. This makes it much easier to go ahead and compare implementations of various .oct files that implement polygon clipping/boolean operations.

For example, I just found a much more recent algorithm with a C++ interface [3] that claims to handle holes, self intersections, coincident edges, and coincident points well. This might be worth making a quick .oct file for to see how well it handles things.


John S.


12
Loading...