Polygon Clipper

Given two arbitrary polygons, the routine calculates the resulting polygon ...

Description

The Polygon Clipper (based on the gpc-library) is used to performe algebraic operations on two polygons.

Given two arbitrary polygons (which may self intersect, may contain holes, may be constructed of several contours) the Polygon Clipper is used to calculate the resulting polygon for the operations diff, union, AND, XOR.

All polygons are specified as structures as described in the example.m-file.

Credit for the gpc-library goes to Alan Murta (s. ReadMe.txt).

• Acknowledgements: This submission has inspired the following:; Polygon_Intersection
• MATLAB release: MATLAB 7.0.1 (R14SP1)
• Other requirements: The supplied dll should work under Windows, however if the c-files need to be recompiled for other OS, an appropriate c-compiler is needed.

[Pancho Blu]

Just what I needed. I have been racking my brains for days to get to a point where my program starts to work, but this one is much better and faster!. Thanks a lot.

[Murray Thomson]

Worked first time. Very easy to use. Did exactly what I needed. (And not an easy thing to program for yourself, as I found out the hard way!)

[Emily Hinz]

An extremely useful and easy to use set of routines. Thank you!

[je che]

Took a lot of work to run on my linux machine. The problem is that the
gpc_mexfile sources use '//' to begin the comments, and this is not part
of the C standard. This probably means the programs were written on a
Windows machine, which uses Microsoft Visual C++ to compile C code.
'//' is the comment prefix in standard C++. Microsoft appears to
believe that C++ is a perfect superset of C, which isn't true.

I removed all the lines beginning with // from those two source files
and the mex command in the readme gave worked fine.

Also, it won't run unless I had the older gcc-3.3 package installed.

Also, the zip file ships with Example.m which doesn't work. PolyClipper_example.m does work. Looks like a great function, though, if these things get tidied up.

[Jaeyoung Jung]

This polygon clipper works very well and easy to use, also has good quality!!

[Gerald Dalley]

Worked well the first time and is reasonably fast. Thanks! It compiled fine for me on 64-bit Linux using Matlab 7.2.

[moho atc]

yes yes

[Ramtin S]

Good work. Have not seen any problems with it so far

[Stanley]

Very good.

[Terrance Nearey]

Just a quick note...Mac OSX 10.5 Matlab Release 2008a
 Compiled and ran example first time using exactly
the instructions from ReadMe.txt
(cut and pasted them to matlab command window)
Compiler used gcc version 4.0.1 (Apple Inc. build 5465)
(default on my system)
Thanks for terse and sufficient instructions.

[Dominic]

For me the installation also worked flawlessly under 64bit Linux - as the code itself - great work!

[Sam Cape]

I'm having problems getting this to work on xp pro 64 bit. Any suggestions?

[Saiful]

i am also having trouble to work on windows xp pro 64 bit. can any of you please post a solution? Thanks....

[Saiful]

Ok, at last I was able to make it work. But because of Mex, its operation is very slow. Can any of you please forward me to a function totally developed in Matlab? Thanks!

[Olivier Planchon]

Works great. (Malab 7.4.0, XP 32 bit)
Thanks for sharing

[Lian Duan]

Dear Sebastian Hölz:

Hi, these programmes are very handy.

However, I have got this error after calling the mex function repeatedly.

there might be a memory leak in the code.

Thanks.

Lian
 
------------------------------------------------------------------------
       Segmentation violation detected at Fri Oct 1 12:53:00 2010
------------------------------------------------------------------------

Configuration:
  MATLAB Version: 7.9.0.529 (R2009b)
  MATLAB License: 161051
  Operating System: Darwin 10.4.0 Darwin Kernel Version 10.4.0: Fri Apr 23 18:28:53 PDT 2010; root:xnu-1504.7.4~1/RELEASE_I386 i386
  Window System: The X.Org Foundation (10402000), display /tmp/launch-9KjGVS/org.x:0
  Current Visual: 0x24 (class 4, depth 24)
  Processor ID: x86 Family 6 Model 7 Stepping 6, GenuineIntel
  Virtual Machine: Java 1.6.0_20-b02-279-10M3065 with Apple Inc. Java HotSpot(TM) 64-Bit Server VM mixed mode
  Default Encoding: US-ASCII

