Re: GSOC 2016 Enquiry (boolean operations on polygons)

[PhilipNienhuis]

John Swensen-3 wrote
>> On Apr 24, 2016, at 9:49 AM, PhilipNienhuis <

> pr.nienhuis@

> > 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
> &lt;https://github.com/greenm01/poly2tri&gt;) 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




--
View this message in context: 
http://octave.1599824.n4.nabble.com/GSOC-2016-Enquiry-tp4675870p4676495.html
Sent from the Octave - Maintainers mailing list archive at Nabble.com.