GSOC Project "Implement boolean operations on polygons" GNU Octave

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

GSOC Project "Implement boolean operations on polygons" GNU Octave

Albu Mihai
Hello,

My name is Albu Mihai and I am a student at University Politehnica of Bucharest, more exactly at Computers and Information Technology. I want to work at Google Summer of Code 2016 and I chosed you because I like mathematics and I saw an interesting project you have there, the one with polygons operations. The proposal I have is to do a dynamic list with the coords of points that creates the polygons and we use mathematic functions to know how are the polygons defined. In this way, we can do easy the operations.


Reply | Threaded
Open this post in threaded view
|

Re: GSOC Project "Implement boolean operations on polygons" GNU Octave

Juan Pablo Carbajal-2
On Mon, Mar 14, 2016 at 4:10 PM, Albu Mihai <[hidden email]> wrote:

> Hello,
>
> My name is Albu Mihai and I am a student at University Politehnica of
> Bucharest, more exactly at Computers and Information Technology. I want to
> work at Google Summer of Code 2016 and I chosed you because I like
> mathematics and I saw an interesting project you have there, the one with
> polygons operations. The proposal I have is to do a dynamic list with the
> coords of points that creates the polygons and we use mathematic functions
> to know how are the polygons defined. In this way, we can do easy the
> operations.
>
>

Hello Albu,

That's great. Read the instructions on the wiki page, and start
coding. If you have questions just ask here on in the IRC channel. Do
not forget to write your application for GSoC on due time.

Reply | Threaded
Open this post in threaded view
|

Re: GSOC Project "Implement boolean operations on polygons" GNU Octave

PhilipNienhuis
Juan Pablo Carbajal-2 wrote
On Mon, Mar 14, 2016 at 4:10 PM, Albu Mihai <[hidden email]> wrote:
> Hello,
>
> My name is Albu Mihai and I am a student at University Politehnica of
> Bucharest, more exactly at Computers and Information Technology. I want to
> work at Google Summer of Code 2016 and I chosed you because I like
> mathematics and I saw an interesting project you have there, the one with
> polygons operations. The proposal I have is to do a dynamic list with the
> coords of points that creates the polygons and we use mathematic functions
> to know how are the polygons defined. In this way, we can do easy the
> operations.
>
>

Hello Albu,

That's great. Read the instructions on the wiki page, and start
coding. If you have questions just ask here on in the IRC channel. Do
not forget to write your application for GSoC on due time.
In order to avoid reinventing the wheel it may be wise to first check what is already available out there and use proven solutions as much as possible.

A while ago in this mailing list some suggestions were mentioned.

Philip
Reply | Threaded
Open this post in threaded view
|

Re: GSOC Project "Implement boolean operations on polygons" GNU Octave

John Swensen-3

On Mar 15, 2016, at 3:10 AM, PhilipNienhuis <[hidden email]> wrote:

Juan Pablo Carbajal-2 wrote
On Mon, Mar 14, 2016 at 4:10 PM, Albu Mihai &lt;

albumihaiupb@

&gt; wrote:
Hello,

My name is Albu Mihai and I am a student at University Politehnica of
Bucharest, more exactly at Computers and Information Technology. I want
to
work at Google Summer of Code 2016 and I chosed you because I like
mathematics and I saw an interesting project you have there, the one with
polygons operations. The proposal I have is to do a dynamic list with the
coords of points that creates the polygons and we use mathematic
functions
to know how are the polygons defined. In this way, we can do easy the
operations.



Hello Albu,

That's great. Read the instructions on the wiki page, and start
coding. If you have questions just ask here on in the IRC channel. Do
not forget to write your application for GSoC on due time.

In order to avoid reinventing the wheel it may be wise to first check what
is already available out there and use proven solutions as much as possible.

A while ago in this mailing list some suggestions were mentioned.

Philip