Fault Count: 1

Register State:
  rax = 47837790 rbx = 00000000
  rcx = 47837790 rdx = 00000001
  rsi = 14783779 rdi = 03d55a00
  rbp = 17afb5c0 rsp = 17afb5a0
  r8 = 478fc0a0 r9 = 478fc0a4
  r10 = 0000001b r11 = 1478377a
  r12 = 00000002 r13 = 00000001
  r14 = 00000000 r15 = 00000000
  rip = 057ae10b flg = 00010206
  cs = 00000027 fs = 00000010
  gs = 00000048

Stack Trace:
  [0] PolygonClip.mexmaci64:add_left~ + 59 bytes
  [1] PolygonClip.mexmaci64:gpc_polygon_clip~ + 2469 bytes
  [2] PolygonClip.mexmaci64:mexFunction~ + 211 bytes
  [3] libmex.dylib:mexRunMexFile + 90 bytes
  [4] libmex.dylib:Mfh_mex::runMexFileWithSignalProtection(int, mxArray_tag**, int, mxArray_tag**) + 137 bytes
  [5] libmex.dylib:Mfh_mex::dispatch_file(int, mxArray_tag**, int, mxArray_tag**) + 276 bytes
  [6] libmwm_dispatcher.dylib:Mfh_file::dispatch_fh(int, mxArray_tag**, int, mxArray_tag**) + 270 bytes
  [7] libmwm_interpreter.dylib:inDispatchFromStack(int, char const*, int, int) + 1030 bytes
  [8] libmwm_interpreter.dylib:inDispatchCall(char const*, int, long, int, int*, int*) + 166 bytes
  [9] libmwm_interpreter.dylib:inInterp(inDebugCheck, int, int, opcodes, inPcodeNest_tag volatile*, long*) + 4997 bytes
  [10] libmwm_interpreter.dylib:protected_inInterp(inDebugCheck, int, int, opcodes, inPcodeNest_tag*, long*) + 140 bytes
  [11] libmwm_interpreter.dylib:inInterPcodeSJ(inDebugCheck, int, int, opcodes, inPcodeNest_tag*, long*) + 265 bytes
  [12] libmwm_interpreter.dylib:inExecuteMFunctionOrScript(Mfh_mp*, bool) + 916 bytes
  [13] libmwm_interpreter.dylib:inRunMfile(int, mxArray_tag**, int, mxArray_tag**, Mfh_mp*, inWorkSpace_tag*) + 666 bytes
  [14] libmwm_dispatcher.dylib:Mfh_file::dispatch_fh(int, mxArray_tag**, int, mxArray_tag**) + 270 bytes
  [15] libmwm_interpreter.dylib:inDispatchFromStack(int, char const*, int, int) + 1030 bytes
  [16] libmwm_interpreter.dylib:inDispatchCall(char const*, int, long, int, int*, int*) + 166 bytes
  [17] libmwm_interpreter.dylib:inInterp(inDebugCheck, int, int, opcodes, inPcodeNest_tag volatile*, long*) + 4997 bytes
  [18] libmwm_interpreter.dylib:protected_inInterp(inDebugCheck, int, int, opcodes, inPcodeNest_tag*, long*) + 140 bytes
  [19] libmwm_interpreter.dylib:inInterPcodeSJ(inDebugCheck, int, int, opcodes, inPcodeNest_tag*, long*) + 265 bytes
  [20] libmwm_interpreter.dylib:inExecuteMFunctionOrScript(Mfh_mp*, bool) + 916 bytes
  [21] libmwm_interpreter.dylib:inRunMfile(int, mxArray_tag**, int, mxArray_tag**, Mfh_mp*, inWorkSpace_tag*) + 666 bytes
  [22] libmwm_dispatcher.dylib:Mfh_file::dispatch_fh(int, mxArray_tag**, int, mxArray_tag**) + 270 bytes
  [23] libmwm_interpreter.dylib:inDispatchFromStack(int, char const*, int, int) + 1030 bytes
  [24] libmwm_interpreter.dylib:inDispatchCall(char const*, int, long, int, int*, int*) + 166 bytes
  [25] libmwm_interpreter.dylib:inInterp(inDebugCheck, int, int, opcodes, inPcodeNest_tag volatile*, long*) + 4997 bytes
  [26] libmwm_interpreter.dylib:protected_inInterp(inDebugCheck, int, int, opcodes, inPcodeNest_tag*, long*) + 140 bytes
  [27] libmwm_interpreter.dylib:inInterPcodeSJ(inDebugCheck, int, int, opcodes, inPcodeNest_tag*, long*) + 265 bytes
  [28] libmwm_interpreter.dylib:inExecuteMFunctionOrScript(Mfh_mp*, bool) + 916 bytes
  [29] libmwm_interpreter.dylib:inRunMfile(int, mxArray_tag**, int, mxArray_tag**, Mfh_mp*, inWorkSpace_tag*) + 666 bytes
  [30] libmwm_dispatcher.dylib:Mfh_file::dispatch_fh(int, mxArray_tag**, int, mxArray_tag**) + 270 bytes
  [31] libmwm_interpreter.dylib:inDispatchFromStack(int, char const*, int, int) + 1030 bytes
  [32] libmwm_interpreter.dylib:inDispatchCall(char const*, int, long, int, int*, int*) + 166 bytes
  [33] libmwm_interpreter.dylib:inInterp(inDebugCheck, int, int, opcodes, inPcodeNest_tag volatile*, long*) + 4997 bytes
  [34] libmwm_interpreter.dylib:protected_inInterp(inDebugCheck, int, int, opcodes, inPcodeNest_tag*, long*) + 140 bytes
  [35] libmwm_interpreter.dylib:inInterPcodeSJ(inDebugCheck, int, int, opcodes, inPcodeNest_tag*, long*) + 265 bytes
  [36] libmwm_interpreter.dylib:inExecuteMFunctionOrScript(Mfh_mp*, bool) + 916 bytes
  [37] libmwm_interpreter.dylib:inRunMfile(int, mxArray_tag**, int, mxArray_tag**, Mfh_mp*, inWorkSpace_tag*) + 666 bytes
  [38] libmwm_dispatcher.dylib:Mfh_file::dispatch_fh(int, mxArray_tag**, int, mxArray_tag**) + 270 bytes
  [39] libmwm_interpreter.dylib:inDispatchFromStack(int, char const*, int, int) + 1030 bytes
  [40] libmwm_interpreter.dylib:inCallFcnFromReference + 205 bytes
  [41] libmwm_interpreter.dylib:inInterp(inDebugCheck, int, int, opcodes, inPcodeNest_tag volatile*, long*) + 1980 bytes
  [42] libmwm_interpreter.dylib:protected_inInterp(inDebugCheck, int, int, opcodes, inPcodeNest_tag*, long*) + 140 bytes
  [43] libmwm_interpreter.dylib:inInterPcodeSJ(inDebugCheck, int, int, opcodes, inPcodeNest_tag*, long*) + 265 bytes
  [44] libmwm_interpreter.dylib:inExecuteMFunctionOrScript(Mfh_mp*, bool) + 916 bytes
  [45] libmwm_interpreter.dylib:inRunMfile(int, mxArray_tag**, int, mxArray_tag**, Mfh_mp*, inWorkSpace_tag*) + 666 bytes
  [46] libmwm_dispatcher.dylib:Mfh_file::dispatch_fh(int, mxArray_tag**, int, mxArray_tag**) + 270 bytes
  [47] libmwm_interpreter.dylib:inDispatchFromStack(int, char const*, int, int) + 1030 bytes
  [48] libmwm_interpreter.dylib:inCallFcnFromReference + 205 bytes
  [49] libmwm_interpreter.dylib:inInterp(inDebugCheck, int, int, opcodes, inPcodeNest_tag volatile*, long*) + 1980 bytes
  [50] libmwm_interpreter.dylib:protected_inInterp(inDebugCheck, int, int, opcodes, inPcodeNest_tag*, long*) + 140 bytes
  [51] libmwm_interpreter.dylib:inInterPcodeSJ(inDebugCheck, int, int, opcodes, inPcodeNest_tag*, long*) + 265 bytes
  [52] libmwm_interpreter.dylib:inExecuteMFunctionOrScript(Mfh_mp*, bool) + 916 bytes
  [53] libmwm_interpreter.dylib:inRunMfile(int, mxArray_tag**, int, mxArray_tag**, Mfh_mp*, inWorkSpace_tag*) + 666 bytes
  [54] libmwm_dispatcher.dylib:Mfh_file::dispatch_fh(int, mxArray_tag**, int, mxArray_tag**) + 270 bytes
  [55] libmwm_interpreter.dylib:inEvalPcodeHeaderToWord(_memory_context*, int, mxArray_tag**, _pcodeheader*, Mfh_mp*, unsigned int) + 244 bytes
  [56] libmwm_interpreter.dylib:inEvalStringWithIsVarFcn(_memory_context*, char const*, EvalType, int, mxArray_tag**, inDebugCheck, _pcodeheader*, int*, bool (*)(void*, char const*), void*, bool, bool) + 1714 bytes
  [57] libmwm_interpreter.dylib:inEvalCmdWithLocalReturn(char const*, int*, bool, bool, bool (*)(void*, char const*)) + 145 bytes
  [58] libmwbridge.dylib:evalCommandWithLongjmpSafety(char const*) + 94 bytes
  [59] libmwbridge.dylib:mnParser + 681 bytes
  [60] libmwmcr.dylib:mcrInstance::mnParser_on_interpreter_thread() + 41 bytes
  [61] libmwmcr.dylib:boost::function0<void>::operator()() const + 38 bytes
  [62] libmwmcr.dylib:mcr::runtime::InterpreterThread::Impl::NoResultInvocationRequest::run() + 21 bytes
  [63] libmwmcr.dylib:mcr::runtime::InterpreterThread::Impl::invocation_request_handler(long) + 41 bytes
  [64] libmwuix.dylib:uix_DispatchOrProcess(_XEvent*, _XtAppStruct*, int, bool) + 457 bytes
  [65] libmwuix.dylib:ws_ProcessPendingEventsHelper(int, int, bool) + 593 bytes
  [66] libmwmcr.dylib:mcr::runtime::InterpreterThread::Impl::process_events(boost::shared_ptr<mcr::runtime::InterpreterThread::Impl> const&) + 46

