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

[John Swensen]

> On Mar 15, 2016, at 12:12 PM, Philip Nienhuis <address@hidden> 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.