patchGNU Octave - Patches: patch #9000, Polygon functions for...

 
 

patch #9000: Polygon functions for geometry/mapping package

Submitter:  Philip Nienhuis <philipnienhuis>
Submitted:  Wed 11 May 2016 10:34:46 PM UTC
   
 
Category:  Forge : new function Priority:  5 - Normal
Status:  Done Privacy:  Public
Assigned to:  None Open/Closed:  Closed
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Mon 27 Mar 2017 09:32:41 PM UTC, comment #42: 

Hi,

It seems they crossed again. I have fixed (almost) all issues raised by Olaf.
I am removing warnings in demos and then I will upload the release.

Please close this patch and post no more updates until after release.

Juan Pablo Carbajal <juanpi>
Group Member
Mon 27 Mar 2017 09:25:37 PM UTC, comment #41: 

BTW, @comment #39:
JuanPi I DID pull before committing (actually re-cloned)  :-)

I suppose our messages crossed?

Philip Nienhuis <philipnienhuis>
Group Member
Mon 27 Mar 2017 09:21:30 PM UTC, comment #40: 

On request by Olaf Till (see packages release tracker) here are new versions of

  1. inst/polygons2d/private/__dbl2int64__.m
  2. src/mexclipper.cpp

incl. copyright & license info.

@JuanPi: I'll close this patch as soon as the release is made.
Currently Olaf is gatekeeper :-)