I would recommend you take a look at a couple of the different existing polygon boolean libraries available. The project ideas page (http://wiki.octave.org/Summer_of_Code_Project_Ideas) has links to four different solutions with compatible licenses (ClipperLib, Boost::Polygon, Boost::Geometry, and KBool) and a link to a partial Octave implementation using ClipperLib. 

I agree with Philip that using an existing solution would make it possible to start tackling the problem of integration with Octave, rather than working on polygon point representations. As far as I know, all of these libraries use the convention of alternating winding direction (clockwise or counter clockwise) to indicate whether the points represent an outer polygon boundary or and inner hole boundary.

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

Re: GSOC Project "Implement boolean operations on polygons" GNU Octave

Philip Nienhuis
John Swensen-3 wrote
> On Mar 15, 2016, at 3:10 AM, PhilipNienhuis <[hidden email]> wrote:
>
> Juan Pablo Carbajal-2 wrote
>> On Mon, Mar 14, 2016 at 4:10 PM, Albu Mihai <
>
>> albumihaiupb@
>
>> > wrote:
>>> Hello,
>>>
>>> My name is Albu Mihai and I am a student at University Politehnica of
>>> Bucharest, more exactly at Computers and Information Technology. I want
>>> to
>>> work at Google Summer of Code 2016 and I chosed you because I like
>>> mathematics and I saw an interesting project you have there, the one with
>>> polygons operations. The proposal I have is to do a dynamic list with the
>>> coords of points that creates the polygons and we use mathematic
>>> functions
>>> to know how are the polygons defined. In this way, we can do easy the
>>> operations.
>>>
>>>
>>
>> Hello Albu,
>>
>> That's great. Read the instructions on the wiki page, and start
>> coding. If you have questions just ask here on in the IRC channel. Do
>> not forget to write your application for GSoC on due time.
>
> In order to avoid reinventing the wheel it may be wise to first check what
> is already available out there and use proven solutions as much as possible.
>
> A while ago in this mailing list some suggestions were mentioned.
>
> Philip
>


I would recommend you take a look at a couple of the different existing polygon boolean libraries available. The project ideas page (http://wiki.octave.org/Summer_of_Code_Project_Ideas <http://wiki.octave.org/Summer_of_Code_Project_Ideas>) has links to four different solutions with compatible licenses (ClipperLib, Boost::Polygon, Boost::Geometry, and KBool) and a link to a partial Octave implementation using ClipperLib.

I agree with Philip that using an existing solution would make it possible to start tackling the problem of integration with Octave, rather than working on polygon point representations. As far as I know, all of these libraries use the convention of alternating winding direction (clockwise or counter clockwise) to indicate whether the points represent an outer polygon boundary or and inner hole boundary.
Last summer I stumbled upon a comparison of various polygon clipping libraries (5 or 6 IIRC) by a Russian (?) guy which outlined that only 2 or 3 could handle holes. (Too bad I can't find that URL anymore.) kBool and (IIRC) boost were among those that could handle holes in polygons (+ of course GPC but that has an incompatible license).

IIRC one of those (clipper IIRC) used integer coordinates rather than float/double. I had it working (I remember vaguely something with a MEX file) but that coordinate translation didn't work in the end because of required coordinate transforms (for GIS shapefiles with real-world coordinates) and back each time depending on the coordinate ranges at hand. From what I remember that became a headache and I intended to switch to kbool/boolean but then I ran out of time.

Philip
Reply | Threaded
Open this post in threaded view
|

Re: GSOC Project "Implement boolean operations on polygons" GNU Octave

John Swensen-3

> On Mar 15, 2016, at 12:12 PM, Philip Nienhuis <[hidden email]> wrote:
>
> John Swensen-3 wrote
>>> On Mar 15, 2016, at 3:10 AM, PhilipNienhuis &lt;
>
>> pr.nienhuis@
>
>> &gt; wrote:
>>>
>>> Juan Pablo Carbajal-2 wrote
>>>> On Mon, Mar 14, 2016 at 4:10 PM, Albu Mihai &lt;
>>>
>>>> albumihaiupb@
>>>
>>>> &gt; wrote:
>>>>> Hello,
>>>>>
>>>>> My name is Albu Mihai and I am a student at University Politehnica of
>>>>> Bucharest, more exactly at Computers and Information Technology. I want
>>>>> to
>>>>> work at Google Summer of Code 2016 and I chosed you because I like
>>>>> mathematics and I saw an interesting project you have there, the one
>>>>> with
>>>>> polygons operations. The proposal I have is to do a dynamic list with
>>>>> the
>>>>> coords of points that creates the polygons and we use mathematic
>>>>> functions
>>>>> to know how are the polygons defined. In this way, we can do easy the
>>>>> operations.
>>>>>
>>>>>
>>>>
>>>> Hello Albu,
>>>>
>>>> That's great. Read the instructions on the wiki page, and start
>>>> coding. If you have questions just ask here on in the IRC channel. Do
>>>> not forget to write your application for GSoC on due time.
>>>
>>> In order to avoid reinventing the wheel it may be wise to first check
>>> what
>>> is already available out there and use proven solutions as much as
>>> possible.
>>>
>>> A while ago in this mailing list some suggestions were mentioned.
>>>
>>> Philip
>>>
>>
>>
>> I would recommend you take a look at a couple of the different existing
>> polygon boolean libraries available. The project ideas page
>> (http://wiki.octave.org/Summer_of_Code_Project_Ideas
>> &lt;http://wiki.octave.org/Summer_of_Code_Project_Ideas&gt;) has links to
>> four different solutions with compatible licenses (ClipperLib,
>> Boost::Polygon, Boost::Geometry, and KBool) and a link to a partial Octave
>> implementation using ClipperLib.
>>
>> I agree with Philip that using an existing solution would make it possible
>> to start tackling the problem of integration with Octave, rather than
>> working on polygon point representations. As far as I know, all of these
>> libraries use the convention of alternating winding direction (clockwise
>> or counter clockwise) to indicate whether the points represent an outer
>> polygon boundary or and inner hole boundary.
>
> Last summer I stumbled upon a comparison of various polygon clipping
> libraries (5 or 6 IIRC) by a Russian (?) guy which outlined that only 2 or 3
> could handle holes. (Too bad I can't find that URL anymore.) kBool and
> (IIRC) boost were among those that could handle holes in polygons (+ of
> course GPC but that has an incompatible license).
>
> IIRC one of those (clipper IIRC) used integer coordinates rather than
> float/double. I had it working (I remember vaguely something with a MEX
> file) but that coordinate translation didn't work in the end because of
> required coordinate transforms (for GIS shapefiles with real-world
> coordinates) and back each time depending on the coordinate ranges at hand.
> From what I remember that became a headache and I intended to switch to
> kbool/boolean but then I ran out of time.
>
> Philip
>

I have experience with Boost::Geometry, ClipperLib, and GPC. Now that you mention it, I remember the integer limitation with ClipperLib. I only needed 3 digits of precision for my applications, so I ended up just operating with coordinates*1000.

GPC was by far the most robust and fastest (and was only two files) but doesn’t have a compatible license.

I really liked Boost::Geometry, but only after it took a while to get used to how much templating they use and all the terminology of Concepts, Algorithms, Strategies, etc. It also didn’t support (at the time) the ability to split a Polygon with a LineString. I needed something that divided polygons.

I would personally recommend using Boost::Geometry. One thing I like about it is that it is a header-only library and tries to follow the C++ STL for lots of things like iterators and such. Unless KBool will be easy to integrate and it enough easier to learn/use than Boost::Geometry. Since you have used KBool and Boost::Geometry, what do you suggest between these two?

John S.






Reply | Threaded
Open this post in threaded view
|

Re: GSOC Project "Implement boolean operations on polygons" GNU Octave

PhilipNienhuis
John Swensen wrote:

>
>> On Mar 15, 2016, at 12:12 PM, Philip Nienhuis <[hidden email]> wrote:
>>
>> John Swensen-3 wrote
>>>> On Mar 15, 2016, at 3:10 AM, PhilipNienhuis &lt;
>>
>>> pr.nienhuis@
>>
>>> &gt; wrote:
>>>>
>>>> Juan Pablo Carbajal-2 wrote
>>>>> On Mon, Mar 14, 2016 at 4:10 PM, Albu Mihai &lt;
>>>>
>>>>> albumihaiupb@
>>>>
>>>>> &gt; wrote:
>>>>>> Hello,
>>>>>>
>>>>>> My name is Albu Mihai and I am a student at University Politehnica of
>>>>>> Bucharest, more exactly at Computers and Information Technology. I want
>>>>>> to
>>>>>> work at Google Summer of Code 2016 and I chosed you because I like
>>>>>> mathematics and I saw an interesting project you have there, the one
>>>>>> with
>>>>>> polygons operations. The proposal I have is to do a dynamic list with
>>>>>> the
>>>>>> coords of points that creates the polygons and we use mathematic
>>>>>> functions
>>>>>> to know how are the polygons defined. In this way, we can do easy the
>>>>>> operations.
>>>>>>
>>>>>>
>>>>>
>>>>> Hello Albu,
>>>>>
>>>>> That's great. Read the instructions on the wiki page, and start
>>>>> coding. If you have questions just ask here on in the IRC channel. Do
>>>>> not forget to write your application for GSoC on due time.
>>>>
>>>> In order to avoid reinventing the wheel it may be wise to first check
>>>> what
>>>> is already available out there and use proven solutions as much as
>>>> possible.
>>>>
>>>> A while ago in this mailing list some suggestions were mentioned.
>>>>
>>>> Philip
>>>>
>>>
>>>
>>> I would recommend you take a look at a couple of the different existing
>>> polygon boolean libraries available. The project ideas page
>>> (http://wiki.octave.org/Summer_of_Code_Project_Ideas
>>> &lt;http://wiki.octave.org/Summer_of_Code_Project_Ideas&gt;) has links to
>>> four different solutions with compatible licenses (ClipperLib,
>>> Boost::Polygon, Boost::Geometry, and KBool) and a link to a partial Octave
>>> implementation using ClipperLib.
>>>
>>> I agree with Philip that using an existing solution would make it possible
>>> to start tackling the problem of integration with Octave, rather than
>>> working on polygon point representations. As far as I know, all of these
>>> libraries use the convention of alternating winding direction (clockwise
>>> or counter clockwise) to indicate whether the points represent an outer
>>> polygon boundary or and inner hole boundary.
>>
>> Last summer I stumbled upon a comparison of various polygon clipping
>> libraries (5 or 6 IIRC) by a Russian (?) guy which outlined that only 2 or 3
>> could handle holes. (Too bad I can't find that URL anymore.) kBool and
>> (IIRC) boost were among those that could handle holes in polygons (+ of
>> course GPC but that has an incompatible license).
>>
>> IIRC one of those (clipper IIRC) used integer coordinates rather than
>> float/double. I had it working (I remember vaguely something with a MEX
>> file) but that coordinate translation didn't work in the end because of
>> required coordinate transforms (for GIS shapefiles with real-world
>> coordinates) and back each time depending on the coordinate ranges at hand.
>>  From what I remember that became a headache and I intended to switch to
>> kbool/boolean but then I ran out of time.
>>
>> Philip
>>
>
> I have experience with Boost::Geometry, ClipperLib, and GPC. Now that you mention it, I remember the integer limitation with ClipperLib. I only needed 3 digits of precision for my applications, so I ended up just operating with coordinates*1000.
>
> GPC was by far the most robust and fastest (and was only two files) but doesn’t have a compatible license.
>
> I really liked Boost::Geometry, but only after it took a while to get used to how much templating they use and all the terminology of Concepts, Algorithms, Strategies, etc. It also didn’t support (at the time) the ability to split a Polygon with a LineString. I needed something that divided polygons.
>
> I would personally recommend using Boost::Geometry. One thing I like about it is that it is a header-only library and tries to follow the C++ STL for lots of things like iterators and such. Unless KBool will be easy to integrate and it enough easier to learn/use than Boost::Geometry. Since you have used KBool and Boost::Geometry, what do you suggest between these two?

Well, we already have oc_polybool (in the OF octclip package) and that
works OK except that it doesn't do holes (-properly at least, AFAICT. I
couldn't discern anywhere if octclip does support polygons with holes).

I have no strong preference (apart from the integer stuff in Clipper
that put me off somewhat at the time), but I do need a polygon clipper
that does handle holes properly. I just noted that Boost can do that
nowadays; if that lib is your preferred one I have no objection.

Maybe the oc_polybool in OF-octclip can be modified to handle holes; but
the source code + comments are all in Spanish. If the GSOC student can
read Spanish and oc_polybool's underlying algorithm lends itself for
handling holes, it might be another starting point.

Just to be clear, I'm just a user of a polygon clipping / boolean
operations library. It should Just Work without too much hassle; code
internals is beyond me if you don't mind :-)
I intend to use it for the OF mapping package.

On the Clipper web page there's a speed comparison where Boost performs
reasonably fast, but Boost is mentioned there to not support "complex
polygons" - I read that as polygons containing holes. So that speed
comparison seems outdated.

BTW there's Octave/Matlab code here:
https://rosettacode.org/wiki/Sutherland-Hodgman_polygon_clipping

I just found the starting point from where I hit the polygon comparison
page:
http://clippoly.sourceforge.net/
and the comparison is here:
https://web.archive.org/web/19990423223742/http://members.xoom.com/msleonov/pbcomp.html
See also here:
https://web.archive.org/web/20000615220540/http://members.xoom.com/msleonov/sample.html
Leonov's polyboolean lib can still be downloaded from:
https://web.archive.org/web/20000615043723/http://members.xoom.com/msleonov/pb.html#Download
but the license is not so clear. It is originally derived from GPL-ed
code and AFAICS it still is GPL, as mentioned on the parent web page.

Philip