[Lian Duan]

To be honest, this is a really waste of time. This programm is tested on windows XP with matlab 2008b, MAC and Linux with matlab 2009. They are all having the same error as I have put out in the last post. Users be aware of this. After 2 days of trying to fix this problem, I am now give up and have to look for an alternative programme. I am not sure if the author check these posts or not. If you do, I could send you my programe for your debugging. Thanks. Lian

[Andrew T]

Hi Lian,

Please see this page:

http://www.cs.man.ac.uk/~toby/alan/software/gpc_faq.htm

GPC is the C clipping library behind PolygonClipper. What you are experiencing is not due to a shortcoming of MATLAB or Hölz' MEX code, but is instead due to a known limitation of the underlying clipping algorithm implementation.

I had the same problem you are having (I only encountered it in certain cases), and I fixed it by snapping all polygon vertices to a grid before clipping, as Murta suggests.

Btw, thank you Sebastian Hölz, you have saved me the trouble of trying to write my own GPC interface!

[m4 Chrennikov]

 

[m4 Chrennikov]

Guys, does anyone know how to fix this issue:

Bugs
----
    ??? 1) It seems that the routine is sometimes passing back empty arrays (0 vertex). This should be handled. ???

[Kate]

Lian -- I had a similar problem when my polygons contained NaNs. After I fixed that, the problem went away. Perhaps yours is similar?

Sebastian -- Thank you very much!

[Martin]