(file #40174)

Philip Nienhuis <philipnienhuis>
Group Member
Mon 27 Mar 2017 09:11:59 PM UTC, comment #39: 

Hi,

Since comment #36 I have improved the demo of clipPolygon, please always update the repository before making changes.

I added the small change to clipPolygon_clipper.m

Thanks.

Please! close this patch.

Juan Pablo Carbajal <juanpi>
Group Member
Mon 27 Mar 2017 05:22:46 PM UTC, comment #38: 

JuanPi,

If you can and would manage (please), here's a patch to make clipPolygon's demo work again.

(BTW1 I find that name better than polygonClip, same for clipPolyline)

(BTW2 Unfortunately Amr's polybool/poly2fv won't build anymore against Octave dev sources :-(   I suppose namespaces are in the way)

Thanks

(file #40171)

Philip Nienhuis <philipnienhuis>
Group Member
Mon 27 Mar 2017 02:30:13 PM UTC, comment #37: 

All added, please close this patch!

Juan Pablo Carbajal <juanpi>
Group Member
Sun 26 Mar 2017 09:43:55 PM UTC, comment #36: 

... and here's a fix to the demo in polygonClip.m


(file #40154)

Philip Nienhuis <philipnienhuis>
Group Member
Thu 23 Mar 2017 08:45:51 PM UTC, comment #35: 

Here are the patches

(file #40099, file #40100)

Philip Nienhuis <philipnienhuis>
Group Member
Thu 23 Mar 2017 08:42:53 PM UTC, comment #34: 

Hi JuanPi,

Attached are two patches relative to rev. 447:
- Updating Clipper to v.6.4.2
- Adding boolean ops on polygons and polylines, incl. demos

I found some issues with polygon2patch as in geometry-2.2.2 to-be-released; I fisrt email you privately about it.

After you've pushed these I think this patch report had better be closed.

Philip Nienhuis <philipnienhuis>
Group Member
Wed 01 Feb 2017 01:45:44 AM UTC, comment #33: 

Hi Philip,

The redundancy is there because some function in geometry already use isP*CCW, I made isP*CW just for you :D.

I guess you will have to provide a wrapper in mapping for the naming 'ispolycw =@(p) isPolygonCW(p)'. I am not sure how much overhead is that (should be an m-file of course). We should ask jwe, maybe there is a way of creating aliases. Could you ask in the mailing list?

Regarding comment #31:

- Camel case is inherited from MatGEom, I also do not like it. Remember that I will make a function to clip polygons with an option to decide which engine to use...just as I did with the orientation. The frontend will be called 'clipPolygon'. It will accept "geometry" and "clipper" as before. You wil have to write a wrapper for the naming and argument convention in mapping.

- I do not plan to add the boost version in the next release. I am very disappointed with that development. Specially because of the huge dependencies. Maybe later on when I have time to distill it.

Cheers

Juan Pablo Carbajal <juanpi>
Group Member
Sat 31 Dec 2016 08:23:04 PM UTC, comment #32: 

To add to comment #31,
isPolygonCW is called ispolycw in the Matlab mapping toolbox.

Plus, I wonder why isPolygonCCW is needed at all if we also have ispolygonCW.
"! isPolygonCW" does the same as "isPolygonCCW"

Philip Nienhuis <philipnienhuis>
Group Member
Sat 31 Dec 2016 08:19:41 PM UTC, comment #31: 

Here's a patch to add polygonClip_clipper.m

BTW, it's your pick, but I'd prefer to retain the name "polyclip" rather than polygonClip_clipper
- it's much shorter
- in Octave camelcasing is generally avoided
- "polyclip" is sufficiently distinct from "polybool"
(- the name polybool needs to be retained for Matlab compatibility)

Philip Nienhuis <philipnienhuis>
Group Member
Fri 23 Dec 2016 12:21:05 PM UTC, comment #30: 

Of course!
Lets try it out.

Juan Pablo Carbajal <juanpi>
Group Member
Fri 23 Dec 2016 10:30:51 AM UTC, comment #29: 

JuanPi,

Would you also add polygonClip_clipper.m to the geometry package?
(see comment 14, file #37344).

If you do I'll separate out the double->int64 and v.v. stanzas for a private/ subdir in both isPolygonCW_Clipper.m and polygonClip_clipper.m.

Philip Nienhuis <philipnienhuis>
Group Member
Thu 22 Dec 2016 09:40:44 PM UTC, comment #28: 

Hi Philip,

I have applied your changes. To track problems with texinfo I use inotify (linux), for example


inotifywait -m $1 -e create |
    while read path action file; do
        egrep '^function' $file
    done


but I need to improve the grep condition because this doesn't seem to match all one needs to identify the function with the problem.
(you run the script in a different terminal, it remains checking the folder you give as a first argument, e.g. /tmp).

Juan Pablo Carbajal <juanpi>
Group Member
Sun 18 Dec 2016 08:44:09 PM UTC, comment #27: 

JuanPi;
Attached are
- fixed isPolygonCCW.m  (test #14 expected wrong orientation)
- fixed isPolygonCW_Clipper.m (had an off-by-one error in assessing NaaN rows
- cset relative to 1ddaad474f41 "ellipse2cov error parsing arguments"

I'll try to look in the doc-cache stuff later on. Must be some invalid texinfo somewhere. Unfortunately there's rarely a clue which file has the error.

(file #39270, file #39271, file #39272)

Philip Nienhuis <philipnienhuis>
Group Member
Wed 30 Nov 2016 01:09:09 AM UTC, comment #26: 

Hi Philip,

I have included most of your contributions in geometry-3.0.0

isPolygonCCW: now accepts a library as an option, currently "geometry" and "clipper" and uses the corresponding function. now is called isPolygonCW_Clipper to maintain naming convention.
When "geometry" is selected it uses the mfile version, which I wrote from scratch because it was too simple for what Amr was doing, sorry for that.

I would appreciate if you can clone the octave forge repo

https://sourceforge.net/p/octave/geometry/ci/default/tree/

and run

make check

or alternatively

make run

and then

test isPoligonCCW

in the octave prompt

You will see two XFAIL, those come from Clipper not giving the right answer! Check the xtests in isPolygonCCW.m
Do you know why it fails?

Also, would you know how to remove this warning that I get when I install geometry?


warning: doc_cache_create: unusable help text found in file 'clipper'


I will work in the boolean operations in the next chance I get.

Juan Pablo Carbajal <juanpi>
Group Member
Fri 07 Oct 2016 09:18:29 PM UTC, comment #25: 

Amr,

As a first thing, could you please fix compilation of boost-1.61? With that version in /usr/include I get:

:
checking whether dissolve is supported or not... no
configure: WARNING:
    You need to update your Boost Version to at least 1.60 such that functions can resolve self-intersections.


Thanks

Philip Nienhuis <philipnienhuis>
Group Member
Mon 03 Oct 2016 05:24:27 PM UTC, comment #24: 

I am willing to contribute in the merging stage.
Just tell me how can i help.

Amr

Amr Mohamed <amr_keleg>
Sun 02 Oct 2016 09:25:01 PM UTC, comment #23: 

(just short)
Most of Amr's work can be absorbed right away.
Why don't you just download his 3.0.0 geometry tarball and play with it?
Then later on we can work through my recommendations-to-come and you can choose what you'll do.

Amr made several functions that were a bit outside the strict boolean-ops-on-polygons subject. Some of those might better live in of-mapping (due to Matlab's naming & ML-compatibility aim) but as a wrapper for similar functions in of-geometry. I can't think of a strong reason to not make of-geometry a "hard" dependency of of-mapping.

Philip

Philip Nienhuis <philipnienhuis>
Group Member
Sun 02 Oct 2016 03:15:32 PM UTC, comment #22: 

Hi Phillip,

I knew we will not assimilate AMr's work right away.
I was looking forward to your advanced contributions. I have a few files from you, but I wasn't sure these wer ein their last stage.

Can we organize the work in the wiki?
http://wiki.octave.org/Talk:Geometry_package

A list with the function to add (just yours) would be great.

We will then add AMr's functions.

I imagine something like the table we did here
http://wiki.octave.org/TISEAN_package:Procedure#Table_of_functions

Thanks

Juan Pablo Carbajal <juanpi>
Group Member
Sat 01 Oct 2016 11:16:00 AM UTC, comment #21: 

Found the URLs in a spare moment:

https://bitbucket.org/amr_keleg/octave-geometry
(Amr's repo)

https://amrkeleg.wordpress.com/
(Amr's blog)

Philip Nienhuis <philipnienhuis>
Group Member
Sat 01 Oct 2016 10:10:15 AM UTC, comment #20: 

Juan Pablo Carbajal wrote:

> On Sat, Sep 3, 2016 at 11:36 PM, Philip Nienhuis
>><INVALID.NOREPLY@gnu.org>  wrote:
> Hi, I will have time soon., where are the latest advances?
> I am still using sourceforge as main repo.


?? Did you reply to the patch tracker post?? that won't work properly. Better answer thrugh the patch tracker

Wow, time ... :-)

I'm almost 95 % tru the review but ran out of time.
ATM I think it is still unwise to absorb Amr's stuff just like that, but you are pkg maintainer not me. The issues:

- boost 1.60 vs 1.61. That itches me the most.

- boost is > 114 MB on disk; Amr did't outline how to strip boost to its essentials. The required functions (include files) seem to be included in his repo.

- Amr implemented some functions that were already in geometry and some I already had implemented. I did sort out which ones are the fastest for most of these. Amr did good work anyway here.

- We need to discuss a clear distinction between what functions go in geometry and which ones in mapping, and related: which ones in mapping might be wrappers for what base functions in geometry. I think most of my original post below still stands.

I have very little time this weekend & week, starting next Friday & next weekend I can do a lot more. Can you wait until then? In the meantime I'll polish & sort out my work on this.


I cannot find Ar's repo URL now (no time/in a rush) but it is in the maintainers-ML archives in a GSOC review thread.
Tonight I can look into the URL

Philip Nienhuis <philipnienhuis>
Group Member
Sat 03 Sep 2016 09:36:45 PM UTC, comment #19: 

JuanPi and Amr:
Just to let you know that I picked up integrating Amr's contribution into the geometry/mapping packages. I think most of it should go in geometry.

@JuanPi: I didn't know that you had already absorbed some of my contributions in the geometry package, thanks for that. (I found out through perusing the log of Amr's code on bitbucket.org.)

In the next days /weeks I'll send a few comments / suggestions; I've almost finished my "review" of Amr's work from package maintainer's POV. Hopefully I do not step (too much) on your territory, JuanPi :-)

- Almost all functions need fixes for octave coding style

- polybool etc only works with boost-1.60 while currently boost-1.61 is current. In spite of what John Swensen apparently interpreted, boost-1.60 features self-intersection well.

Philip Nienhuis <philipnienhuis>
Group Member
Tue 14 Jun 2016 06:27:25 PM UTC, comment #18: 

Same here :-(  until after next week.

Philip Nienhuis <philipnienhuis>
Group Member
Mon 13 Jun 2016 08:31:31 PM UTC, comment #17: 

Thanks Philip,

I am a little bit overloaded at the moment, I think I can finish with this ticket sometime next week.

Juan Pablo Carbajal <juanpi>
Group Member
Fri 03 Jun 2016 04:09:35 PM UTC, comment #16: 

I have fixed optimize_branch_cuts to accept "incomplete" (not closed) polygon sets and renamed it to polygon2patch as you suggested (attached).
It already accepts XY matrices and X & Y vectors (plus XYZ matrices & X & Y & Z vectors).

For the mapping package I'll write a polycut.m that offers more input options (a.o., cell arrays) and merely calls polygon2patch.m in geometry.

(file #37379)

Philip Nienhuis <philipnienhuis>
Group Member
Wed 01 Jun 2016 07:59:08 PM UTC, comment #15: 

Before I forget, ispolycw.m returns winding direction of many (sub)polygons.
Does your ispolyccw.m also do multiple (sub)polygons?

Philip Nienhuis <philipnienhuis>
Group Member
Wed 01 Jun 2016 07:57:45 PM UTC, comment #14: 

JuanPi,

Attached are

polygonClip_clipper.m

ispolycw.m

both dissected from the polyclip.m uploaded earlier.

(file #37343, file #37344)

Philip Nienhuis <philipnienhuis>
Group Member
Sun 29 May 2016 03:55:35 PM UTC, comment #13: 

I have implemented isPolygonCWW using polygonArea (which, btw now handles CCW polygons with CW holes).

I will wait for your dissected version of polyclip to do the benchmarking

Juan Pablo Carbajal <juanpi>
Group Member
Sat 28 May 2016 10:09:29 PM UTC, comment #12: 

No plans yet for joinPolygons, lets first finish with this.

about isPolygonCCW: ispolycw collides withhte naming convention in geometry (camel case, decide by matgeom dev, not me). Do you prefer to wirte a mapping function that wraps it? or shall we add it to geometry and then write a function for the sake of naming convention?

polyclip: if the code you mention will be repeated better to private/ if bugs pop up is less places to maintain.

1. Currently it doesn't but it would be easy (although a hassle: many functions!) to do so. I prefer to force users to pass correct input arguments. Keep my functions cleaner and my users better trained (they understand they programs better).

2. If it is aboutignoring the other arguments. I think only a few functions do force Nx2, in the others Nxd would be silently ignored.


Juan Pablo Carbajal <juanpi>
Group Member
Sat 28 May 2016 07:43:01 PM UTC, comment #11: 

Looks good.
I'll help, but only next week from -say- Wednesday on (other priorities)

What is your plan with joinPolygons.m ?

Is it isPolygonCCW or ispolycw?  (matgeom, or ML mapping toolbox?)

To dissect polyclip (yep, not polysplit) the code to convert doubles into scaled int64 either needs to be duplicated for each function (clipping/boolean ops, and CCW check) or can be made a function in private/  But it isn't about much code so duplication isn't a big problem IMO.
I can split polyclip.m up for you and try to add some tests and demos.

Two questions:

1. Does the geometry package accept only column vectors and/or Nx2 (Nx3)arrays, or are row vectors and 2xN arrays accepted?

2. I like to be able to process X-Y-Z (or later on maybe even X-Y-Z1-Z2-Z3... arrays) but perform operations on polygons only in XY plane. Most functions I contributed allow that in some way. Would you continue support for that?

Philip Nienhuis <philipnienhuis>
Group Member
Sat 28 May 2016 04:24:17 PM UTC, comment #10: 

Ok, so here is my proposed plan

Boost: we leave it as external dependecy. If the user have it then the function works/exists

isPolygonCCW:
- Wrapper around polygonArea using cellfun for polygon sets
- Wrapper around (dissected) polyclip (I guess you meant polyclip not polysplit).

We check which one goes faster, we package that one. (we could also benchmark the boost version).

polygonClip:
- Frontend function for
  - polygonClip_boost
  - polygonClip_clipper.m (Dissected from polyclip)
  - polygonClip_native.m
  - ...

optimize_branch_cuts.m --> polygon2patch.m

Merge examples (demos) and test into respective functions.

Write a nice Wiki section on the geometry package.

Are you in or do I take it alone?



Juan Pablo Carbajal <juanpi>
Group Member
Sat 28 May 2016 11:36:32 AM UTC, comment #9: 

The boost "libraries" turn out to comprise 105 MB of include files. Wow.
Its a personal thing but I'm never fond of big piles of junk of which in the end only a few files will be used. 105 MB is > 10 % of the total install size of current mxe-octave builds.

A native .m ccw (for one polygon) could be a simple wrapper about polygonArea: s/th like:

<texinfo>
:
ccw = polygonArea (XY) >= 0;

..but polysplit/clipper also do sets of polygons. So an ispolycw could also be:

cw = polysplit (XY);

Philip Nienhuis <philipnienhuis>
Group Member
Fri 27 May 2016 10:28:57 PM UTC, comment #8: 

I will see if I can make a file to check for the boost libraries at compilation time and provide the functions accordingly. Beign a check of ccw so basic, it would be nice to have also a native .m implementation.

Juan Pablo Carbajal <juanpi>
Group Member
Fri 27 May 2016 06:40:27 PM UTC, comment #7: 

Good that geometry accepts both vectors and matrices, I wasn't aware of it (didn't pay due attention :-) ).

There's no specific reason to combine the two modes of polyclip, other than that the mexclipper routine (enclosed in the Clipper library download) also implemented it this way.
It is not all that hard to strip polyclip.m but why bother? It isn't quite in the way.

Would you rather accept ispolycw from
http://octave.1599824.n4.nabble.com/GSoC-16-Sample-implementation-for-ispolycw-function-tc4675763.html
into geometry? Looking a bit closer it is a fully binary module w/o wrappers so I expect it to be the fastest.

Boost:Geometry comprises merely headers; I wouldn't know how to make this into an external dependency but as there's no compilation involved it can't be hard. I suppose those headers should end up somewhere in /usr/include/boost.
In principle, similar goes for Clipper; but as it happens Clipper has been turned into just 2 mex cpp files that are far more easily put in an OF package. I can't imagine any other package to depend on Clipper and if there are the geometry package can be made a dependency.

Next week I'll have a bit more time to really assist with coding. I first want to make a new io release after fixing bug #48025

Philip Nienhuis <philipnienhuis>
Group Member
Fri 27 May 2016 08:43:37 AM UTC, comment #6: 

Philip,

Lets go by parts. First lets finish merging your functions into geometry and decide what to do with the ccw functions and thne lets go for polytri.

Many functions in the geometry package accept Nx2 arrays (x,y single matrix) or two Nx1 (x,y separated arrays).

Is there a reason to keep this two modes inside polyclip, like performance or something? If not, then I would really like to separate into two functions. One to query the orientation of the polygon and one to do the actual clipping.

Libraries that are packaged in linux distributions is better to have them as external dependencies. If the library is obscure, not easily accesible or can't be compiled automatically, then we can consider packaging it. In the latter case we need to have a full Octave binding not to waste what we package.

Juan Pablo Carbajal <juanpi>
Group Member
Fri 27 May 2016 07:18:55 AM UTC, comment #5: 

JuanPi,

polyclip.m has two modes:
- with 1 arg, return which subpolys are ccw/cw
- with 2 or more args, perform boolean ops.
Just peruse polyclip's help text for more clarification.

As to naming, please do what you think is good. I just figured polyclip would be nice and short (I like short names without camelcase better, but that is just me.)

Does isCounterClockWise only accept three points? if so, it isn't enough. I have no extreme demands but several of the polygons I'd like to handle (from ArcGIS shape files) contain several hundreds of vertices, some of them thousands.

I've been thinking a little more about the OF mapping/geometry divide.
AFAICS the polygon functions in Matlab's mapping toolbox:
- Accept separate X and Y vectors, AFAIU in any orientation (row or column)
- Only handle 2D polygons, not even with (ArcGIS-like) M and Z values per vertex (the Matlab docs explicity state that M and Z values are ignored),
... while the OF geometry package's polygon functions:
- Accept complete polygons in Nx2 (or Nx3?) format

So one option would be to have polygon functions as feature-complete as possible & accepting Nx2..NxM [*] polygons in the geometry package, and have Matlab-compatible wrappers for them in the mapping package that accept X and Y vectors.

[*] Nx2 = just XY; NxM = XY with one or more values ("measures") per vertex (e.g., XYZM).

The Clipper "library" merely comprises two mex files (.cpp) and a .h file that can be compiled/built with an extremely simple Makefile. With proper acknowledgements as regards license it can be absorbed in a src/ subdir in the OF geometry package so any system could have the Clipper library "available" through the geometry package. IOW it doesn't need to be an external dependency.

AFAICS the Boost:Geometry library is similar: it just comprises headers, so it can also live in a src/ subdir in the OF geometry package.

John Swensen suggested to use the polytri library to be able to convert polygon sets with holes into a triangulated patch surface leaving holes uncovered. That is just another way (next to optimize_branch_cuts and polycut) to be able to draw hollow polygons in Octave. So polytri might be yet another external dependency.

BTW shall we also cc John Swensen?

Philip Nienhuis <philipnienhuis>
Group Member
Thu 26 May 2016 10:39:39 PM UTC, comment #4: 

btw, have you checked isCounterClockwise?

Juan Pablo Carbajal <juanpi>
Group Member
Thu 26 May 2016 10:31:56 PM UTC, comment #3: 

Hi Philip,

Ok, so the function polyclip is just saying which one of the subpolygons (separated by nan rows) are ccw (outer polygons, guess should be considered as union) and which ones are cw (holes, to be substracted from the union of outer polygons).

Maybe polyclip is not the best name. I think isPolyCW or (iscw) might be better. When we get the all the functions we will select the best in terms of performance.

In the geometry package we always make sure the polygons are closed before plotting. So we always add a point repeating the last/first one. I would do that to avoid the problem I had with optimize_branch_cuts...name is still very unhappy...

Regarding dependency with other packages. Just let the functions fail, the error should give the user a hint of what packages to install (because they get a "missing XX function" error).
This reduces the amount of checks you have to do and simplifies code.

I would definitely like to have multiple functions doing the same thing, so we just need to agree on good names for them.
I will probably decorate the name of the function with the external library they use and then provide an interface function with the most general name. For example

clipPolygon.m

can call

clipPolygon_clipper.m
clipPolygon_boost.m
clipPolygon_native.m

depending on a user defined argument. clipPolygon would do all the input sanity checks and error handling, the clipPolgon_* functions would be unsafe and terser.

This also allows for clipping in systems without boost or clipper.

PS: I am adding Mohamed to the CC list

Juan Pablo Carbajal <juanpi>
Group Member
Thu 26 May 2016 09:04:25 PM UTC, comment #2: 

@Juanpi

Is it worth the trouble incorporating polyclip etc now that a GSOC polybool will happen this summer?
I'd be flattered :-) if you do and I think it is cool, but maybe a next geometry package would need some changes. -Or- we can have both polyclip (Clipper) and polybool (Boost:Geometry) living next to each other - I like the statement "What is wrong with choice?"
(A.: maintainability but IMO that is a subjective thing)


To answer your questions:

polyclip is called in drwpatch to assess which subpolygons are holes; type "help polyclip", you'll see that if it is called with one argument (just the subject polygons) it returns 1s for "hole" (clockwise) subpolygons and 0s for counterclockwise subpolygons.

So a new ispolycw.m function could simply be a wrapper for polyclip(). I do not know which is fastest:
- the ispolycw.m already shown in the maintainers ML:
http://octave.1599824.n4.nabble.com/GSoC-16-Sample-implementation-for-ispolycw-function-tc4675763.html
https://ideone.com/w6WFzB (binary so probably fast)

- a wrapper function around polygonArea() as I suggested there,

- or a wrapper around polyclip.


drwpatch's "varargin" are not holes arguments but drawing arguments conveyed 1:1 to patch().  So drwpatch has to find out which subpolygons are holes. This is stated in a comment as well.
The thing that isn't in comments is that drwpatch accepts one compound polygon comprising several sets of outer + inner polygons; so it uses polyclip to find out which inner polygons (holes) belong to which outer polygon (i.e., distinguish the sets) and process those sets one after the other. This way it can draw polygons with holes that are nested.
polyclip can return a compound polygon comprising several sets of subpolygons whose outer polygons may or may not be connected. drwpatch was designed to handle this easily.


Checking for installed packages: if you absorb the functions into geometry the OF geometry check isn't required. It's your pick as maintainer :-)  But if they go into e.g., mapping I'd rather (1) politely inform the user of the issue and (2) if at all possible try to follow an alternative route or even skip the "special effects".


As to your example code: drwpatch assumes the subpolygons are closed. Adding the first vertex to the end of each subpolygon gives the correct picture.

p  = [0 0; 0 1; 1 1; 1 0; 0 0]; %ccw
ph = p + [1.2 0];
# add hole
ph(end+1,:) = nan;
ph          = [ph; ([0 0; 1 0; 1 1; 0 1; 0 0]-[0.5 0.5])*0.5+[1.7 0.5]];
po = optimize_branch_cuts(ph);
patch (po(:,1), po(:,2))


Hmmm, maybe checks are required for each subpolygon to be a closed polygon.
Note that polyclip should also be capable of clipping polylines rather than polygons. So I'd need to find out which functions need such checks.
I have little time until somewhere next week for diving into additional checks like this.

Philip Nienhuis <philipnienhuis>
Group Member
Thu 26 May 2016 05:50:59 PM UTC, comment #1: 

Hi,
Thanks!
I am trying to merge this into geometry.
I have some questions

  • drwpatch

 Why is this function calling polyclip? If the holes are already given in the input argument, why do we need to clip again?
I will probably merge this function with current filklPolygon or make a new one called drawPolygonPatch

  • optimize_branch_cuts

 We shouldn't check for installed packages. Let the function fail when it calls the geometry functions. The error should make the
user aware of the missing function.

Trying out the function I use this code

p  = [0 0; 0 1; 1 1; 1 0]; %ccw
ph = p + [1.2 0];
# add hole
ph(end+1,:) = nan;
ph          = [ph; ([0 0; 1 0; 1 1; 0 1]-[0.5 0.5])*0.5+[1.7 0.5]];
po = optimize_branch_cuts(ph);
patch (po(:,1), po(:,2))


But the patch doesn't look correct. It has the hole alright, but the I get edges that go from the outer polygon to inner polygon:  (bottom left)->(bottom left) and (bottom left)->(top left). I am missing something?

Juan Pablo Carbajal <juanpi>
Group Member
Wed 11 May 2016 10:34:46 PM UTC, original submission:  

In the last year I've experimented with various polygons-with-holes drawing functions and polygon clipping, using the Clipper library.
In the current state it worked for me, so after a bit of polishing and private emails with the geometry package maintainer & John Swensen (GSOC boolean polygon ops. mentor) I just put it up here.

Contents are:
- polyjoin.m  (depends on supplied joinPolygons.m)
- polysplit.m  (depends on existing splitPolygons.m)
- polycut.m   (depends on supplied optimize_branch_cuts.m)
These three might go in the mapping package

- joinPolygons.m   (complement of existing splitPolygons in geometry pkg)
- optimize_branch_cuts.m   (separated from shapedraw.m in mapping package)
- polybool.m  (depends on supplied polyclip.m)
- polyclip.m   (wrapper for Clipper library)
I think these could go in the geometry package.

I also have a ispolycw (fairly rough) but that depends on polyclip.m/Clipper as well.

clipper.cpp, clipper.hpp and mexclipper.cpp can be found in Clipper (I used v. 6.2.1), subdir Third Party/Matlab
https://sourceforge.net/projects/polyclipping/files/
To build clipper.mex in Octave:
mkoctfile -mex -s clipper.cpp mexclipper.cpp

polyclip / polybool / clipper are IMO at most a temporary solution until the polybool from the GSOC project becomes available. Maybe just for those who can't wait (like me :-) ).

- Makefile might be a start for including in a package.


- drwpatch.m  A utility function for drawing (possibly nested) polygons with holes

- polyclip_tst2.m    demo function

- holes.mat, example_holes.m   Example polygons with holes to be used for optimize_branch_cuts.m. Usage examples are in supplied polyclip_tst2.m


All these functions probably contain bugs, but I didn't hit them yet.


Note:
I've seen polyjoin.m & polysplit.m in bug #47502; as I commented there polyjoin could benefit from vectorization and polysplit can depend on splitPolygons in the geometry package.
I suggest to check relative performance and -depending on the results- decide which versions end up where.

Philip Nienhuis <philipnienhuis>
Group Member

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #40174:  mexclp_dbl2i64_copyright.cset added by philipnienhuis (2KiB - application/octet-stream)
file #40171:  geometry_clipPolygon.cset added by philipnienhuis (3KiB - application/octet-stream)
file #40154:  polygonClip.cset added by philipnienhuis (2KiB - application/octet-stream)
file #40099:  Clipper_update_6.4.2.cset added by philipnienhuis (318KiB - application/octet-stream)
file #40100:  Add_polyline_and_polygon_clipping.cset added by philipnienhuis (42KiB - application/octet-stream)
file #39270:  isPolygonCCW.m added by philipnienhuis (4KiB - text/x-matlab)
file #39272:  isPolygonCCW_18dec2016.cset added by philipnienhuis (2KiB - application/octet-stream)
file #37379:  polygon2patch.m added by philipnienhuis (6KiB - text/x-matlab)
file #37343:  ispolycw.m added by philipnienhuis (2KiB - text/x-matlab)
file #37133:  polygon_clip.zip added by philipnienhuis (14KiB - application/x-zip-compressed)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by amr_keleg (Posted a comment)
  • -email is unavailable- added by lachlan (Updated the item)
  • -email is unavailable- added by juanpi (GSoc developer)
  • -email is unavailable- added by juanpi (Posted a comment)
  • -email is unavailable- added by philipnienhuis (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only logged-in users can vote.

     

    Follow 17 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2017-03-28 philipnienhuis StatusNone Done
        Open/ClosedOpen Closed
    2017-03-27 philipnienhuis Attached File- Added mexclp_dbl2i64_copyright.cset, #40174
    2017-03-27 philipnienhuis Attached File- Added geometry_clipPolygon.cset, #40171
    2017-03-26 philipnienhuis Attached File- Added polygonClip.cset, #40154
    2017-03-23 philipnienhuis Attached File- Added Clipper_update_6.4.2.cset, #40099
        Attached File- Added Add_polyline_and_polygon_clipping.cset, #40100
    2016-12-18 philipnienhuis Attached File- Added isPolygonCCW.m, #39270
        Attached File- Added isPolygonCW_Clipper.m, #39271
        Attached File- Added isPolygonCCW_18dec2016.cset, #39272
    2016-07-07 lachlan CategoryNone Forge : new function
    2016-06-03 philipnienhuis Attached File- Added polygon2patch.m, #37379
    2016-06-01 philipnienhuis Attached File- Added ispolycw.m, #37343
        Attached File- Added polygonClip_clipper.m, #37344
    2016-05-26 juanpi Carbon-Copy- Added -email is unavailable-
    2016-05-26 philipnienhuis SummaryPolgon functions for geometry/mapping package Polygon functions for geometry/mapping package
    2016-05-11 philipnienhuis Attached File- Added polygon_clip.zip, #37133

    Back to the top

    Powered by Savane 3.13-cf05.
    Corresponding source code