Re: GSoC '16 - Boolean Operations on Polygons : Merge Code to geometry Package

[PhilipNienhuis]

John Swensen-3 wrote
>> On Aug 15, 2016, at 8:05 AM, Philip Nienhuis <

> pr.nienhuis@

> > wrote:
>> 
>> Juan Pablo Carbajal wrote:
>>> Hi all,
>>> 
>>> I am sorry for the delay. I am quite behind updating several patches I
>>> got for geometry. I will check the bitbucket repo and see how long it
>>> will take me to integrate these changes (hopefully not much!).
>>> 
>>> After a quick look, what is the include/poli2try folder? Is it meant
>>> to be part of the package?
>> 
>> Juan /others
>> 
>> Now that I am (just) back from vacation it appears to me that Amr has
>> implemented several functions that have already been submitted earlier on
>> in patch #9000; most of them have matgeom counterparts that are already
>> in the geometry package. In hindsight I think the communication between
>> John S. as mentor and you and me as involved package maintainers could
>> have been better :-(
>> 
>> Once I have my holiday backlog sorted out (~end of this week) I'll try to
>> make an overview of the various implementations of the function we now
>> have so that we can decide what goes where. Some performance tests might
>> be helpful.
>> IMO some of the new functions should go in geometry, some in mapping.
>> Patch #9000 is still a good start.
>> 
>> As to polytri, that is a dependency hat Amr hasn't mentioned - it is a
>> library for triangulation that can transform patches-with-holes into a
>> triangulated surface for the filled part(s). It is merely meant for
>> drawing polygons (and as such indispensable although polycut does merely
>> the same - hopefully the polytri solution is faster).
>> 
>> Philip
>> 
> 
> Sorry, that is probably my fault. I guess I had missed this bug/patch. We
> had gone and looked at the splitPolygon and joinPolygon in the geometry
> package repository, but I don’t recall why we didn’t just repurpose those.
> 
> We had discussed the usage of clipper vs Boost.Polygon vs Boost.Geometry
> vs one other library at the outset. We had seen an implementation of the
> polybool using Clipper, but there was some discussion about whether
> converting to 64 bit integer, performing the boolean operations, then
> converting back to floating point numbers was the correct approach. We had
> decided to us Boost.Geometry instead because of its ability to use
> float/double as the core representation, has emerging support for
> correcting self-intersections, and it very actively being maintained by a
> community of GIS professionals. Maybe we should have gotten
> permission/blessing from you guys as maintainers before heading in that
> direction full-force.
> 
> poly2tri is a library I have used with great success in the past for doing
> triangulations of polygons with holes. I had seen that one of you was
> working on the polycut function, but because the poly2tri library has been
> around for so long, seems to have the majority of kinks and corner cases
> worked out, and it involved including a relatively small number of source
> files as a dependency, that it would be an ideal solution to implementing
> the poly2fv function. Sometimes I like to re-invent the wheel because I
> learn a lot about what is really going on under the hood, and other times
> I just want to use an algorithm that I know works well. This was one of
> those latter cases.
> 
> I don’t think Amr has checked it into his repository yet, but one of the
> really great things he accomplished was to take all of the polygon tests
> from http://www.angusj.com/delphi/clipper.php
> <http://www.angusj.com/delphi/clipper.php> and implement them to run
> in both Matlab and Octave. This allows us to compare performance between
> both Matlab and Octave, other non-Octave implementation, and the
> alternative Octave implementations that were in this Patch #9000.
> 
> I apologize if we duplicated work unnecessarily. That was not our intent.
> I think Amr has done a pretty good job and any shortcomings are really my
> fault for not keeping tabs with you two better.

John, 

It wasn't my intention  to blame anyone :-)  I just made the observation
that apparently some duplicate work has been done due to less than optimal
communications. From my side setting insufficient priority (due to lack of
time) is also to "blame"; probably the same goes for JuanPi. Well, that is
how it goes with volunteer projects.

However, the not-to-be-ignored upside of that is that we now have choice; we
can select the best solutions/implementations or make a combination of the
best ones.

I agree with what you wrote about polytri - AFAICS Matlab also suggests to
use poly2fv rather than polycut. I just "made" polycut.m because I already
had a similar implementation lying around. Initially I didn't even know
about the existence of polycut in TMW's mapping toolbox, I just found that
the use of branch cuts was one way of properly drawing of (nested) polygons
with holes and initially my sub-function for that job was called
"optimize_branch_cuts" (it is in shapedraw.m in the mapping package).

A remaining question for me is how to interpolate clipped Z-values. In my
work I often have "3D"-planes (e.g., polygons of semi-3D tiles of geological
strata) that I want to visualize in 3D views. I know that clipperlib can do
it using callbacks.
In a more general sense, unlike Matlab's mapping toolbox I'd like all
polygon functions in the mapping package  to be able to handle semi-3D
polygons (i.e.,polygons with different Z-values for each vertex). Most of
what I have made already does so.

OK, as far as I'm concerned to be continued later this week,

Philip



--
View this message in context: 
http://octave.1599824.n4.nabble.com/GSoC-16-Boolean-Operations-on-Polygons-Merge-Code-to-geometry-Package-tp4679083p4679230.html
Sent from the Octave - Maintainers mailing list archive at Nabble.com.